n different toys can be distributed among n children total no of ways in which it can be distributed so that exactly one child gets no toy

Printable View

- Jan 17th 2011, 01:37 AMprasumtoys question
n different toys can be distributed among n children total no of ways in which it can be distributed so that exactly one child gets no toy

- Jan 17th 2011, 02:15 AMemakarov
One first chooses an unlucky child (n ways) and then distributes n toys between the rest n - 1 children. The latter number is $\displaystyle \tbinom{n-1}{n-2}$ (see Wikipedia). Indeed, to distribute n toys between n - 1 children so that every child gets at least one toy means to select a child that gets two toys (n - 1 ways) and then give the rest of the children one toy.

- Jan 17th 2011, 03:44 AMPlato
The fact that the toys are different means we are counting functions.

The number of**onto functions(surjections)**from a set of M to a set of N, $\displaystyle M\ge N$, is $\displaystyle \text{Surj}(M,N) = \sum\limits_{k = 0}^N {( - 1)^k \binom{N}{k}\left( {N - k} \right)^M }$.

Now there areways to select the unlucky child. There are then $\displaystyle n\cdot \text{Surj}(n,n-1)$ ways to give the toys to give the toys out so that exactly one child gets no toy.*n* - Jan 18th 2011, 01:32 AMprasum
can yu please give me a simpler method

- Jan 18th 2011, 03:59 AMPlato
- Jan 18th 2011, 04:45 AMSoroban
Hello, prasum!

Quote:

$\displaystyle n \text{ different toys are distributed among }n\text{ children.}$

$\displaystyle \text{Find the number of ways in which exactly one child gets no toy.}$

There are $\displaystyle 6$ choices for the unlucky child.

The six toys are distributed among the five Others.

. . Each of them get at least one toy.

Give one toy to each of the five Others.

. . There are: .$\displaystyle _6P_5 \,=\,720$ ways.

The sixth toy can be given to any of the five Others: .$\displaystyle 5$ ways.

Therefore, there are: .$\displaystyle 6\cdot720\cdot5 \:=\:21,600$ ways.

- Jan 18th 2011, 05:10 AMawkward
First select the unlucky child. This can be done in n ways.

Next distribute the first n-1 toys among the remaining children. This can be done in (n-1)! ways.

Finally, select a lucky child to get the nth toy. This can be done in n-1 ways.

So the total number of possibilities is n (n-1)! (n-1).

I suppose that Plato's answer can be simplified to this form, but just thinking about it gives me a headache. - Jan 18th 2011, 06:39 AMPlato
@ awkward: actually the two counts are not the same. See the graphic.

Take the example of three toys and three children.

There are six ways to give three toys to two children so that both get at least one toy. There are three ways to have an unlucky child. That is 18 not

$\displaystyle 3\cdot(3-1)!\cdot(3-1)=12$.

Soroban's count is twice the actual. - Jan 18th 2011, 01:44 PMawkward
Akkk! Plato is right, as usual.

i now see my error-- I was failing to count some of the distributions like 1-1-2 in the case of 3 children, where the first two gifts do not go to the first two children.

So, in a feeble attempt to rehabilitate my reputation, here is another try at it.

First choose the unlucky child who gets no gift. This can be done in $\displaystyle n$ ways.

Somebody must get two gifts. These two gifts can be selected in $\displaystyle \binom{n}{2}$ ways.

If we consider the bundle of two gifts to be one object and the single gifts to be $\displaystyle n-2$ objects, there are a total of $\displaystyle n-1$ objects to distribute among the $\displaystyle n-1$ children. This can be done in $\displaystyle (n-1)!$ ways.

So the total number of possibilities is $\displaystyle n \cdot \binom{n}{2} \cdot (n-1)!$.

I think this formula will be found to agree with Plato's numbers, but I still get faint at the thought of showing the formulas are the same algebraically (although I see Plato has listed them as equivalent in his post).