Discrete mathematics and graph theory · Maths EE idea · Solid
The Catalan numbers everywhere
A research question to start from
Why do bracket sequences, lattice paths and polygon triangulations all give the Catalan numbers?
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
Several bijections and one formula: the argument links them all.
Mathematics you would need
- Counting and binomial coefficients
- Bijections
- Recurrences
- The reflection principle
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 each structure for small n.
- Derive the formula with the reflection principle.
- Construct bijections between at least two structures.
Scope and difficulty
Solid. Solid.
Pitfalls
- Listing applications.
- Bijections asserted, not proved.
Where to start reading
Search a library catalogue or a university's open lecture notes for: Catalan numbers reflection principle proof; bijection triangulations brackets. 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
Similar ideas
- Derangements and the hat-check problemGraph theoryAccessible
- Colouring graphs to build timetablesGraph theorySolid
- Why greedy works for spanning treesGraph theoryAccessible
- How good is a quick tour?Graph theoryAmbitious
All discrete mathematics and graph theory ideas · the full ideas library