Results 1 to 9 of 9

Math Help - toys question

  1. #1
    Senior Member
    Joined
    Feb 2010
    Posts
    456
    Thanks
    34

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by prasum View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    456
    Thanks
    34
    can yu please give me a simpler method
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by prasum View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,689
    Thanks
    617
    Hello, prasum!

    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.

    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by awkward View Post
    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.
    Attached Thumbnails Attached Thumbnails toys question-untitled.gif  
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Plato View Post
    @ 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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Buying two different kinds of toys.
    Posted in the Algebra Forum
    Replies: 3
    Last Post: November 7th 2011, 09:25 PM

Search Tags


/mathhelpforum @mathhelpforum