[Math] Derangement formula for repeated permutation

combinatoricsderangementspermutations

I need general formula for repeated permutation:

For any set of $n$ numbers $\{1,2,3,\ldots,n\}$, the formula for its number of derangements is given by the recursion $$!n=(n-1)(!(n-1)+!(n-2)).$$ Here, the numbers are distinct from one another (no number is repeated in the set).

Is there any general formula for the number of derangements when the numbers are repeated? For example, for a multiset like $ \{1,1,2,2,3,3,4,5\} $.

Thanks in advance.

Best Answer

Yes, there is a formula for counting these generalized derangements. It is due to Even and Gillis and it is in terms of products of Laguerre polynomials. See e.g. this paper by Gessel for a derivation from rook theory (p.4). Let $$l_n(x) = \sum_{k=0}^n (-1)^k { n \choose k}^2 k! x^{n-k},$$ and define $\Phi$ to be the linear function on polynomials mapping $x^n$ to $n!$. It's shown that $$\Phi\left( \prod_{i=1}^r l_{n_i}(x)\right)$$ is the number of permutations of $n_1 + \cdots + n_r$ colored elements, with $n_i$ of the $i$-th color, so that no element is mapped to an element of the same color.

Here all elements are labeled, so the elements in a given color class are distinguishable, but if you don't want that just divide by $\prod_{i=1}^r n_i!$ to account for the permutations of each color class. And if you want a more compact formula, note that $\Phi(p(x)) = \int_0^\infty e^{-x} p(x)\,dx$.

Edit: Here are some more details.

First, an example of using this formula. The first few polynomials $l_n(x)$ are

\begin{align*} l_0(x) &= 1\\ l_1(x) &= x - 1\\ l_2(x) &= x^2 - 4x + 2\\ l_3(x) &= x^3 - 9x^2 + 18x - 6. \end{align*}

Now let's find the number of permutations of $1234$ where $1,2$ are colored red and $3,4$ are colored blue and no element can map to another with the same color. Since there are $2$ of each color, we get $$l_2(x)l_2(x) = (x^2 - 4x + 2)(x^2 -4x + 2) = x^4 - 8x^3 + 20x^2 - 16x + 4.$$

Then we just apply $\Phi$, which means replacing each variable $x^k$ with $k!$. We get

\begin{align*} \Phi(l_2(x)l_2(x)) &= 1 \cdot 4! - 8 \cdot 3! + 20 \cdot 2! - 16 \cdot 1! + 4 \cdot 0!\\ &= 4. \end{align*}

This corresponds to the $4$ permutations $3412, 4312, 3421, 4321$ with no element of $\{1,2\}$ mapping to an element of $\{3,4\}$ or vice versa.

If you want the number of derangements of the multiset $1122$ where the $1$s and $2$s are not distinguishable, just divide take this answer and divide by $2! \cdot 2!$ to get $1$, corresponding to the single word $2211$.

As for the proof - I will not give it entirely, but I will give the main ingredients. (Note: We use $[n]$ to mean the set $\{1,2, \ldots, n\}$ and $[m,n]$ to mean $\{m, m+1, \ldots, n-1, n\}$.)

  1. There is a well-known formula from rook theory, proven using inclusion-exclusion. If $B$ is a "board", a subset of the $n \times n$ grid $[n] \times [n]$, then let $r_k$ be ways of placing $k$ elements on the board $B$ with no two in the same row or column (i.e., the number of ways of placing $k$ rooks from chess that cannot attack each other.) Then $$\sum_{k} (-1)^k r_k (n-k)!$$ is the number of permutations $\sigma \in S_n$ with no $\sigma(i) = j$ for $(i,j) \in B$; that is, no $1$s on the set $B$ when you write the adjacency matrix. You can write this as $\Phi(p_B(x))$ where $$p_B(x) = \sum_{k=0}^n (-1)^k r_k x^{n-k}$$ is the "rook polynomial" for $B$. (Note this is a variant of the usual definition of rook polynomial.)

  2. If $$B_1 \subseteq [n_1] \times [n_1], B_2 \subseteq [n_2]\times[n_2],$$ let $B_1 \oplus B_2$ be board in $[n_1 + n_2] \times [n_1 + n_2]$ given by the disjoint union of $B_1$ with the translate of $B_2$ to the upper-right square $[n_1+1, n_1 + n_2] \times [n_1+1, n_1 + n_2]$. Then $p_{B_1}(x) p_{B_2}(x) = p_{B_1 \oplus B_2}(x)$. Inductively we get $p_{B_1}(x) \cdots p_{B_k}(x) = p_{B_1 \oplus \cdots \oplus B_k}(x)$, the rook polynomial for the board given by the block-diagonal board $B_1 \oplus \cdots \oplus B_k$.

  3. Show that if $B$ is the whole board $[n] \times [n]$ then $p_B(x) = l_n(x)$ given above.

  4. Note that if we have boards $B_i = [n_i] \times [n_i]$ for some $n_i$, permutations of $[n_1 + \cdots + n_k]$ avoiding the block-diagonal $B_1 \oplus B_2 \oplus \cdots \oplus B_k$ are exactly the generalized derangements: no $i \in B_l$ can map to $j \in B_l$ for any $l$. Then we count these by applying 1, 2, 3 above.

Related Question