Catalan numbers & lattice-path counting
Monotone lattice paths from (0,0) to (m,n) number C(m+n, n), since a path is determined by which of its steps go up. Constraining a path to stay below the diagonal gives the Catalan numbers Cₙ = C(2n,n)/(n+1), counted by the reflection principle. They also count balanced bracket strings, binary tree shapes and triangulations of a polygon.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Count unconstrained paths with a binomialA path with m rights and n ups is a word in R and U, so there are C(m+n, n) of them.
- Apply reflection for the constrained countReflect the offending prefix of a bad path to build a bijection with paths to a shifted endpoint, then subtract.
- Use the Catalan formulaCₙ = C(2n,n)/(n+1), giving 1, 1, 2, 5, 14, 42, 132.
- Recognise Catalan structuresBalanced brackets, binary trees, non-crossing chords, and polygon triangulations all reduce to the same count.
Worked example
How many monotone lattice paths from (0,0) to (4,3), and how many balanced bracket strings with 4 pairs?
- Paths: 7 steps of which 3 are up, so C(7,3).
- = 35.
- Balanced brackets with 4 pairs: the Catalan number C₄ = C(8,4)/5.
- = 70/5.
Answer. 35 lattice paths; 14 balanced bracket strings with 4 pairs.
Where marks get dropped
These are the specific errors that cost credit on catalan numbers & lattice-path counting questions — QED's rubric penalises each of them separately.
- Using C(m+n, n) for a constrained path count. The staying-below-the-diagonal condition needs reflection or the Catalan formula.
- Forgetting the +1 in the denominator of the Catalan formula, which gives C(2n,n) — the unconstrained count instead.
- Confusing Cₙ with the binomial coefficient notation C(n,k). Context and the single subscript distinguish them.
Practise this until it is automatic
Unlimited fresh questions
QED generates new catalan numbers & lattice-path counting problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Combinatorics mastery is tracked so you know when this is exam-ready.
Catalan numbers & lattice-path counting — frequently asked questions
What is the reflection principle?
Bad paths crossing a boundary are put in bijection with all paths to a reflected endpoint, so the bad count is a binomial and can be subtracted from the total.
What do Catalan numbers count?
Balanced brackets, binary tree shapes, triangulations of an (n+2)-gon, non-crossing chord diagrams, and Dyck paths — dozens of families, all bijective with each other.
What is the Catalan recurrence?
Cₙ₊₁ = Σ_{k=0}^{n} CₖCₙ₋ₖ, obtained by splitting a structure at its first return to the axis, or at the root of a binary tree.
The rest of Combinatorics
Counting principles, permutations, combinations. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Sum & product rules
- 2Permutations & combinations
- 3Binomial theorem & Pascal’s triangle
- 4The pigeonhole principle
- 5Inclusion–exclusion
- 6Counting with repetition (stars & bars)
- 7Derangements & counting surjections
- 8Double counting & bijective proofs
- 9Setting up & solving counting recurrences
- 10Generating functions — an introduction
- 11Multinomial coefficients & repeated items
- 12Hockey stick & Vandermonde identities
- 13Catalan numbers & lattice-path counting
Ready to make catalan numbers & lattice-path counting exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →