Finite Mathematics Lesson 6

Chapters 5.4 - 5.5

This may be a little harder.  I recommended writing out sample spaces by hand or even drawing pictures to help you see how to count.  

Counting
Counting is a general term that describes a method for counting objects in a set.  We may want to count the number of objects in a set or the numbers of ways the objects can be arranged.  We could also count the number of possible poker hands that could be dealt given a single deck of cards.   Many of these type of counting problems are much to difficult to use a trail and error approach.  Could you image actually trying to count out each possible hand of poker?.  Chapter 5 will explore different counting techniques.

Course Notes

Section 5.4   The Multiplication Principle

Generalized Multiplication Principle
Suppose a task consists of t operations perform consecutively.  Suppose OPERATION 1 can be performed in m₁ ; for each of these , OPERATION 2 can be performed in m₂ ; for each each of these, OPERATION 3 can be performed in m₃ ; and so forth.  The the task can be performed in   m₁ · m₂ · m₃ · · ·  m_t   ways. 

Example
A women has 4 blouses, 3 skirts and and 5 pairs of shoes.  Assuming the woman does not care what she looks like, how many different outfits can she wear?

• She has 4 × 3 × 5 = 60 different outfits.  

Example - A classic Problem
License plates for cars have to be unique. If a license plate contains 6 characters: 2 letters followed by 4 digits  i.e.  we2354  etc..

• There are 26 × 26 × 10 × 10 × 10 × 10 =  6,760,000 different plates.  

What if letters were allowed to repeated but numbers were not allowed to be repeated?

• 26 × 26 × 10 × 9 × 8 × 7 = 3,407,040 different plates

Example
Fred has 10 different pairs of shoes.  In how many ways can Fred put on a pair of shoes that do not match.

Let's look at this problem two ways....The first way is to count all the combinations. 

• Let's name each pair A, B, C, ...., J
• Every pair has a left and a right shoe.
• Assume we have to wear a left and a right.
• AA, BB, CC, DD, EE, FF, GG, HH, II, JJ
• Start the left shoe A, A can be paired with right shoes starting with B.  That means shoe  can be paired with 9 other left shoes.  
• Next take the left shoe B, it has already been paired with A so that means B can be paired with 8 remaining right shoes. C, D,...,J
• Continue this pattern until you reach the last shoe.

  Left Shoe	mismatching pairs	Right  Shoe	mismatching pairs
  A	9 other shoes	A	9 other shoes
  B	8	B	8
  C	7	C	7
  D	6	D	6
  E	5	E	5
  F	4	F	4
  G	3	G	3
  H	2	H	2
  I	1	I	1
  J	Already paired	J	Already paired
  Total	45		45
  There are 90 mismatching pairs.

The second way is much easier, but harder conceptionally. Apply the multiplication rule...

• Each pair can mate with 9 different pairs.
• Start the Pair AA, it can be paired with 9 other pairs excluding itself.
• Next  choose Pair BB, it can be paired with 9 other pairs. In this case, we don't get a repeat because there are 2 combinations for each pairing.  AB and BA are different mismatching pairs.
  
• There are 10 × 9  = 90 different mismatching pairs.

When you are ready, click here for the assignment for this section.

Section 5.5   Permutations and Combinations

• Permutation  P(n,r)   = the number of permutations of n objects taken r at a time.
  
  Example   Order is important when talking about permutations.  Lets say 3 people (Andy, Betty, and Clark) compete in a running race.  How many possible outcomes are there?  6 distinct outcomes

  1st Place	2nd Place	3rd Place
  Andy	Betty	Clark
  Andy	Clark	Betty
  Betty	Clark	Andy
  Betty	Andy	Clark
  Clark	Andy	Betty
  Clark	Betty	Andy

  Here,  order is very important (especially to the runners).

  If  awards (1st place and 2nd place) were given to the top 2 finishers,  how many different arrangements of awards could be given?  P(3,2) = 3(2) = 6
  

  Here is the formula.  P(n,r) = n(n - 1)(n - 2) ·   ·  · (n - r  + 1)
  The first number is the  total number of objects, n.
  The last number is 1 more than n - r

  • If you were to choose 3 objects from 10 possible choices (order being important)
    The first numbers 10 and the last number is 10 - 3 +1 = 7 +1 = 8
    P(10,3) = 10 · 9 · 8  =720

• Combination  C(n,r)   = the number of combinations of n objects taken r at a time.
  
  Example   Order is NOT important when talking about combinations.  Lets say 3 people (Andy, Betty, and Clark) compete in a running race.  Here are the possible outcomes. 

  1st Place	2nd Place	3rd Place
  Andy	Betty	Clark
  Andy	Clark	Betty
  Betty	Clark	Andy
  Betty	Andy	Clark
  Clark	Andy	Betty
  Clark	Betty	Andy

  This time the top 2 finishers go on to the final round,  how many different arrangements of finalists could be given? 

  Here is the formula. 

  

  Notice there are less possibilities when order is not considered. 
  If you were to choose 3 objects from 10 possible choices (order NOT important)
  

  These alternate forms for counting combinations and permutations are introduced in 5.7
  You can use them now,  I think the are easier to use.

  An alternate form for combinations	unordered
  	Notice  C(7,4) = C(7,3)  = 35 Why?

   

  An alternate form for permutations	ordered
  	Notice P(7,4) = 840 but P(7,3) = 210

  
  A final note:  Logically speaking, these are some of the hardest problems in the book.  Don't be afraid to ask questions.

When you are ready, click here for the assignment for this section.

Back to Top

• There are additional online tutorials at the books' web site. http://cw.prenhall.com/bookbind/pubbooks/goldstein3/ 

Please notify me of any errors on this page   joe@joemath.com