Generating functions and combinatorial structures

Three strips or two selections: what are you counting?

You can fill a strip of length 3 with tiles of lengths 1 and 2. From left to right the possibilities are (1,1,1), (1,2) and (2,1): three tilings. If instead you choose an unordered collection of those lengths totalling 3, there are only two choices: three ones, or one one and one two. The second and third strips use the same collection but place its tiles in different orders.

A generating function keeps all these totals in one indexed record. Its coefficient at degree 3 will be 3 for ordered tilings and 2 for unordered selections. Before choosing a formula, define what one object is, how its size is measured, and when two objects are considered different.

Useful preparation is collecting terms in polynomial multiplication, reading powers, and following a rule through a numbered sequence. The linked published lessons provide that algebra and pattern background. Formal series, coefficient extraction, pairs, multiplicity vectors, partitions and recurrences are defined here; later counting articles are optional.

On a first reading, follow the coefficient examples, two-factor grid, ordered-versus-unordered comparison and length-three tilings. Return to the formal inverse proof and the infinite partition product after you can explain why only finitely many terms affect one chosen coefficient. You do not need limits or analytic convergence for the counting formulas.

A coefficient's position gives the size

For n = 0,1,2,… let aₙ count the objects of size n, with finitely many objects at each size. The ordinary generating function is A(x) = a₀+a₁x+a₂x²+⋯. Ordinary means the coefficient is aₙ itself, without a factorial denominator. We will not use exponential generating functions here.

The symbol [xⁿ]A(x) means the coefficient aₙ. For A(x) = 1+2x², we have [x⁰]A = 1, [x¹]A = 0 and [x²]A = 2. A missing term is zero, rather than permission to shift the later indices. If this expression denotes a finite polynomial, all higher coefficients are also zero.

The constant coefficient records size zero. A class containing just one empty object has series 1. A class with no objects at any size has the zero series 0. These are different classes: one has a size-zero object, and the other does not.

Integer sizes are nonnegative throughout this lesson. Object counts are nonnegative integers, but formal algebra can also use signed coefficients: (1−x)(1+x) = 1−x². The coefficient −1 is useful algebraically and is not a number of objects. A coefficient list becomes a counting model only after its objects and size rule have been specified.

A formal series is a sequence, without evaluating x

A formal power series over the integers is a sequence of integer coefficients written A(x) = Σₙ₌₀^∞ aₙxⁿ. Here x is a bookkeeping symbol. Equality means agreement of every coefficient. Addition is coefficientwise: [xⁿ](A+B) = aₙ+bₙ. Multiplication will use the finite rule below. An infinite-looking expression is legitimate only when each requested coefficient has a finite, well-defined computation.

This interpretation differs from an analytic power series, where x is a number and the numerical series must converge before it gives a value. The formal identity 1+x+x²+⋯ = 1/(1−x) does not license substituting x = 1 or x = 2 into the left side as a convergent real sum. Analytically the geometric series converges for |x| < 1; formally no such numerical input is being chosen.

Write A(x) ≡ B(x) modulo x^(N+1) when their coefficients agree from degree 0 through N, where N is a nonnegative integer. This is a finite prefix claim, not full equality. In diagrams the horizontal coordinate is degree n, not a numerical input value of x. A seven-column display cannot by itself prove an identity at every degree.

Multiply by all pairs of indices with the same total

Let A(x) = Σᵢ₌₀^∞ aᵢxⁱ and B(x) = Σⱼ₌₀^∞ bⱼxʲ. Their Cauchy product has coefficient cₙ = Σᵢ₌₀^n aᵢbₙ₋ᵢ. In the grid, every product aᵢbⱼ belongs to degree i+j because xⁱxʲ = x^(i+j). Exactly the n+1 index pairs (0,n),(1,n−1),…,(n,0) can contribute to degree n.

This defines multiplication even when both series are infinite: the sum for one fixed n contains finitely many products. Neither a coefficient beyond n nor a negative index can affect it. For finite polynomials, use zero for any coefficient beyond the last term.

For (1+2x)(1+x), the degree-one terms are 1×1 and 2×1, so c₁ = 3. At degrees zero and two the coefficients are 1 and 2. The product is 1+3x+2x². For (1−x)(1+x), the two degree-one contributions cancel, giving 1−x²; forgetting the second grid cell would give the wrong coefficient.

For counting, choose an ordered pair (a,b) consisting of one object from class A and one from class B, and give the pair size size(a)+size(b). For total n, first separate disjoint cases by size(a)=i. There are aᵢbₙ₋ᵢ pairs in that case. Every pair has one first size, so adding these cases counts each pair exactly once. This proves the product formula when sizes add; a different size rule requires its own argument.

