Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives

Balls in Boxes

Date: 05/05/99 at 13:49:04
From: Alp Bassa
Subject: A combinatorial problem (putting balls in boxes)


I tried to solve the following problem. I know the answer, but I 
don't know how to find it. I hope you can help me:

in 2 of the boxes should be more then the balls in the other box. How 
many ways are there to do this?

Answer: t*(t+1)/2 (why?)

I tried to solve it this way:


If there are B(n-2) ways to do this with n-2 balls, then we can to 
this with n Balls in B(n) ways. Now we just have to find some relation 
between B(n) and B(n-2). So it seems like a recursion problem.

Thank you very much,
Alp Bassa

Date: 05/05/99 at 16:09:40
From: Doctor Anthony
Subject: Re: A combinatorial problem (putting balls in boxes)

If any box is empty one box will have more balls than the other two, 
so we know that every box has some balls. Also with 2t+1 balls no box 
can have more than t balls or again it would not satisfy the condition 
of being outnumbered by the other two. So the generating function is

(x + x^2 + x^3 + ..... + x^t)^3 and we require coefficient of x^(2t+1)

We can write the series as  

                 x^3(1 - x^t)^3
                    (1 - x)^3 

       = x^3(1-x^t)^3(1-x)^(-3)

  =  x^3[1 -3x^t + 3x^(2t) - x^(3t)][1 + C(3,1)x + C(4,2)x^2 + ....

  = x^3 - 3x^(t+3) + 3x^(2t+3) - x^(3t+3)]SUM[C(r+2,2)x^r] 

We can ignore the terms 3x^(2t+3) - x^(3t+3) as they are already 
beyond the power of 2t+1 that we require.

  We have x^3.C(2t,2t-2).x^(2t-2)  =  C(2t,2t-2).x^(2t+1)

  also  -3x^(t+3).C(t,t-2).x^(t-2)  =  -3.C(t,t-2).x^(2t+1)

So required coefficient is

    2t(2t-1)     3t(t-1)       4t^2 - 2t - 3t^2 + 3t
      2!           2!                    2!

                                t^2 + t        t(t+1)
                                   2             2 

and so the number of arrangements satisfying the condition is 


- Doctor Anthony, The Math Forum
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:


parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]


Ask Dr. MathTM
© 1994-2013 The Math Forum