BTT Mathematics / Primary Mathematics Learning Hub / Catalan Numbers
Catalan numbers count many structures that are balanced, nested or non-crossing. The first values are
C0=1, C1=1, C2=2, C3=5, C4=14, C5=42, C6=132.
These numbers appear in several apparently different problems: paths that never cross below a boundary, balanced pairs of opening and closing marks, triangulations of a convex polygon, and non-crossing pairings around a circle.
This guide is Primary Mathematics enrichment. The point is not to memorize a famous sequence. The mathematical job is to identify why the same recursive structure appears in different settings and to count small cases carefully enough that the pattern can be justified.
It extends Systematic Listing and Logical Counting, Pascal’s Triangle and Path Counting and Route Networks and Traversal Puzzles.
Formal generating functions or advanced recurrence solving are outside this guide. Use the MOE Primary curriculum page and the learner’s school programme for required content.
Balanced paths · Balanced structures · Polygon triangulations · Non-crossing pairings · Recursive splitting · 24 questions · Worked answers
1. Balanced up/down paths never fall below the baseline
Consider a path made from U=(1,+1) and D=(1,−1). A balanced path with n U-steps and n D-steps starts at height zero, ends at height zero and never goes below height zero.
Worked example A: One pair
With one U and one D, only UD is valid. DU goes below zero immediately. Thus C1=1.
Worked example B: Two pairs
The valid paths are UUDD and UDUD. Therefore C2=2.
Worked example C: Three pairs
The five valid paths are:
UUUDDD
UUDUDD
UUDDUD
UDUUDD
UDUDUD
Hence C3=5.
Worked example D: Compare with unrestricted paths
With three U and three D steps, there are C(6,3)=20 unrestricted arrangements. Only five stay at or above the baseline throughout. The Catalan restriction is a path condition, not merely a fixed number of each step.
2. Balanced bracket strings obey the same rule
Interpret U as an opening bracket and D as a closing bracket. “Never below zero” becomes “never close more brackets than have already been opened.” Ending at zero means every opening bracket is eventually matched.
Worked example E: Two pairs
The two valid structures are (()) and ()().
Worked example F: Three pairs
There are five:
((()))
(()())
(())()
()(())
()()()
Worked example G: Invalid structure
())( uses two opening and two closing brackets, but at the third symbol it has closed more pairs than are open. Equal totals are not enough; every prefix must also be valid.
Worked example H: Translate path to brackets
Path UUDUDD corresponds to (()()). Every height records the number of currently open unmatched pairs.
3. Convex polygon triangulations are Catalan-counted
A triangulation divides a convex polygon into triangles using non-crossing diagonals between existing vertices.
Worked example I: Triangle
A triangle needs no diagonal. There is 1 triangulation, matching C1=1 when the polygon has n+2=3 vertices.
Worked example J: Quadrilateral
A quadrilateral can be triangulated by either diagonal. There are 2 triangulations, matching C2=2.
Worked example K: Pentagon
A convex pentagon has 5 triangulations, matching C3=5.
Worked example L: Hexagon
A convex hexagon has 14 triangulations, matching C4=14.
Number of triangles produced
Every triangulation of a convex m-gon uses exactly m−3 diagonals and produces m−2 triangles. This is separate from the number of distinct triangulations.
4. Non-crossing pairings around a circle give the same counts
Place 2n labelled points around a circle. Pair the points with chords so that no two chosen chords cross in the interior. The number of complete non-crossing pairings is Cn.
Worked example M: Four points
For four points around a circle, there are 2 non-crossing perfect pairings. The third possible pairing uses the two diagonals and crosses.
Worked example N: Six points
There are 5 non-crossing perfect pairings.
Worked example O: Eight points
There are 14 non-crossing perfect pairings.
Why the first partner splits the problem
Fix one starting point. If it is paired with another point, the chord separates the remaining points into two independent regions. Each region must contain an even number of points and can be paired independently without crossing the chosen chord.
5. Recursive splitting creates the Catalan recurrence
The Catalan numbers satisfy
Cn = C0C(n−1)+C1C(n−2)+…+C(n−1)C0.
This says: choose the first split, then multiply the number of valid structures on the left and right, and finally add across all possible split positions.
Worked example P: C3
C3=C0C2+C1C1+C2C0=1×2+1×1+2×1=5.
Worked example Q: C4
C4=C0C3+C1C2+C2C1+C3C0=5+2+2+5=14.
Worked example R: C5
C5=1×14+1×5+2×2+5×1+14×1=14+5+4+5+14=42.
Worked example S: Balanced-path interpretation
Every non-empty balanced path begins with U. Match this first U with the D that first returns the path to height zero. The steps inside that pair form one smaller balanced path; the steps after it form another. Summing over all possible inside sizes gives the recurrence.
Worked example T: Why multiplication appears
If the inside region has 2 possible structures and the outside region has 5, then there are 2×5=10 combined structures because every valid inside choice can be paired with every valid outside choice.
6. Practice: 24 original questions
Questions 1–8: Balanced paths and brackets
1. List the valid balanced U/D paths with one U and one D.
2. List the two valid paths with two U and two D.
3. How many valid paths use three U and three D?
4. Is UDDU a valid balanced path? Explain.
5. Translate UUDUDD into brackets.
6. How many balanced bracket strings use two pairs?
7. How many balanced bracket strings use three pairs?
8. Explain why equal numbers of opening and closing brackets do not by themselves guarantee validity.
Questions 9–16: Triangulations and pairings
9. How many triangulations does a triangle have?
10. How many triangulations does a convex quadrilateral have?
11. How many triangulations does a convex pentagon have?
12. How many triangulations does a convex hexagon have?
13. How many triangles appear in any triangulation of a convex hexagon?
14. How many diagonals are used in any triangulation of a convex hexagon?
15. How many non-crossing perfect pairings are there on four points around a circle?
16. How many on six points?
Questions 17–24: Catalan recurrence and values
17. Given C0=1,C1=1,C2=2, compute C3 using the recurrence.
18. Given C0=1,C1=1,C2=2,C3=5, compute C4.
19. Compute C5 from C0 through C4.
20. State C6.
21. How many balanced paths use four U and four D steps?
22. How many non-crossing perfect pairings are there on eight points around a circle?
23. How many triangulations does a convex seven-sided polygon have?
24. Explain why the first matched pair in a balanced structure naturally splits the remainder into two independent smaller structures.
7. Worked answers
Answers 1–8
1. UD.
2. UUDD and UDUD.
3. 5.
4. No. After UDD the height is −1, so the path has gone below the baseline.
5. (()()).
6. 2.
7. 5.
8. A prefix may close more pairs than have been opened, which corresponds to the path falling below zero.
Answers 9–16
9. 1.
10. 2.
11. 5.
12. 14.
13. 4 triangles. A convex m-gon gives m−2 triangles.
14. 3 diagonals. A convex m-gon uses m−3 diagonals.
15. 2.
16. 5.
Answers 17–24
17. 5. 1×2+1×1+2×1.
18. 14. 1×5+1×2+2×1+5×1.
19. 42. 14+5+4+5+14.
20. 132.
21. 14. This is C4.
22. 14. Eight points means n=4 pairs.
23. 42. A seven-gon has n=5 in the Cn triangulation count.
24. Once the first opening element is matched, the material inside that match and the material after it cannot interfere with one another; each must itself be valid, so their counts multiply for a fixed split and then add across possible split sizes.
8. Teaching and transfer
If a learner memorizes 1,1,2,5,14 without meaning, begin with two-pair paths or bracket strings and list them completely. The number sequence should emerge from a clear constraint.
When unrestricted path counts are confused with Catalan counts
Ask whether the path is allowed below the baseline. Pascal-style path counting counts all move arrangements; Catalan counting keeps only those respecting a barrier condition.
When triangulations are counted by drawing random diagonals
Require non-crossing diagonals and a complete division into triangles. Use a fixed vertex or diagonal to organize cases systematically.
When the recurrence seems arbitrary
Identify the first matched pair. It creates two independent smaller regions. This physical or diagrammatic split explains both multiplication and addition in the recurrence.
When different Catalan models seem unrelated
Translate one into another. Balanced brackets become up/down paths; the first matched pair becomes a non-crossing separator. The same recursive structure survives the change in representation.
Continue through this enrichment collection
For quotient-based fraction representations, use Continued Fractions, Convergents and Rational Approximation. For polyhedral structure, use Euler Characteristic, Polyhedra, Faces, Edges and Vertices. For self-similar constructions, use Fractals, Self-Similarity and Scaling Patterns.
Return to the BTT Primary Mathematics Learning Hub.
Original enrichment guide with 24 original practice questions and separate worked answers. Catalan indexing in this guide uses C0=1, C1=1.