Transcript Permutation, or Combination

Ch. 5: Counting
5.1: The Basics of Counting
• Intro Example #1: If we have a class of 6 math
majors and 7 CS majors (with no double
majors)
– A) In how many ways could we pick one
representative from the class?
– B) In how many ways could we pick 1 math and 1
CS major?
• Intro Example #2: If a class has 10 math and
13 CS majors, and 4 of these are joint majors,
how many are in the class?
Summary of Basic Counting
Techniques
• Ex 1A uses the SUM rule
• 6+7=13
• Ex 1B uses the PRODUCT rule
• 6*7=42
• Ex 2 uses INCLUSION/EXCLUSION
• 10+13-4=19
Multiplication Problems
1.
At a restaurant, you have a choice of main dish (beef, chicken,
fish, vegetarian), vegetable (broccoli, corn), potato (baked, fries),
and dessert (chocolate, strawberry). LIST all possible choices.
2.
A teacher wishes to make all possible different answer keys to a
multiple choice quiz. How many possible different answer keys
could there be if there are 3 questions that each have 4 choices
(A,B,C,D). LIST them all.
3.
What if there were 20 multiple choice questions with 5 choices
each? Explain (don’t list).
4.
With 9 baseball players on a team, how many different batting
orders exist?
Answers
1.
At a restaurant, you have a choice of main dish (beef, chicken,
fish, vegetarian), vegetable (broccoli, corn), potato (baked, fries),
and dessert (chocolate, strawberry). LIST all possible choices.
main
Beef
Beef
Beef
…
4*2*2*2=32
vegetable
potato
dessert
broc
broc
broc
baked
baked
fries
chocolate
strawb
chocolate
Answers
2.
A teacher wishes to make all possible different
answer keys to a multiple choice quiz. How many
possible different answer keys could there be if there
are 3 questions that each have 4 choices
(A,B,C,D). LIST them all.
4*4*4=64
3.
What if there were 20 multiple choice questions
with 5 choices each? Explain (don’t list). 5^20
4.
With 9 baseball players on a team, how many
different batting orders exist? 9! = 362,880
Permutation Examples
1. If there are 4 people in the math club (Anne,
Bob, Cindy, Dave), and we wish to elect a
president and vice-president, LIST all of the
different ways that this is possible.
2. From these 4 people (Anne, Bob, Cindy,
Dave), we wish to elect a president, vicepresident, and treasurer. LIST all of the
different ways that this is possible.
Answers
1. If there are 4 people in the math club (Anne,
Bob, Cindy, Dave), and we wish to elect a
president and vice-president, LIST all of the
different ways that this is possible.
AB
BA
CA
DA
AC
BC
CB
DB
AD
BD
CD
DC
4*3=12
or 4P2 = 12
Answers
2. From these 4 people (Anne, Bob, Cindy,
Dave), we wish to elect a president, vicepresident, and treasurer. LIST all of the
different ways that this is possible.
ABC
ABD…
•
A
B
C
D
•
B
A
C
D
•
C
A
B
A
•
D
A
B
C
4*3*2 = 24 outcomes
Or 4P3 = 24
C
D
B
D
A
C
C
D
A
D
A
C
B
D
A
D
B
C
B
C
A
C
A
B
ABC
ABD
ACB
ACD
BDA
BDC
BAC
BCD
BCA
BCD
BDA
BDC
CAB
CAD
CBA
CBD
DAB
DAC
DAB
DAC
DBA
DBC
DCA
DCB
Combination Examples
1. If there are 4 people in the math club (Anne,
Bob, Cindy, Dave), and 2 will be selected to
attend the national math conference. LIST all
of the different ways that this is possible.
2. From these 4 people (Anne, Bob, Cindy,
Dave), and 3 will be selected to attend the
national math conference. LIST all of the
different ways that this is possible.
Combination answers
1. If there are 4 people in the math club (Anne,
Bob, Cindy, Dave), and 2 will be selected to
attend the national math conference. LIST all
of the different ways that this is possible.
AB
AC
BC
AD
BD
CD
4C2= 6
Combination answer
2. From these 4 people (Anne, Bob, Cindy,
Dave), and 3 will be selected to attend the
national math conference. LIST all of the
different ways that this is possible.
ABC BCD
ABD
ACD
4C3 = 4
Permutations and Combinations
• Permutations
– Use when ORDER matters and NO repitition
– nPr = n!/(n-r)!
– Example: If 10 people join a club, how many ways
could we pick pres and vp? 10P2 = 90
• Combinations
– Use: ORDER does NOT matter and NO repitition
– nCr = n!/ [(n-r)!r!]
– Example: 10 people join a club. In how many ways
could we pick 2? 10C2 = 45
Multiplication, Permutation, or
Combination?
1. With 14 players on a team, how many ways could we pick a
batting order of 11?
2.
If license plates have 3 letters and then 4 numbers, how
many different license plates exist?
3.
How many different four-letter radio station call letters can
be formed if the first letter must be W or K?
4.
A social security number contains nine digits. How many
different ones can be formed?
5.
If you wish to arrange your 7 favorite books on a shelf, how
many different ways can this be done?
6. If you have 10 favorite books, but only have room for
7 books on the shelf, how many ways can you arrange
them?
7. You wish to arrange 12 of your favorite
photographs on a mantel. How many ways can this be
done?
8. You have 20 favorite photographs and wish to
arrange 12 of them on a mantel. How many ways can
that be done?
9. You take a multiple choice test with 12 questions (and
each can be answered A B C D E). How many different
ways could you answer the test?
10. If you had 13 pizza toppings, how many ways could
you pick 5 of them?
Answers
1. 14P11
6. 10P7
2. 26*26*26*10*10*10*10
7. 12! or 12P12
3. 2*26*26*26
8.
4. 10^9
9. 5^12
5. 7! Or 7P7
10. 13 C5
20P12
Review- which method do we use
with …
•
•
•
•
Order matters, repetition allowed
Order matters, repetition NOT allowed
Order DOESN’T matter, repetition allowed
Order DOESN’T matter, repetition NOT
allowed
Answers
• Order matters, repetition allowed
– Multiplication Rule
– Ex: Social Security numbers
• Order matters, repetition NOT allowed
– Permutations: P(n,r)= n!/(n-r)!
– Ex: number of ways to pick 1st, 2nd, 3rd from 30
• Order DOESN’T matter, repetition allowed
– ??? See section 5.5
• Order DOESN’T matter, repetition NOT allowed
– Combinations: C(n,r)= n!/ [(n-r)!*r!]
– Ex: number of ways to pick a committee of 3 from 30
Harder problems- if time
1. How many bit strings (0s and 1s) are there are
length 5?
2. How many license plates exist if repetition is
allowed and they can be 3 letters, 3 digits OR
3 letters, 4 digits?
3. In how many ways can a photographer
arrange 8 people in a row from a group of 12?
If the bride must be in the picture?
If both the bride and groom must be in the picture?
More examples
4. How many passwords exist with 6 letters (and
no restrictions)?
5. How many 6 letter passwords exist if:
There is no repetition allowed?
All are consonants, and repetition is allowed?
There is exactly one vowel?
There is at least one vowel? (use the COMPLEMENT
RULE here)
6. How many vanity plates are there with 4 to 7
characters (letters or digits) with at least 1
digit
answer
1. 2^5
2. 26^3*10^3 + 26^3*10^4 =193,336,000
3. 12*11*10*9*8*7*6*5=19,958,400
8*11P7=8*1,663,200=13,305,600
8*7*10P6=8,467,200
4.26^6
26P6
21^6
6*5*21^5
26^6-21^6
Review of complement rule: |E|=total = |E complement|
5. uses product, sum, and complement rule
(36^4-26^4)+(36^5-26^5)+(36^6-26^6)+ (36^7-26^7) =
550,466,822,600
More complicated 5.3 problems
• Next class