9. Ordinary generating functions: ordered arrangements, compositions, and recurrences#
Suppose a staircase must be climbed using steps of several allowed heights. We might ask how many distinct ways we can reach a total height of . When we climb using a sequence of steps, the order of the heights matters: taking a -step and then a -step describes a different climb from taking a -step and then a -step. Earlier, we used ordinary generating functions to count independent selections where order does not matter. To count ordered sequences, we assign generating functions to successive positions in the sequence. By substituting variables, we can track both the total sum of the parts and the number of parts used.
After studying these notes, you will be able to do the following.
Use the substitutions and to impose divisibility and remainder conditions on exponents.
Construct the OGF for ordered arrangements of exactly objects by first assigning a separate variable to each position.
Interpret the composition as replacing each position of an outer arrangement by an inner object.
Count climbs of a prescribed height with either a fixed or unrestricted number of allowed steps.
Distinguish integer compositions from integer partitions and construct their generating functions.
Derive Fibonacci and Catalan recurrences from combinatorial decompositions and translate those recurrences into OGF equations.
9.1 Substitution and restrictions on exponents#
When a generating function records the size or number of objects, replacing the variable with a power of itself scales the recorded values. Let Replacing by , where is a positive integer, gives The coefficients have not changed, but the term that was in degree is now in degree . Substitution multiplies every recorded size by .
Proposition 1 (Scaling and shifting exponents)#
If , , and , then Consequently,
The geometric series records the choice of any nonnegative number of copies of one kind of object. Substituting for gives Only even exponents occur, so this is the OGF for choosing an even number of copies. Multiplying by shifts every exponent by one: This is the OGF for choosing an odd number of copies. The constant zero is included among the even choices. If a strictly positive even number is required, the constant term must be removed:
The same arithmetic handles any remainder condition. For example, records a number of copies congruent to modulo .
Example 2 (Parity conditions in a product)#
A bag contains red, blue, and green tokens of each color in unlimited supply. How many selections of tokens use an even number of red tokens, an odd number of blue tokens, and any number of green tokens?
The three color counts are independent and order does not matter. Their OGFs are, respectively, Therefore the required number is Each selected collection contributes once: its red, blue, and green counts choose one term from each of the three factors, and the exponents add to the total number of tokens.
9.2 A fixed number of positions in an ordered arrangement#
In this section, a position means a labeled slot in an ordered list. For a three-step climb, position is the first step, position is the second step, and position is the third step. Thus means that the three slots contain steps of heights , , and , in that order. Changing the entry in one slot changes the ordered arrangement; and are different because their first slots contain different heights.
Suppose a staircase allows steps of heights , , and . Consider three-step climbs whose total height is . The possible ordered lists of step heights are
There are three climbs. The lists and are different because the second step has a different height. If we temporarily label the three step positions by , then the first list contributes , while the second contributes . The position labels keep these two climbs separate.
Each slot may receive a step of height , , or , so the generating function for the three labeled slots is
To see how the product works, choose one term from each factor. Choosing , , and gives , which represents the climb . Every ordered three-step climb gives one such product, and every product comes from one ordered climb.
Now replace all three position variables by the same variable : The monomial for a climb becomes Thus all climbs of total height contribute to the coefficient of : The three contributions to come from the three lists displayed above. After the substitution, the exponent records total height, while the coefficient records how many ordered climbs have that height. If the order of the steps did not matter, those three lists would describe only one choice, so the coefficient depends on the fact that the positions are ordered.
The same construction works when the allowed objects are not merely step heights. Suppose that there are distinct object types of size . The one-slot generating function is For example, if there are two distinct size- objects, then the term for size is : either object may fill the slot. For ordered slots, each factor of corresponds to one slot, so the product is . Choosing one term from each factor specifies the object in every slot; multiplying the terms adds their sizes. Therefore the coefficient of counts exactly the arrangements with total size .
Theorem 3 (Ordered arrangements of fixed length)#
Suppose types of objects have size , and one object is placed in each of ordered slots (positions). Let The number of ordered arrangements of exactly objects and total size is
The positive-size assumption makes the fixed-length statement finite in the usual counting problems: an arrangement of positions has a total size at least . If size-zero objects are allowed, the same coefficient formula can still be used when is fixed, but an unrestricted number of positions can then produce infinitely many arrangements of the same total size.
Problem 4 (A fixed number of steps)#
A staircase allows steps of heights , , and . In how many ways can a climber reach height using exactly four steps?
Solution: Each of the four labeled step positions has the same generating function, The requested number is therefore To evaluate the coefficient, write the height in position as . Because a step has height , , or , each is , , or . The four mandatory units contribute height , so the remaining height must satisfy If we temporarily ignore the upper bound , stars and bars gives nonnegative solutions. The invalid solutions are the four with one and the other three -values equal to . No solution has two coordinates equal to , since their sum would already exceed . Hence For each remaining solution, the step in position has height . This gives one ordered four-step sequence, and every valid sequence gives one solution of the equation, so the answer to the staircase question is .
If both total height and number of steps need to remain visible, introduce a second variable. Give every step an additional weight . An arrangement of steps then contributes , and Therefore The exponent of records total height, and the exponent of records the number of steps.
9.3 Substitution as replacement of ordered positions#
The geometric series above represents a substitution of one generating function into another. Let count outer arrangements with positions, and let count the objects that may fill one position. The variable counts unfilled positions in the outer arrangement, and counts the size contributed by a filling object.
An outer arrangement with exactly ordered positions has weight . Replacing each of those positions independently by a -object changes that weight to If there are possible outer arrangements of length , their total contribution is . Summing over all gives The algebraic substitution executes a combinatorial replacement: every outer position is filled by one inner object.
Proposition 5 (OGF substitution rule)#
Let count outer arrangements by their number of positions. Let count the allowed fillings of one position by size. If the positions of each outer arrangement are distinct, and each position is filled independently, then counts the resulting objects by total size.
For an ordered sequence, there is one outer arrangement of every length, giving Substitution produces The term counts sequences of exactly objects. The constant term counts the empty sequence, which has length and total size zero.
Warning (A product of supplies counts a different set)#
For allowed step heights and , the expression counts unordered selections of -steps and -steps. It records how many of each height are used, but it does not record their order. Ordered step sequences are counted by These generating functions model strictly different sets.
Problem 6 (Allowed step lengths and any number of steps)#
A climber may use steps of height or . How many ordered step sequences reach height ?
Solution: One step has OGF . A climb is an ordered sequence of such steps, so its OGF is We seek . A sequence reaching height can use six -steps and no -steps, giving one sequence. It can instead use one -step and two -steps. The latter three steps may be ordered in ways, according to the position of the -step. Therefore The unordered-selection product would give coefficient , counting only the two valid pairs of multiplicities without differentiating the three distinct orders in the second case.
9.4 Compositions of an integer#
Definition 7 (Composition)#
A composition of a positive integer is an ordered list of positive integers whose sum is . The entries in the list are called its parts.
The tuples and are different compositions of . A positive part has OGF A composition with exactly parts is an ordered arrangement of positive parts, giving the OGF
Theorem 8 (Compositions with a fixed number of parts)#
For and , the number of compositions of with exactly parts is
Proof#
A composition of has . Place identical marks in a row. There are gaps between consecutive marks. Choosing of those gaps for separators produces nonempty consecutive groups. Their sizes, read from left to right, are . Conversely, the partial sums specify the separator gaps. The two constructions strictly correspond, leaving valid compositions.
Allowing any positive number of parts gives the sum
A positive integer therefore has total compositions. This matches the separator logic: each of the gaps is either cut or not cut.
Example 9 (Compositions of into three parts)#
The formula gives . The six compositions are The distinct orders are strictly maintained.
9.5 Partitions of an integer#
Definition 10 (Partition)#
A partition of a positive integer is an unordered collection of positive integers whose sum is . We write the parts in weakly decreasing order so that each partition has one consistent representation.
The partitions and identify the same partition of , even though and are different compositions. To construct a partition, choose a nonnegative number of parts of size , a nonnegative number of parts of size , and so on. The choices for parts of size have OGF The choices for different part sizes are independent, so their product is the partition generating function.
Theorem 11 (Euler’s product for integer partitions)#
If is the number of partitions of , with , then For a fixed target , factors with may be omitted.
Selecting from the th factor specifies parts of size . A term contributing to corresponds to a sequence of multiplicities satisfying This multiplicity sequence precisely determines one partition of .
For example, the seven partitions of are Thus , whereas has compositions.
To record the number of parts as well as their sum, assign a variable to each chosen part. The bivariate generating function is Its coefficient counts partitions of into exactly parts.
9.6 Recurrences from combinatorial decompositions#
A recurrence relation defines terms of a sequence using earlier terms and requires initial conditions to fix a single sequence. We construct recurrences by classifying an object according to its final step or root structure.
Let be the number of ordered climbs of height using step heights in a fixed set of positive integers. Count the empty climb by , and set for . Every nonempty climb has a unique final step of some height . Removing that final step leaves a climb of height . Appending an -step to a climb of height produces a unique climb of height whose final step has height . The classes for distinct final-step heights are disjoint, giving
The OGF yields the identical algebraic structure. If , ordered climbs have OGF Equivalently, The term represents the empty climb. In , the factor chooses a final step and chooses the shorter preceding climb. Comparing coefficients directly recovers the recurrence.
9.6.1 Fibonacci numbers from steps of heights one and two#
For , let count ordered climbs to height . Classifying a nonempty climb by whether its final step has height or produces with , , and for . The sequence begins Defining the Fibonacci numbers by , , and yields . The index shift accounts for the sequence starting with instead of .
The one-step OGF is , making Multiplying by the denominator gives For , the coefficient of on the left side is . Its vanishing algebraically mirrors the Fibonacci recurrence.
9.6.2 Catalan numbers from a split into two smaller objects#
The Catalan recurrence arises from classifying full rooted binary trees. Let count full rooted binary trees with internal vertices, and let count the tree consisting of a single leaf. In a nontrivial tree, the root is an internal vertex with a left subtree and a right subtree. If the left subtree has internal vertices, the right subtree must have internal vertices, where ranges from to .
For a fixed , there are choices for the left subtree and choices for the right subtree. The product rule and sum rule give Starting from , this recurrence generates Defining the OGF the Cauchy product algebraically represents an ordered pair consisting of a left and a right subtree. Multiplication by represents the addition of the new internal root. Including the size-zero tree gives the OGF equation The coefficient of in is exactly . The generating function equation and the recurrence express the same structural root decomposition. Solving this quadratic equation algebraically allows for the extraction of a closed formula, while the recurrence computes terms dynamically.
The form of a generating function reflects exactly what constitutes one assembled object. When counting exactly ordered parts chosen from , the formula requires a power . If any finite ordered sequence is valid, it forms a geometric series . Compositions are ordered positive parts evaluated through powers of , whereas partitions use independent multiplicities for every allowable part size, producing the product . When every nonempty object permits a unique decomposition into smaller objects—such as stripping a final step or detaching a root—the generating function obeys an algebraic equation mirroring the recurrence.