Here is a "colourful" description of what I would like to count. Suppose you have one of those tables you see in a casino. I think they are for roulette, with $m$ squares, each of them with a number inside them. You have $c_1$ chips of type 1, $c_2$ chips of type $2,\dots,c_n$ chips of type $n$. You have to place the chips on top of the squares such that each number has at least $1$ chip over it but no square has two or more chips of the same colour on top of it. In how many ways can we do this?
The answer is the coefficient of $x_1^{c_1}\cdots x_n^{c_n}$ in $[(1+x_1)(1+x_2)\cdots(1+x_n)1]^m$. Here $(1+x_1)\cdots (1+x_n) 1$ corresponds to the chips placed on each square; zero or one of each color, but at least one chip. We can expand by the binomial theorem to get that this coefficient is $$\sum_{k=0}^m (1)^{mk}\binom mk \binom k{c_1}\cdots \binom k{c_n}.$$ This formula can also be proved directly by inclusionexclusion: $\binom mk \binom k{c_1}\cdots \binom k{c_n}$ is the number of ways to choose $k$ of the $m$ squares and place all of the chips on these squares, with at most one chip of each color on each square (but with some squares possibly having no chips).



$\begingroup$ can I use your solution for a different problem in another website ? the url of that website is math.stackexchange.com but most people just call it math.se $\endgroup$– GorkaJun 3 '14 at 0:04
