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
P(4,3) = 4 · 3 · 2 = 24
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
ABC 
ABD 
ACD 
BCD 
We say that there are 4 combinations of 4 objects taken 3 at a time, and write
C(4,3) = 4 .
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
C(N,1) = N 
, 
C(N,N) = 1 . 
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 parttime 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
P(6,3) = 6 · 5 · 4 = 120.
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
P(10,2) = 10 · 9 = 90 .
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
S = {a,b,c,d,e} .
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 NM of them; that is,
C(N,M) = C(N,N−M) .
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


