Permutations with restriction

Solution 1:

Gessel gives a formula for this (Section 6) as an application of his theory of generalized rook polynomials (see also http://arxiv.org/abs/1306.6232). Let $L^{(\alpha)}_n(x)$ be the generalized Laguerre polynomial $\sum_{k=0}^n (-1)^k \frac{1}{k!}{n+\alpha \choose n-k} x^k$ and $q_n(x) = (-1)^n L^{(-1)}_n(x)$, and let $\Phi$ be the linear functional on polynomials taking $x^n$ to $n!$. Then $$ \Phi(q_{n_1}(x) \cdots q_{n_k}(x)) $$ is the number of words with $n_i$ $i$'s where no two letters are adjacent. To treat the $i$'s as distinct, replace $q_n$ by $n! q_n$.

For example, $$q_2(x) = -x + \frac{1}{2}x^2\\ q_3(x) = x - x^2 + \frac{1}{6}x^3, $$ so the number of permutations of $aaabbcc$ with no adjacent identical letters is \begin{align*}\Phi(q_3(x)q_2(x)^2) &= \Phi(x^3 - 2x^4 + \frac{17}{12}x^5 - \frac{5}{12}x^6 + \frac{1}{24}x^7)\\ &= 3! - 2\cdot 4! + \frac{17}{12}\cdot 5! - \frac{5}{12}\cdot 6! + \frac{1}{24}\cdot 7!\\ &= 38. \end{align*}

Not surprisingly, this comes from inclusion-exclusion. Let $$B_p = \{(i,j) : n_1 + \cdots + n_{p-1} + 1 \leq i \neq j \leq n_1 + \cdots + n_p\},$$ and $B = B_1 \cup \cdots \cup B_p$. Say a permutation $w_1 \cdots w_n$ of $n = n_1 + \cdots + n_p$ matches $A$ if $j$ immediately follows $i$ in $w$ for each $(i,j) \in A$, and say $A$ is compatible if any permutations match it. We're after the number of permutations of $n$ which don't match any non-empty subset of $B$. By inclusion-exclusion, this is $$ \sum_{\substack{A \subseteq B\\ A \text{ compatible}}} (-1)^{|A|} (n-|A|)! = \Phi(r_B(x)), $$ where $\displaystyle r_B(x) = \sum_{\substack{A \subseteq B\\ A \text{ compatible}}} (-1)^{|A|} x^{n-|A|}$.

Define $r_{B_p}(x)$ similarly; then $r_B = r_{B_1} \cdots r_{B_k}$. You get a compatible $i$-subset of $B_p$ by choosing an ordering on $\{n_1 + \cdots + n_{p-1} + 1, \ldots, n_1 + \cdots + n_p\}$, then choosing $n_p-i-1$ commas to break the list into chunks (e.g. if the ordered set is $(2,3,1,5,4)$, you might break it into chunks $23|1|54$, meaning the conditions $3$ follows $2$ and $4$ follows $5$), and finally dividing by $(n_p-i)!$ since the order of the chunks doesn't matter.

Hence, $$r_{B_p}(x) = \sum_{i=0}^{n_p} (-1)^i n_p! {n_p - 1 \choose n_p - i - 1} \frac{x^{n_p - i}}{(n_p-i)!},$$ which ends up as $n_p! q_{n_p}(x)$ after a bit of reindexing.

Solution 2:

Let $\mathbf e_1$ through $\mathbf e_n$ be the unit vectors in $\mathbb R^n$, and $\mathbf a = \sum_{i=1}^n a_i \mathbf e_i\in\mathbb N^n$ be the vector of counts. So $\mathbf a-\mathbf e_i$ is a way to say “take the counts from $\mathbf a$ and subtract one from the $i$-th count”.

Let $C(\mathbf a)$ be the number of ways to arrange items according to the count vector $\mathbf a$ with no duplicates, and let $D(i, \mathbf a)$ be the number of ways to arrange items according to counts $\mathbf a$ in such a way that $i$ is the first item. You get these relations:

\begin{align*} C(\mathbf a) &= \sum_{i=1}^n D(i, \mathbf a) \\ D(i, \mathbf a) &= C(\mathbf a - \mathbf e_i) - D(i, \mathbf a - \mathbf e_i) \end{align*}

This formulation does gloss over the cases where counts become zero. But the idea should be pretty clear: you have $n$ ways to start your sequence, and for each possible start element, you count the number of ways to arrange the remaining, but then again remove those arrangements which would have repeated the first element. You can reformulate this without $D$:

$$C(\mathbf a) = \sum_{i=1}^n C(\mathbf a-\mathbf e_i) - C(\mathbf a-2\mathbf e_i) + C(\mathbf a-3\mathbf e_i) \dots = \sum_{i=1}^n\sum_{j=1}^{a_i}(-1)^{j+1}C(\mathbf a-j \,\mathbf e_i)$$

Now you know how to compute $C(\mathbf a)$ if you have the number of combinations $C(\mathbf{a'})$ for all $\mathbf{a'}$ with $\lVert \mathbf{a'}\rVert_1=\lVert \mathbf a\rVert_1-1$, i.e. for all count vectors where one count has been reduced by one. You also have $$C(\mathbf 0)=1$$ as the basis for all your counting. So you can compute $C(\mathbf a)$ using dynamic programming. Along the way, all count vectors $\mathbf{a'}$ for which you compute $C(\mathbf{a'})$ will be less or equal to $\mathbf a$ in every single coordinate, so you can compute a bound for the number of such intermediate values as

$$\prod_{i=1}^n a_i+1$$

Depending on the counts $a_i$ this may or may not be suitable for your application.

For your example case (computed either without $D$ or with $D$) I get $C(3,2,2)=38$, which is consistent with a brute-force computation of that count. In case you actually want to distinguish the different objects of the same type, you have to consider all permutations within each type, and obtain $38\cdot3!\cdot2!\cdot2!=912$ which according to a similar brute-force computation should be the correct number for that setup as well.

For the case of $a=(2,2,2,2)$, i.e. $n=4$ and $a_1=a_2=a_3=a_4=2$, my approach gives an answer of 864, consistent with this answer to a related but more specific question.