Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
The $6$ pieces of candy are not considered identical objects! The answer then is indeed $540$. –  Shai Covo Dec 19 '10 at 10:40

2 Answers 2

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.

share|improve this answer
2  
Are you sure that Stanley claims that $S(0,0)=0$? That would seem rather surprising, because it's wrong. $S(0,0)=1$ for precisely the same reason that $\binomial(0,0)=1$ –  Peter Taylor Mar 30 '11 at 14:45
up vote 3 down vote accepted

You have assumed that $6$ candies are identical but that is not the case here.

This problem can be modeled be letting A represent the set of candies and B represent the set of children.Then a function $f \colon A \to B $ can be interpreted as giving candy $a_i$ to $c_J$. Since each child must receive at-least one candy, we are considering only onto functions.So your problem boils down to counting number of onto functions in $f \colon A \to B $.

To calculate this value we could use a formula which is actually derived by using the principle of inclusion-exclusion:

If A,B are non-empty sets of cardinality $m$,$n$ with $m \ge n$.Then there are $$\sum_{i=0}^{(n-1)} (-1)^i {n \choose i} (n-i)^m \text{ onto functions in } f \colon A \to B $$

In this case we have $m = 6$ and $n = 3$ then we get : $3^6 - {3 \choose 1} (3 - 1)^6 + {3 \choose 2} (3 - 2)^6 = 540$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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