Counting Subsets of a Set: Combinations

Consider the question: Suppose five members of a group of twelve are to be chosen to work as a team on a special project. How many distinct five-person teams can be selected? This question is a special case of the more general question: Given a set S with n elements, how many subsets of size r can be chosen form S? Here each subset of size r is called an r-combination of the set.

Definition

Let n and r be nonnegative integers with r £ n. An r-combination of a set of n elements is a subset of r of the n elements. The symbol n choose r, read "n choose r," denotes the number of subsets of size r (r-combinations) that can be chosen from a set of n elements.

There are two distinct methods that can be used to select r objects from a set of n elements. In an ordered selection, it is not only what elements are chosen but also the order in which they are chosen that matters. Two ordered selections are said to be the same if the elements chosen are the same and also if the elements are chosen in the same order. An ordered selection of r elements from a set of n elements is an r-permutation of the set. In an unordered selection, on the other hand, it is only the identity of the chosen elements that matters. Two unordered selections are said to be the same if they consist of the same elements, regardless of the order in which the elements are chosen. An unordered selection of r elements from a set of n elements is the same as a subset of size r or an r-combination of the set.

Theorem 6.4.1

The number of subsets of size r (r-combinations) that can be chosen from a set of n elements, n choose r, is given by the formula

n choose r equation

or equivalently,

n choose r equation

where n and r are nonnegative integers with r £ n.

So to answer our original question: Suppose five members of a group of twelve are to be chosen to work as a team on a special project. How many distinct five-person teams can be selected? 12 choose 5 is
12! / (5!(12 – 5)! = (12(11)(10)(9)(8)(7!)) / (5(4)(3)(2)(7!)) = 11(9)(8) = 792.

Now suppose two members of the group, Jack and Jill, insist on working together as a pair or not at all (John can’t be with Jill or Jack gets jealous likewise if Janice works with Jack). How many five-person teams can be formed with Jack and Jill either on a team or not on a team?

Solution: Because a team that contains both Jack and Jill contains exactly three other people from the remaining ten in the group, there are as many such teams as there are subsets of three people that can be chosen from the remaining ten. That is ten choose 3 or 120. Because a team that doesn’t contain the Jack and Jill combination has exactly 5 members chosen from the remaining ten, there are ten choose 5 or 252 different teams without the pair. By the addition rule there is a total of 372 possible satisfactory combinations this week (subject to change as neither John nor Janice is jealous).

1 week later…

Now suppose that Jack and Jill have recently broken up and refuse to work together. How many satisfactory teams can be formed?

We look at the number of teams that contain Jack and not Jill, the number of teams that contain Jill and not Jack, and the number of teams that contain neither Jack nor Jill. Because any team that contains one but not the other has exactly 4 other people from the remaining ten in the group, the first two conditions lead to groups of size ten choose 4 or 210. The third condition is again, ten choose 5 or 252.
So by the addition rule, there are 210 + 210 + 252 = 672 satisfactory teams, this week. An alternative approach is to consider the set difference of the total number of teams of five and the number of teams that contain both Jack and Jill, twelve choose 5 minus ten choose 3 = 792 – 120 = 672.

Example 6.4.9 Poker Hand Problems

  1. How many five-card poker hands contain two pairs?
  2. If a five-card hand is dealt at random from an ordinary deck of cards, what is the probability that the hand contains two pairs?

Solution

  1. Consider forming a hand with two pairs as a four-step process.
    1. Choose the two denominations for the pairs.
      13 choose 2 = 78.
    2. Choose two cards from the smaller denomination.
      4 choose 2 = 6.
    3. Choose two cards from the larger denomination.
      4 choose 2 = 6.
    4. Choose one card from those remaining.
      44 choose 1 = 44, careful here not to double count the eight cards in the two chosen denominations, 52 – 8 = 44.

E = 78(6)(6)(44) = 123,552.

  1. The total number of five-card hands from an ordinary deck of cards is 52 choose 5 = 52! / (5!(52 – 5)!) = 2,598,960. If all hands are equally likely, the probability of obtaining a hand with two pairs is |E| / |S| = 123,552 / 2,598,960 @ 4.75%.

In counting it helps to imagine the objects you are to count. If you can imagine the elements to be counted as being obtained through a multistep process (each step is performed a fixed number of ways regardless of how preceding steps were performed), then you can use the multiplication rule. The total number of elements is the product of the number of ways to perform each step. If you can imagine the set of elements to be counted as being broken up into disjoint subsets, then you can use the addition rule. The total number of elements in the set is the sum of the number of elements in each subset. In either case special effort is required to avoid double counting errors.

Some additional links:
http://regentsprep.org/Regents/math/combin/Lcomb.htm
http://regentsprep.org/Regents/math/combin/excomb.htm