Transcript Elementary Counting Techniques & Combinatorics

Elementary Counting
Techniques & Combinatorics
Jim Skon
Consider:
 How many license plates are possible with
3 letters followed by 3 digits?
 How many license plates are possible with
3 letters followed by 3 digits if no letter
repeated?
 How many different ways can we chose
from 4 colors and paint 6 rooms?
Consider
 How many different orders may 9 people be
arranged in a line?
 How many ways can I return your quizzes
so that no one gets their own?
 How many distinct function exist between
two given finite sets A and B?
Combinatorics
 the branch of discrete mathematics
concerned with determining the size of finite
sets without actually enumerating each
element.
Combinatorics
 The Sum Rule (task formulation):


Suppose that a task can be completed by performing
exactly one task from a collection of disjoint subtasks:
subtask1, subtask2, ... , subtaskn;
Now suppose each subtask has a choice of ways to
perform it, e.g.
•
•
•
•

subtask1 can be performed t1 ways,
subtask2 can be performed t2 ways,
...
subtaskn can be performed tn ways.
Then number the number of ways to perform the task
is:
t1 + t2 + ... + tn
The Sum Rule
 Example:


You have five novels, four magazines, and three
devotional books. How many options do you
have for taking one for your wait in the bank
line?
You have 3 subtasks - pick a novel, pick a
magazine, or pick a devotional book. The first
can be done 5 ways, the second, 4 ways, and the
third 3 ways. Thus:
5 + 4 + 3 = 12 ways to perform.
The Sum Rule
 Example:

Suppose either a CS faculty or a CS student
must be chosen for a committee, and there are 4
CS faculty and 16 CS students. How many
possible choices are there?
The Sum Rule
 Example:

Suppose a student can meet the humanities
course requirement by taking either a religion,
literature, or art course. There are 3 religion, 4
literature, or 4 art courses to chose from. How
many possible choices are there?
Combinatorics
 The Product Rule (task formulation):

Suppose a task needs to be done, and the tasks
consists of a sequence of n steps or subtasks:
task = task1, task2, task3, ..., taskn
where each task taskx has a certain number of ways
(tx) in which it can be performed after the preceding
tasks have been performed, e.g.
•
•
•
•
task1 = t1 ways,
task2 = t2 ways after task1 is complete,
task3 = t3 ways after task1 and task2 is complete, ... ,
taskn = tn ways after task1 ... taskn-1 is complete
Then the number of ways the task can be performed is:
t1  t2  t3  ...  tn
Example - Product Rule
 How many different ways can we chose
from 4 colors and paint 3 rooms?

Tasks:
• 1 - paint room 1 - 4 ways to perform (4 colors)
• 2 - paint room 2 - 4 ways to perform (4 colors)
• 3 - paint room 3 - 4 ways to perform (4 colors)

Thus t1 = 4, t2 = 4, t3 = 4, and
4  4  4 = 64
ways to paint the rooms
Example - Product Rule
 How many different ways can we chose
from 4 colors and paint 3 rooms, if no room
is to be the same color?

tasks:
• 1 - paint room 1 - 4 ways to perform (4 colors)
• 2 - paint room 2 - 3 ways to perform (3 colors left)
• 3 - paint room 3 - 2 ways to perform (2 colors left)

Thus t1 = 4, t2 = 3, t3 = 2, and
4  3  2 = 24 ways to paint the rooms
Example - Product Rule
 How many different orders may 9 people be
arranged in?


There are nine tasks - picking the first person,
picking the second, …
The first task has 9 choices, the second 8, ... and
finally the ninth task has 1 choice:
9  8  7  6  5  4  3  2  1 = 362880
Example - Product Rule
 How many different 3 people can be
selected from a group of 8 people to a
president, vice-president, treasure of the
group?
Example - Product Rule
 If student ID’s are two capital letters
followed by three numeric digits, then how
many ID’s are possible?


What if the two letters must be distinct?
What if the letters and the numbers must all be
distinct?
Combinatorics
 The Product Rule (set formulation):

If A and B are finite sets, then:
|A  B| = |A|  |B|


The cardinality of the Cartesian product of two
sets is the product of the their cardinalities.
Note that ANY ordered list of items is trivially
equivalent to a Cartesian product.
Example - Product Rule
Let A = {a, b, c, d, e}, B = {1, 3, 5, 7}
 How many pairs (x, y) exist where x  A and
y  B?
 A  B has cardinality |A|  |B| = 5  4 = 20
Example - Product Rule
 How many license plates are possible with 3
letters followed by 3 digits?
262626101010 = 17576000
Combinatorics
 The Sum Rule (set formulation):
