Generalized Derangement Problem with $k$ unchanged elements

Question

I am seeking a formula which answers this question:

If we have a set with $n_1$ elements $X_1$, $n_2$ elements $X_2$, $\ldots$, and $n_r$ elements $X_r$, what is the number of ways we can reorder this set so that $k$ elements are in their original position?

If we set $k=0$, the answer would be (Derangements and Laguerre Polynomials)

$$P_{n_1, \ldots, n_r} = (-1)^{n_1 + \cdots + n_r} \int^{\infty}_{0} dx\, e^{-x} \prod_{i=1}^{r} L_{n_i}(x),$$

where $L_{n}(x)$ is the $n$th Laguerre polynomial.

Such a formula would give the number of ways we can reshuffle an initially ordered deck of $52$ cards, so that $10$ cards are in places where their rank (but not necessarily their suit) match the respectively ordered card in the original deck.

Also, there should be a way to use the obtained formula in a summation identity so that the final result is equal to the multinomial coefficient

$$ \frac{(n_1 + \cdots +n_{r})!}{n_1!\times \cdots \times n_{r}!},$$

i.e., the total number of ways to reorder a set with $n_1$ elements $X_1$, $n_2$ elements $X_2$, $\ldots$, and $n_r$ elements $X_r$.

Answer 1

After some thought, you can reason that if we have a list with $n_1$ elements $X_1$, $n_2$ elements $X_2$,... and $n_r$ elements $X_r$, the number of ways we can reorder this list so that only $k$ elements remain in their original position is

$$ \Omega^{k}_{\,\,n_1, \ldots, n_r} = \sum_{j_1=0}^{n_1} \cdots \sum_{j_r = 0}^{n_r} \binom{n_1}{j_1} \cdots \binom{n_r}{j_r} P_{j_1, \ldots, j_r} \delta_{N-k,\, j_1 + \cdots +j_r}, $$ where $N \equiv n_1 + \cdots + n_r$, $\delta_{i, j}$ is the Kronecker delta, and $P_{j_1, \ldots, j_r}$ is defined as it is in the prompt.

Normalization Check

We can check this result by summing over all possible values of $k$ and ensuring we get the multinomial coefficient in return. Namely, checking that

$$ \frac{(n_1+\cdots + n_r)!}{n_1! \cdots n_r!} = \sum_{k=0}^{n_1 + \cdots + n_r} \Omega^{k}_{\,\,n_1, \ldots, n_r}, $$ is satisfied.

Performing the outer sum first eliminates the Kronecker delta and we obtain \begin{align} \sum_{k=0}^{n_1 + \cdots + n_r} \Omega^{k}_{\,\,n_1, \ldots, n_r} & = \sum_{j_1=0}^{n_1} \cdots \sum_{j_r = 0}^{n_r} \binom{n_1}{j_1} \cdots \binom{n_r}{j_r} P_{j_1, \ldots, j_r} \\ & = \int^{\infty}_{0} dx \, e^{-x} \prod_{k=1}^{r}\left[ \sum_{j_k=0}^{n_k} (-1)^{j_k} \binom{n_k}{j_k}\,L_{j_k}(x)\right], \end{align} where $L_{j_k}(x)$ is the $j_k$th Laguerre polynomial. Using the identity

$$ \sum_{\ell=0}^{m} u^{\ell} \binom{m}{\ell} L_{\ell}(x) = (1+u)^{m} L_{m}\left( \frac{u x}{1+u}\right) $$

and the limit

$$ \lim_{\alpha\to 0}\, \alpha^{m} L_{m}\left(\frac{x}{\alpha}\right) = (-1)^m\frac{\alpha^m}{m!},$$

both of which are provable by referring to the series definition of the Laguerre polynomial, we find

\begin{align} \sum_{j_k=0}^{n_k} (-1)^{j_k} \binom{n_k}{j_k}\,L_{j_k}(x) & = \frac{x^{n_k}}{n_k!}, \end{align}

and so we obtain

\begin{align} \sum_{k=0}^{n_1 + \cdots + n_r} \Omega^{k}_{\,\,n_1, \ldots, n_r} & = \int^{\infty}_{0} dx \, e^{-x} \prod_{k=1}^{r}\left[ \frac{x^{n_k}}{n_k!} \right]\\ & = \frac{1}{n_1! \cdots n_r!} \int^{\infty}_{0} dx\, e^{-x} \, x^{n_1 + \cdots n_r}\\ & = \frac{(n_1+\cdots + n_r)!}{n_1! \cdots n_r!}, \end{align}

as expected. Thus the stated equation satisfies the desired consistency requirement.