calculate all combination of indistinguishable objects

Question

I am thinking a question of picking $k$ objects out of $n$($n>k$). But among the $n=4m$ objects, only $m$ distinguishable objects. For example, a deck of poker cards, total $n=52$ cards, but we consider only $m=13$ are distinguishable. I am trying to calculate the total combination if I pick $k$ out of $n$ without considering the order. To make it simple, I am trying to consider a small problem, when $n=8$, $k=4$, $m=4$.

To start with, I consider all possible combination just by picking 4 objects out of 8 without considering the order, I have

$$ C_n^k = C_8^4 = \dfrac{8!}{4!4!} = 70 $$

But I know if there is only $m=4$ distinguishable objects there, the actual number of combination is much less that 70. I try the computer programming to list all possible combination and it turns out to be 19. I wonder if anyone could give me some hint to work out the general expression to pick out $k$ object out of $n$ but with only $m$ is distinguishable. Thanks.

p.s. I am thinking that the question could be restated in this way: how many unique hand I could have if I pick $k$ cards out of 52 from a poker deck without including the joker.

Answer 1

You are looking for the number of weak compositions of $k$ into $m$ pieces with no piece greater than $n/m$. The "with no piece greater than $n/m$" ruins the nice formula you can get from a stars-and-bars argument, that there are ${k+m-1 \choose m-1}=\frac {(k+m-1)!}{(m-1)!k!}$ of them.

Answer 2

So you have $4 m$ objects, $4$ of each of $m$ types, of which you want to pick $k$. Set it up as generating functions. Each type can be represented 0 to 4 times, so result is the following coefficient of the generating function: \begin{align} [z^k] (1 + z + z^2 + z^3 + z^4)^m &= [z^k] \left( \frac{1 - z^5}{1 - z} \right)^m \\ &= [z^k] (1 - z^5)^m \sum_{r \ge 0} (-1)^r \binom{-m}{r} z^r \\ &= [z^k] (1 - z^5)^m \sum_{r \ge 0} \binom{m + r - 1}{m - 1} z^r \\ &= \sum_{r \ge 0} \binom{m + r - 1}{m - 1} [z^{k - r}](1 - z^5)^m \end{align} This gets a bit messy, use Iverson's bracket to pick just the right elements: $$ [z^k] (1 + z + z^2 + z^3 + z^4)^m = \sum_{r \ge 0} [5 \mid k - r] \binom{m + r - 1}{m - 1} (-1)^{(k - r)/5} \binom{m}{(k - r) / 5} $$ No closed formula, I'm afraid.

Answer 3

This is equivalent to the problem of distributing $k$ balls over $m$ bins, each of limited capacity $\frac nm$, which can be solved using inclusion-exclusion; see e.g. Balls In Bins With Limited Capacity, or Brian's answer here. The result in your case is

$$ \sum_{t=0}^m(-1)^t\binom mt\binom{m+k-t\left(\frac nm+1\right)-1}{m-1}\;, $$

where, contrary to convention, the binomial coefficient is taken to vanish if the upper index is negative. In your example with $n=8$, $k=4$, $m=4$ this is

$$ \sum_{t=0}^4(-1)^t\binom4t\binom{7-3t}3=\binom73-4\binom43=35-16=19\;. $$