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)^{m-k}\binom mk \binom k{c_1}\cdots \binom k{c_n}.$$ This formula can also be proved directly by inclusion-exclusion: $\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 this for a question in math.se? $\endgroup$ – Jorge Fernández Jun 2 '14 at 15:19
  • $\begingroup$ I don't understand what you are asking. $\endgroup$ – Ira Gessel Jun 3 '14 at 0:01
  • $\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$ – Jorge Fernández Jun 3 '14 at 0:04
  • $\begingroup$ As far as I'm concerned you can. $\endgroup$ – Ira Gessel Jun 3 '14 at 4:21

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.