A finite truncation can answer an exact finite question

To find coefficients through degree N, keep the coefficients 0 through N of each factor. In a Cauchy term i+j = n ≤ N, both i and j are at most N. Therefore deleting all higher-degree terms leaves every required coefficient unchanged. The same argument works for a finite number of factors by induction on the number of multiplications.

A shift by xᵏ, for integer k ≥ 0, moves each coefficient k places right: [xⁿ](xᵏA) is aₙ₋ₖ when n ≥ k and is 0 otherwise. For x²(1+2x+x²), the degree-three coefficient is 2. Keep the zero coefficients at degrees zero and one rather than reindexing the output.

These guarantees require nonnegative exponents. If negative powers were allowed, a discarded high positive degree could combine with a negative degree to reach a low target. Such Laurent-series questions are outside this lesson. Likewise, a truncated coefficient table must not be presented as the full polynomial unless all later coefficients are actually zero.

Ordered lists use repeated products

Suppose the available item types have positive integer weights. There are finitely many types of each weight; let aⱼ be their number at weight j. Then A(x) = Σⱼ₌₁^∞ aⱼxʲ has a₀ = 0. A list remembers the first, second and subsequent item types. Its weight is their sum. Distinct types remain distinct even if they have the same weight.

Lists of exactly k items have series A(x)^k by the ordered-pair product rule, used repeatedly. The empty list has weight zero and contributes A(x)^0 = 1. All finite lists therefore have series L(x) = 1+A+A²+⋯. At target degree n, a list can have at most n items because every item has weight at least 1. Only k ≤ n can contribute, and there are finitely many types at every weight up to n, so that coefficient is a finite count.

Check the Cauchy product one coefficient at a time: (1−A)(1+A+A²+⋯) = 1. At every fixed degree the terms cancel within finitely many relevant powers; no numerical limit is being used. Thus L(x) = 1/(1−A(x)), where the fraction means the unique formal multiplicative inverse of 1−A. Its constant coefficient is 1, so integer coefficients can be solved successively: l₀ = 1 and lₙ = Σⱼ₌₁^n aⱼlₙ₋ⱼ for n ≥ 1.

The condition a₀ = 0 matters. If one repeatable type had weight zero, arbitrarily long lists of it would all have weight zero, giving infinitely many size-zero objects. The geometric list construction would not define a finite coefficient at that degree. We are not saying every series with a nonzero constant term is uninvertible; the counting interpretation of this unlimited-list sum specifically needs positive weights.

With one type of weight 1 and one of weight 2, A = x+x². Then L = 1/(1−x−x²), whose degree-three coefficient is 3. With two distinct types of weight 1 and one of weight 2, A = 2x+x². At degree three, eight lists use three weight-one items; four more have one weight-one item and the weight-two item. The total is 12.

Multisets choose one multiplicity per type

A multiset selection specifies a nonnegative integer multiplicity kⱼ for each available named type j. It does not record an order. With a finite list of types of positive weights w₁,…,wᵣ, the total weight is Σⱼ₌₁^r wⱼkⱼ. The vector (k₁,…,kᵣ) identifies the object completely. For an empty type list, there is one empty vector of total weight zero.

For one type of weight w ≥ 1, its permitted multiplicities 0,1,2,… give series 1+xʷ+x^(2w)+⋯ = 1/(1−xʷ). Choices for different types combine by adding weights, so the multiset series is M(x) = ∏ⱼ₌₁^r 1/(1−x^(wⱼ)). Every coefficient is finite since each kⱼ ≤ n/wⱼ at total n. Each vector is selected once; reordering the chosen items does not create another vector.

With weights 1 and 2, M = 1/((1−x)(1−x²)). To reach 3, solve k₁+2k₂ = 3: the solutions are (3,0) and (1,1). The coefficient is 2, unlike the ordered-list coefficient 3. This is the distinction behind the two unordered selections in the opening example.

If two named types both have weight 1, retain two separate factors (1−x)⁻¹. Together with one weight-two type, reaching 3 means k₀+k₁+2k₂ = 3. When k₂ = 0 there are four pairs (k₀,k₁); when k₂ = 1 there are two. The coefficient is 6, still different from the 12 ordered lists. If those two types were physically indistinguishable, merging them would change the class and its formula.

A coin-change question normally ignores the order of the coins, so one factor per denomination is appropriate. An ordered list of coin denominations is a different question and uses the list formula. For denominations 2 and 3 and target 5, one of each coin is one multiset but has two ordered lists, (2,3) and (3,2). State the convention instead of inferring it from the word change.

