Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Balls in Boxes


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

Hello!

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:

You have 2*t + 1 balls to put into 3 boxes, but the sum of the balls 
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:

t*(t+1)/2=1+2+3+...+t

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 + ....

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

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 

      t(t+1)/2         

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/   
    
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:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/