Results 1 to 6 of 6

Math Help - Sorting With Restrictions

  1. #1
    Junior Member
    Joined
    May 2009
    Posts
    42

    Sorting With Restrictions

    How many ways can we put 'z' different objects into 4 boxes such that at least two boxes remain empty?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,670
    Thanks
    1618
    Awards
    1
    Quote Originally Posted by JoAdams5000 View Post
    How many ways can we put 'z' different objects into 4 boxes such that at least two boxes remain empty?
    Are the boxes labeled or unlabeled? That is are the boxes identical or not?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    May 2009
    Posts
    42
    The four boxes in this question are different.

    However, I would also be interested in how the answer would change if the boxes were identical instead.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,739
    Thanks
    645
    Hello, JoAdams5000!

    I will assume that the boxes are distinguishable.


    How many ways can we put z different objects into 4 boxes
    such that at least two boxes remain empty?

    There are only two cases:

    . . (1) There are two empty boxes.

    . . (2) There are three empty boxes.



    Case (1): Two empty boxes

    There are: . {4\choose2} = 6 choices for the 2 empty boxes.

    The z objects are partitioned between the other two boxes.
    . . There are: . z-1 ways.

    Hence, there are: . 6(z-1) ways to have two empty boxes.



    Case (2): Three empty boxes

    There are: . {4\choose3} = 4 choices for the three empty boxes.

    The z objects are placed in the remaining box.
    . . There is: . 1 way.

    Hence, there are: . 4\cdot1 = 4 ways to have three empty boxes.


    Therefore, there are: . 6(z-1) + 4 \:=\:6z - 2 ways to have at least two empty boxes.

    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by JoAdams5000 View Post
    How many ways can we put 'z' different objects into 4 boxes such that at least two boxes remain empty?

    Thanks!
    There are 4 ways to place all 21 objects into 1 of 4 boxes.
    This is the number of ways to have 3 empty boxes.

    For the case of 2 empty boxes, there are \binom{4}{2}=4c_2=6 ways to choose 2 of them, if they are different.

    Taking one pair of 2 boxes...
    the objects can be placed as follows

    1 object in one box and 20 in the other

    There are \binom{21}{1}=21 ways to do this as the 'z" objects are different.

    2 objects in one box and 19 in the other

    There are \binom{21}{2} ways to choose 2 objects,

    so that's the number of ways to place 2 in one and 19 in the other.

    Continue on for 3 in one and 18 in the other, 4 in one and 17 in the other etc
    and sum all the results. Multiply that sum by 6.

    Add the number of ways to have 2 and 3 empty boxes.

    However, there is likely to be a faster calculation.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,670
    Thanks
    1618
    Awards
    1
    Quote Originally Posted by JoAdams5000 View Post
    The four boxes in this question are different.
    However, I would also be interested in how the answer would change if the boxes were identical instead.
    The objects are distinct and the boxes are distinct.
    There are \binom{4}{2} to choose two empty boxes.
    There are 2^z-2 ways to assign the z objects to the two other boxes so neither is empty.

    There are \binom{4}{1} to choose three empty boxes.
    There is only one way to put the objects into the remaining box.

    To have either exactly two or exactly three empty boxes:
    \binom{4}{2}\left(2^z-2\right)+\binom{4}{3}\.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sorting Elements of Set Before Working On it?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 20th 2010, 06:59 AM
  2. Sorting Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 15th 2008, 02:54 AM
  3. Fastest sorting algorithm
    Posted in the Discrete Math Forum
    Replies: 18
    Last Post: April 7th 2008, 08:31 PM
  4. sorting algorithm
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: November 26th 2007, 07:12 AM

Search Tags


/mathhelpforum @mathhelpforum