 Topics in

P R E C A L C U L U S

# PERMUTATIONS AND COMBINATIONS

Topic 24, Section 2 - Combinations

Section 1:  Permutations

If we have 10 letters abcdefgahij, then we have seen that the number of ways to rearrange -- permute -- any 4 of them is

10· 9· 8· 7

Say, however, that the order is not important. We care only that 4 particular letters -- begh, say -- have been selected. And it does not matter in which order they appear. That is, we will count all the permuatation of begh --

begh, egbh, gbeh, hebg, . . .

-- as one selection or combination.

Now, how are the combinations of 10 things taken 4 at a time related to its permutations?

Answer:  For any one combination -- begh -- there are its 4! permutations. But all of those permutations are one combination. In other words, there are 4! times as many permutations as combinations. Therefore, the number of combinations is equal to the number of permutations divided by 4!.

 Number of combinations = The number of permutations                    4! = 10· 9· 8· 71· 2· 3· 4 = 210.

This is The number of combinations -- or selections -- of 10 different things taken 4 at a time. We will denote it by the symbol  10C4.
 10C4 = 10· 9· 8· 71· 2· 3· 4

Notice:   The numerator and denominator have the same number of factors, 4, which is indicated by the lower index.  The numerator has 4 factors starting with the upper index and going down, while the denominator is 4 .

 In general,  nCk  = k .
 nCk = n(n − 1)(n − 2)·  ·  ·  to k factors                      k Example 1.   How many combinations are there of 5 distinct things taken 4 at a time?

 Solution.   5C4  = 5· 4· 3· 21· 2· 3· 4 =  5.

Again, both the numerator and denominator have the number of factors indicated by the lower index, which in this case is 4.  The numerator has four factors beginning with the upper index 5 and going backwards.  The denominator is 4 .

Example 2.   Evaluate  8C6.

 Solution.   8C6  = 8· 7· 6· 5· 4· 31· 2· 3· 4· 5· 6 =  28.

Both the numerator and denominator have 6 factors.  The entire denominator cancels into the numerator.  This will always be the case.

Example 3.   Evaluate  8C2.

 Solution.   8C2  = 8· 71· 2 =  28.

We see that  8C2 , the number of ways of taking 2 things from 8, is equal to 8C6 (Example 2), the number of ways of taking 8 minus 2, or 6.  For, the number of ways of taking 2, is the same as the number of ways of leaving 6 behind.

Always:

nCk =  nCnk

The bottom indices, k on the left and nk on the right, together add up to n.

Example 4.   Write out  nC3.

 Solution.   nC3  = n(n − 1)(n − 2)      1· 2· 3

The 3 factors in the numerator begin with n and go down.

Factorial representation

In terms of factorials, the number of selections -- combinations -- of n distinct things taken k at a time, can be represented as follows:

 nCk  = n (n − k) k This is  nPk divided by k . Compare line (1) of Section 1.

Notice:  In the denominator, nk and k together equal the numerator n.

Note also the convention that the factorial of the lower index, k, is written in the denominator on the right.

 Example 5.   8C3  = 8 5 3 .  (Note:  5 + 3 in the denominator equals 8 in    the numerator.
 Show that this is equal to 8· 7· 61· 2· 3 .

Solution.   5 is a factor of 8 , so it will cancel.

 8 5 3 = 8· 7· 6· 5 5 · 1· 2· 3 = 8· 7· 61· 2· 3 .

Example 6.   Write each of the following with factorials:  8C6 ,  8C2 .

 Solution.   8C6 = 8 2 6 .   8C2  = 8 6 2 .  But 2 6 is equal to 6 2 .

Therefore, we see that the number of ways of taking 6 things from 8, is the same as the number of ways of taking 2.

8C6  =  8C2

In general,

nCk  =  nCn − k

(See Problem 9, below.)

Example 7.   Write  8C0   with factorials.

 Solution.   8C0  = 8 8 0 .  Since 0 = 1, that fraction is equal to 1.  There is

only 1 way to take 0 things from 8.  This is the same as the number of ways of taking all 8.

Example 8.   Write  nCk + 1  with factorials.

Solution.   Let us look at the factorial form:

 mCj  = m (m − j) j The lower factorials are the difference of the indices,  mj, times the lower index, j.

Let us apply this to  nC k + 1.  The difference of the indices is

n − (k + 1) = nk − 1

Therefore,

 nCk + 1  = n (n − k − 1) (k + 1) a)   Write all the combinations of abcd taken 1 at a time.

