In how many ways can $n$ identical balls be distributed to nine persons $A,B,C,D,E,F,G,H,I$ so that the number of balls recieved by $A$ is the same as the total number of balls recieved by $B,C,D,E$ together,.
Problem
Source: Indian Postal Coaching 2005
Tags: function, combinatorics unsolved, combinatorics
05.10.2005 21:34
these sort of problems are readily handled by the exponential generating function. let $x_A,\ldots,x_I$ denote the distribution of the balls. Then we have $x_A=x_B+x_C+x_D+x_E$ so that we have that $2(x_B+x_C+x_D+x_E)+x_F+\cdots+x_I=n$ or in other words we need the number of ordered $8$-tuples such that $4$ terms are even. The Exponential generating function here is simply $(\sum_{k\geq 0} \dfrac{x^{2k}}{(2k)!})^4(\sum_{k\geq 0} \dfrac{x^k}{k!})^4$. what you need here is the coeff of $x^n$ which is easily obtained by simplification.
05.10.2005 23:58
seshadri wrote: in other words we need the number of ordered $8$-tuples such that $4$ terms are even. The Exponential generating function here is simply $(\sum_{k\geq 0} \dfrac{x^{2k}}{(2k)!})^4(\sum_{k\geq 0} \dfrac{x^k}{k!})^4$ I think this E.G.F. is incorrect. It is better to use regular G.F. here which is \[ \left(\sum_{k\geq 0} x^{2k}\right)^4 \left(\sum_{k\geq 0} x^k\right)^4 = (1-x^2)^{-4} (1-x)^{-4} \]
06.10.2005 00:07
oh yes, you are right. i misread the 'identical balls' part and assumed that the balls are distinguishable.