Results 1 to 2 of 2

Math Help - A balls and boxes problem

  1. #1
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    48
    Awards
    1

    A balls and boxes problem

    Hello,
    I would be extremely grateful for any help with this problem:

    Let r,n,k \in \mathbb{N} be numbers such that r \geq (n-3) \cdot k and n \geq 5.

    Find the number of ways we can put r indistinguishable balls into n distinguishable boxes, so that:
    -exactly three boxes remain empty,
    -two boxes contain exactly k balls, and that
    -each of the remaining boxes has at least k balls.

    *******

    For example, I tried to sketch one of the possible distributions in case that r=7,n=6 and k=2:



    -the second, third and sixth boxes are empty;
    -the first and fourth box contain exactly 2 balls;
    -the fifth box contains three balls (which is > 2).

    ******

    Now, how could this problem be solved for any r,n,k as defined above? I know that we can find the number of partitions of a set containing n elements into k non-empty parts by Stirling numbers of the second kind, S(n,k) -- but in this problem, three of the parts must be empty! Should we first break this problem down into several disjoint cases where we first determine where would the empty boxes be, and then fill the remaining boxes with balls? There are, I believe, \begin{pmatrix}n\\3\end{pmatrix} ways we can choose three of n distinguishable boxes to be empty, there then remain (n-3) boxes in each case to be filled with balls. Of those (n-3) boxes, 2 must contain exactly k balls. We can choose those boxes in \begin{pmatrix}n-3\\2\end{pmatrix} ways, and in those boxes we put 2k balls. There now remain (n-5) boxes to be filled with (r-2k) balls, but under the condition that there are at least k balls in each of the remaining (n-5) boxes...


    Is this the right way to approach this problem? I'm not certain that the above argument is entirely correct, and would really appreciate some pointers in the right direction.

    Many thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by gusztav View Post
    Hello,
    I would be extremely grateful for any help with this problem:

    Let r,n,k \in \mathbb{N} be numbers such that r \geq (n-3) \cdot k and n \geq 5.

    Find the number of ways we can put r indistinguishable balls into n distinguishable boxes, so that:
    -exactly three boxes remain empty,
    -two boxes contain exactly k balls, and that
    -each of the remaining boxes has at least k balls.
    [snip]
    PaulRS and Gustav,

    I think the preceding solution over-counts some of the arrangements by looking at \binom{n-3}{2} ways to choose 2 boxes which contain exactly k balls and then multiplying by the number of ways to arrange at least k balls in the remaining boxes. The problem is that some of those arrangements will also include 2 boxes containing exactly k balls, and those arrangements are counted more than once.

    So here is an alternative approach which I think avoids that difficulty. As before, first choose the three empty boxes, which can be done in
    \binom{n}{3}
    ways. We now want to count the number of ways in which r balls can be put into n-3 boxes so that at least 2 boxes contain exactly k balls and all boxes contain at least k balls. Call this number N.

    To compute N, we count the number of ways to put r balls into n-3 boxes with at least k balls in each box and then subtract the number of arrangements which violate the "at least 2 boxes with exactly k balls" constraint. The unsatisfactory arrangements can be broken into two disjoint subsets: (1) those with no box containing k balls, so all the boxes contain at least k+1 balls; and (2) those with exactly one box containing k balls, and all the other boxes containing at least k+1 balls. Modifying PaulRS’s notation slightly, let

    R(n,k) = \binom{n-k+1}{k},

    the number of ways to place k balls in n boxes with no constraints. Then the number of ways to put r balls into n-3 boxes with at least k balls in each box is
    R(n-3, r -(n-3)k).
    The number of ways to put r balls into n-3 boxes with at least k+1 balls in each box is
    R(n-3, r-(n-3)(k+1)).
    The number of ways to put k balls into one box and at least k+1 balls into each of the remaining boxes is
    \binom{n-3}{1} R(n-4, r - k - (n-4)(k+1)).

    So
    N = R(n-3, r -(n-3)k) - R(n-3, r-(n-3)(k+1)) - \binom{n-3}{1} R(n-4, r - k - (n-4)(k+1))
    and the answer to the original problem is
    \binom{n}{3} N.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Puzzle: There are 3 boxes with two golf balls each.
    Posted in the Math Puzzles Forum
    Replies: 3
    Last Post: August 28th 2011, 10:51 AM
  2. Replies: 9
    Last Post: May 15th 2011, 05:29 PM
  3. a basket contains 5 red balls, 3 blue balls, 1 green balls
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: May 28th 2010, 03:39 AM
  4. different balls, identical boxes
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 21st 2010, 02:29 AM
  5. Probabilty, Putting balls in boxes
    Posted in the Statistics Forum
    Replies: 3
    Last Post: February 4th 2009, 06:49 PM

Search Tags


/mathhelpforum @mathhelpforum