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/