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?

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search