The Central Idea
Suppose \(a_n\) counts the number of objects of size \(n\).
Then the sequence
\[ a_0,a_1,a_2,a_3,\ldots \]becomes a record of how the number of objects changes with size.
A recurrence such as
\[ \boxed{a_n=a_{n-1}+a_{n-2}} \]may arise because every size-\(n\) object falls into exactly one of two disjoint classes:
- one corresponding to a size-\(n-1\) object;
- one corresponding to a size-\(n-2\) object.
The recurrence then follows from counting those two cases.
Sequences as Counting Functions
A sequence may be viewed as a function
\[ n\longmapsto a_n \]where \(a_n\) counts objects associated with the integer \(n\).
Examples include:
- subsets of an \(n\)-element set;
- binary strings of length \(n\);
- tilings of a board of length \(n\);
- paths of a given length;
- partitions or compositions of an integer;
- arrangements satisfying restrictions.
A Counting Interpretation Gives Meaning to the Terms
The numerical sequence
\[ 1,\ 2,\ 4,\ 8,\ 16,\ldots \]has closed form
\[ 2^n \]if indexing begins at \(n=0\).
One combinatorial interpretation is:
\[ \boxed{2^n=\text{number of subsets of an }n\text{-element set}}. \]The same sequence also counts binary strings of length \(n\).
One Sequence Can Have Many Interpretations
A single sequence may count many apparently different kinds of objects.
For example, \(2^n\) counts:
- subsets of an \(n\)-element set;
- binary strings of length \(n\);
- yes/no decision patterns across \(n\) independent choices.
Discovering that two families are counted by the same sequence can reveal a hidden structural relationship.
Recursive Counting
A combinatorial recurrence is often derived by breaking a collection into smaller disjoint cases.
If \(a_n\) counts size-\(n\) objects and every such object belongs to exactly one of two cases counted by \(a_{n-1}\) and \(a_{n-2}\), then
\[ \boxed{a_n=a_{n-1}+a_{n-2}}. \]The addition principle justifies the recurrence.
Example: Tiling with Squares and Dominoes
Let \(T_n\) be the number of ways to tile a board of length \(n\) using:
- squares of length \(1\);
- dominoes of length \(2\).
Every tiling ends with exactly one of these two tile types.
Deriving the Tiling Recurrence
If a tiling ends in a square, remove that final square.
What remains is any valid tiling of length
\[ n-1. \]If a tiling ends in a domino, remove that domino.
What remains is any valid tiling of length
\[ n-2. \]Therefore,
\[ \boxed{T_n=T_{n-1}+T_{n-2}}. \]Initial Conditions for the Tiling Count
A board of length \(0\) has one empty tiling:
\[ T_0=1. \]A board of length \(1\) has one tiling:
\[ T_1=1. \]Then
\[ T_2=2,\qquad T_3=3,\qquad T_4=5. \]Thus,
\[ \boxed{1,\ 1,\ 2,\ 3,\ 5,\ 8,\ldots}. \]The tiling sequence is Fibonacci-type.
Why the Empty Object Often Counts as One
In combinatorics, there is often exactly one empty object of size \(0\).
For tilings, the empty board has one way to be tiled: use no tiles.
This convention makes recurrences and products behave naturally.
Therefore,
\[ \boxed{T_0=1} \]is not an arbitrary choice.
Example: Stair-Step Counting
Suppose a person climbs a staircase using steps of size \(1\) or \(2\).
Let \(S_n\) be the number of ways to reach stair \(n\).
Every route reaches stair \(n\) from either
\[ n-1 \]or
\[ n-2. \]Therefore,
\[ \boxed{S_n=S_{n-1}+S_{n-2}}. \]Same Recurrence, Different Objects
The tiling problem and stair-step problem count different objects.
Yet both satisfy the same recurrence and compatible initial conditions.
Therefore, they produce the same counting sequence.
This is a basic example of a combinatorial correspondence.
Binary Strings
Let \(B_n\) be the number of binary strings of length \(n\).
Each position may contain
\[ 0 \quad\text{or}\quad 1. \]Therefore,
\[ \boxed{B_n=2^n}. \]Recursive Interpretation of Binary Strings
A length-\(n\) binary string can be formed by appending either \(0\) or \(1\) to a length-\(n-1\) string.
Thus,
\[ B_n=2B_{n-1}. \]With
\[ B_0=1, \]we recover
\[ \boxed{B_n=2^n}. \]Subsets of an \(n\)-Element Set
Let \(S_n\) be the number of subsets of an \(n\)-element set.
Choose one distinguished element.
Every subset either:
- contains that element;
- does not contain that element.
Each case corresponds to a subset of the remaining \(n-1\) elements.
Therefore,
\[ S_n=2S_{n-1}. \]Combinatorial Proof that \(S_n=2^n\)
Since
\[ S_0=1 \]and
\[ S_n=2S_{n-1}, \]we obtain
\[ \boxed{S_n=2^n}. \]The recurrence follows directly from the include-or-exclude decision.
Sequences of Binomial Coefficients
For fixed \(n\), the sequence
\[ \binom n0,\binom n1,\binom n2,\ldots,\binom nn \]counts subsets by size.
Specifically,
\[ \boxed{ \binom nk = \text{number of }k\text{-element subsets of an }n\text{-element set} }. \]Pascal's Recurrence as a Counting Identity
The identity
\[ \boxed{ \binom nk = \binom{n-1}{k} + \binom{n-1}{k-1} } \]has a direct combinatorial interpretation.
Choose one distinguished element from the \(n\)-element set.
Deriving Pascal's Recurrence
A \(k\)-element subset either excludes the distinguished element or includes it.
If it excludes the element, choose all \(k\) elements from the remaining \(n-1\):
\[ \binom{n-1}{k}. \]If it includes the element, choose the remaining \(k-1\) elements from the other \(n-1\):
\[ \binom{n-1}{k-1}. \]Adding the disjoint cases proves Pascal's recurrence.
Row Sums of Pascal's Triangle
Every subset of an \(n\)-element set has some size \(k\) between \(0\) and \(n\).
Therefore,
\[ \sum_{k=0}^{n}\binom nk \]counts all subsets of the set.
Since there are \(2^n\) subsets,
\[ \boxed{ \sum_{k=0}^{n}\binom nk=2^n }. \]Combinatorial Identities Compare Two Counts
A combinatorial proof often counts the same collection in two different ways.
If both expressions count exactly the same objects, then the expressions must be equal.
This method can prove sequence identities without purely algebraic manipulation.
Example: Counting Ordered Pairs
Let \(C_n\) count ordered pairs
\[ (i,j) \]of nonnegative integers satisfying
\[ i+j=n. \]The possibilities are
\[ (0,n),(1,n-1),\ldots,(n,0). \]Therefore,
\[ \boxed{C_n=n+1}. \]Ordered Triples
Let \(D_n\) count ordered triples
\[ (i,j,k) \]of nonnegative integers satisfying
\[ i+j+k=n. \]This is a stars-and-bars problem.
The count is
\[ \boxed{ D_n=\binom{n+2}{2} }. \]Thus, a quadratic sequence can arise from a simple counting model.
Compositions of an Integer
A composition of \(n\) is an ordered sum of positive integers whose total is \(n\).
For example, the compositions of \(3\) are
\[ 3, \] \[ 1+2, \] \[ 2+1, \] \[ 1+1+1. \]Therefore, \(3\) has \(4\) compositions.
Counting Compositions
For \(n\ge1\), there are
\[ n-1 \]gaps between \(n\) ones:
\[ 1\ \square\ 1\ \square\cdots\square\ 1. \]At each gap, either place a separator or do not.
Therefore, the number of compositions is
\[ \boxed{2^{n-1}}. \]Restricted Compositions and Fibonacci-Type Counts
Suppose compositions are allowed to use only parts \(1\) and \(2\).
Let \(C_n\) count such compositions of \(n\).
Every composition begins with either:
\[ 1 \]or
\[ 2. \]Removing the first part leaves a composition of \(n-1\) or \(n-2\).
Therefore,
\[ \boxed{C_n=C_{n-1}+C_{n-2}}. \]Lattice Paths
A lattice path can move through a grid using specified step types.
Suppose a path from
\[ (0,0) \]to
\[ (m,n) \]may move only right or up.
Every path uses exactly \(m\) right steps and \(n\) up steps.
Counting Lattice Paths
A path consists of
\[ m+n \]total moves.
Choose which \(m\) positions are right moves.
Therefore, the number of paths is
\[ \boxed{ \binom{m+n}{m} }. \]Lattice-Path Recurrence
Let \(P(m,n)\) count right-up paths from \((0,0)\) to \((m,n)\).
Every path reaches \((m,n)\) from either:
\[ (m-1,n) \]or
\[ (m,n-1). \]Therefore,
\[ \boxed{ P(m,n)=P(m-1,n)+P(m,n-1) }. \]This is a two-dimensional version of Pascal's recurrence.
Paths and Binomial Coefficients
The recurrence
\[ P(m,n)=P(m-1,n)+P(m,n-1) \]and the boundary values
\[ P(m,0)=P(0,n)=1 \]generate binomial coefficients.
Therefore,
\[ \boxed{ P(m,n)=\binom{m+n}{m} }. \]Counting Strings with Restrictions
Sequences often count strings that avoid certain patterns.
For example, let \(a_n\) count binary strings of length \(n\) with no two consecutive \(1\)s.
Such restrictions naturally create recurrence relations.
No-Consecutive-Ones Recurrence
A valid length-\(n\) binary string either ends in \(0\) or ends in \(1\).
If it ends in \(0\), removing that \(0\) leaves any valid string of length \(n-1\).
If it ends in \(1\), the preceding bit must be \(0\), so the string ends in
\[ 01. \]Removing that final \(01\) leaves any valid string of length \(n-2\).
Therefore,
\[ \boxed{a_n=a_{n-1}+a_{n-2}}. \]Initial Counts for Restricted Binary Strings
For length \(0\), there is one empty string:
\[ a_0=1. \]For length \(1\), the valid strings are
\[ 0,\ 1, \]so
\[ a_1=2. \]Therefore,
\[ 1,\ 2,\ 3,\ 5,\ 8,\ldots \]is another Fibonacci-type counting sequence.
Counting Matchings on a Path
Consider a row of \(n\) points connected consecutively.
Let \(M_n\) count ways to choose edges so that no two chosen edges share a vertex.
Looking at the first vertex leads to a Fibonacci-type recurrence.
This is another example of the same sequence appearing in a new combinatorial setting.
Why Recursive Decomposition Works
A valid combinatorial recurrence requires:
- the cases to cover all objects;
- the cases to be disjoint;
- each case to correspond correctly to a smaller counting problem.
If any of these conditions fail, the recurrence may overcount or undercount.
Combinatorial Bijections
A bijection pairs every object in one collection with exactly one object in another collection.
If a bijection exists, the two collections have the same size.
Therefore, if sequences \(a_n\) and \(b_n\) count two families connected by a size-preserving bijection, then
\[ \boxed{a_n=b_n}. \]Example: Subsets and Binary Strings
Label the elements of an \(n\)-element set
\[ 1,2,\ldots,n. \]Represent a subset by a binary string of length \(n\):
- write \(1\) if the element is included;
- write \(0\) if it is excluded.
This is a bijection between subsets and binary strings.
Therefore, both families are counted by
\[ \boxed{2^n}. \]Combinatorial Proofs of Recurrence Relations
To prove a recurrence combinatorially:
- define what \(a_n\) counts;
- partition size-\(n\) objects into disjoint classes;
- identify the count of each class with earlier sequence terms;
- add the class counts.
This proves the recurrence by counting rather than algebraic manipulation.
Combinatorial Proofs of Identities
To prove an identity combinatorially:
- identify one collection of objects;
- show that the left side counts that collection;
- show that the right side counts the same collection;
- conclude that the expressions are equal.
Example: Vandermonde-Type Reasoning
Suppose a group contains \(r\) people of one type and \(s\) of another.
To choose \(n\) people total, we may choose \(k\) from the first group and \(n-k\) from the second.
Summing over possible \(k\) gives
\[ \sum_k \binom rk \binom{s}{n-k}. \]Counting the same \(n\)-person selections directly gives
\[ \binom{r+s}{n}. \]Therefore,
\[ \boxed{ \sum_k \binom rk \binom{s}{n-k} = \binom{r+s}{n} }. \]Sequence Identities Can Reflect Structural Decompositions
An algebraic identity may look mysterious until the counted objects are identified.
Once a sequence term is understood as a count, sums and recurrences often correspond to natural case splits.
This is one of the major benefits of combinatorial interpretation.
Generating Functions Preserve Counting Meaning
If \(a_n\) counts objects of size \(n\), then
\[ A(x)=\sum_{n\ge0}a_nx^n \]packages those counts by size.
The exponent records size.
The coefficient records how many objects have that size.
Products Represent Combined Structures
Suppose \(A(x)\) counts one type of object and \(B(x)\) counts another.
The coefficient of \(x^n\) in
\[ A(x)B(x) \]is
\[ \sum_{k=0}^{n}a_kb_{n-k}. \]Combinatorially, this counts pairs of objects whose sizes add to \(n\).
Recursion Trees and Combinatorial Counts
A recursion tree can represent the branching construction of objects.
If each root-to-leaf path corresponds uniquely to a valid object, then counting leaves counts objects.
Care is required if different branches can lead to the same final object, because then the tree may overcount.
Example: Independent Binary Choices
Suppose an object is determined by \(n\) independent yes/no choices.
A complete binary decision tree has depth \(n\).
It contains
\[ 2^n \]leaves.
Therefore,
\[ \boxed{a_n=2^n}. \]Sequence Growth Can Reflect Structural Freedom
Fast-growing counting sequences often indicate many choices or branching possibilities.
For example,
\[ 2^n \]arises from two independent choices at each of \(n\) positions.
Polynomial counts often arise from distributing or selecting among a bounded number of structural components.
Recurrence Order Can Reflect Memory
In combinatorial counting, the order of a recurrence often reflects how much previous structural information is needed.
A first-order recurrence may depend only on one smaller size.
A second-order recurrence may need two possible smaller sizes or two recent states.
Thus, recurrence order can have a direct combinatorial interpretation.
Example: Strings Ending in Different States
Sometimes one sequence is not enough to describe a restricted counting problem.
We may define:
\[ a_n=\text{number of valid strings of length }n\text{ ending in }0, \] \[ b_n=\text{number of valid strings of length }n\text{ ending in }1. \]The two counting sequences can then satisfy a coupled recurrence system.
This is a state-transition interpretation of combinatorial counting.
Counting by Last Step
A common recursive strategy classifies objects by their final component.
Examples include:
- the final tile;
- the final stair step;
- the final symbol of a string;
- the final move of a lattice path.
Removing the final component often exposes a smaller object counted by an earlier sequence term.
Counting by First Step
The same idea can be applied at the beginning instead of the end.
For restricted compositions using parts \(1\) and \(2\), classify by the first part.
If the first part is \(1\), the remainder totals \(n-1\).
If the first part is \(2\), the remainder totals \(n-2\).
Therefore,
\[ C_n=C_{n-1}+C_{n-2}. \]Counting by Distinguished Element
Another common method selects one distinguished element and separates objects according to whether that element is used.
This leads to recurrences such as Pascal's identity and the subset doubling recurrence.
The distinguished-element method is one of the most reusable tools in combinatorial reasoning.
Counting by Maximum or Minimum
Collections can also be partitioned according to a largest or smallest element, part, position, or value.
The resulting decomposition may produce sums over earlier sequence values.
This is one way convolution-style identities arise naturally.
Common Error: Cases That Overlap
If two cases contain some of the same objects, simply adding their counts overcounts the union.
A recursive decomposition should use disjoint cases unless overlap is explicitly corrected.
Common Error: Cases That Are Not Exhaustive
If some valid objects belong to none of the listed cases, the recurrence undercounts.
Always verify that every object is included in exactly one intended case.
Common Error: Forgetting the Empty Object
Many recursive counting models need
\[ a_0=1. \]Forgetting the unique empty object can break the recurrence at small indices.
Common Error: Counting Ordered and Unordered Objects the Same Way
The ordered pair
\[ (1,2) \]and
\[ (2,1) \]are different if order matters.
In an unordered setting, they may represent the same object.
A sequence count depends on the exact definition of the objects.
Common Error: Assuming the Same Recurrence Means the Same Objects
Different combinatorial families can satisfy the same recurrence.
Tiling counts, stair-step counts, and restricted binary strings can all be Fibonacci-type.
Equality of counting sequences does not mean the underlying objects are identical.
Common Error: Using a Numerical Pattern without a Counting Argument
Observing that several values match a familiar sequence can suggest a conjecture.
A combinatorial interpretation requires more: we must explain why the counted objects satisfy the same recurrence, formula, or bijection.
A Reliable Procedure for Finding a Combinatorial Recurrence
- Define precisely what \(a_n\) counts.
- Choose a structural feature for splitting size-\(n\) objects into cases.
- Make the cases disjoint and exhaustive.
- Relate each case to a smaller counting problem.
- Add the case counts.
- Determine the necessary initial values.
- Check the recurrence against small cases.
A Reliable Procedure for a Combinatorial Identity
- Identify one collection of objects.
- Interpret the left side as a count of that collection.
- Interpret the right side as another count of the same collection.
- Verify that both interpretations count each object exactly once.
- Conclude that the two expressions are equal.
A Reliable Procedure for Building a Bijection
- Define the two collections precisely.
- Describe a rule mapping every object in the first collection to one object in the second.
- Show that different source objects do not map to the same target object.
- Show that every target object arises from some source object.
- Conclude that the collections have equal size.
Practice 1: Binary Strings
Let \(B_n\) count binary strings of length \(n\).
Write a recurrence and initial condition for \(B_n\).
Practice 2: Subsets
Let \(S_n\) count subsets of an \(n\)-element set.
Explain combinatorially why
\[ S_n=2S_{n-1}. \]Practice 3: Tiling Count
Let \(T_n\) count tilings of a board of length \(n\) using squares and dominoes.
Write the recurrence and initial conditions.
Practice 4: Pascal's Recurrence
Explain combinatorially why
\[ \binom nk = \binom{n-1}{k} + \binom{n-1}{k-1}. \]Practice 5: Row Sum Identity
Give a combinatorial interpretation of
\[ \sum_{k=0}^{n}\binom nk=2^n. \]Practice 6: Ordered Pairs
How many ordered pairs of nonnegative integers satisfy
\[ i+j=7? \]Practice 7: Compositions
How many compositions does \(5\) have?
Practice 8: Restricted Binary Strings
Let \(a_n\) count binary strings of length \(n\) with no two consecutive \(1\)s.
Write the recurrence and the first two initial values.
Practice 9: Lattice Paths
How many right-up lattice paths go from
\[ (0,0) \]to
\[ (3,2)? \]Practice 10: Same Sequence, Different Interpretation
Give two different combinatorial families counted by \(2^n\).
Practice Answers
Practice 1
Every length-\(n\) binary string is formed by appending either \(0\) or \(1\) to a length-\(n-1\) string.
Therefore,
\[ \boxed{B_n=2B_{n-1}} \]with
\[ \boxed{B_0=1}. \]Practice 2
Choose one distinguished element.
Every subset either includes it or excludes it.
Each case corresponds to an arbitrary subset of the remaining \(n-1\) elements, so each case has \(S_{n-1}\) possibilities.
Therefore,
\[ \boxed{S_n=2S_{n-1}}. \]Practice 3
Classify tilings by their final tile.
A final square leaves a tiling of length \(n-1\).
A final domino leaves a tiling of length \(n-2\).
Therefore,
\[ \boxed{T_n=T_{n-1}+T_{n-2}} \]with
\[ \boxed{T_0=1,\qquad T_1=1}. \]Practice 4
Choose one distinguished element.
A \(k\)-element subset either excludes it, giving
\[ \binom{n-1}{k}, \]or includes it, leaving \(k-1\) choices from the remaining \(n-1\):
\[ \binom{n-1}{k-1}. \]Therefore,
\[ \boxed{ \binom nk = \binom{n-1}{k} + \binom{n-1}{k-1} }. \]Practice 5
The term
\[ \binom nk \]counts \(k\)-element subsets of an \(n\)-element set.
Summing over all possible sizes counts every subset exactly once.
Since each element is either included or excluded, there are \(2^n\) subsets.
\[ \boxed{ \sum_{k=0}^{n}\binom nk=2^n }. \]Practice 6
The ordered pairs are
\[ (0,7),(1,6),\ldots,(7,0). \]Therefore,
\[ \boxed{8}. \]Practice 7
The number of compositions of \(n\ge1\) is
\[ 2^{n-1}. \]For \(n=5\),
\[ 2^4=16. \]Therefore,
\[ \boxed{16}. \]Practice 8
Classifying by the ending gives
\[ \boxed{a_n=a_{n-1}+a_{n-2}}. \]There is one empty string:
\[ a_0=1. \]The valid length-\(1\) strings are \(0\) and \(1\), so
\[ a_1=2. \]Therefore,
\[ \boxed{a_0=1,\qquad a_1=2}. \]Practice 9
The path uses three right moves and two up moves, for five moves total.
Choose the positions of the three right moves:
\[ \binom53=10. \]Therefore,
\[ \boxed{10}. \]Practice 10
Two examples are:
- binary strings of length \(n\);
- subsets of an \(n\)-element set.
Both are counted by
\[ \boxed{2^n}. \]What to Remember
A combinatorial interpretation gives sequence terms a counting meaning.
- A term \(a_n\) may count objects of size \(n\).
- Recurrences often arise by partitioning objects into disjoint structural cases.
- Initial conditions count the smallest valid objects, often including one empty object.
- The same numerical sequence can count many different combinatorial families.
- Bijections prove equality of counts by pairing objects directly.
- Pascal's recurrence, Fibonacci-type recurrences, and powers of two all have natural counting interpretations.
- Lattice paths, tilings, compositions, strings, and subsets are common sources of sequence counts.
- Generating functions package counting sequences by size.
- Recursion trees can represent branching constructions, but care is needed to avoid overcounting repeated outcomes.
- Combinatorial proofs explain identities by showing that two expressions count the same collection.
Where We Go Next
Combinatorial interpretations complete the basic sequence toolkit by connecting recurrences, closed forms, generating functions, recursion trees, and counting arguments.
From here, later discrete mathematics topics can reuse these structures to study combinatorial classes, algorithmic recurrences, probability models, graph processes, and more advanced generating methods.