Integer partitions have one type for each part size

An integer partition of n ≥ 0 is an unordered collection of positive integers whose sum is n. Equivalently it is a nonincreasing list of positive parts, or a multiplicity vector: mⱼ records how many parts equal j. The empty partition is the one partition of 0. For n > 0, only part sizes j ≤ n can occur.

For a maximum part size k ≥ 1, the generating series is Pₖ(x) = ∏ⱼ₌₁^k 1/(1−xʲ). Its degree-n coefficient counts the nonnegative solutions m₁+2m₂+⋯+kmₖ = n. This is exactly the multiset construction with one type of every permitted part size. Define P₀ = 1 for no permitted parts, so it has coefficient 1 at degree zero and 0 at every positive degree.

For k = 3 and n = 4, the four partitions are 3+1, 2+2, 2+1+1 and 1+1+1+1. The partition 4 is excluded because its part is larger than 3. Thus [x⁴]P₃ = 4, whereas the unrestricted partition count p(4) is 5.

The unrestricted formal series is P(x) = ∏ⱼ₌₁^∞ 1/(1−xʲ). This infinite product is defined coefficient by coefficient: through degree N, every factor with j > N contributes only its constant term 1. Consequently P and the finite product P_N agree through degree N. All coefficients are finite, and no analytic convergence claim is needed. A zero-sized part would destroy this reasoning; partitions here have strictly positive parts.

Removing the first tile gives a recurrence

Let tₙ count the ways to tile a strip of integer length n ≥ 0 with tiles of lengths 1 and 2, preserving left-to-right order. There is one empty tiling, so t₀ = 1. A strip of length 1 has only a length-one tile, so t₁ = 1. For n ≥ 2, separate tilings by their first tile. Removing a first tile of length 1 leaves a tiling of n−1, while removing one of length 2 leaves a tiling of n−2.

The two cases are disjoint and reversible: prepend the removed tile to reconstruct exactly one original tiling. Therefore tₙ = tₙ₋₁+tₙ₋₂ for n ≥ 2. The coefficients begin 1,1,2,3,5,8,13. The empty tiling is necessary both for a lone length-two tile at n = 2 and for the constant term in the series.

Let T(x) = Σₙ₌₀^∞ tₙxⁿ. Then T−1−x = x(T−1)+x²T, because each shifted sum starts at the correct initial index. Rearranging gives (1−x−x²)T = 1, hence T = 1/(1−x−x²). This agrees with the ordered-list construction for item series x+x².

With the convention F₀ = 0, F₁ = 1 and Fₙ = Fₙ₋₁+Fₙ₋₂ for n ≥ 2, these tiling counts are tₙ = Fₙ₊₁. The Fibonacci series Σₙ₌₀^∞ Fₙxⁿ instead has numerator x: x/(1−x−x²). Keeping the initials prevents an off-by-one error. The picture enumerates all eight length-five tilings, but the first-tile argument proves the recurrence for every n ≥ 2.

Check the objects before the algebra

Use a sum for disjoint alternatives, a product for an ordered tuple whose sizes add, a geometric list formula for arbitrarily long ordered lists of positive-weight items, and one multiplicity factor per type for unordered selections. A partition product is a special multiset model with one type per positive integer size. These descriptions explain the formulas, rather than making the symbols interchangeable.

For a desired coefficient, first write the object and size definitions. Check the empty object, positivity of repeatable weights and finiteness at each degree. Then choose the construction, keep enough terms, and compare a small hand-counted case with the computed coefficient. A numerical match is a useful error check; the reversible counting argument is what establishes the formula in general.

The explorer uses exact small integer data through degree 6, with every selected convolution term and every short list or multiplicity vector shown where stated. Its finite input and enumeration caps keep the interaction readable. They are not bounds on the mathematics of formal series, and the displayed prefix does not establish the whole infinite identity.

Worked examples

Try it yourself

1. A class has one empty object and no positive-size objects. Is its series 0 or 1? How does a class containing no objects differ?

   Show the answer and reasoning

   Its series is 1. The class containing no objects has series 0.

   The constant coefficient counts size-zero objects. One empty object contributes one, whereas an empty class contributes zero. Absence of positive-size objects does not settle the constant coefficient.

2. Find [x²](1−2x+x²)(1+x). Can every coefficient of these factors be interpreted as an object count?

   Show the answer and reasoning

   The degree-two coefficient is −1. No: negative coefficients are algebraic values rather than numbers of objects.

   The products on the degree-two diagonal are 1×0, (−2)×1 and 1×1. Their sum is −1. Formal multiplication works for integer coefficients even when a direct counting interpretation does not.

