2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 1. $n$ is not a set. 2. neither is $(\alpha_1,\dots,\alpha_k)$. 3. what exactly do you mean by replace? $\endgroup$ – Trevor Gunn Mar 18 '18 at 11:29
  • $\begingroup$ Ok my mistake, so if we replace $n,$ with $\alpha_1,....\alpha_k,$ in to the formula $D(n),$ how will it change? $\endgroup$ – Aurora Borealis Mar 18 '18 at 11:31
  • $\begingroup$ It will change from making sense to not making sense. $\endgroup$ – Trevor Gunn Mar 18 '18 at 11:32
  • $\begingroup$ 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. $\endgroup$ – Aurora Borealis Mar 18 '18 at 11:35
  • 1
    $\begingroup$ 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) $\endgroup$ – Jair Taylor Mar 20 '18 at 18:04
2
$\begingroup$

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}. $$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Aurora Borealis Mar 25 '18 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.