HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Recurrences and Counting by Recursion
  1. 1Setting up a recurrence
  2. 2Solving linear recurrences
  3. 3Derangements and Catalan numbers
  1. Mathematics
  2. /Recurrences and Counting by Recursion
  3. /Derangements and Catalan numbers

Course 30.2·Lesson 3 of 3

Derangements and Catalan numbers

A derangement is an order in which nothing stays in its own place. By inclusion and exclusion there are Dn=n!(1−11!+12!−⋯+(−1)nn!)D_n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \dots + \frac{(-1)^n}{n!}\right)Dn​=n!(1−1!1​+2!1​−⋯+n!(−1)n​)

Lesson 3 of 3Show all lessonsHide
Recurrences and Counting by Recursion
  1. 1Setting up a recurrence
  2. 2Solving linear recurrences
  3. 3Derangements and Catalan numbers

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 kkk items in place;
  • recognise problems counted by the Catalan numbers and use the formula.

Letters in the wrong envelopes

A secretary writes nnn letters and addresses nnn 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,…,n1, 2, \dots, n1,2,…,n in which no number stays in its own place is called a derangement. Let DnD_nDn​ be the number of derangements of nnn items. For n=3n = 3n=3 the derangements are 231231231 and 312312312, so D3=2D_3 = 2D3​=2.

Counting by inclusion and exclusion

Let AiA_iAi​ be the set of orders that keep item iii in place. We want the orders in none of the AiA_iAi​.

  • Orders that keep a chosen set of kkk items in place: (n−k)!(n - k)!(n−k)!.
  • There are (nk)\binom{n}{k}(kn​) ways to choose the kkk items.

Inclusion and exclusion subtracts the orders with one fixed item, adds back those with two, and so on:

Dn=∑k=0n(−1)k(nk)(n−k)!.\displaystyle D_n = \sum_{k=0}^{n} (-1)^k \binom{n}{k}(n - k)!.Dn​=k=0∑n​(−1)k(kn​)(n−k)!.

Each term simplifies, because (nk)(n−k)!=n!k!\binom{n}{k}(n - k)! = \dfrac{n!}{k!}(kn​)(n−k)!=k!n!​. So

Dn=n!∑k=0n(−1)kk!.\displaystyle D_n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!}.Dn​=n!k=0∑n​k!(−1)k​.

The sum is the start of the series for e−1e^{-1}e−1. So Dnn!\dfrac{D_n}{n!}n!Dn​​ tends to 1e≈0.368\dfrac{1}{e} \approx 0.368e1​≈0.368, and in fact DnD_nDn​ is the whole number nearest to n!e\dfrac{n!}{e}en!​ for every n≥1n \ge 1n≥1.

A recurrence for derangements

Look at where item 111 goes. Say it goes to place kkk, which is one of n−1n - 1n−1 choices. Now look at item kkk.

  • Item kkk goes to place 111. The two swap, and the other n−2n - 2n−2 items form a derangement: Dn−2D_{n-2}Dn−2​ ways.
  • Item kkk does not go to place 111. Treat place 111 as the forbidden place of item kkk. Then the n−1n - 1n−1 items other than 111 form a derangement: Dn−1D_{n-1}Dn−1​ ways.

So

Dn=(n−1)(Dn−1+Dn−2),D1=0,D2=1.\displaystyle D_n = (n - 1)(D_{n-1} + D_{n-2}), \quad D_1 = 0, \quad D_2 = 1.Dn​=(n−1)(Dn−1​+Dn−2​),D1​=0,D2​=1.

This gives D3=2D_3 = 2D3​=2, D4=9D_4 = 9D4​=9, D5=44D_5 = 44D5​=44, D6=265D_6 = 265D6​=265. A second form, Dn=nDn−1+(−1)nD_n = nD_{n-1} + (-1)^nDn​=nDn−1​+(−1)n, follows from the first by induction.

Exactly k in place

To keep exactly kkk items in place, choose them in (nk)\binom{n}{k}(kn​) ways and derange the rest:

(nk)Dn−k.\displaystyle \binom{n}{k}D_{n-k}.(kn​)Dn−k​.

For 555 letters with exactly one in the right envelope: (51)D4=5×9=45\binom{5}{1}D_4 = 5 \times 9 = 45(15​)D4​=5×9=45.

The Catalan numbers

How many strings of nnn opening and nnn closing brackets are balanced, so that no prefix has more closing than opening brackets? For n=3n = 3n=3 there are five:

  • ((())) and (()());
  • (())() and ()(());
  • ()()().

These numbers are the Catalan numbers CnC_nCn​: C0=1,1,2,5,14,42,132C_0 = 1, 1, 2, 5, 14, 42, 132C0​=1,1,2,5,14,42,132.

A recurrence. In a balanced string of n+1n + 1n+1 pairs, the first bracket "(" is closed by some ")". Inside that pair sits a balanced string of iii pairs, and after it a balanced string of n−in - in−i pairs. So

Cn+1=∑i=0nCiCn−i.\displaystyle C_{n+1} = \sum_{i=0}^{n} C_iC_{n-i}.Cn+1​=i=0∑n​Ci​Cn−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)(0, 0)(0,0) to (n,n)(n, n)(n,n) that never goes above the diagonal. There are (2nn)\binom{2n}{n}(n2n​) paths in all. A bad path touches the line y=x+1y = x + 1y=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)(n - 1, n + 1)(n−1,n+1), and there are (2nn+1)\binom{2n}{n+1}(n+12n​) of them. So

Cn=(2nn)−(2nn+1)=1n+1(2nn).\displaystyle C_n = \binom{2n}{n} - \binom{2n}{n + 1} = \frac{1}{n + 1}\binom{2n}{n}.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 CnC_nCn​. The ways to cut a convex polygon with n+2n + 2n+2 sides into triangles by diagonals that do not cross. The ways to put brackets into a product of n+1n + 1n+1 factors. A queue of 2n2n2n people where nnn pay with exact money and nnn need change, and the seller can always give change.

Practise with new numbers

Try it in Python

The program lists every order of nnn items and counts the derangements. It then counts balanced bracket strings by trying every string, and compares both counts with the formulas.

Read it first. Then run it. Do the brute-force counts match the formulas?

1. Change n = 5 to n = 6. How long does the brute force take now?

2. Count the orders of 555 items with exactly two items in place. Predict it with (52)D3\binom{5}{2}D_3(25​)D3​ first.

Common mistakes

  • Subtracting only the order with all items in place. n!−1n! - 1n!−1 is far too many.
  • Using Dn−kD_{n-k}Dn−k​ without (nk)\binom{n}{k}(kn​). The items that stay in place must be chosen too.
  • Mixing up CnC_nCn​ and (2nn)\binom{2n}{n}(n2n​). The Catalan number divides by n+1n + 1n+1.
  • A polygon with nnn sides. It has Cn−2C_{n-2}Cn−2​ triangulations, not CnC_nCn​.

Remember these

  • Dn=n!∑k=0n(−1)kk!D_n = n!\displaystyle\sum_{k=0}^{n}\frac{(-1)^k}{k!}Dn​=n!k=0∑n​k!(−1)k​, the whole number nearest to n!e\dfrac{n!}{e}en!​.
  • Dn=(n−1)(Dn−1+Dn−2)D_n = (n - 1)(D_{n-1} + D_{n-2})Dn​=(n−1)(Dn−1​+Dn−2​), with D1=0D_1 = 0D1​=0 and D2=1D_2 = 1D2​=1.
  • Exactly kkk fixed: (nk)Dn−k\binom{n}{k}D_{n-k}(kn​)Dn−k​.
  • Cn=1n+1(2nn)C_n = \dfrac{1}{n + 1}\dbinom{2n}{n}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.

  1. Find D4D_4D4​ from the recurrence.
  1. Four friends each bring a gift and draw one at random. What is the probability that nobody draws their own gift?
  1. In how many orders of 1,2,3,4,51, 2, 3, 4, 51,2,3,4,5 does exactly one number stay in its place?
  1. Use the formula to find C4C_4C4​.
  1. 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.
No payment. You can leave at any time.

Problems (2)

Six friends each bring a wrapped gift with their name on it…Hard · High School (11–12) · by StemPy Lab
A convex polygon with 9 sides is to be cut into triangles by drawing diagonals that do not cross…Advanced · High School (11–12) · by StemPy Lab

Python Labs (1)

That was the last lessonBack to the course: take the test
← Recurrences and Counting by Recursion
← Solving linear recurrencesNext →

Discussion (0)

Log in to join the discussion.

Loading…

of them, and
Dn=(n−1)(Dn−1+Dn−2)D_n = (n - 1)(D_{n-1} + D_{n-2})Dn​=(n−1)(Dn−1​+Dn−2​)
. About
1e\frac{1}{e}e1​
of all orders are derangements. The Catalan numbers
Cn=1n+1(2nn)C_n = \frac{1}{n + 1}\binom{2n}{n}Cn​=n+11​(n2n​)
count balanced brackets, paths that stay below a diagonal and triangulations.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

Derangements and Catalan numbersPython Lab · by StemPy Lab

Question Sets (1)

Recurrences and Recursion: Concept Check10 questions · by StemPy Lab

Notes (1)

Recurrences and Counting by Recursion: Quick RevisionNote · by StemPy Lab