Lecture 3: Combinatorial Analysis

The solution of many classical problems in probability revolve around counting, since in many of the problems the sample space is a finite set (poker hands, tosses of dice) and the probability of each outcome is assumed to be the same. The basic idea is to partition the set into disjoint subsets and the count the number of elements of each subset. This process may be repeated with the subsets until sets that are easily counted are arrived at. What is subtle is what sets are being counted. Usually each subdivision yields subsets of the same size, and instead of adding we can multiply. For example:

A child has one pair of red shorts, one pair of blue shorts, one green shirt, one white shirt and one yellow shirt. How many combinations of one shirt and one pair of shorts can he wear?

The set of objects to be counted consists of pairs of shirts and shorts. We can divide this set into those pairs where the shorts are red, and those pairs where the shorts are green. These two subsets are clearly disjoint, and each consists of 3 elements, so there are 3 + 3 = 6 outfits.

Another example:

A child has one pair of red shorts, one pair of blue shorts, one green shirt, one white shirt and one yellow shirt. How many combinations of one shirt and one pair of shorts can he wear if he cannot wear the red shorts with the yellow shirt?

Again we can divide the set up according to the color of the shorts. There are 2 elements in the set where the shorts are red and 3 elements in the set where the shorts are blue, so there are 2 + 3 = 5 outfits.

Common problems

The following four kinds of problems occur frequently, and many counting problems can be reduced to some combination of the following.

• Ordered samples with replacement. Consider our coin tossing experiment. We toss a coin 100 times, and want to know how many different sequences of heads (H) and tails (T) we can obtain. If we partition this according to the outcome on the first toss, we see that it is twice the number of sequences of length 99. A moments thought reveals we may continue in this fashion and get that the number of different sequences is 2¹⁰⁰. In the same way, we see that if a die with six different faces is tossed 9 times there are 6⁹ differents sequences of tosses that might occur.
• Ordered samples without replacement. I want to draw 6 pool balls from the usual set of 15, one at a time, and record the number of the ball before discarding the ball. How many sequences of 6 numbers are possible?

  Here the key is that each ball can be considered at most once, hence the phrase ``without replacement''. I have 15 choices for the first ball, 14 choices for the second ball, 13 for the third ball, 12 for the fourth ball, 11 for the fifth ball and 10 for the sixth and final ball, making

  $$15\times 14\times 13\times 12\times 11\times 10 = \frac{15!}{(15-6)!} = \frac{15!}{9!}$$

  choices. This number is called the number of permutations of 6 items out of 15. By adopting the convention that 0! = 1 we see that the number of permutations of n items out of n is n!. Usually this case is refered to as the number of permutations of n items, and the phrase ``out of n'' is omitted. There are two common notations for the number of permutations of r items out of n. One is (n)_r and the other is nPr or _nP_r.
• Unordered samples without replacement. This is what is counted in games like Powerball and Megabucks. Here the order of the items does not matter, and no item may appear more than once. The way to solve this counting problem is to relate it to the problem of ordered samples without replacement. For example, suppose we return to the pool ball problem. Let ₁₅C₆ represent the number of ways of drawing 6 of the balls out of the 15 where order does not matter. We could count the number of ordered samples by reasoning as follows. The set of ordered samples could be divided into subsets according to which six balls were ordered. This would give us ₁₅C₆ disjoint subsets to count. Each of these subsets contains 6! elements (the number of ways of ordering 6 items. Therefore

  $$\frac{15!}{9!} = _{15}C_6\times 6!$$

  so that

  $$_{15}C_6 = \frac{15!}{9!6!} = \mbox{$\left(\begin{array} {c}15\ 6\end{array}\right)$}.$$

  This is what happens in general: the binomial coefficients tell us the number of ways of choosing r items out of n.
• Unordered samples with replacement. Suppose that I have 5 red balls, 5 green balls and 5 yellow balls. How many different collections of 4 balls can I make? What I need to keep track of is the number of each color ball, call them R, G and Y, subject to R + G + Y = 4. Consider a collection of 4 stars, *, and 2 bars, |, a total of 6 symbols. If these six symbols are to be put in a row, say *|**|*, there are

  $$\mbox{$\left(\begin{array} {c}6\ 4\end{array}\right)$} = \mbox{$\left(\begin{array} {c}6\ 2\end{array}\right)$}$$

  ways to do this. Each of these ways represents a way of solving the equation R + G + Y = 6. We simply let the number of stars to the left of the first bar represent the number of red balls, the number of stars between the bars represent the number of green balls and the number of stars to the right of the last bar represent the number of yellow balls. Thus *|**|* represents R = 1, G = 2 and Y = 1, while |****| represents R = 0, G = 4 and Y = 0. Generalizing, we see that the number of non-negative integer solutions to

  $$r_1 + r_2 + \cdots + r_n = r$$

  is given by

  $$\mbox{$\left(\begin{array} {c}n+r-1\ r\end{array}\right)$} = \mbox{$\left(\begin{array} {c}n+r-1\ n-1\end{array}\right)$}$$

As you can see if we have a large number of objects to choose from and or a large number of choices to make, we will need to compute ratios involving factorials of very large numbers. A handy result is such cases is Stirling's formula, which says

$$\lim_{n\rightarrow\infty} \frac{n!}{n^n\exp(-n)\sqrt{2\pi n}} = 1$$

Thus, for example, if we want an idea of the size of

$$\mbox{$\left(\begin{array} {c}100\\ 60\end{array}\right)$} = \frac{100!}{60!40!}$$

we can say

$$\frac{100!}{60!40!} \approx \frac{100^{100}\exp(-100)\sqrt{2... ...right)^{60}\left(\frac{5}{2}\right)^{40}\frac{1}{\sqrt{48\pi}}$$

Recommended reading:

• BPT pages 15 through 25 and pages 39 through 45.
• MSA pages 35 through 45