a, b, c, d.

b) Write their combinations taken 2 at a time.

ab, ac, ad, bc, bd, cd.

c) Write their combinations taken 3 at a time.

abc, abd, acd, bcd.

d) Write their combinations taken 4 at a time.

abcd

Problem 2.

a)   There are 3 permutations of the letters rpt.  Those 3 permutations
a)   include how many  combinations of rpt?    One.

b)   rpt is one of the  5C3  combinations of pqrst.  Therefore, by how much

b)   must the  5P3  permutations of pqrst be reduced, in order to have

b)   only their 5C3  combinations?    By 3!.  5C3 = 5P3/3!.

*      *      *

 nCk = n(n − 1)(n − 2)·  ·  ·  to k factors                      k Problem 3.   You have 5 shirts, but you will take with you only 3 for your vacation.  In how many different ways can you do this?

5C3 = 10.  The order in which you select them does not matter.

Problem 4.   From a class of 12 students, 4 will be chosen to do a job.  In how many different ways could that happen?

12C4 = 495.  The order in which you choose them does not matter.

Problem 5.   Evaluate the following.

 a)   6C4 = 15 b)   5C3 = 10 c)   10C2 = 45 d)   10C8 = 45 e)   8C5 = 56 f)   8C3 = 56 g)   4C4 = 1 h)   4C0 = 1

Problem 6.

a)   Write out  nC4 .  Notice how the last factor in the numerator is
a)   related to the lower index.

 n(n − 1)(n − 2)(n − 3)         1· 2· 3· 4

b)   In the numerator of  nCk , what will be the last factor?   (nk + 1)

In part a) where k = 4, the last factor is (n − 3), and 3 is 4 − 1. In general then, the last factor will be [n − (k − 1)] = (nk + 1).
We could also see that by imagining that each of the k factors has the form (nj). In the first factor, j = 0. And in the kth, j = k − 1.

c)   In the numerator of  20Cm , what will be the last factor?   (21 − m)

*      *      *

 nCk  = n (n − k) k Problem 7.   Write the following with factorials.

 a)   uCv u!       (u − v)! v! b)   9C3 9!  6! 3! c)   9C6 9!  3! 6!
 d)   12C11 12!  1! 11! e)   12C12 12!  0! 12! f)   12C0 12!  12! 0!

Therefore, what number is 12C0 ?

Problem 8.   Write the following with factorials.

 a)   nCn − k n!      k! (n − k)! b)   n + 1Ck (n + 1)!     (n − k + 1)! k! c)   nCk − 1 n!             (n − k + 1)! (k − 1)! d)   n − 1Ck − 1 (n − 1)!     (n − k)! (k − 1)!

a)   In how many ways could you select three of these digits: 1, 2, 3, 4, 5 ?

5C3 = 10

b)   In how many ways could you not select two of them?

5C2 = 10

c)   Prove:   nCk   =  nCnk

 nCk  = n!      (n − k)! k! = n!      k! (n − k)! =  nCn − k

The sum of all combinations

What is the sum of all possible combinations of n distinct things?  That is, what is the sum of  nC0 + nC1 + nC2 + .  .   . + nCn?

We will see that the sum is equal to 2n.

For, consider any situation in which there are exactly two possibilities:  Succeed or Fail.  Yes or No.  In or Out.  Boy or Girl.  And so on.

Now suppose that we are going to make a choice between those two possibilities exactly n times.  To be specific, let n = 4.  And say that the choice will be between Yes or No.  Then upon choosing either Yes or No 4 times, one outcome might be

Yes No Yes Yes.

