# Permutations with restriction

We have $n$ types of objects, and the number of objects of type $i$ is $a_i$, $1\leq i\leq n$.

What is the number of permutation of the $\sum_{i=1}^n a_i$ objects, if no two objects of the same type are next to each other?

A simple example: If we have the objects $\{a,a,a,b,b,c,c\}$, then we allow $abcabac$ but not $aaabbcc$.

-
Interesting quite non-standard question. It may be difficult. – André Nicolas Mar 14 '12 at 6:45
This reminds me of concepts from Lara K. Pudwell's PhD thesis. – Andrew MacFie May 29 '12 at 22:36
Do you distinguish between objects of the same type? In other words, is there one possible arrangement $aba$ or are there two because the two objects of type $a$ are nevertheless distinct and swapping them leads to another permutation? – MvG Mar 22 '13 at 10:06
@MvG, as Joel Adler was last seen a month ago and I am the bounty holder, I think the language suggests that each object of type $a$ should be indistinguishable. – George V. Williams Mar 23 '13 at 1:23
Also, is there a method that uses the Principle of Inclusion and Exclusion? I understand that it may be tedious in the general case, but in this specific case I feel it would be more illuminating. – Vincent Tjeng Mar 24 '13 at 9:47

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.

-
Sorry for my edits; I made a mistake in testing this, and thought I had to correct your answer. But the error was mine; as it stands the answer works well enough for the example case. Nice! – MvG Mar 23 '13 at 18:57
@Brendan would you mind giving a numerical example for your solution? I think it would help greatly. – Vincent Tjeng Mar 24 '13 at 9:45
@Vincent: done. – Brendan Pawlowski Mar 25 '13 at 9:26
thank you! that's nice. – Vincent Tjeng Mar 25 '13 at 11:50

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.

-