Browse · MathNet
PrintCzech-Polish-Slovak Match
counting and probability
Problem
We distribute labelled balls among nine persons , , , , , , , , . Determine in how many ways it is possible to distribute the balls under the condition that gets the same number of balls as the persons , , and together.
Solution
Consider the polynomial and suppose that we multiply out the brackets, obtaining summands. We show the one-to-one correspondence between the number of 's and the number of the distributions we deal with in the problem. Suppose we have such a distribution. If the -th ball goes to , we pick from the -th bracket. If it goes to , , , , we pick the first, second, third or fourth , respectively, from the -th bracket. If it goes to , , , , then we take the first, second, third or fourth from the -th bracket. Now if we multiply the factors we have chosen, we see, that the result is equal to if and only if gets the same number of balls as , , , jointly. Therefore, the number of the distributions we are interested in is equal to the coefficient at in the polynomial , that is,
Final answer
binom(2n, n) * 2^n
Techniques
Generating functionsRecursion, bijection