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/