How many ways of giving out 6 pieces of candy to 3 children if each child must receive at-least one piece ?
I think, $ 5 \choose 2$ is the answer,consistent to $ n-1 \choose r $ as this is similar to finding the number of non-zero positive integer solution of the equation $X_1 + X_2 + X_3 = 6$ ,but the correct answer (as given in my module) is $540$.
Where exactly am I wrong?
Best Answer
If all you care about is how many pieces of candy each chuld gets, then you are right. We would say in this case that the pieces of candy are "indistinguishable". But if you care WHICH piece of candy each child gets, e.g if the individual candies are numbered from 1 to 6, then there are many solutions corresponding to each solution of the equation $X_1+X_2+X_3=6$, In this case the problem is to count the number of surjective (or "onto") functions from a six-element set to a three-element set.
In general there is no "nice" formula (comparable to the one for the binomial coefficients) for the number of surjective functions from an $n$ element set to an $m$ element set, but this number is $m!S(n,m)$, where the expression $S(n,m)$ refers to a Stirling number of the second kind, and is defined recursively for $n,m>1 $ by $S(n,m)=mS(n-1,m)+S(n-1,m-1)$. The basis cases are a bit messy: $S(n,1)=1$, $S(n,n)=1$, and $S(n,m)=0$ if $n<m$ or $n=m=0$.
Actually $S(n,m)$ counts the number of partitions of $n$ distinguishable elements into $m$ non-empty sets. All onto functions from an $n$ element set to an $m$ element set are obtained choosing such a partition $p$ arbitrarily, and then assigning each of the $m$ elements of $p$ to one of the $m$ elements of the $m$-element set. There are $m!$ ways to do this, hence the formula $m!S(n,m)$.
A nice discussion of all this can be found in Section 1.4, "The Twelvefold Way", in Stanley's "Enumerative Combinatorics" volume 1.