Placing Balls in Urns
Date: 05/15/2001 at 04:28:16 From: Jonathan Subject: Combinatorics Hi! I hope someone could please help me to prove this result: The number of different ways we can place b indistinguishable balls into u distinguishable urns is: C(b+u-1,b) = C(b+u-1,u-1) where the notation C(n,r) means the number of ways to choose r things from n things, i.e., the usual binomial coefficient. Thanks, Jon
Date: 05/15/2001 at 13:29:16 From: Doctor Rob Subject: Re: Combinatorics Number the urns from 1 to u. Line up the indistinguishable balls in a row. Split this row up into u sections by inserting u-1 separators. All balls to the left of the jth separator and to the right of the (j-1)st separator (counting from, say, the left end) go into the jth urn. You now have a row of b + u - 1 objects of which b are balls and u - 1 are separators. There are C(b+u-1,b) ways to choose the locations for the b balls among the b + u - 1 objects. Example: 4 balls (o), 3 urns, 2 separators (|): o o o o | | (4,0,0) o o o | o | (3,1,0) o o | o o | (2,2,0) o | o o o | (1,3,0) | o o o o | (0,4,0) o o o | | o (3,0,1) o o | o | o (2,1,1) o | o o | o (1,2,1) | o o o | o (0,3,1) o o | | o o (2,0,2) o | o | o o (1,1,2) | o o | o o (0,2,2) o | | o o o (1,0,3) | o | o o o (0,1,3) | | o o o o (0,0,4) 15 ways, C(6,4) = C(6,2) = 15. - Doctor Rob, 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.