# Derangement formula for multisets

The usual derangement formula, for permutations of $\{1,\dots,n\}$ without fixed points, is given as follows:

$$\sum_{i=0}^n (-1)^{n-i}i!\binom{n}{i} = D(n)$$

Richard Stanley, in his Enumerative Combinatorics (bottom of page 269), gives the following formula for derangements of a multiset of type $\alpha=(\alpha_1,....,\alpha_k)$:

$$D(\alpha) = \sum_{\beta_{1} =0}^{\alpha_1} ... \sum_{\beta_k=0}^{\alpha_k} \binom{\alpha_1}{\beta_1}\binom{\alpha_2}{\beta_2}...\binom{\alpha_k}{\beta_k}(-1)^{\beta_1+....+\beta_k} \binom{\sum (\alpha_i-\beta_i)}{\alpha_1-\beta_1,\alpha_2-\beta_2,...,\alpha_k-\beta_k}$$

In the solution it says the derangement formula of $D(n)$ can be straightforwardly generalized to the sum above for the given type $\alpha=(\alpha_1,...., \alpha_k)$, where $M_\alpha$ is the multi-set $\{1^{\alpha_1},....,k^{\alpha_k}\}$.

Stanley defines a derangement of $M_\alpha$ as "a permutation $a_1a_2...a_n$ (where $\sum\alpha_i=n$) of $M_\alpha$ such that it disagrees with every position we get by listing the elements of $M$ in a weakly increasing order, for example for the set $\{1,2^2,3\}$ the two possible derangements are $(2132,2312)$."

My question is how is that generalization straightforward? I don't see how that is achieved.

• 1. $n$ is not a set. 2. neither is $(\alpha_1,\dots,\alpha_k)$. 3. what exactly do you mean by replace? – Trevor Gunn Mar 18 '18 at 11:29
• Ok my mistake, so if we replace $n,$ with $\alpha_1,....\alpha_k,$ in to the formula $D(n),$ how will it change? – Aurora Borealis Mar 18 '18 at 11:31
• It will change from making sense to not making sense. – Trevor Gunn Mar 18 '18 at 11:32
• Because from the problem 12, in Richard P. Stanleys's book enumerative combinatorics chapter 2, its more specifically stated there, math.mit.edu/~rstan/ec/ec1.pdf. I guess I am not sure how to approach the summation. – Aurora Borealis Mar 18 '18 at 11:35
• Note that if you want to compute this faster, there is a pretty formula for this due to Evan and Gillis in terms of Laguerre polynomials (see eq (2.4) in people.brandeis.edu/~gessel/homepage/papers/rookp.pdf) – Jair Taylor Mar 20 '18 at 18:04

First you need to understand the formula for "simple" derangements. It's inclusion-exclusion with the following form: $$\sum_{k = 0}^n (-1)^{k}(\text{permutations with k fixed points})(\text{number of ways to select k points to be fixed})$$ for each set of $k$ fixed points.

If there are $n - i$ fixed points, then the number of permutations is $i!$ and there are $\binom{n}{i}$ ways to select the fixed points. Note that these fixed points are not necessarily the only fixed points but they are fixed nonetheless. Inclusion-exclusion takes care of the "more fixed points than originally selected."

If you have a multiset of type $(\alpha_1,\dots,\alpha_k)$, then there are $$\binom{\alpha_1 +\dots+\alpha_k}{\alpha_1,\dots,\alpha_k} = \frac{(\alpha_1 + \dots + \alpha_k)!}{\alpha_1! \cdots \alpha_k!}$$ multiset permutations.

Now suppose we specify $\beta_i$ of the symbol $i$ to be fixed. This gives us a total of $\beta_1 + \dots + \beta_k$ fixed points and there are

$$\binom{\sum_i(\alpha_i - \beta_i)}{\alpha_1-\beta_1,\dots,\alpha_k - \beta_k}$$

multiset permutations of the remaining symbols. The number of ways to select these $\beta_1,\dots,\beta_k$ fixed points is

$$\binom{\alpha_1}{\beta_1} \cdots \binom{\alpha_k}{\beta_k}.$$

So just as before, we sum over the number of ways to select the fixed points, times the number of fixed points, times $(-1)^{\text{number of fixed points}}$. This gives

$$\sum_{\beta_1 = 0}^{\alpha_1} \cdots \sum_{\beta_k = 0}^{\alpha_k} (-1)^{\beta_1 + \dots + \beta_k} \binom{\alpha_1}{\beta_1} \cdots \binom{\alpha_k}{\beta_k} \binom{\sum_i(\alpha_i - \beta_i)}{\alpha_1-\beta_1,\dots,\alpha_k - \beta_k}.$$

• Thank you for this, I finally solved this problem and fully understood it. This explanation served as the ground in which it helped me solve this problem 12, in this particular text I am reading. – Aurora Borealis Mar 25 '18 at 7:37