Another might be

No No No Yes.

Another might be

Yes No Yes No.

And so on.

Let us ask:  In how many of those outcomes will there be, for example, exactly 3 Yes's?

To answer, consider that there will be 4 positions to fill with either Yes or No.  In how many different ways, then, could we choose 3 positions to have a Yes?  It will be the combinatorial number 4C3 because the order will not matter.  (Compare Problem 4 above, which is choosing students for a job.  Here the "job" is to have a Yes )

Similarly, the number of outcomes with exactly 1 Yes will be 4C1; the number with 2 will be 4C2; while the number with no Yes's -- that is, all No's -- will be 4C0.

The sum of those combinatorial numbers will account for the total number of ways to choose between two things 4 times.

4C0 + 4C1 + 4C2 + 4C3 + 4C4.

What is that total number?  Consider that to each choice of either Yes or No, there will be 2 possibilities, obviously.  The first of the 4 choices can happen in 2 different ways.   After that has happened, the second choice can also happen in 2 different ways, and similarly with the third and fourth choices.  The total number of possible outcomes, then, is

2· 2· 2· 2 = 24.

The sum of all the combinations of 4 things is 24.

 4C0 + 4C1 + 4C2 + 4C3 + 4C4 = 1 + 4 + 6 + 4 + 1 (See Pascal's triangle, Topic 24) = 16 = 24.

There is exactly 1 way, 4C0, in which there are no Yes's, that is, all No's; 4 ways in which there is 1 Yes;  6 in which there are 2;  4 in which there are 3;  and 1 in which there are 4.

Each combinatorial number 4Ck signifies the number of times one of the two choices appears exactly k times.

That distribution of outcomes that consists of the sum of all possible combinations, is called a binomial distribution.  It is called that because, as we will see in the next topic, the combinatorial numbers are the binomial coefficients.

In general, the sum of all the combinations of n distinct things is 2n.

nC0 + nC1 + nC2 + .  .   . + nCn = 2n.

(Compare Problem 5, Topic 26.)

Problem 10.

a) If 5 children are born over the years, what is the total number of
a) possible boy-girl sequences?
a) For example, one sequence might be bgggb; another, gbbbb; and so on.

25 = 32.

b)  How many of those sequences will have 0 boys, how many 1 boy,
b)  how many 2, and so on?

1  5  10  10  5  1

These are the combinatorial numbers 5Ck. Their sum is 32.

There will be 1 with no boys, 5 with 1 boy, 10 with 2, 10 with 3, 5 with 4, and 1 with 5.

Problem 11.   Of all possible outcomes on tossing a coin 6 times, how many of them will have heads 4 times?

6C4 = 6C2 = 15.

Problem 12.   At Joe's Pizza Parlor, in addition to cheese there are 8 different toppings.  If you can order any number of those 8 toppings, then how many different toppings could you possibly order?

28 = 256.  For, this is the sum of all possible combinations: either no topping, or 1, or 2, and so on, up to 8.

Problem 13.

a)  A door can be opened only with a security code that consists of five
a)  buttons:  1, 2, 3, 4, 5.  A code consists of pressing any one button, or
a)  any two, or any three, or any four, or all five.
a)  How many possible codes are there?
a)  (You are to press all the buttons at once, so the order doesn't matter.)

There are 5C1 ways to press a code consisting of just one button; 5C2 ways of pressing a code consisting of two buttons; and so on. The number of possible codes, then, is the sum of all the combinations of 5 things -- except not taking any, 5C0, which is 1.  The sum of all those combinations, then, is 25 − 1 = 32 − 1 = 31.

b)  If, to open the door you must press three codes consecutively, then
b)  how many possible ways are there to open the door?
b)  Assume that the same code may be repeated.

According to part a), there are 31 ways to choose the first code. Again, 31 ways to choose the second, and 31 ways to choose the third. Therefore, the total number of ways to open the door is 313 = 29,791.

Section 1:  Permutations Next Topic:  The binomial theorem

Please make a donation to keep TheMathPage online.
Even \$1 will help.