🔢 mathematics

Classical Fibonacci compositions

This paper provides tiling-based proofs for three classical restricted integer compositions that enumerate to the Fibonacci sequence, explores their application in proving Fibonacci identities, and demonstrates via MacMahon's conjugation that subsets of compositions for any $n \ge 2$ satisfy the Fibonacci recurrence.

Original authors: Brian Hopkins

Published 2026-06-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Brian Hopkins

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a long wooden plank, say 5 feet long. Your job is to cover this plank completely using smaller wooden blocks. You can't leave any gaps, and you can't let the blocks hang over the edge.

This paper is about counting how many different ways you can arrange these blocks to cover the plank, but with a twist: the rules change depending on which "game" you are playing. The author, Brian Hopkins, shows that three very different games all lead to the same magical number sequence: the Fibonacci sequence (1, 1, 2, 3, 5, 8, 13...).

Here is a breakdown of the three games and the big discovery at the end, explained simply.

The Three Games

Game 1: The Poet's Rhythm (Ancient India)
Imagine you are writing a line of poetry that must be exactly 5 beats long. In ancient Sanskrit poetry, syllables come in two sizes:

Short syllables: Like a quick tap (1 beat).
Long syllables: Like a held note (2 beats).

The question is: How many different patterns of short and long syllables can you make to fill exactly 5 beats?

You could use five short taps: tap-tap-tap-tap-tap.
You could use two long notes and one short: long-long-short.
You could mix them up in many ways.

The paper proves that if you count all these patterns for a 5-beat line, you get 8 patterns. If you do this for a 6-beat line, you get 13. This matches the Fibonacci sequence perfectly. The author uses a visual trick: imagine the plank as a floor, and you are tiling it with 1x1 squares (short syllables) and 1x2 dominoes (long syllables).

Game 2: The Victorian Odd-Only Challenge (19th Century England)
Now, imagine a new rule. You still have a plank of length 5, but you can only use blocks with odd numbers of units (1, 3, 5, 7...). You cannot use a block of size 2 or 4.

You can use a 5-block.
You can use a 3-block and a 1-block.
You can use three 1-blocks and a 2-block? No! 2 is even, so that's forbidden.

The author shows that even with this strict "odd numbers only" rule, the number of ways to fill a 5-unit plank is 5. For a 6-unit plank, it's 8. Again, we hit the Fibonacci numbers.

Game 3: The "No Tiny Blocks" Challenge (19th Century England)
For the third game, the rule is the opposite: You are forbidden from using the smallest block (size 1). You must use blocks that are at least size 2 (2, 3, 4, 5...).

For a 5-unit plank, you can use a single 5-block.
You can use a 3-block and a 2-block.
You can use a 2-block and a 3-block.
You cannot use a 1-block.

The count for a 5-unit plank here is 3. For a 6-unit plank, it's 5. Once again, the Fibonacci sequence appears.

The "Magic Mirror" Trick (Conjugation)

The paper introduces a clever tool invented by a mathematician named MacMahon called conjugation. Think of this as a magic mirror.

When you arrange your blocks, you can imagine the spaces between the blocks as "cuts" and the places where blocks touch as "joins." If you look at your arrangement in the magic mirror, you swap every "cut" to a "join" and every "join" to a "cut."

If you had a long block (like a 3), the mirror might break it into smaller pieces.
If you had many small blocks, the mirror might glue them together into a big block.

The author uses this mirror to show a surprising connection between the games.

The Grand Finale: The Fibonacci Recurrence

The most exciting part of the paper is the final theorem. It connects all three games together.

The Fibonacci sequence works by adding the two previous numbers to get the next one (e.g., $5 + 3 = 8$ ). The paper proves that for any plank size $n$ :

The number of ways to tile it with only 1s and 2s (Game 1) is exactly equal to:
- The number of ways to tile it with only odd numbers (Game 2)
- PLUS
- The number of ways to tile it with numbers 2 or bigger (Game 3).

In simple terms:
If you take all the valid "Odd-Only" arrangements and all the valid "No-Tiny-Blocks" arrangements, and you mix them together (using a special sorting method involving the magic mirror), you get exactly the same total number of arrangements as the "1s and 2s" game.

This proves that the famous Fibonacci rule ( $F_n + F_{n-1} = F_{n+1}$ ) isn't just a math trick; it's a physical reality about how you can break a line of wood into pieces under different rules. The paper provides a visual, step-by-step "recipe" to turn a solution from one game into a solution for another, proving they are two sides of the same coin.

Technical Summary: Classical Fibonacci Compositions

Problem Statement
The paper investigates three distinct types of restricted integer compositions whose enumeration counts match the Fibonacci sequence ( $F_n$ ). While the general count of compositions of an integer $n$ is known to be $2^{n-1}$ , this work focuses on subsets defined by specific constraints on their parts:

Prosodic Compositions ( $C_{12}(n)$ ): Compositions of $n$ where parts are restricted to the set $\{1, 2\}$ . This model originates from ancient Indian prosody (specifically the works of Pi˙ngala and later scholars) regarding the counting of long and short syllables in poetic meters.
Odd-Part Compositions ( $C_o(n)$ ): Compositions of $n$ where all parts are odd integers. This type was analyzed by Augustus De Morgan in 19th-century England.
Large-Part Compositions ( $\hat{C}_1(n)$ ): Compositions of $n$ where all parts are at least 2. This type was considered by Arthur Cayley in 1876.

The paper aims to provide combinatorial proofs for the enumeration of these sets and demonstrate how they satisfy the Fibonacci recurrence relation ( $F_n = F_{n-1} + F_{n-2}$ ) through tiling arguments.

Methodology
The primary methodology employed is combinatorial proof via tiling arguments. The author models a composition of $n$ as a tiling of a $1 \times n$ board:

A part of size $k$ corresponds to a $1 \times k$ tile.
The sequence of parts corresponds to the arrangement of tiles.
Cut/Join Sequences: The author utilizes Percy MacMahon's concept of representing compositions as binary sequences of "Cut" (C) and "Join" (J) choices between $n$ cells.
Bijections: The core of the proofs involves establishing explicit bijections between the set of compositions of $n$ and the disjoint union of compositions of $n-1$ and $n-2$ . This structural decomposition directly mirrors the Fibonacci recurrence.
Conjugation: The paper employs MacMahon's notion of "conjugate compositions," where the cut/join sequence of a composition is inverted (swapping C and J) to generate a new composition. This operation is central to the final theorem.

Key Contributions and Results

Enumeration of Prosodic Compositions ( $C_{12}(n)$ ):
- Result: $c_{12}(n) = F_{n+1}$ .
- Proof: A bijection is established between $C_{12}(n)$ and $C_{12}(n-1) \cup C_{12}(n-2)$ . A composition in $C_{12}(n-2)$ is mapped to $C_{12}(n)$ by appending a part of 2 (a domino), while a composition in $C_{12}(n-1)$ is mapped by appending a part of 1 (a square). The distinction lies in the final part of the resulting composition.
Enumeration of Odd-Part Compositions ( $C_o(n)$ ):
- Result: $c_o(n) = F_n$ .
- Proof: A bijection maps $C_o(n-2)$ to $C_o(n)$ by increasing the final part $k$ to $k+2$ (preserving oddness), and maps $C_o(n-1)$ to $C_o(n)$ by appending a part of 1. The sets are distinguished by whether the final part is 1 or $\ge 3$ .
Enumeration of Large-Part Compositions ( $\hat{C}_1(n)$ ):
- Result: $\hat{c}_1(n) = F_{n-1}$ for $n \ge 2$ .
- Proof: A bijection maps $\hat{C}_1(n-2)$ to $\hat{C}_1(n)$ by appending a part of 2, and maps $\hat{C}_1(n-1)$ to $\hat{C}_1(n)$ by increasing the final part $k$ to $k+1$ . Distinction is made based on whether the final part is exactly 2 or $\ge 3$ .
Synthesis via Conjugation (Theorem 4):
- Result: For $n \ge 2$ , there exists a bijection $C_{12}(n) \cong \hat{C}_1(n) \cup C_o(n)$ .
- Significance: This result provides a direct combinatorial realization of the identity $F_{n+1} = F_n + F_{n-1}$ by showing that the set of compositions with parts $\{1, 2\}$ can be partitioned (via a specific mapping involving conjugation) into the sets of compositions with parts $\ge 2$ and compositions with odd parts.
- Mechanism: The proof utilizes MacMahon's conjugation. For a composition in $\hat{C}_1(n)$ , its conjugate has no adjacent "Join" terms (no parts $>2$ ) and starts/ends with 1; removing these boundary 1s and appending a 2 yields an element in $C_{12}(n)$ . For $C_o(n)$ , odd parts are expanded into sequences of 2s and a final 1.

Significance and Claims
The paper claims to provide rigorous combinatorial proofs for well-known enumeration results, connecting ancient Indian prosody with 19th-century English mathematics. The author emphasizes that while the numerical results ( $c_{12}(n) = F_{n+1}$ , etc.) were known, the specific bijective proofs using tiling and conjugation offer distinct tools for proving Fibonacci identities.

The author notes that different composition types offer varying degrees of ease for proving specific identities (e.g., sums of even or odd indexed Fibonacci numbers). The paper concludes modestly, stating that the bijection in Theorem 4 (linking $C_{12}$ , $\hat{C}_1$ , and $C_o$ ) may be a novel contribution, providing a unified combinatorial framework for the recurrence relation $F_{n+1} = F_n + F_{n-1}$ through the lens of restricted integer compositions. The work serves as a resource for combinatorial proofs of Fibonacci identities, referencing the author's own book and the work of Benjamin and Quinn as context for these methods.

The Three Games

The "Magic Mirror" Trick (Conjugation)

The Grand Finale: The Fibonacci Recurrence

Technical Summary: Classical Fibonacci Compositions

More like this