Discrete mathematics and graph theory · Maths EE idea · Accessible

Derangements and the hat-check problem

A research question to start from

What is the probability that nobody gets their own hat back, and why does it approach 1/e?

A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.

Why it works as a maths EE

Inclusion–exclusion and a recurrence give the same answer, with a surprising limit.

Mathematics you would need

Inclusion–exclusion
Recurrences
Series for e
Probability

Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.

One possible line of attack

Count derangements by inclusion–exclusion.
Derive the recurrence another way.
Show the limit and how fast it is approached.

Scope and difficulty

Accessible. Accessible.

Pitfalls

One method only.
Limit asserted.

Where to start reading

Search a library catalogue or a university's open lecture notes for: derangements inclusion exclusion recurrence 1/e. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).

Make it your EE

Plan this EEOpens the free EE planner with this question as a starting point. Sharpen the questionSix quick checks for a focused research question. Self-check a draftCheck a section against each criterion, free.