Transcript Combinatorics - The Copa Room

Combinatorics
CSLU 1100.003
Fall 2007
Cameron McInally
[email protected]
Fordham University
Combinatorics
• Counting
– Figuring out how many.
– This can be a bit confusing.
– The best way to learn it? Practice problems!
Combinatorics
• Common Sense
– “If there are 10 boys and 12 girls in a class, how
many people are there altogether?”
10 + 12 = 22
Combinatorics
• Common Sense
– “If a car dealership sells 3 different models of cars
and offers them in 4 different colors, how many
different ways can you purchase a car?”
3 * 4 = 12
Combinatorics
• A little more difficult
– “If a New York State license plate consists of 3
letters followed by 4 numbers, how many different
license plate possibilities are there?”
26 * 26 * 26 * 10 * 10 * 10 * 10
= 263 * 104
= 175760000
Combinatorics
• Counting
– When counting possible outcomes, we may wish
to combine terms. We can combine terms using
And or Or.
Combinatorics
• And
– If terms combine with “AND” then you multiply
the numbers.
– Example: Pick one letter and one number
between 0 and 9. How many possible
combinations are there?
26 *10  260
Combinatorics
• Or
– If terms combine with “OR” then you add the
numbers.
– Example: Pick one letter or one number between
0 and 9. How many possible combinations are
there?
26 10  36
Combinatorics
• The counting process considers the number of
different ways you can select items from a
group of items.
• There are 4 types of groups we can select
from: (Note: Memorize the definition of each and your life will be much easier!!!)
– Unordered List
– Ordered List
– Set
– Permutation
Combinatorics
• Permutation
– An ordered list of elements. We CANNOT have
duplicates. We DO care about the order of
elements in a set.
– If the list is of size n and we want to know how
many ways we can select r elements…
n!
P(n,r) 
(n  r )!
Combinatorics
• Permutation Example
– We have 6 unique Xbox games. We let 6 friends
F={f0,f1,f2,f3,f4,f5} each borrow 1 game. How many
different ways can we distribute the 6 games to 6
friends?
6!
P(6,6) 
(6  6)!
6!

0!
 6!
 120
Combinatorics
• Ordered List
– An ordered list of elements. We CAN have
duplicates. We DO care about the order of
elements in a set.
– If the list is of size n and we want to know how
many ways we can select r elements…
n
r
Combinatorics
• Ordered List Example
– How many numbers are there between 0 and 999,
inclusive? That is to say, how many permutations
of three digits exist, if each digit is between 0 and
9?
1000  1000
1
Combinatorics
• Set
– It’s a set. We CANNOT have duplicates. We DO
NOT care about the order of elements in a set.
– If the list is of size n and we want to know how
many ways we can select r elements…
P(n, r )
C(n,r) 
r!
Combinatorics
• Set Example
– We have 9 friends on MySpace. We want to fill our
top 8 spots. How many different combinations of
8 friends can we picks?
C (9,8)
C (9,8) 
8!
9!

8!(9  8)!
9!

8!*1!
9
Combinatorics
• Unordered List
– Kind of like a set. We CAN have duplicates. We DO
NOT care about the order of elements in a set.
– If the list is of size n and we want to know how
many ways we can select r elements…
P(n  r  1, r )
C(n  r  1,r) 
r!
Combinatorics
• Unordered List Example
– There are 5 different colors of iPod nanos. We
want to buy two. How many different
combinations of colors could we pick?
P (5  2  1,2)
C( 5  2  1,2 ) 
2!
P (6,2)

2!
6!

2!*4!
 15
Combinatorics
• A quick reference
Does Order Matter?
Are
Repetitions
Allowed?
Yes
No
Yes
Ordered
List
Unordered
List
No
Permutation
Set
Combinatorics
• Permutation Practice Problem
– There are 3 horses running in a race. What are the
possible outcomes of the horse race.
{123,132,213,231,312,321}
– So, there are 6 possible outcomes and…
3!
P (3,3) 
(3  3)!
 3!  3 * 2 *1
6
Combinatorics
• Ordered List Practice Problem
– We have 3 bits. Each bit can have either the value
0 or 1. How many unique 3 digit strings can we
have?
{000,001,010,011,100,101,110,111}
– So, there are 8 possible outcomes and…
2 8
3
Combinatorics
• Set Practice Problem
– We have 3 lamps and 2 electric sockets. How
many different ways can we light 2 lamps?
{011,101,110}
– So, there are 3 possible outcomes and…
C (3,2) 
3!

2!(1)!
6
 3
2
P (3,2)
2!
Combinatorics
• Unordered Practice Problem
– There are three different brands of beer at a bar.
You want to buy 2 beers. How many ways can you
buy 2 beers?
{ab,ac,bc,aa,bb,cc}
– So, there are 6 possible outcomes and…
C (3  2  1,2) 
P(3  2  1,2)
2!
(3  2  1)!

2!(3  2  1  2)!
4!

6
2!*2!
Combinatorics
Homework
(Always Due in One Week)
• Read Section 5.1, 5.2. Skim Section 5.3.
• Complete Section 5.1 pages 382 :
4 (a - e)
• Complete Section 5.2 pages 395-396 :
1 (a,b), 3 (a,b), 9 (a,b)
• Solve the “Towers of Hanoi” problem for n = 1 through 4, page
420. Write out each step! Approximately how many moves
would it take to solve this for n = 64?