If A and B are disjoint finite sets, then:
|A  B| = |A| + |B|
The cardinality of the union of two disjoint
sets is the sum of their cardinalities.
Example - The Sum Rule
Let A = {a, b, c, d, e}, B = {1, 3, 5, 7}
 How many ways can one element be
chosen?
|A  B| = |A| + |B| = 5 + 4 = 9.
Example - The Sum Rule
 You have five novels, four magazines, and
three devotional books.

How many options do you have for taking one
for your wait in the bank line?
Example
 Suppose that you own 3 pairs of shoes, 6
pairs of socks, 4 pairs of pants, and 6 shirts.

How many different outfits can you make out of
these articles of clothing?
(An outfit consists of one pair of shoes, one
pair of socks, one pair of pants, and one shirt.)
Example
 Consider the following road map.
A
B
C
a)How many ways are there to travel from A to B,
and back to A, without going through C?
b) How many ways are there to go from A to C,
stopping once at B?
c)How many ways are there to go from A to C,
making at most one intermediate stop?
Example
 A certain apartment complex has 26
television antennas. Each pair of apartments
shares a common antenna. How many
apartments are there in the complex?
Example
 Two cards are drawn from a deck of cards,
one at a time. How many outcomes are
possible
a) if the order in which the cards are draw
matters?
b) if the order in which the cards are drawn does
not matter?
Example
 Suppose that you flip a coin 5 times and
record the sequence of heads and tails.

How many possibilities are there for this
sequence?
Example
 How many integers between 0 and
1,000,000 contain the digit 9?
 (Hint, it is easier to count the number of
integers that do not contain the digit 9.)
The Pigeonhole Principle
 If k + 1 or more objects are placed in k
boxes, then there is at least one box
containing two or more objects.
The Pigeonhole Principle
 If k + 1 or more objects are placed in k
boxes, then there is at least one box
containing two or more objects.
The Pigeonhole Principle
 If k + 1 or more objects are placed in k
boxes, then there is at least one box
containing two or more objects.
The Pigeonhole Principle
 If k + 1 or more objects are placed in k
boxes, then there is at least one box
containing two or more objects.
 Proof: Suppose that none of the k
boxes contains more then one object.
Then the maximum number of objects
would be k. This is a contradiction,
since there is at least k + 1 objects.
The Pigeonhole Principle
 Among 367 people, there must be at
least 2 with the same birthday, since
there is only 366 possible birthdays.
 In a collection of 10 numbers, at least 2
must have the same most significant
digit.
 In a collection of 11 numbers, at least 2
must have the same least significant
digit.
The Pigeonhole Principle
 How many people must we have in the
same room to be sure that at least two
have the same birthday?
The Pigeonhole Principle
 Are there two people in Ohio with the
same number of hairs?
 Are there two people at MVNC the same
birthday?
 Are there two people at MVNC with
birthdays on July 14?
The Pigeonhole Principle
 The Generalized Pigeonhole Principle:
If N objects are placed into k boxes,
then there is at least one box containing
at least N/k objects.
Generalized Pigeonhole
Principle
 If N objects are placed into k boxes,
then there is at least one box containing
at least N/k objects.
Generalized Pigeonhole
Principle
 If N objects are placed into k boxes,
then there is at least one box containing
at least N/k objects.
Generalized Pigeonhole
Principle
 If N objects are placed into k boxes,
then there is at least one box containing
at least N/k objects.
Generalized Pigeonhole
Principle
 Proof: Suppose that none of the boxes
