CSE 312 Recitation 2
Please feel free to ask questions before, during, or after section!
Announcements
Agenda
Slides originally written by Alex Tsun & TA’s (William Howard-Snyder, Mitchell Estberg, Maggie Jiang, Ege Caglar).
Super Mario Bros Example
Video game characters Mario and Luigi are trying to advance through levels of the game to save Princess Peach. Before they attempt the first two levels, they enter a Toad House that may provide powerups to increase their chances of beating the levels. For simplicity, assume that if they receive a powerup in the Toad House, then they retain it for both of the first two levels.
Suppose that they have a 1/4 chance of obtaining a powerup from the Toad House. If they have a powerup, they will beat any given level with probability 7/10. If they do not receive a powerup, they will beat any given level with probability 4/10.
Super Mario Bros Example
(a) If Mario and Luigi defeated the first level, what is the probability that they received a powerup from the Toad House?
Super Mario Bros Example
(a) If Mario and Luigi defeated the first level, what is the probability that they received a powerup from the Toad House?
Let 𝑇 be the event that they received a powerup from the Toad House, 𝑇C be the event that they did not receive a powerup, and 𝑊ᵢ be the event that they win level i.
Super Mario Bros Example
(a) If Mario and Luigi defeated the first level, what is the probability that they received a powerup from the Toad House?
Let 𝑇 be the event that they received a powerup from the Toad House, 𝑇C be the event that they did not receive a powerup, and 𝑊ᵢ be the event that they win level i.
Bayes’
Super Mario Bros Example
(a) If Mario and Luigi defeated the first level, what is the probability that they received a powerup from the Toad House?
Let 𝑇 be the event that they received a powerup from the Toad House, 𝑇C be the event that they did not receive a powerup, and 𝑊ᵢ be the event that they win level i.
Bayes’
Values needed for numerator are given, but…
How can we find P(W1) if it depends on their powerup status?
Super Mario Bros Example
(a) If Mario and Luigi defeated the first level, what is the probability that they received a powerup from the Toad House?
Let 𝑇 be the event that they received a powerup from the Toad House, 𝑇C be the event that they did not receive a powerup, and 𝑊ᵢ be the event that they win level i.
Bayes’
LTP
Super Mario Bros Example
(a) If Mario and Luigi defeated the first level, what is the probability that they received a powerup from the Toad House?
Let 𝑇 be the event that they received a powerup from the Toad House, 𝑇C be the event that they did not receive a powerup, and 𝑊ᵢ be the event that they win level i.
Bayes’
LTP
Plug given probabilities
Super Mario Bros Example
(a) If Mario and Luigi defeated the first level, what is the probability that they received a powerup from the Toad House?
Let 𝑇 be the event that they received a powerup from the Toad House, 𝑇C be the event that they did not receive a powerup, and 𝑊ᵢ be the event that they win level i.
Bayes’
LTP
Plug given probabilities
Simplify
Super Mario Bros Example
(a) If Mario and Luigi defeated the first level, what is the probability that they received a powerup from the Toad House?
Let 𝑇 be the event that they received a powerup from the Toad House, 𝑇C be the event that they did not receive a powerup, and 𝑊ᵢ be the event that they win level i.
Bayes’
LTP
Plug given probabilities
Unintuitive, but note low P(T) and how�P(T | W1) > P(T)!
Super Mario Bros Example
(b) If Mario and Luigi defeat the first level, what is the probability that they lose in the second level?
Super Mario Bros Example
(b) If Mario and Luigi defeat the first level, what is the probability that they lose in the second level?
Let 𝑇 be the event that they received a powerup from the Toad House, 𝑇 C be the event that they did not receive a powerup, 𝑊ᵢ be the event that they win level i, and 𝑊 Ci be the event that they did not win level i.
Super Mario Bros Example
(b) If Mario and Luigi defeat the first level, what is the probability that they lose in the second level?
Let 𝑇 be the event that they received a powerup from the Toad House, 𝑇 C be the event that they did not receive a powerup, 𝑊ᵢ be the event that they win level i, and 𝑊 Ci be the event that they did not win level i.
Want to find 𝑷 (𝑊 C2 | 𝑊1)... can we try Bayes’?
𝑷 (𝑊 C2 | 𝑊1) = 𝑷 (𝑊1 | 𝑊 C2)𝑷 (𝑊 C2) � 𝑷 (𝑊1 )
Super Mario Bros Example
(b) If Mario and Luigi defeat the first level, what is the probability that they lose in the second level?
Let 𝑇 be the event that they received a powerup from the Toad House, 𝑇 C be the event that they did not receive a powerup, 𝑊ᵢ be the event that they win level i, and 𝑊 Ci be the event that they did not win level i.
Want to find 𝑷 (𝑊 C2 | 𝑊1)... can we try Bayes’?
𝑷 (𝑊 C2 | 𝑊1) = 𝑷 (𝑊1 | 𝑊 C2)𝑷 (𝑊 C2) � 𝑷 (𝑊1 )
???�Does not make sense contextually
Super Mario Bros Example
(b) If Mario and Luigi defeat the first level, what is the probability that they lose in the second level?
Let 𝑇 be the event that they received a powerup from the Toad House, 𝑇 C be the event that they did not receive a powerup, 𝑊ᵢ be the event that they win level i, and 𝑊 Ci be the event that they did not win level i.
Let’s try a different approach:
Def. Conditional Prob.
Super Mario Bros Example
Def. Conditional Prob.
Super Mario Bros Example
Numerator: Lose level 2 and win level 1… two cases (powerup vs. no powerup)
Multiple cases → Use LTP to break down the cases!
Def. Conditional Prob.
LTP
Super Mario Bros Example
Def. Conditional Prob.
LTP
Def. Conditional Prob.
Super Mario Bros Example
Def. Conditional Prob.
LTP
LTP (same as part (a))�
Def. Conditional Prob.
Super Mario Bros Example
Def. Conditional Prob.
LTP
LTP (same as part (a))
Def. Conditional Prob.��Plug values in��Simplify
Robot Example
Suppose Joe is a k-legged robot, who wears a sock and a shoe on each leg. Suppose he puts on k socks and k shoes in some order. Each action is specified by saying whether he puts on a sock or a shoe, and saying which leg he puts it on. In how many ways can he put on his socks and shoes in a valid order? We say an ordering is valid if, for every leg, the sock gets put on before the shoe. Assume all socks are indistinguishable from each other, and all shoes are indistinguishable from each other.
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
k-1
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
k-1
k
k-1
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
k-1
k
k-1
k-1
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
k-1
k
k-1
k-1
Pattern Searching
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
k-1
k
k-1
k-1
Pattern Searching
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
k-1
k
k-1
k-1
Pattern Searching
Count Something Else
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
k-1
k
k-1
k-1
Pattern Searching
Count Something Else
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
k-1
k
k-1
k-1
Pattern Searching
Count Something Else
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
k-1
k
k-1
k-1
Pattern Searching
Count Something Else
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
k-1
k
k-1
k-1
Pattern Searching
Simplify, then Complicate
Count Something Else
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
k-1
k
k-1
k-1
Pattern Searching
Simplify, then Complicate
Count Something Else
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
k-1
k
k-1
k-1
Pattern Searching
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
Count Something Else
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
k-1
k
k-1
k-1
Pattern Searching
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
Count Something Else
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
k-1
k
k-1
k-1
Pattern Searching
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
Count Something Else
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
What are some possible approaches?
Brute Force
k
k
k-1
k
k-1
k
k-1
k-1
Pattern Searching
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
Count Something Else
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
sock1, shoe1, sock2, shoe2 vs. sock1,sock2,shoe1,shoe2..
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
sock1, shoe1, sock2, shoe2 vs. sock1,sock2,shoe1,shoe2..
these are distinct orderings of how many objects?
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
sock1, shoe1, sock2, shoe2 vs. sock1,sock2,shoe1,shoe2..
these are distinct orderings of how many objects? (2k)!
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
sock1, shoe1, sock2, shoe2 vs. sock1,sock2,shoe1,shoe2..
these are distinct orderings of how many objects? (2k)!
what’s wrong?
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
sock1, shoe1, sock2, shoe2 vs. sock1,sock2,shoe1,shoe2..
these are distinct orderings of how many objects? (2k)!
what’s wrong? count invalid:
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
sock1, shoe1, sock2, shoe2 vs. sock1,sock2,shoe1,shoe2..
these are distinct orderings of how many objects? (2k)!
what’s wrong? count invalid: shoe1,sock1, sock2, shoe2…
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
sock1, shoe1, sock2, shoe2 vs. sock1,sock2,shoe1,shoe2..
these are distinct orderings of how many objects? (2k)!
what’s wrong? count invalid: shoe1,sock1, sock2, shoe2…
how do we address this?
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
sock1, shoe1, sock2, shoe2 vs. sock1,sock2,shoe1,shoe2..
these are distinct orderings of how many objects? (2k)!
what’s wrong? count invalid: shoe1,sock1, sock2, shoe2…
how do we address this? each leg has one valid order
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
sock1, shoe1, sock2, shoe2 vs. sock1,sock2,shoe1,shoe2..
these are distinct orderings of how many objects? (2k)!
what’s wrong? count invalid: shoe1,sock1, sock2, shoe2…
how do we address this? each leg has one valid order
sock comes before shoe!
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
sock1, shoe1, sock2, shoe2 vs. sock1,sock2,shoe1,shoe2..
these are distinct orderings of how many objects? (2k)!
what’s wrong? count invalid: shoe1,sock1, sock2, shoe2…
how do we address this? each leg has one valid order
sock comes before shoe!
this counts both,
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
sock1, shoe1, sock2, shoe2 vs. sock1,sock2,shoe1,shoe2..
these are distinct orderings of how many objects? (2k)!
what’s wrong? count invalid: shoe1,sock1, sock2, shoe2…
how do we address this? each leg has one valid order
sock comes before shoe!
this counts both, so divide by 2
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
sock1, shoe1, sock2, shoe2 vs. sock1,sock2,shoe1,shoe2..
these are distinct orderings of how many objects? (2k)!
what’s wrong? count invalid: shoe1,sock1, sock2, shoe2…
how do we address this? each leg has one valid order
sock comes before shoe!
this counts both, so divide by 2
for each leg
Robot Example
A k-legged robot, puts on k socks and k shoes in some order. An ordering is valid if, for every leg, the sock gets put on before the shoe. All socks are indistinguishable from each other, and all shoes are indistinguishable from each other. How many ways can he put on his socks and shoes in a valid order?
Simplify, then Complicate
sock1, shoe1, sock2, shoe2….
sock1, shoe1, sock2, shoe2 vs. sock1,sock2,shoe1,shoe2..
these are distinct orderings of how many objects? (2k)!
what’s wrong? count invalid: shoe1,sock1, sock2, shoe2…
how do we address this? each leg has one valid order
sock comes before shoe!
this counts both, so divide by 2
for each leg
(2k)!
2
k
Restaurant Example
Suppose n people sit around a table. Each person orders a different dish, but the waiter did not mark positions unfortunately. He has the correct n dishes, but gives a random dish to each person (each of the n! assignments is equally likely). What is the probability that no one has the dish they ordered placed in front of them?
Restaurant Example
Let E be the event that no one gets their dish
Let Ei be the event that the ith person does not get their dish.
Initial approach: people getting their correct dishes are independent events…?
Restaurant Example
The events are not independent because if one person does not get their dish it changes the probability that another person does not get their own dish
Restaurant Example
Let be all the possible ways that the waiter could return the group’s dishes (with no restrictions). Let E be the event that no one gets their dish.
What is the size of ?
Restaurant Example
Let be all the possible ways that the waiter could return the group’s dishes (with no restrictions). Let E be the event that no one gets their dish.
What is the size of ?
Restaurant Example
Let be all the possible ways that the waiter could return the group’s dishes (with no restrictions). Let E be the event that no one gets their dish.
What is the size of ?
What is the size of ?
Restaurant Example
Let be all the possible ways that the waiter could return the group’s dishes (with no restrictions). Let E be the event that no one gets their dish.
What is the size of ?
What is the size of ?
Restaurant Example
Remember: If a set is hard to count, maybe we should try counting its complement
Restaurant Example
Remember: If a set is hard to count, maybe we should try counting its complement
Let be the event that the ith person does get their own dish back. Then,
Restaurant Example
Remember: If a set is hard to count, maybe we should try counting its complement
Let be the event that the ith person does get their own dish back. Then,
Question: Suppose n people order n different dishes. Unfortunately, the waiter did not mark positions. He has the correct n dishes, but gives a random dish to each person. What is the probability that no one has the dish they ordered placed in front of them?
Restaurant Example
Applying the Inclusion-Exclusion Rule we get
Restaurant Example
Applying the Inclusion-Exclusion Rule we get
Restaurant Example
Each k-tuple in the equation (i.e. singles, doubles, etc.), represents the number of dish assignments where exactly k people get their correct dish
k-tuple = (# of ways you can choose groups of k people) x (# of ways you can assign the correct dishes to that group)
Let’s first try to come up with a formula for the number of ways you can choose groups of people
Restaurant Example
How many individuals are there?
How many pairs are there?
How many triplets are their?
Restaurant Example
How many individuals are there?
How many pairs are there?
How many triplets are their?
Restaurant Example
How many individuals are there?
How many pairs are there?
How many triplets are their?
Restaurant Example
How many individuals are there?
How many pairs are there?
How many triplets are their?
Restaurant Example
How many individuals are there?
How many pairs are there?
How many triplets are there?
Restaurant Example
How many individuals are there?
How many pairs are there?
How many triplets are there?
Restaurant Example
How many individuals are there?
How many pairs are there?
How many triplets are there?
Restaurant Example
Have we made progress??
Restaurant Example
Have we made progress??
# of groups of 1 person
# of groups of 2 people
# of groups of n people
Restaurant Example
Have we made progress??
# of groups of 1 person
# of groups of 2 people
# of groups of n people
# of dish assignments s.t. first 1 person has their dish
# of dish assignments s.t. first 2 people have their dishes
# of dish assignments s.t. first 3 people have their dishes
Restaurant Example
Have we made progress??
Restaurant Example (Recap)
Restaurant Example (Recap)
Restaurant Example (Recap)
Restaurant Example (Recap)
Restaurant Example (Recap)
Restaurant Example
Almost there!
The number of ways for the the first k out of n people to get the dishes that they ordered (i.e. number of dish assignments s.t. k people have their own dish).
Restaurant Example
Almost there!
The number of ways for the the first k out of n people to get the dishes that they ordered (i.e. number of dish assignments s.t. only k people have their own dish).
Restaurant Example
Size of event space:
Restaurant Example
Size of event space:
Restaurant Example
Size of event space:
k-tuples from before
Restaurant Example
Size of event space:
Restaurant Example
Size of event space:
Restaurant Example
The probability that no one gets their dish back is
Restaurant Example
The probability that no one gets their dish back is
Restaurant Example
As n approaches infinity the probability that no one gets their dish converges
Restaurant Example (Bonus)
Here’s another approach that uses less counting