Printer-friendly versionPrinter-friendly version

Example

Maria has three tickets for a concert.  She'd like to use one of the tickets herself.  She could then offer the other two tickets to any of four friends (Ann, Beth, Chris, Dave).  How many ways can 2 people be selected from 4 to go to a concert?

Hmmm... could we solve this problem without creating a list of all of the possible outcomes?  That is, is there a formula that we could just pull out of our toolbox when faced with this type of problem?  Well, we want to find C, the number of unordered subsets of size r that can be selected from a set of n different objects.

We can determine a general formula for C by noting that there are two ways of finding the number of ordered subsets (note that that says ordered, not unordered):

(Method #1) We learned how to count the number of ordered subsets on the last page.  It is just nPr, the number of permutations of n objects taken r at a time.

(Method #2) Alternatively, we could take each of the C unordered subsets of size r and permute each of them to get the number of ordered subsets.  Because each of the subsets contains r objects, there are r! ways of permuting them.  Applying the Multiplication Principle then, there must be C × r! ordered subsets of size r taken from n objects.

Because we've just used two different methods to find the same thing, they better equal each other.  That is, it must be true that:

nPC × r!

Ahhh, we now have an equation that involves C, the quantity for which we are trying to find a formula.  It's straightforward algebra at this point.  Let's take a look.

Here's a formal definition.

Definition. The number of unordered subsets, called a combination of n objects taken r at a time, is:

\(_nC_r=\dbinom{n}{r}=\dfrac{n!}{r!(n-r)!}\)

We say “n choose r.”

The r represents the number of objects you'd like to select (without replacement and without regard to order) from the n objects you have.   

Example

Twelve (12) patients are available for use in a research study. Only seven (7) should be assigned to receive the study treatment. How many different subsets of seven patients can be selected?

Solution. The formula for the number of combinations of 12 objects taken 7 at a time tells us that there are:

\(\dbinom{12}{7}=\dfrac{12!}{7!(12-7)!}=792\)

different possible subsets of 7 patients that can be selected.

Example

Let's use a standard deck of cards containing 13 face values (Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, and King) and 4 different suits (Clubs, Diamonds, Hearts, and Spades) to play five-card poker.  If you are dealt five cards, what is the probability of getting a "full-house" hand containing three kings and two aces (KKKAA)?  

If you are dealt five cards, what is the probability of getting any full-house hand?

An Aside on Binomial Coefficients

The numbers:

\(\dbinom{n}{r}\)

are frequently called binomial coefficients, because they arise in the expansion of a binomial. Let's recall the expansion of (a+b)2 and (a+b)3.

Now, you might recall that, in general, the binomial expansion of (a+b)n is:

\((a+b)^n=\sum\limits_{r=0}^n \dbinom{n}{r} b^r a^{n-r}\)

Let's see if we can convince ourselves as to why this is true.

Now, you might want to entertain yourself by verifying that the formula given for the binomial expansion does indeed work for n = 2 and n = 3.