2C  Combinations

Suppose that Alice, Betty, Cindy, and Dianne have their own private outdoors club, and that they need to select a president, a secretary, and a treasurer. This problem is a permutation one; they have to fill a president slot, then a secretary slot, and finally a treasurer slot. As no woman would wish to hold two of these jobs, the three choices must be different. They have 4 choices for president, then 3 for secretary, and 2 for treasurer, for a total of

ways of selecting officers.

To demonstrate a point, we list all 24 possibilities:

ABC	ABD	ACD	BCD
ACB	ADB	ADC	BDC
BAC	BAD	CAD	CBD
BCA	BDA	CDA	CDB
CAB	DAB	DAC	DBC
CBA	DBA	DCA	DCB

In each group of three, the first letter refers to the President, the second to the secretary, and the third to the treasurer. Note that in the first column we have listed all the permutations with A, B, and C as officers. In the second column A, B, and D are officers, in the third A, C, and D are officers, and in the fourth column B, C, and D are officers.

Next we consider a somewhat modified problem. We suppose that the four women will choose not officers but only an executive committee, consisting of three members of equal status. The difference here is that the order of the choosing makes no difference - for example, the listings ABC and ACB give exactly the same committee of three women. In fact, the six listings in the first column above refer to the same committee consisting of Alice, Betty, and Cindy. Likewise the six listings in the second column refer to only one committee, as do the six listings in the third column and the six listings in the fourth column. Altogether there are only four possible committees of three people, which we may list as

We say that there are 4 combinations of 4 objects taken 3 at a time, and write

Observe that the number of ways of selecting 3 officers is 6 times as large as the number of ways of selecting a committee of 3. The factor 6 is just 3!, the number of permutations of 3 objects. For the listing ABC in the committee list, there are 6 listings in the first column of the officer list, corresponding to the number of ways of permuting the letters A, B, C. Likewise, for each of the other listings in the committee list there correspond six listings in the officer list. The relation between C(4,3) and P(4,3) then is

Now we discuss combinations in general. We have N objects, and we wish to choose M objects from these N objects without regard to order. We will not order the M objects - we will just choose them and give them all equal status, without distinguishing one from another. Any single way of doing this is called a combination. The number of ways of doing this is denoted with the notation C(N,M). We say that C(N,M) is the number of combinations of N objects taken M at a time. We calculate C(N,M) with the formula

.

This relation holds because, as the preceding example shows, when choosing M objects from N objects there are M! as many permutations as there are combinations. In a permutation the objects are ordered, but in a combination they are not. The number of ways of ordering M objects is M!, so you get M! times as many permutations as you get combinations. Each combination corresponds to one whole column in the permutation list, whereas each column in the permutation list has M! entries.

Of course, now that we have the formula we do not need to write down any lists to compute C(N,M). Here are a few examples:

	,		,
	,		.

The last two examples illustrate the general formulas

These formulas are easy to remember if you just recall what they mean. The expression C(N,1) denotes the number of ways of choosing 1 object from N objects - obviously N ways because you have N choices. On the other hand, C(N,N) is the number of ways of choosing N objects from N objects without ordering them - since you have to choose all the objects there is only one way. (But if you order the objects after choosing them, the number of ways becomes P(N,N) = N!)

Newcomers to counting techniques very often have trouble deciding whether a problem involves permutations or combinations. Remember, if you order or distinguish the choices it is a permutation, but if you treat all choices equally without ordering them or distinguishing between them, it is a combination.

example 1

Six young women have applied for a part-time job at Miguel's Restaurant. How many ways can Miguel choose

(a)  a cook, a dishwasher, and a cashier?

(b)  three waitresses?

In part (a) the three choices will be ordered, so we are dealing with permutations; the number of ways is

In part (b) the three choices have equal status as waitresses, with no distinction between them, so we are counting combinations; the number of ways now becomes

example 2

A basketball team has 10 players. How many ways can the coach select

(a)  5 players to start the game?

(b)  2 starting guards?

(c)  a starting center?

(d)  a starting center and a backup center?

In parts (a), (b), and (c) the choices are not being ordered, so we are dealing with combinations; the three respective answers are

C(10,1) = 10  .

In (d) the two choices are distinguished from one another, so we are counting permutations; the number of ways is

example 3

From a standard deck of 52 playing cards, how many ways can you choose

(a)  a poker hand of 5 cards?

(b)  5 clubs?

(c)  2 aces?

(d)  4 queens?

These questions all involve combinations, as order in a hand of cards makes no difference. In (a) we select 5 cards from 52; the number of combinations is

In (b) we restrict the choices to clubs, limiting the number of available cards to 13; the number of ways to choose 5 of 13 clubs from the deck is

In (c) we select 2 aces from 4 available aces, and in (d) we select 4 queens from only 4 queens; the respective answers are

,

C(4,4) = 1

.

example 4

