Permutations and Combinations
Section 2.4

 

The previous section covered selections of one item for each decision.  Now choices include more than one item selected with or without replacement.

With replacement means the same item can be chosen more than once.

Without replacement means the same item cannot be selected more than once.

Example 1: 

A PIN code at your bank is made up of 4 digits, with replacement.  (The same digit can be selected more than once)

        10 X 10 X 10 X 10 = 10,000 combinations are possible.

 

The PIN code is an example when order is important.  The PIN code 1234 is different from the PIN code 4321.

When selecting more than one item without replacement and order is important, it is called a Permutation.  When order is not important, it is called a Combination.

Example 2: 

There are 10 entries in a contest.  Only three will win, 1st, 2nd, or 3rd  prize.  What are the possible results? 

Order does matter and there is no replacement.

        10 X 9 X 8 = 720 possible outcomes

Or 720 permutations of 10 items chosen 3 at a time.

 

There is a formula for Permutations.  In the last example         

          10!       =   10!   = 720 
        (10 – 3)!     7!

            n!                 n = total number of items
        (n – r )!           r = number of chosen items

 

Represented by:       

         n Pr           P(r, n) ,            P n , r  

 

Example 3: 

A softball league has 7 teams, what are the possible ways of ranking the teams?

n = 7, r = 7                 

            7!        = 5040
         (7– 7)!                                     Recall 0! = 1

What happens if order is not important?

 

Example 4: 

From a group of 4 people, 3 are selected to form a committee.  How many combinations are there?            Abe, Bob, Carol, Dee.

 

If we use the previous formula: 

         4 !     =   24   
        (4-3)!

is too many.  

        ABC, ACD, BCD, ABD.

                                                 

 

 The formula for combinations is   

            n !        
         (n – r)!r!  

Is represented by   

        n Cr , C(r, n) , C ­n , r

                                                              

We divide by r! to reduce the number of combinations repeated since order is not important.

 

Exampel 5: 

A group of 12 women and 5 men are used to pick a committee of 6 people.  What is the possible outcomes if

a)     5 women and 1 man is selected

b)     any mixture of women and men

 

a)     From the FCP we know that two decisions will be made, choosing 5 women out of 12 and choosing 1 man out of 5.  Since order does not matter and there is no replacement, we use combinations.

           12!          X        5!      =   792 X 5 = 3,960   combinations
        (12-5)!5!          (5-1)!1!

 

b)     Any combination of men and women means only one choice or category is made, people.

 

          17!             =    17!      =   12,376
        (17-16)!6!          11!6!

 

Class exercise:         Find  n C r , for 

          5 C r,  n = 5                  4 C r ,  n = 4             

        3 C r ,  n = 3        2 C r ,  n = 2         1 C r ,  n = 1

 

R = 0               1                      1                                  1                      1                      1

R = 1               5                      4                                  3                      2

R = 2               10                    6                                  3                      1

R = 3               10                    4                                  1

R = 4               5                      1

R = 5               1

 

Pascal’s Triangle uses combinations to find coefficients.

 

Example 7: 

How many five-card hands containing exactly one pair are possible?


 

 

REVIEW for EXAM #2

 

9.0A

Exponentials and Logarithms: inverses of each other, irrational number e, using calculators, rewriting each in terms of the other.

9.0B

Properties of Logarithms: Inverse properties to solve equations, 3 rules of logs.

9.1

Exponential Growth: Average growth rate, exponential growth model, population, appreciation in real estate.

9.2

Exponential Decay: Exponential Decay model, carbon-dating, half-lifes, radioactive decay.

2.1

Sets and Set Operations:  Definitions, notation, empty set, Intersection, Union, Subsets.

2.3

Fundamental Principles of Counting, Combinations, Permutations: Combinatorics.  Tree diagrams, shortcuts, Factorials.

2.4

Permutations and Combinations: n P r , n C r .  Choosing without replacement, order matters, order does not matter.

 


Back to Counting and Probability Main Page

Back to the Survey of Math Ideas Home Page

Back to the Math Department Home Page

e-mail Questions and Suggestions