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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.