A Counting Tutorial: Part 4

A combination is a collection of distinguishable objects. Examples of a combination are poker hand drawn from a deck of cards, a trawler's catch on a given day and a handful of tickets taken from a lottery barrel.

In each example, order among the elements within the combination is not important. For rearranging the cards in a poker hand will not yield a different hand nor will a rearranging the fishes in the trawler's net change the results of the catch. In summary, when order is not important within a collection, the collection is a combination.

Recall the defining attribute of a permutation. A change in the order of its elements yields a different permutation.

So, how does one distinguish a permutation from a combination?

Consider the following.
Condition 1: A teacher selected Joe, Joanne, Mary and Sam from the class. The collection: Joe, Joanne, Mary, Sam is a combination.

Condition 2: A teacher selects four students from the class to form an organizing committee for an upcoming field trip. She selects the committee chairman, the vice-chair, the secretary, and the treasurer of the committee in that order. The chosen collection is a permutation because the order of their selections conferred influence. Generally, a rearrangement of the committee officers yields a different functioning committee.

This tutorial discusses combinations selected from a collection of n elements. We are interested in the number of ways to select a combination of a given size from a larger collection of objects. Of course, the size of the combination cannot be larger than the size of the collection from whence the combination is selected. We admit the possibility of selecting a combination with zero elements. There is only one way to select such a combination namely, make no selection. Let's formalize the above.

The number of ways of selecting a combination of r elements from a collection of n elements is demoted by C(n,r) where (r; 0 ≤ r ≤ n). It is evaluated by the formula

C(n,r) = n! / [ r! • (n-r)!]

We set C(n,0)=1. And there is only one way to select all n elements from a collection of n elements, so set C(n,n)=1.

The symbol C(n,r) is read " a combination of n things taken r at a time ".

How does one evaluate this expression?
As an example, consider C(5,3).

C(5,3)=5!/[3!• (5-3)!} =5!/[3!• 2!] = (5• 4• 3• 2• 1)/[(3• 2• 1)(2• 1)] = 5• 4/[2• 1] = 10

Note the 3! in the denominator cancels the 3! in the numerator. A similar situation always exist when evaluating C(n,r).

To illustrate, consider C(50,6)

C(50,6)=50!/[6!• 44!]= 50• 49• 48• 47• 46• 45• 44!/[6!• 44!]=50• 49• 48• 47• 46• 45/[6• 5• 4• 3• 2• 1]=50• 49• 47• 46• 3/1=15,890,700

Note the 44! in the numerator and denominator cancels.

When evaluating C(n,r), one needs only evaluate a product of r numbers in the numerator, namely the product of the integers from n to (n-r+1), then divide r!.

In our example of n=50 and r=6, the product in the numerator is 50• 49• 48• 47• 46• 45 . The product in the denominator is 6• 5• 4• 3• 2• 1. To further simplify the calculation, divide out all factors common to the numerator and the denominator.

Interpret C(50,6)

C(50,6) is the number of ways of selecting 6 distinguishable objects from a collection of 50 distinguishable objects. In a lottery in which 6 numbers are selected from 50 numbers, 15,890,700 possible selections are possible. Thus the chance of having the winning six numbers is pretty small.

How does the formula come about?
To gain insight into this formula, we answer the question,

"How many different poker hands are in a poker deck?" The answer demonstrates the general situation.

(*) Place the 52 cards of a poker deck side by side on a line. Select any five cards and place the symbol, 1, under them. Place the symbol, 0, under the remaining cards. The five "ones" identify the selected poker hand. Now place the five "ones" under a different set of five cards. A different poker hand is identified. So placing the five ones under five cards identifies different poker hands in the deck.

Thus the number of different poker hands in the deck is the same as the number of ways one can arrange the five ones and the 47 zeros under the cards. From a previous tutorial, it is which is C(52,5).

One can use this insight to prove the validity of the formula.

The technique in the paragraph headed by (*) can be used in many other situations. The reader should remember it to use in other counting situations.

Example: Let's consider another example to illustrate the value of combinations in counting. Daniel Bernoulli discussed this situation in 1786.

On a given date, 2m individuals constitute m married couples. Assume each individual's survival is independent of the others and each has the same probability of being alive on a given future date. If a individuals are alive on the future date, how many couple should one expect to have survive to that date?

Since all the couples have the same chance of survival, we single out a particular couple and compute its chance of survival. Then we alter this answer to include all couples.

The number of ways to select a individuals to be alive on the future date is the same as the number of ways of selecting a combination of a individuals from the 2m individuals, namely C(2m,a).

Among these ways, the number of ways the special couple will be alive with (a-2) others is C(2m-2,a-2). To get this result, count the number of ways to select (a-2) individuals from the remaining 2m-2 to pair with the particular couple.

Since all couples have an equal chance of surviving, the chance that the particular couple will be alive on the given date is C(2m-2,a-2)/C(2m,a).

Since there are m couples. We expect C(2m-2,a-2)/C(2m,a) percent of m to be alive on the given date. This evaluates to a(a-1)/(4m-2).

Starting with m =1 00 couples. One should expect about 89• 88/(2• 199) = 20 couples to survive when 89 individuals are alive on the future date.

Some Counting Problems.
A poker deck has 52 cards and there are 13 hearts.

1. How many ways can a 9-card hand be selected for a poker deck?

2. How many ways can a 9-card hand be selected without having any hearts?

3. What percentage of the 9-card hands are free of hearts?

Thought Question: Do you think this is a large percent?

4. What percentage of the 9-card hands will have one heart, one spade and one ace?