Permutation of $h$ cards drawn from a deck of $n$ cards made up of $r$ types

Solution 1:

One way to get a (not "simple") general expression is the following.

Let $r_k$ be the number of types of cards such that their number is greater or equal than $k$, i.e.:

$$r_k = |\{j: 1 \le j \le r \land n_j \ge k\}|$$

We have that $r_1 = r$.

Given $h$, we can compute the number of wanted permutations for one solution of the equation:

$$\sum_{k=1}^{n}{ki_k}=h \tag{1}\label{1}$$

where $i_k$ is the number of distinct types of cards appearing each exactly $k$ times in the draw.

Starting from $k=n$, there are ${r_n \choose i_n}$ ways of choosing the $i_n$ types of cards. Then, for $k=n-1$ there are ${r_{n-1}-i_n \choose i_{n-1}}$ ways of choosing the $i_{n-1}$ types of cards, and in general ${r_k-\sum_{m=k+1}^{n}{i_m} \choose i_k}$ ways of choosing the $i_k$ types of cards.

Starting from $k=1$, the number of ways to choose $i_1$ distinct cards among the $h$ drawn is:

$${h \choose 1}{h-1 \choose 1}\ldots{h-i_1+1 \choose 1}=\frac{h!}{(h-i_1)!} \tag{2}$$

For $k=2$ we are left with $h-i_1$ cards for choosing $i_2$ couples of distinct types in the following number of ways:

$${h-i_1 \choose 2}{h-i_1-2 \choose 2}{h-i_1-4 \choose 2}\ldots{h-i_1-2(i_2-1) \choose 2} \tag{3}$$

and so on, giving the following total:

$$\prod_{k=1}^{n}\biggl[{r_k-\sum_{m=k+1}^{n}{i_m} \choose i_k}\prod_{j=0}^{i_k-1}{{h-\sum_{m=1}^{k-1}{mi_m}-kj} \choose k}\biggr] \tag{4}$$

where we can express a factor as a multinomial coefficient:

$$\prod_{k=1}^{n}\prod_{j=0}^{i_k-1}{{h-\sum_{m=1}^{k-1}{mi_m}-kj} \choose k}={h \choose h_1,h_2,\ldots,h_s} \tag{5}$$

where $s=\sum_{k=1}^{n}{i_k}$ and $h_1=h_2=\ldots=h_{i_1}=1$, $h_{i_1+1}=h_{i_1+2}=\ldots=h_{i_1+i_2}=2$, $h_{i_1+i_2+1}=h_{i_1+i_2+2}=\ldots=h_{i_1+i_2+i_3}=3$, and so on.

And summing over all solutions of \eqref{1} we get the final result:

$$\sum_{\sum_{k=1}^{n}{ki_k}=h}\;\prod_{k=1}^{n}\biggl[{r_k-\sum_{m=k+1}^{n}{i_m} \choose i_k}\prod_{j=0}^{i_k-1}{{h-\sum_{m=1}^{k-1}{mi_m}-kj} \choose k}\biggr] \tag{6}$$

Note that we can sum over all solutions because when $0 \le r_k-\sum_{m=k+1}^{n}{i_m} \lt i_k$ the binomial coefficient ${r_k-\sum_{m=k+1}^{n}{i_m} \choose i_k}$ evaluates to $0$. If instead $r_k-\sum_{m=k+1}^{n}{i_m} \lt 0$ then, since $r_{k+1} \le r_k$, we will have $r_{k+1}-\sum_{m=k+2}^{n}{i_m}-i_{k+1} \le r_k-\sum_{m=k+1}^{n}{i_m} \lt 0$ and therefore $r_{k+1}-\sum_{m=k+2}^{n}{i_m} \lt i_{k+1}$. Now, if $0 \le r_{k+1}-\sum_{m=k+2}^{n}{i_m}$ we are done, because the corresponding binomial coefficient evaluates to $0$, otherwise we continue to go up till we have $0 \le r_n \lt i_n$ and ${r_n \choose i_n} = 0$.

When $h=1$ the multinomial coefficient simplifies to $1$, we have the only solution $i_1=1$, $i_2=i_3=\ldots=i_n=0$ to \eqref{1}, and therefore the solution is $r_1=r$ as expected.

When $r=n$ we have $r_1=n$, the only solution $i_1=h$, $i_2=i_3=\ldots=i_n=0$ to \eqref{1}, and the multinomial coefficient evaluates to $h!$, therefore the solution is ${n \choose h}h!=\frac{n!}{(n-h)!}$ as expected.