![]](http://coweb.math.gatech.edu:8080/files/schemes/math/after.gif)
Counting Problems Using Balls and Urns-- Corey Cato (A1) and Kristy Hanson (A1)
Counting Problems Using Balls and Urns
Authors: Corey Cato (A1) and Kristy Hanson (A1)
A classical way of solving common counting problems is to find an equivalent problem such as counting the number of ways to place b balls into u urns. Although these counting problems appear to be complex most can be simplified into one of the four basic situations using balls and urns. There are four basic situations to a ball and urn problem:
A. Balls- distinguishable and Urns- distinguishable
B. Balls- indistinguishable and Urns- distinguishable
C. Balls- indistinguishable and Urns- indistinguishable
D. Balls- distinguishable and Urns- indistinguishable
Note: Distinguishable means the balls or urns are labeled with numbers, colors, or other identifying marks so you can tell them apart. When the balls or urns are indistinguishable they have no identifying marks so you cannot differentiate one from another. For the problems below assume each urn can hold any number of balls and there is no order to the balls within an urn.
Problem A: Balls- distinguishable and Urns- distinguishable
Formula: u^b = # of possibilities (where u is the # of urns and b is the # of balls)
Example: Coach Gailey wants you to list all ways of putting 5 distinguishable balls into 3 distinguishable urns.
Solution: You can begin by numbering the balls 1, 2, 3, 4, and 5 and labeling the urns with letters A, B, and C. There is obviously a difference between putting Ball 1 into Urn A, B, or C. There is also a difference between placing Ball 1 in Urn A and placing Ball 2 in Urn A. By the product rule the total number of choices is equal to ub.
Number of Possibilities: 3^5 = 243
Problem B: Balls- indistinguishable and Urns- distinguishable
Formula: C(b+u–1,b) (where u is the # of urns and b is the # of balls)
Example: Calvin Johnson wants you to list all ways of putting 8 indistinguishable balls into 6 distinguishable urns.
Solution: Consider 6 urns in a row, labeled A, B, C, . . . F. And remember there is no restriction on the number of balls each urn can contain. You start at Urn A and move down the row placing x number of balls in each urn making sure that by Urn F you have used all eight balls. This means that for u-1 urns the number of balls inside each urn is arbitrary. So you merely count the number of ways to line up b balls and u-1 urns, which is equal to b+u-1 total positions in the lineup. Because b of these positions must be balls we choose b balls from b+u-1 positions.
Number of Possibilities: C(8+5–1,8) = C(12,8) = 495
Problem C: Balls- indistinguishable and Urns- indistinguishable
Formula: No standard formula
Example: P.J. Daniels wants you to list all the ways of putting 11 indistinguishable balls into 4 indistinguishable urns, with each urn having at least 2 balls.
Solution: Begin by placing 2 balls in each of the 4 urns to meet the initial criteria. You are then left with 3 balls to distribute among the 4 urns. There are three different combinations to distribute the balls:
• You can place all three remaining balls in a single urn with following combination: 2 2 2 5.
• You can place one ball in one urn and place the other two balls in a different urn which give you the combination: 2 2 3 4.
• You can place each of the three balls in a different urn leaving you with the combination: 2 3 3 3.
It is important to remember that both the balls and urns are indistinguishable. Therefore the configuration 2 2 2 5 and 2 5 2 2 are not considered different combinations and are only counted as one possibility.
Number of Possibilities: There are three different ways for putting 11 indistinguishable balls into 4 indistinguishable urns, with each urn having at least 2 balls: 2 2 2 5, 2 2 3 4, and 2 3 3 3.
Problem D: Balls- distinguishable and Urns- indistinguishable
Formula: Summation of j from 0 to u and summation of k from 0 to j of the following formula- [(-1)k/j!](C(j,k))(j-k)b (where u is the # of urns and b is the # of balls)
Example: Nate Curry wants you to place 4 distinguishable balls into 3 indistinguishable urns.
Solution: The number of different ways to distribute b labeled balls into u unlabeled urns (with empty urns allowed) is equal to B(b,u). In order to find B(b,u), we will first consider the number of possibilities when no urn is empty and introduce T(b,u) and S(b,u). T(b,u) is equal to the number of ways to put b distinguishable balls into u distinguishable urns, with no empty urns. S(b,u) is equal to the number of ways to put b distinguishable balls into u indistinguishable urns, with no empty urns. S(b,u) is then equal to T(b,u) divided by u!. Because the urns are indistinguishable, if k of them are empty, it doesn’t matter which k. Therefore it is as if we only had u-k urns to start with. Thus B(b,u) is the summation of j from 0 to u of S(b,j). B(b,u) is then the summation of j from 0 to u of T(b,j)/j!. Using Inclusion-Exclusion, T(b,j) is equal to the summation of k from 0 to j of the formula- [(-1)k](C(j,k))(j-k)b. For example B(1,1) = 1 because there is only one way to put one labeled ball into one unlabeled urn.
Number of Possibilities: Summation of j from 0 to 3 and summation of k from 0 to j of the following formula- [(-1)k/j!](C(j,k))(j-k)4
Additional Problem: A counting problem initially may not look like a ball and urn problem but can easily be solved by thinking of the variables as either distinguishable or indistinguishable balls or urns and then applying one of the four basic formulas.
Example: Reggie Ball wants to know how many solutions are there to the equation: x + y + z + w = 56? (All solutions must contain positive integer values.)
Solution: First realize that the variables (x, y, z, and w) are our 4 urns. You know the total number of “things” put inside these urns sums to 56, so 56 is the total number of balls. Next you must determine what is distinguishable and indistinguishable. It makes no difference whether you assign the first five balls to Urn x, or the last five balls to Urn x. The only thing that affects the end solution is that there are 5 balls in Urn x. Since it doesn’t matter which ball is placed into an urn, the balls are considered to be indistinguishable. It does matter whether you assign a ball to Urn x versus assigning it to Urn y, so that is like having distinguishable urns. This means that we can solve this problem as if we had 56 indistinguishable balls and 4 distinguishable urns.
Formula: C(b+u–1,b) (where u is the # of urns and b is the # of balls)
Number of Possibilities: C(56+4–1,56) = C(59,56) = 32,509
