A derangement is an order in which nothing stays in its own place. By inclusion and exclusion there are Dn=n!(1−1!1+2!1−⋯+n!(−1)n)
Lesson 3 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
count derangements by inclusion and exclusion and by a recurrence;
count orders with exactly k items in place;
recognise problems counted by the Catalan numbers and use the formula.
Letters in the wrong envelopes
A secretary writes n letters and addresses n envelopes, then puts the letters in at random, one in each. In how many ways does every letter go into a wrong envelope?
An order of 1,2,…,n in which no number stays in its own place is called a derangement. Let Dn be the number of derangements of n items. For n=3 the derangements are 231 and 312, so D3=2.
Counting by inclusion and exclusion
Let Ai be the set of orders that keep item i in place. We want the orders in none of the Ai.
Orders that keep a chosen set of k items in place: (n−k)!.
There are (kn) ways to choose the k items.
Inclusion and exclusion subtracts the orders with one fixed item, adds back those with two, and so on:
Dn=k=0∑n(−1)k(kn)(n−k)!.
Each term simplifies, because (kn)(n−k)!=k!n!. So
Dn=n!k=0∑nk!(−1)k.
The sum is the start of the series for e−1. So n!Dn tends to e1≈0.368, and in fact Dn is the whole number nearest to en! for every n≥1.
A recurrence for derangements
Look at where item 1 goes. Say it goes to place k, which is one of n−1 choices. Now look at item k.
Item k goes to place 1. The two swap, and the other n−2 items form a derangement: Dn−2 ways.
Item k does not go to place 1. Treat place 1 as the forbidden place of item k. Then the n−1 items other than 1 form a derangement: Dn−1 ways.
So
Dn=(n−1)(Dn−1+Dn−2),D1=0,D2=1.
This gives D3=2, D4=9, D5=44, D6=265. A second form, Dn=nDn−1+(−1)n, follows from the first by induction.
Exactly k in place
To keep exactlyk items in place, choose them in (kn) ways and derange the rest:
(kn)Dn−k.
For 5 letters with exactly one in the right envelope: (15)D4=5×9=45.
The Catalan numbers
How many strings of n opening and n closing brackets are balanced, so that no prefix has more closing than opening brackets? For n=3 there are five:
((())) and (()());
(())() and ()(());
()()().
These numbers are the Catalan numbersCn: C0=1,1,2,5,14,42,132.
A recurrence. In a balanced string of n+1 pairs, the first bracket "(" is closed by some ")". Inside that pair sits a balanced string of i pairs, and after it a balanced string of n−i pairs. So
Cn+1=i=0∑nCiCn−i.
A formula. Draw a string as a path on a grid: "(" is a step right and ")" is a step up. A balanced string is a path from (0,0) to (n,n) that never goes above the diagonal. There are (n2n) paths in all. A bad path touches the line y=x+1. Reflect its part after the first touch in that line. This turns bad paths one to one into all paths to (n−1,n+1), and there are (n+12n) of them. So
Cn=(n2n)−(n+12n)=n+11(n2n).
A 4 by 4 grid with the diagonal from the bottom left to the top right drawn dashed. A blue path of right and up steps goes from the bottom left corner to the top right corner and never goes above the diagonal. A red path crosses above the diagonal, touching the line one unit above it, and after that touch its reflected copy is drawn dotted, ending at the point (3, 5).
Other things counted by Cn. The ways to cut a convex polygon with n+2 sides into triangles by diagonals that do not cross. The ways to put brackets into a product of n+1 factors. A queue of 2n people where n pay with exact money and n need change, and the seller can always give change.
Practise with new numbers
Try it in Python
The program lists every order of n items and counts the derangements. It then counts balanced bracket strings by trying every string, and compares both counts with the formulas.
Common mistakes
Subtracting only the order with all items in place.n!−1 is far too many.
Using Dn−k without (kn). The items that stay in place must be chosen too.
Mixing up Cn and (n2n). The Catalan number divides by n+1.
A polygon with n sides. It has Cn−2 triangulations, not Cn.
Remember these
Dn=n!k=0∑nk!(−1)k, the whole number nearest to en!.
Dn=(n−1)(Dn−1+Dn−2), with D1=0 and D2=1.
Exactly k fixed: (kn)Dn−k.
Cn=n+11(n2n) counts balanced brackets, diagonal paths and triangulations.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Find D4 from the recurrence.
Four friends each bring a gift and draw one at random. What is the probability that nobody draws their own gift?
In how many orders of 1,2,3,4,5 does exactly one number stay in its place?
Use the formula to find C4.
In how many ways can a convex pentagon be cut into triangles by diagonals that do not cross?
References
R. A. Brualdi, Introductory Combinatorics, Chapter 6 on derangements and Chapter 8 on the Catalan numbers.
R. P. Stanley, Catalan Numbers, Cambridge University Press, 2015.
Enroll free in Recurrences and Counting by Recursion
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.