Topics in

P R E C A L C U L U S

Table of Contents | Home

PERMUTATIONS AND COMBINATIONS

Topic 23, Section 2 - Combinations

Section 1:  Permutations

Factorial representation of combinations

Combination problems

The sum of all combinations

In permutations, the order is all important -- we count abc as different from bca.  But in combinations we are concerned only that a, b, and c have been selected.  abc and bca are the same combination.

Here are all the combinations of abcd taken three at a time:

abc  abd  acd  bcd.

There are four such combinations.  We call this

The number of combinations of 4 things taken 3 at a time.

We will denote this number as  4C3.  In general,

nCk = The number of combinations of n things taken k at a time.

Now, how are the number of combinations  nCk  related to the number of permutations, nPk ?  To be specific, how are the combinations  4C3  related to the permutations  4P3?

Since the order does not matter in combinations, there are clearly fewer combinations than permutations.  The combinations are contained among the permutations -- they are a "subset" of the permutations.  Each of those four combinations, in fact, will give rise to 3! permutations:

abc   abd   acd   bcd
acb   adb   adc   bdc
bac   bad   cad   cbd
bca   bda   cda   cdb
cab   dab   dac   dbc
cba   dba   dca   dcb

Each column is the 3! permutations of that combination.  But they are all one combination -- because the order does not matter.  Hence there are 3! times as many permutations as combinations.   4C3 , therefore, will be  4P3 divided by 3! -- the number of permutations that each combination generates.

4C3   =  
 3!		   =   4· 3· 2
1· 2· 3

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

In general,  nCk  =  
 k!		 .
nCk   =   n(n − 1)(n − 2)·  ·  ·  to k factors
                      k!

Example 1.   How many combinations are there of 5 things taken 4 at a time?

   Solution.   5C4  =   5· 4· 3· 2
1· 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· 3
1· 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· 7
1· 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  =  nCn − k

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

Example 4.   Write out  nC3.

   Solution.   nC 3  =   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 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, n − k 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· 6
1· 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· 6
1· 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 14, 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,  m − j, times the lower index, j.

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

n − (k + 1) = n − k − 1

Therefore,

nCk + 1  =                 n!              
(n − k − 1)! (k + 1)!

Problem 7.

a)   Write all the combinations of abcd taken 1 at a time.

To see the answer, pass your mouse over the colored area.
To cover the answer again, click "Refresh" ("Reload").

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 8.

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 9.   You have 5 shirts, but you will select 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 10.   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 11.

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?   (n − k + 1)

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

*      *      *

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

Problem 12.   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 ?   1 

Problem 13.   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)!

Problem 14.   

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   =  nCn − k

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

The sum of all combinations

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

We will see that it is equal to 2n.

To analyze that sum, let us consider 4 distinct things -- a, b, c, d.  And suppose that we are going to either choose or not choose each one of them.  That is, without regard to order, in how many different ways could we choose either none of them, or any 1, or any 2, or any 3, or all 4?

That number will be the sum of all the combinations of 4 things.

To find that number, let us assign either Yes or No to each one.  

To a, then, there will be 2 possibilities.  After that has happened, b will have one of those 2 assignments.  After that, so will c, and after that so will d.  The total number of possible assignments of Yes or No, then, is

2· 2· 2· 2 = 24.

This is the total number of ways that we could choose any of those four letters.  The sum of all the combinations of 4 things is 24.

4C0 + 4C1 + 4C2 + 4C3 + 4C4   =   1 + 4 + 6 + 4 + 1
 
    =   16
 
    =   24.

In fact, here are these 16 possibilities:

a b c d
Yes Yes Yes Yes
 No  Yes Yes Yes
Yes  No  Yes Yes
Yes Yes  No  Yes
Yes Yes Yes  No 
 No   No  Yes Yes
 No  Yes  No  Yes
 No  Yes Yes  No 
Yes  No   No  Yes
Yes  No  Yes  No 
Yes Yes  No   No 
 No   No   No  Yes
 No   No  Yes  No 
 No  Yes  No   No 
Yes  No   No   No 
 No   No   No   No 

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

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

(Compare Problem 7, Lesson 25.)

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

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

Problem 16.

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.)

This 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, then how many
b)  possible ways are there to open the door?
a)  Assume that the same code may be repeated.

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


Table of Contents | Home

www.proyectosalonhogar.com