Distributing chocolates to children

If we consider all chocolates to be different/unique, then the first chocolate can go to any one of the m children and the next one too can go to any one of the m children and so on. This gives \(m * m * m *m...(n\ times) = m^n\) possibilities.

here the chocolates aren't different from each other. So the first chocolate going to first child and second going to second one is the same as first chocolate going to second child and the second one going to the first one. These cases must be counted only once. So we are concerned only with how many chocolates each child gets in the end. This means the possible distributions are less than \(m^n\) . But exactly how much is it? is an interesting mathematical problem that I ask you to try yourself for a while :unamused: .

This problem becomes trivial, when it is converted to a permutation problem concerned with arranging children and chocolates. Let's consider a case of 4 children and 7 chocolates. Denoting children by | and chocolates by * a possible arrangement is:

*|**||****|

If each child gets chocolates to the left of it then here the first child gets one chocolate, second one gets 2, third one gets nothing while the fourth one gets four. The single stick at the rightmost end is compulsory because all chocolates have to be distributed. Since a fixed stick doesn't change the number of combinations/arrangements, we can remove the rightmost stick and say that the remaining stars are given to the last child. i.e. the equivalent arrangement is:

|**||***

Since, each distribution can be represented in this pattern of stars & sticks, and each stars-sticks pattern represents a possible distribution, the number of possible distributions is equal to number of possible star-sticks patterns. So, now the problem is just this : In how many ways can we arrange n stars and m-1 sticks ?

There are (4-1)+7 = 10 places/position. So the sticks can be placed in =\({{10}\choose {3}} = \frac {10!} {(10-3)! * 3!} = 120\) ways. After placing the sticks we can just fill in the position with chocolates in only one way. So this is the total number of way to distribute 7 chocolates to 4 children. Now of course, we could have filled in chocolates first and then the sticks. It gives the same result as \({{10}\choose {7}} = \frac {10!} {(10-7)! * 7!} = 120\)

So for the case of n chocolates and m children, the result is : =\({{n+m-1}\choose{n}} = \frac {n+m-1} {(m-1)! n!} = {{n+m-1}\choose{m-1}}\)

If we are to put n identical particles in m non-identical boxes. Then the number of ways we can do this is same as the number of ways we can distribute n chocolates to m children. \({{n+m-1}\choose{n}} = \frac {n+m-1} {(m-1)! n!}\)

For example, the number 4 can be expressed as sum of 3 numbers in following four ways: * 0+0+4, 0+4+0, 4+0+0, * 0+1+3, 0+3+1, 1+0+3, 1+3+0, 3+0+1, 3+1+0 * 0+2+2, 2+0+2, 2+2+0, * 1+1+2, 1+2+1, 2+1+1

This is similar to distributing 4 chocolates to 3 children and equals \({{6}\choose{4}} = 15\). But if we are to disregard order then there are just 4 possible ways. Generalizing to number N with n partitions is not this simple.