Elementary Combinatorics
CE 311S
INTRODUCTION
How can we actually calculate probabilities?
Let’s assume that there all of the outcomes in the sample space S are
equally likely. If |A| is the number of outcomes included in the event A,
then
|A|
P(A) =
|S|
Elementary Combinatorics Introduction
How can we actually calculate probabilities?
Let’s assume that there all of the outcomes in the sample space S are
equally likely. If |A| is the number of outcomes included in the event A,
then
|A|
P(A) =
|S|
In this case, calculating probabilities is reduced to counting.
Elementary Combinatorics Introduction
For situations with a small number of outcomes, we can count directly.
Example: A family has three children; what is the probability that
exactly two of them are boys?
Elementary Combinatorics Introduction
For situations with a larger number of outcomes, we need something more
systematic.
Example: In five-card draw poker, what’s the probability of being dealt a
royal flush?
Elementary Combinatorics Introduction
MULTIPLICATION RULE
FOR COUNTING
The Multiplication Rule for Counting
If we have a set n1 objects, and a set n2 objects, the number of ways to
choose one object from each set is n1 × n2 .
The same rule applies where there are more than two sets.
Elementary Combinatorics Multiplication Rule for Counting
LUNCH MENU
Pick a sandwich from column A and a soup from column B
Column A Column B
Ham and Cheese Minestrone
Pastrami Chicken Noodle
Hummus Pita Chili
Tuna
How many different lunches can I have?
Elementary Combinatorics Multiplication Rule for Counting
LUNCH MENU
Pick a sandwich from column A and a soup from column B
Column A Column B
Ham and Cheese Minestrone
Pastrami Chicken Noodle
Hummus Pita Chili
Tuna
There are 4 different sandwiches, each of which can be paired with 3
different soups, so there are 4 × 3 = 12 possible lunches.
Elementary Combinatorics Multiplication Rule for Counting
What if there are more than two options?
SOMEWHAT SIMPLER LUNCH MENU
Pick a salad from column A, a sandwich from column A and a soup from
column C
Column A Column B Column C
Caesar Ham and Cheese Minestrone
House Pastrami Chicken Noodle
Hummus Pita Chili
Tuna
The multiplication rule still applies: 2 × 3 × 4 = 24 possible lunches.
Elementary Combinatorics Multiplication Rule for Counting
If we are choosing k things from the same set, and we can choose the
same thing multiple times, then the multiplication rule gives us nk
possibilities (assuming order matters).
In how many ways can we assign birthdays to students in this class?
Elementary Combinatorics Multiplication Rule for Counting
PERMUTATIONS
(ORDERED WITHOUT
REPLACEMENT)
Let’s shift gears here... we’ll now talk about choosing multiple items from
a set X without any duplications. Examples:
Dealing a hand from a deck of cards
Choosing a starting lineup for a sports team
Borrowing books from the library
This is frequently called sampling without replacement. Unlike the
previous examples, we are picking multiple items from the same set.
However, the fundamental principle still applies.
Elementary Combinatorics Permutations (Ordered without replacement)
Given a set A, a permutation is an ordered subset of A.
Example: To discourage cheating, a professor develops 10 exam
questions. Each exam will consist of four of these questions in a different
order. How many different exams can be created?
Elementary Combinatorics Permutations (Ordered without replacement)
The following logic shows how the multiplication rule can
be applied
The first question can be any of the 10 questions developed
The second question can be any of the 9 questions which are not the
first
The third question can be any of the remaining 8
The fourth question can be any of the remaining 7
Elementary Combinatorics Permutations (Ordered without replacement)
The following logic shows how the multiplication rule can
be applied
The first question can be any of the 10 questions developed
The second question can be any of the 9 questions which are not the
first
The third question can be any of the remaining 8
The fourth question can be any of the remaining 7
Therefore, there are 10 × 9 × 8 × 7 = 5040 possible exams.
Elementary Combinatorics Permutations (Ordered without replacement)
In general, for a set X containing n elements, the number of permutations
of size k is given by:
Pkn = (n)(n − 1) · · · (n − k + 1)
This can also be written as
k−1
Y
Pkn = (n − i)
i=0
or
n!
Pkn =
(n − k)!
Elementary Combinatorics Permutations (Ordered without replacement)
A factorial sidebar
n! is defined recursively as n × (n − 1)! if n ≥ 1, with 0! = 1.
Elementary Combinatorics Permutations (Ordered without replacement)
A factorial sidebar
n! is defined recursively as n × (n − 1)! if n ≥ 1, with 0! = 1.
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
Factorials grow really quickly. 10! = 3,628,800, 20! ≈ 2.4 × 1018 , 50! has
more than sixty digits.
Elementary Combinatorics Permutations (Ordered without replacement)
Example
My hipster friend only likes 15 songs. How many different playlists can be
made from these songs? Each playlist contains ten songs, and the order of
the songs matters.
15 × 14 × 13 × · · · × 6 = 1089728640
(Surprised? Permutations can be very large even for relatively small sets.)
Elementary Combinatorics Permutations (Ordered without replacement)
The birthday paradox revisited...
What is the probability that two people in this room have the same
birthday?
Elementary Combinatorics Permutations (Ordered without replacement)
COMBINATIONS
(UNORDERED WITHOUT
REPLACEMENT)
A combination is a subset of X where order doesn’t matter,
Combinations (Unordered without
Elementary Combinatorics replacement)
A combination is a subset of X where order doesn’t matter,
COMBO LUNCH MENU
Pick any three items from the following list.
Caesar Salad Ham and Cheese Minestrone
House Salad Pastrami on Rye Chicken Soup
Tuna Sandwich Hummus Pita Chili
How many different combo meals can I make? There are 9 × 8 × 7 = 504
permutations, but this double-counts some of the meals. (Minestrone +
chicken soup + chili is the same souper combo meal as chicken soup +
minestrone + chili).
Combinations (Unordered without
Elementary Combinatorics replacement)
The question is, how many times is each combo meal counted in the full
list of permutations?
This is really asking, “How many different ways can I rearrange 3 items?”
This is really asking how many permutations of 3 items can I take from a
set of 3.
The answer is P33 = 3! = 6
Therefore, each of the 504 permutations contains 6 copies of each combo
meal.
Therefore, the number of combinations is 504/6 = 84.
Combinations (Unordered without
Elementary Combinatorics replacement)
In general, the number of combinations is given by
n Pk,n Pk,n n!
= = =
k Pk,k k! k!(n − k)!
pronounced “n choose k.”
Combinations (Unordered without
Elementary Combinatorics replacement)
n 1
What is the relationship between k and Pk,n ?
n
A: k ≤ Pk,n
n
B: k ≥ Pk,n
n
C: k = Pk,n
D: Impossible to say
1
Assuming, of course, n and kCombinations
are positive integers with k ≤ n
(Unordered without
Elementary Combinatorics replacement)
UNORDERED SAMPLING
WITH REPLACEMENT
What if order doesn’t matter, but I can choose the same thing multiple
times?
DELUXE COMBO LUNCH MENU
Pick any three items from the following list (repetition allowed).
Caesar Salad Ham and Cheese Minestrone
House Salad Pastrami on Rye Chicken Soup
Tuna Sandwich Hummus Pita Chili
Different than the previous version, I can now order 3 Caesar salads for
lunch if I want.
Elementary Combinatorics Unordered sampling with replacement
Let x1 , . . . , x9 represent how many times I order each of the nine menu
items. (So ordering 3 Caesar salads would be x1 = 3,
x2 = x3 = · · · = x9 = 0).
Then any solution to the equation x1 + x2 + · · · + x9 = 3 represents a
possible combo meal, if each xi is a nonnegative integer (xi ∈ Z+ ).
The number of nonnegative integer solutions to this equation is the
number of possible combo meals.
Elementary Combinatorics Unordered sampling with replacement
In total I will order three items, let me put a tick mark in each column for
each order:
x1 x2 x3 x4 x5 x6 x7 x8 x9
|||
I can encode this table as a string of 11 characters: 3 tick marks for the
order, and 8 separators (use ’+’) between columns: |||++++++++
Elementary Combinatorics Unordered sampling with replacement
In fact, any string of 11 characters which contains 3 | and 8 + marks
represents a valid order.
11
I can decide the 3 | locations (the remainder must be +), so 3 = 165.
I could
just as well have chosen the 8 + locations (the rest must be |), or
11
8 = 165.
So, in general the formula is
n+k −1 n+k −1
or
k n−1
Elementary Combinatorics Unordered sampling with replacement
EXAMPLES
Answer the following questions:
How many...
1 three-topping pizzas can be made if there are five toppings available?
2 the same as (1), but if you can repeat toppings.
3 seven-member committees can be chosen from ten eligible members?
4 four-digit PIN numbers can you make if you can’t repeat digits?
5 four-digit PIN numbers can you make if you can repeat digits?
Elementary Combinatorics Examples
A more involved example
In five-card draw poker, what’s the probability of being dealt a royal flush?
First, what are the outcomes and sample space?
Let A denote the event “I am dealt a royal flush.” Assuming the deck is
shuffled perfectly,
|A|
P(A) =
|S|
Thus, we need to calculate |S| and |A|.
Elementary Combinatorics Examples
Since the order of the cards in my hand doesn’t matter in poker, the
number of distinct hands I can draw is
52
= 2598960
5
Neglecting simple rearrangements of the order of the cards, there are only
four different royal flushes (one for each suit).
Therefore, the probability of a royal flush is 4/2598960 = 1/649740.
Elementary Combinatorics Examples
If we wanted to use permutations, we could use the following logic:
The number of possible hands is
P552 = 52!/47! = 52 × 51 × 50 × 49 × 48 = 311875200
Elementary Combinatorics Examples
How many royal flushes are there? Consider each suit separately. For
spades, there are exactly 5 cards I need to draw; these 5 cards can be
drawn in P55 = 5! = 120 ways.
The same is true for the other suits, so in total only 480 of the hands are
royal flushes.
Therefore, the probability of a royal flush is 480/311875200 = 1/649740.
Elementary Combinatorics Examples