A business meeting has 9 participants. If everyone at the meeting shakes hands with each other person once, how many handshakes are there?

You have to look at this question the right way. When two people shake hands, you can think of them as forming a temporary “handshaking committee”. The total number of handshakes will be the same as the number of ways of forming a committee of 2 people from 9 people. As the 2 choices are not ordered, we are counting combinations; thus the number of handshakes is

example 5

A set has 5 elements. How many subsets of the set are there consisting of

(a)  2 elements

(a)  3 elements?

To be specific, let us suppose the set is

In (a) we must count the number of ways of selecting 2 elements from 5 elements to form a subset. As the order of listing of elements in a subset does not matter - for example, {a,b} = {b,a} - we are counting the number of combinations of 5 elements taken 2 at a time; we get

In (b) we select 3 objects from 5, so the calculation changes to

An alert student might notice that the two answers in the preceding example are the same - is that only a coincidence? Think of it this way - when we select 2 elements for a subset from a set of 5 elements, we are at the same time selecting 3 elements not to be in that subset. Thus the number of ways of selecting a subset of 2 elements is the same as the number of ways of selecting 3 elements for another subset - the chosen subset's complement.

More generally, if you begin with N objects, then the number of ways of choosing M of these objects is the same as the number of ways of choosing N-M of them; that is,

For instance, suppose we want to count the number of possible committees of 6 people chosen from a club of 8 people. Instead of calculating C(8,6), it is easier to calculate C(8,2), the number of ways of leaving 2 people off the committee. We get

EXERCISES 2C

1. A set has 20 elements. How many 2-element subsets does the set have? How many 18-element subsets does it have?
   
   
2. A club has 100 members. How many ways can the club form a committee of
   (a)  3 members?      (b)  97 members?      (c)  100 members?      (d)  1 member?
   
   
3. A Waianae farmer has 6 horses. How many ways can he choose 3 horses to march in the Kamehameha Day parade?
   
   
4. There are 11 cats living on Mr. Yau's block. If every cat gets into a fight with each other cat once during the night, how many catfights are there?
   
   
5. A singing class has 8 students. How many ways can the teacher choose
   1. one student to sing a solo?
   2. two students to sing a duet?
   3. three students to sing a trio?
   4. one student to sing, another to hold the music, and a third to play the piano?

The Wahine cross country team has 4 freshmen, 2 sophomores, 4 juniors, and 3 seniors. How many ways can the coach choose 6 runners to race on the mainland? 3 freshmen to enter a freshmen meet? 4 runners and line them up for a publicity picture? 1 runner from each class to visit a high school? 2 senior co-captains? 1 senior co-captain and 1 junior co-captain?

7. A history test has 7 questions, and you must answer 4 out of 7.
   1. How many ways can you choose which 4 questions to answer?
   2. How many ways can you choose which 3 questions not to answer?
   3. How many ways can you choose a question to answer first, a question to answer second, a question to answer third, and a question to answer fourth?
   
   
8. From a jury pool of 17 citizens, how many ways can 12 jurors be chosen?
   
   

From a deck of 52 cards, how many ways can you choose 3 face cards? 2 black cards? a rummy hand of 6 cards? 3 jacks? 5 aces?

10. Mr. Dela Cruz, madly in love with his wife, has 15 nice photos of her. How many ways can he choose
    1. 3 photos to place on his office desk?
    2. one photo to carry in his wallet, another to place on his desk, and a third to hang from the rear view mirror in his car?
    
    
    
11. In the Miss Chinatown Hawaii pageant, there are 12 semifinalists.
    1. From the 12 semifinalists, how many ways can 5 finalists be chosen?
    2. From the 5 finalists, how many ways can a winner, a first runner-up, and a second runner-up be chosen?
    3. How many ways can the winner and two runner-ups be lined up for a picture?
    4. How many ways can the winner and two runner-ups be lined up for a picture, with the winner in the middle?
    5. From the 5 finalists, how many ways can a winner, a first runner-up, and a second runner-up be chosen and then lined up for a picture with the winner in the middle?
       
       
12. How many ways can Janet select 3 of her 8 business suits to pack for a trip?
    
    
13. In a race of 13 horses, how many ways can you bet one horse to win, a second horse to place, and a third to show?

At a dinner party of 6 people, someone has just proposed a toast. If everyone clinks everyone else's wine glass and if you listen carefully, how many clinks will you hear?

15. Sylvia and Raymond will be getting married next June. How many ways can they choose
    
    
    1. 2 of Sylvia's 5 sisters to serve as bridesmaids?
    2. one of Raymond's 6 brothers to serve as best man, and a second to serve as head usher?
    3. 4 of their 11 siblings to serve refreshments at the reception?
    4. 3 of Sylvia's sisters or 3 of Raymond's brothers to sing the wedding song as a trio?
    5. one sister to sing solo, or 2 brothers to sing as a duet, or 3 sisters to sing as a trio, or 4 brothers to sing as a quartet?