contains more than N/k - 1 objects. Then
the total number of objects is at most:
k (N/k - 1).
But since N/k < (N/k + 1), we get the
following:
k (N/k - 1) < k (((N/k + 1) - 1) = N, thus
k (N/k - 1) < N
which is a contradiction since there is a total
of N objects.
Generalized Pigeonhole
Principle
 Among 100 people there are at least
100/12 = 9 people with the same
birthday month.
Generalized Pigeonhole
Principle
 In MVNC there are at least 1500/366 =
5 people with the same birthday.
Generalized Pigeonhole
Principle
 In a class of 44 students, how many will
receive the same grade on a scale {A,
B, C, D, F}.
Generalized Pigeonhole
Principle
 How many people must we survey, to be
sure at least 50 have the same political
party affiliation, if we use the three
affiliations {Democrat, Republican,
neither}?
 (Make N/3 = 50)
Generalized Pigeonhole
Principle
 What is the least number of area codes
needed to guarantee that 25,000,000
phones in a state have distinct 10 digit
numbers.
(Assume that telephone numbers are of
the form NXX-NXX-XXXX, where N is a
a digit from 2-9, and X represents any
digit.)
Generalized Pigeonhole
Principle
 Let n be a positive integer.
 Show that in any set of n consecutive
integers there is exactly one divisible by
n.
Generalized Pigeonhole
Principle
 A computer network consists of 6
computers.
 Each computer is is directly connected
with zero or more of the other
computers.
 Show that there is at least two
computers with the same numbers of
connections.
Generalized Pigeonhole
Principle
 Show that if seven integers are selected
from the first eight positive integers,
there must be pair of these integers with
a sum equal to to 9.

Is this still true if four integers are chosen
instead of five?
Generalized Pigeonhole
Principle
 What is the minimum number of
students MVNC must have to be
assured that at least 40 come from the
same state?
Generalized Pigeonhole
Principle
 How many students must attend MVNC
to assure use that at least two have the
same 3 letter initials?
Permutations and
Combinations
 Consider: How many ways can we choose r
things from a collection of n things?
pick
Pick 4 from 9
colored balls
Permutations and
Combinations
 Consider: How many ways can we choose r
things from a collection of n things?
 This statement is ambiguous in several
ways:



Are the n things distinct or indistinguishable?
Do the selected items form a set (unordered
collection) or a sequence (ordered)?
May the same item be selected from the r items
more then once? (Are repetitions permitted?).
Permutations and
Combinations
 Example using balls:



Are the balls identical or different colors? Are
some different colors, others the same?
Are balls tossed in a bucket (unordered) or lined
up in a line in the order chosen?
Each ball returned to the collection before the
next is selected?
Permutation
 An ordered selection of objects.
 If there is a collection of n objects to chose
from, and we are selecting all n objects, then
we call each possible selection a
permutation from the collection.
 In the general case the items are all distinct,
and repetitions are not permitted.
Permutation
 Possible permutations of three colored balls:
Permutation
 Consider the set S = {a, b}. What are the
permutations?
ab ba
Permutation
 Consider the set S = {a, b, c}. What are the
permutations?
abc acb bca bac cab cba
Permutation
 Consider the set S = {a, b, c, d}. What are
the permutations?
abcd
abdc
adbc
dabc
acbd
acdb
adcb
dacb
bcad
bcda
bdca
dbca
bacd
badc
bdac
dbac
cabd
cadb
cdab
dcab
cbad
cbda
cdba
dcba
Permutation
 Theorem: The number of permutations of a
set of n objects is the product of the first n
positive integers, that is
n(n -1) ... 1 = n
Permutation
Justification:
Arranging n objects into order requires n tasks.
Task 1
Pick first object (n choices)
Task 2
Pick second object (n-1 choices)
...
Task n
Pick last (nth) object (1 choice)
Thus, by the product rule, the number of ways to
arrange n objects is:
n(n -1) ... 1 = n!
Permutation
 How many ways are there to arrange 9 floats
in the Christmas parade?
9  8  7  6  5  4  3  2  1 = 362880
r-Permutations
 Consider ordering a subset of a collection of
objects.
 If there is a collection of n objects to chose
from, and we are selecting r of the objects,
where 0<rn, then we call each possible
selection a r-permutation from the
collection.
r-Permutations
 Consider a 4-permutation of 9 balls
pick
r-Permutations
Consider the set S = {a, b, c}.
 What are the 2-permutations of S?
ab ba ac ca bc cb
 What are the 3-permutations of S?
abc acb bca bac cab cba
r-Permutations
Consider the set S = {a, b, c, d}.
 What are the 2-permutations of S?
ab ac ad ba bc bd
ca cb cd da db dc
r-Permutations
Consider the set S = {a, b, c, d}.
 What are the 3-permutations of S?
abc acb bac bca cba cab (from {a, b, c})
abd adb bad bda dba dab (from {a, b, d})
adc acd dac dca cda cad (from {a, c, d})
dbc dcb bdc bcd cbd cdb (from {b, c, d})
r-Permutations
 Theorem: The number of r-permutations of
a set of n objects, written P(n, r) is:
n!
P(n, r)  n(n-1) ... (n-r  1) 
(n  r )!
r-Permutations
 Justification:

Arranging r of n objects into order requires r tasks.
Task 1 Pick first object
Task 2 Pick second object
…
Task r Pick rth object

(n choices)
(n-1 choices)
(n - r + 1 choices)
Thus, by the product rule, the number of ways to
arrange n objects is:
n!
n(n-1) ... (n-r  1) 
(n  r )!
r-Permutations
Consider a horse race with 8 horses.
 If a spectator were select three different
horses at random to bet on for first, second
and third places, how likely is he to be
completely correct?
 P(8,3) = 8  7  6 = 336 permutations
possible
 Thus he has a 1 in 336 chance.
r-Permutations
 To send secret messages, two ships have
three flagpoles and 10 different flags (one
flag per pole).


If a set of three flags indicates a message, how
many messages are possible?
If 0, 1, 2, or 3 flags all represent messages?
r-Permutations
 Suppose license plates for some state
contain 3 letters followed by 3 numbers,
where no number or letter can be repeated?


How many possibilities are there?
If we consider all possibilities where repetitions
are allowed, how many have at least one
repeated number or letter?
r-Permutations
 How many ways can we hand out 7
different free books to 15 students (where
each gets exactly one book)?
Combinations
 Combination - an unordered selection of
objects.
 Definition:

Consider a set S with n objects.
Every k sized subset of those objects
(0<rn) is a combination of size r, or
a r-combination taken from S.
Combinations
Consider the set A = {a, b, c}.
 What are the 2-combinations of A?
{a, b} {a, c} {b, c}
 What are the 3-combinations of A?
{a, b, c}
 What are the 1-combinations of A?
{a} {b} {c}
Combinations
Consider the set B = {a, b, c, d}.
 What are the 2- combinations of B?
{a, b} {a, c} {a,d} {b, c} {b, d} {c, d}
 What are the 3-combinations of B?
{a, b, c} {a, c, d} {b, c, d} {a, b, d}
Combinations
 Notice the comparison of 3-combinations of
B with 3-permutations:
3-permutations
3-combinations
abc acb bac bca cba cab {a, b, c}
abd adb bad bda dba dab {a, b, d}
adc acd dac dca cda cad {a, c, d}
dbc dcb bdc bcd cbd cdb {b, c, d}
Combinations
 This shows that each r-combination has
r-permutations possible. Thus the following
theorem:
 Theorem: The number of r -combinations
of a set of n distinct objects is:
P(n, r )
n!
C (n, k ) 

r!
r!(n  r )!
Combinations
P(n, r )
n!
C (n, k ) 

r!
r!(n  r )!

Justification: We find the number of
permutations, then divide by a factor which we
have overcounted. Since each r-combination of
the n objects can be ordered P(r,r) = r! ways, we
divide the number of r-permutations from n
objects by the number of r-permutations of r
objects.
Combinations
 The number C(n,r) is also written:
 n
C (n, r )   
r
 And is be read n choose r objects.
Combinations
 How many subsets of size 5 are there of the
set {1, 2, 3, ..., 10}?
10 P(10,5) 10!
C (10,5)    

5!
5!5!
5
10  9  8  7  6  5  4  3  2  1

5  4  3  2 1  5  4  3  2 1
10  9  8  7  6 30240


 252
5  4  3  2 1
120
Combinations
 How many subsets of size 7 are there of the
set {1, 2, 3, ..., 10}?
 How many subsets of size 3?
 How many subsets of size 2?
 How many subsets of size 8?
Combinations
 How many different 5-card hands can be
made from a deck of 52 cards?
Combinations
 A certain club has 5 male and 7 female
members.

How many ways are there to form a 7 member
committee consisting of 3 men and 4 women?
• Two tasks - pick a man, then pick a woman.
• Thus: C(7,4) · C(5,3)

How many ways can any 7 member committee
be selected from the membership?
Combinations
 How many ternary words of length 12 have
exactly seven 0's, three 1's, and two 2's?
 Solution:


Here we can think in terms of picking slots to
put numbers in. We thus have three tasks:
Task 1 - pick 7 of 12 places to put 0's
Task 2 - pick 3 of 5 places to put 1's
Task 1 - pick 2 of 2 places to put 2's
Thus: C(12,7)·C(5,3)·C(2,2)
Combinations
 How many subsets of size 2 are there of
{1, 2, ..., 20} which do not consist of two
consecutive integers?
 Solution:



Count the number of subsets which do contain
two consecutive integers, then subtract from
total number of subsets of size two.
Clearly 19 subset contain two consecutive
integers, e.g. {1,2}, {2,3}, {3,4}, ... , {19,20}.
Thus: C(20,2) - 19.
Combinations
 How many bytes contain exactly four 1's?
 Solution: C(8,4).
Combinations
 A certain club has 5 men and 6 women.




How many ways are there to form a committee
of 3 people?
How many ways are there to form a committee
consisting of 3 men and 4 woman?
How many ways are there to form a committee
of 6 people if 2 woman refuse to serve together?
How many ways are there to form a committee
of 4 men and 3 woman if 2 men refuse to serve
together?
Combinations
 Solution:




How many ways are there to form a committee of 3
people?
C(11,3)
How many ways are there to form a committee
consisting of 3 men and 4 woman?
C(5,3)·C(6,4)
How many ways are there to form a committee of 6
people if 2 woman refuse to serve together?
C(11,6)-C(9,4)
How many ways are there to form a committee of 4 men
and 3 woman if 2 men refuse to serve together?
(C(5,4)-C(3,2))·C(6,3)