3. For x³(2+x+4x²+⋯), find the coefficients at degrees 2 and 4. Could any term hidden after degree two of the inner series alter them?

   Show the answer and reasoning

   They are 0 and 1. Later inner terms cannot alter either coefficient.

   The shift makes all degrees below three zero and takes the degree-four coefficient from inner degree one. With nonnegative exponents, a higher inner degree shifts to an even higher total; it cannot return to these targets.

4. Using one type of weight 2 and one of weight 3, compare the coefficients at degree 5 for ordered lists and unordered selections. State both series.

   Show the answer and reasoning

   Ordered lists give 2, with series 1/(1−x²−x³). Multisets give 1, with series 1/((1−x²)(1−x³)).

   The ordered lists are (2,3) and (3,2). The only multiplicity vector is (1,1). Both constructions allow the empty object at weight zero, and their positive weights make every target coefficient finite.

5. Why can one freely repeatable type of weight zero not be inserted into the unlimited-list counting formula as though it were an ordinary positive-weight type?

   Show the answer and reasoning

   There would be infinitely many ordered lists of total weight zero, one for every length, so the constant coefficient would not be a finite object count.

   The positive-weight proof bounded the number of items by the target weight. A zero-weight item removes that bound. This objection concerns the list construction; it is not a claim that every series with a nonzero constant term lacks a formal inverse.

6. With no available item types, how many ordered lists and multiplicity vectors have weight zero? How many have weight 4?

   Show the answer and reasoning

   Each construction has one empty object of weight zero and no object of weight 4. Both series are 1.

   The empty sequence and empty vector are well-defined single objects. A positive total cannot be built without items. This is distinct from the zero series, whose class has no objects even at size zero.

7. List the partitions of 5 whose parts are at most 2, and state their generating series.

   Show the answer and reasoning

   They are 2+2+1, 2+1+1+1 and 1+1+1+1+1. Their series is 1/((1−x)(1−x²)), so the degree-five coefficient is 3.

   Solving m₁+2m₂ = 5 gives m₂ = 0,1,2 and determines m₁ as 5,3,1 respectively. Different orders of the same parts are not new partitions.

8. Why do part factors 1/(1−xʲ) with j > 6 have no effect on p(6)? Does the prefix prove analytic convergence at x = 1?

   Show the answer and reasoning

   Their first nonconstant terms have degree greater than 6, so they act as 1 through that degree. No analytic convergence at x = 1 follows.

   Products use only nonnegative degrees. A contribution using one of those nonconstant terms already exceeds the target, even if the other chosen terms are constant. This defines a formal finite coefficient; it does not evaluate the infinite series numerically.

9. What are t₀, t₁ and t₄ for lengths-one-and-two tilings? With F₀ = 0 and F₁ = 1, is t₄ = F₄ or F₅?

   Show the answer and reasoning

   t₀ = 1, t₁ = 1 and t₄ = 5. The correct relation is t₄ = F₅, with tₙ = Fₙ₊₁.

   The empty strip is one tiling. The recurrence gives 1,1,2,3,5 for tilings, whereas Fibonacci begins 0,1,1,2,3,5. Their formal series have the same denominator but numerators 1 and x respectively.

10. Explain why (1−x)(1+x+x²+⋯) = 1 is valid formally, but substituting x = 2 does not give a convergent real sum on the left.

    Show the answer and reasoning

    At each positive degree the two formal contributions cancel, and the constant coefficient is 1. At x = 2 the numerical terms 1,2,4,… do not even tend to zero.

    Formal multiplication checks each coefficient separately and needs only a finite calculation for that coefficient. Numerical convergence is a different requirement; the analytic geometric formula is valid for |x| < 1, not for this input.

What to carry forward

• Ordinary coefficients record sizes from degree zero. A missing term is zero; the series 1 for an empty object differs from the zero series.
• Formal series are coefficient sequences. Equality at every degree is stronger than a displayed prefix, and formal identities do not automatically permit numerical substitution.
• The Cauchy coefficient at n sums all aᵢbₙ₋ᵢ for i = 0,…,n. Nonnegative exponents make truncation through the target exact.
• Positive-weight ordered lists give 1/(1−A), with A₀ = 0. Multisets instead use one reciprocal factor per named type.
• Positive-part partitions have a coefficientwise finite infinite product. Length-one-and-two tilings have initial values 1,1 and series 1/(1−x−x²).