Skip to main content
1 of 3
Richard Stanley
  • 50.8k
  • 14
  • 155
  • 279

The formula based on Inclusion-Exclusion for the usual number $D(n)$ of derangements of $n$ objects can be generalized. The result is the following.

Fix $k\geq 1$. Let $\mathbb{N}=\lbrace 0,1,2,\dots\rbrace$. For $\alpha=(\alpha_1,\dots,\alpha_k)\in\mathbb{N}^k$, let $D(\alpha)$ be the number of fixed-point free permutations of the multiset with $\alpha_1$ 1's, $\alpha_2$ 2's, etc. Write $x^\alpha = x_1^{\alpha_1}\cdots x_k^{\alpha_k}$. Then $$ \sum_{\alpha\in\mathbb{N}^k} N(\alpha)x^\alpha = \frac{1}{(1+x_1)\cdots (1+x_k)\left(1-\frac{x_1}{1+x_1}-\cdots - \frac{x_k}{1+x_k}\right)} $$ $$ = \frac{1}{1-\sum_S (|S|-1)\prod_{i\in S}x_i}, $$ where $S$ ranges over all nonempty subsets of $\lbrace 1,2,\dots,n\rbrace$.

Perhaps this result is already known. It can be used to obtain a lot of information about $D(\alpha)$.

Richard Stanley
  • 50.8k
  • 14
  • 155
  • 279