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 m1 ; for each of these , OPERATION 2 can be performed in m2 ; for each each of these, OPERATION 3 can be performed in m3 ; and so forth.  The the task can be performed in   m1 À m2 À m3 À À À  mt   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. 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. 