toys question

Printable View

January 17th 2011, 01:37 AM
prasum

toys 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
January 17th 2011, 02:15 AM
emakarov

One first chooses an unlucky child (n ways) and then distributes n toys between the rest n - 1 children. The latter number is $\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.
January 17th 2011, 03:44 AM
Plato

Quote:

Originally Posted by prasum

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

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, $M\ge N$ , is $\text{Surj}(M,N) = \sum\limits_{k = 0}^N {( - 1)^k \binom{N}{k}\left( {N - k} \right)^M }$ .

Now there are n ways to select the unlucky child. There are then $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.
January 18th 2011, 01:32 AM
prasum

can yu please give me a simpler method
January 18th 2011, 03:59 AM
Plato

Quote:

Originally Posted by prasum

can yu please give me a simpler method

This is not a simple question so there is no simple solution.
If the toys were identical then there is a somewhat simpler solution, see reply #2.
January 18th 2011, 04:45 AM
Soroban

Hello, prasum!

Quote:

$n \text{ different toys are distributed among }n\text{ children.}$
$\text{Find the number of ways in which exactly one child gets no toy.}$

There are $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: . $_6P_5 \,=\,720$ ways.

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

Therefore, there are: . $6\cdot720\cdot5 \:=\:21,600$ ways.
January 18th 2011, 05:10 AM
awkward

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.
January 18th 2011, 06:39 AM
Plato

1 Attachment(s)

Quote:

Originally Posted by awkward

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.

@ 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
$3\cdot(3-1)!\cdot(3-1)=12$ .

Soroban's count is twice the actual.
January 18th 2011, 01:44 PM
awkward

Quote:

Originally Posted by Plato

@ 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
$3\cdot(3-1)!\cdot(3-1)=12$ .

Soroban's count is twice the actual.

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 $n$ ways.

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

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

So the total number of possibilities is $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).