1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ Can I use this for a question in math.se? $\endgroup$
    – Gorka
    Jun 2, 2014 at 15:19
  • $\begingroup$ I don't understand what you are asking. $\endgroup$
    – Ira Gessel
    Jun 3, 2014 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$
    – Gorka
    Jun 3, 2014 at 0:04
  • $\begingroup$ As far as I'm concerned you can. $\endgroup$
    – Ira Gessel
    Jun 3, 2014 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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