Chapter 5: Combinatorial Constructions #
Language serves not only to express thoughts, but to make possible thoughts which could not exist without it.
— Bertrand Russell
Money, mechanization, algebra. The three monsters of contemporary civilization.
— Simone Weil
With the technology of generating series developed, we now systematically build up increasingly complicated combinatorial classes in ways that allow us to determine their generating series. This symbolic method gives one of the most powerful tools to derive generating functions and enumerate combinatorial sequences.
In order to build new combinatorial classes out of old ones, we start with two base classes.
The atomic class $\mathcal{Z}=\{ \bullet \}$ is the combinatorial class containing one object of size $1$ and no objects of any other size. The neutral class $\epsilon$ is the combinatorial class containing one object of size $0$ and no objects of any other size.
The generating series of the atomic class is $z$ while the generating function of the neutral class is $1.$
Warning: Don’t confuse $\epsilon$ with the empty set! The empty set has no elements while $\epsilon$ is a set with a single element, but that element has size $0.$
Basic Constructions #
We now describe our main combinatorial operations.
Sum #
Let $\mathcal{A}$ and $\mathcal{B}$ be two combinatorial classes with weight functions $|\cdot|_{\mathcal{A}}$ and $|\cdot|_{\mathcal{B}}.$ The sum of $\mathcal{A}$ and $\mathcal{B}$ is the new combinatorial class $\mathcal{C} = \mathcal{A} + \mathcal{B},$
-
whose objects are the disjoint union of the objects in $\mathcal{A}$ and $\mathcal{B},$
-
whose weight function $|\cdot|_{\mathcal{C}}$ is defined by $$ |\sigma|_{\mathcal{C}} = \begin{cases} |\sigma|_\mathcal{A} &\text{if $\sigma \in \mathcal{A}$} \\ |\sigma|_\mathcal{B} &\text{if $\sigma \in \mathcal{B}.$} \end{cases} $$
It is crucial that the elements of $\mathcal{A}$ and $\mathcal{B}$ are considered distinct. For instance, one can imagine colouring all the elements in $\mathcal{A}$ red and all the elements of $\mathcal{B}$ blue, so that none of the elements are equivalent.
Example: Let $\mathcal{Z} = \{ \bullet \}$ be the atomic class. Then we can consider $\mathcal{Z} + \mathcal{Z} = \{ {\color{red}\bullet}, {\color{blue}\bullet} \}$ to be the class with two distinct atoms of size 1, one of which is red and the other of which is blue, with generating function $2z.$
Lemma 1: If $\mathcal{C} = \mathcal{A} + \mathcal{B}$ then $C(z) = A(z) + B(z).$
Proof of Lemma 1
Product #
Let $\mathcal{A}$ and $\mathcal{B}$ be two combinatorial classes with weight functions $|\cdot|_{\mathcal{A}}$ and $|\cdot|_{\mathcal{B}}.$ The product of $\mathcal{A}$ and $\mathcal{B}$ is the new combinatorial class $\mathcal{C} = \mathcal{A} \times \mathcal{B},$
-
whose objects consist of all pairs $(\alpha,\beta)$ with $\alpha \in A$ and $\beta \in B,$
-
whose weight function $|\cdot|_\mathcal{C}$ is defined by $|(\alpha,\beta)|_\mathcal{C} = |\alpha|_\mathcal{A} + |\beta|_\mathcal{B}.$
Lemma 2: If $\mathcal{C} = \mathcal{A} \times \mathcal{B}$ then $C(z) = A(z) B(z).$
Proof of Lemma 2
Iterating the product, for any positive integer $k$ we define the $k\text{th}$ power class $$\mathcal{A}^k = \underbrace{A \times \cdots \times A}_\text{$k$ times}.$$ Lemma 2 implies the generating function of $\mathcal{A}^k$ is $A(z)^k.$
Sequence #
Let $\mathcal{A}$ be a combinatorial class with no elements of size $\mathit{0}$. The sequence class $$ \text{SEQ}(\mathcal{A}) = \epsilon + \mathcal{A} + \mathcal{A}^2 + \mathcal{A}^3 + \cdots $$ defined by $\mathcal{A}$ is the class
-
whose objects consist of all finite length tuples $(\alpha_1,\dots,\alpha_r) \in \mathcal{A}^r$ for any $r \in \mathbb{N},$
-
whose weight function is defined by $|(\alpha_1,\dots,\alpha_r)|_{\mathcal{C}} = |\alpha_1|_\mathcal{A} + \cdots + |\alpha_r|_\mathcal{A}.$
Unlike the sum, product, and power constructions, the sequence operator constructs a class with an infinite number of objects from a class with a finite set of objects.
Remark: Because $\mathcal{A}$ has no objects of size $0,$ any element in $\mathcal{A}^r$ has size at least $r.$ The fact that $\mathcal{A}$ is a combinatorial class then implies $\text{SEQ}(\mathcal{A})$ contains a finite number of elements of any fixed size, and is thus a combinatorial class itself. The class $\text{SEQ}(\mathcal{A})$ is not defined when $\mathcal{A}$ has objects of size $0.$
Lemma 3: If $\mathcal{C} = \text{SEQ}(\mathcal{A})$ then $\displaystyle C(z) = \frac{1}{1-A(z)}.$
Remark: The constant term $A(0)=0$ because $\mathcal{A}$ has no objects of size $0.$ This implies that the series $1-A(z)$ has a constant term of $1,$ and thus has a multiplicative inverse as a formal power series by the results in Chapter 4.
Proof of Lemma 3
Example: A binary string can be viewed as a finite tuple of $0\text{s}$ and $1\text{s},$ whose size is the length of the tuple. Thus, if we let $\mathcal{Z}_0$ denote an atomic class representing the digit $0$ and $\mathcal{Z}_1$ denote an atomic class representing the digit $1$ then the class $\mathcal{B}$ of binary strings has the specification $$ \mathcal{B} = \text{SEQ}(\mathcal{Z}_0 + \mathcal{Z}_1). $$ This implies the generating function equality $$ B(z) = \frac{1}{1-(z+z)} = \frac{1}{1-2z}, $$ so that there are $[z^n]B(z) = 2^n$ binary strings of length $n$ as expected.
It is convenient to use the notation $\text{SEQ}_{\text{property}}(\mathcal{A})$ to denote the sum of powers $\mathcal{A}^k$ where $k$ has a specific property. For instance,
-
$\text{SEQ}_{\leq r}(\mathcal{A}) = \epsilon + \mathcal{A} + \cdots + \mathcal{A}^r$ is the sum of the powers of $\mathcal{A}$ with exponent at most $r$
-
$\text{SEQ}_{\geq r}(\mathcal{A}) = \mathcal{A}^r + \mathcal{A}^{r+1} + \cdots $ is the sum of the powers of $\mathcal{A}$ with exponent at least $r$
-
$\text{SEQ}_{\text{even}}(\mathcal{A}) = \epsilon + \mathcal{A}^2 + \mathcal{A}^4 + \cdots $ is the sum of the powers of $\mathcal{A}$ with even exponents
-
$\text{SEQ}_{\text{odd}}(\mathcal{A}) = \mathcal{A} + \mathcal{A}^{3} + \cdots $ is the sum of the powers of $\mathcal{A}$ with odd exponents
Exercise: Let $\mathcal{A}$ be a combinatorial class with no objects of size $0.$
Prove that the generating function of $\text{SEQ}_{\leq r}(\mathcal{A})$ is $$\frac{1-A(z)^{r+1}}{1-A(z)}.$$
Prove that the generating function of $\text{SEQ}_{\geq r}(\mathcal{A})$ is $$\frac{A(z)^r}{1-A(z)}.$$
Prove that the generating function of $\text{SEQ}_{\text{even}}(\mathcal{A})$ is $$\frac{1}{1-A(z)^2}.$$
Prove that the generating function of $\text{SEQ}_{\text{odd}}(\mathcal{A})$ is $$\frac{A(z)}{1-A(z)^2}.$$
Example: Let $\mathcal{N}$ denote the combinatorial class of natural numbers, containing one element of size $n$ for every $n\in\mathbb{N},$ and let $\mathcal{P}$ denote the combinatorial class of positive integers, containing one element of size $n$ for every $n>0$ and no objects of size $0.$ Then we can write $$ \mathcal{N} = \text{SEQ}(\mathcal{Z}) \qquad\qquad \mathcal{P} = \text{SEQ}_{\geq 1}(\mathcal{Z}) $$ so that $$N(z) = \frac{1}{1-z} \qquad\qquad P(z) = \frac{z}{1-z}.$$
Specifications #
More generally, a combinatorial construction is a function $\Phi$ that takes a sequence $\mathcal{A}_1,\dots,\mathcal{A}_r$ of combinatorial classes from some family and returns a new combinatorial class $\Phi(\mathcal{A}_1,\dots,\mathcal{A}_r).$ We call the construction $\Phi$ admissible if the counting sequence of $\Phi(\mathcal{A}_1,\dots,\mathcal{A}_r)$ depends only on the counting sequences of $\mathcal{A}_1,\dots,\mathcal{A}_r.$
Example: The sum, product, power, and sequence constructions above are admissible. The construction that takes any combinatorial class $\mathcal{A}$ containing some collection of binary strings and returns the combinatorial class $\Phi(\mathcal{A})$ containing only those strings in $\mathcal{A}$ that begin with a $0$ is not admissible, since additional information on the elements of $\mathcal{A}$ is needed to find the counting sequence of $\Phi(\mathcal{A}).$
A specification of a class $\mathcal{A}$ is an system of admissible constructions $$ \begin{aligned} \mathcal{C}_1 &= \Phi_1(\mathcal{C}_1,\dots,\mathcal{C}_r) \\ \mathcal{C}_2 &= \Phi_2(\mathcal{C}_1,\dots,\mathcal{C}_r) \\ &\;\; \vdots \\ \mathcal{C}_r &= \Phi_r(\mathcal{C}_1,\dots,\mathcal{C}_r) \end{aligned} $$ where $\mathcal{C}_1 = \mathcal{A}.$ Not all specifications are interesting or meaningful. For instance, the specification $$ \mathcal{A} = \mathcal{A} $$ always holds and says nothing, while the specification $$ \mathcal{A} = \mathcal{Z} + \mathcal{A} $$ has no solution. It thus makes sense to restrict the types of specifications we consider.
The dependency graph of a specification is a directed graph whose vertices are the classes $\mathcal{C}_1,\dots,\mathcal{C}_r$ in the specification, with an edge from the vertex corresponding to the class $\mathcal{C}_i$ to the vertex corresponding to the class $\mathcal{C}_j$ if $\mathcal{C}_j$ appears in $\Phi_i(\mathcal{C}_1,\dots,\mathcal{C}_r).$ A specification is called iterative if its dependency graph has no directed cycles, and recursive if it has a directed cycle (including a self loop).
Remark: A combinatorial class may be specified in multiple ways, some of which are iterative and some of which are recursive. For instance, the class $\mathcal{B}$ of binary strings admits the iterative specification $$ \mathcal{B} = \text{SEQ}(\mathcal{Z}_0 + \mathcal{Z}_1)$$ and the recursive specification $$ \mathcal{B} = \epsilon + (\mathcal{Z}_0 + \mathcal{Z}_1) \times \mathcal{B}. $$
A rational specification is an iterative specification that uses only the sum, product, and sequence constructions together with the atomic and neutral classes. According to the results proved above, a class described by a rational specification will always admit a rational generating function.
We will also see many examples of recursive specifications. Although it is possible for recursive specifications to have no solution (or multiple solutions) the types of combinatorial objects we consider will lead to specifications that clearly have a unique solution. The best known and most useful approach to testing when a recursive specification has a unique solution is Joyal’s implicit species theorem (and computational extensions), which uses notions from Species Theory and thus goes beyond the scope of these notes.
Rational Specifications #
We now give some examples of rational specifications. We begin by proving a result previously derived in Chapter 2 using a direct counting argument.
Example: Recall from Chapter 2 that a composition of size $n$ is a tuple of positive integers $(k_1,\dots,k_r)$ with $k_1 + \cdots + k_r = n.$ Use a rational specification of the class $\mathcal{C}$ to prove that for any $n>1$ there are $2^{n-1}$ compositions of size $n.$
Click for Answer
If $\mathcal{P}$ denotes the combinatorial class of positive integers then the definition of compositions implies $\mathcal{C} = \text{SEQ}(\mathcal{P}).$ Since we have seen above that $\mathcal{P} = \text{SEQ}_{\geq 1}(\mathcal{Z}),$ we thus have $$ \mathcal{C} = \text{SEQ}\left(\text{SEQ}_{\geq 1}(\mathcal{Z})\right)$$ so that $$ C(z) = \frac{1}{1-\frac{z}{1-z}} = \frac{1-z}{1-2z} = \frac{1}{1-2z} - \frac{z}{1-2z}.$$ The rules of coefficient extraction imply that $$ [z^n]C(z) = [z^n]\frac{1}{1-2z} - [z^n] \frac{z}{1-2z} = 2^n-2^{n-1} = 2^{n-1} $$ for $n \geq 1,$ as claimed.
Exercise: (a) Find the number of compositions of size $n$ that have exactly $k$ parts (i.e., are $k$ tuples).
(b) Find the number of compositions of size $n$ that have at most $k$ parts.
Restricted String Enumeration #
A (binary) regular expression is any specification defined by the neutral class $\epsilon,$ the atomic classes $\mathcal{Z}_0$ and $\mathcal{Z}_1,$ and the sum, product, and sequence constructions. By convention, when studying regular expressions we use the digits $0$ and $1$ for the atomic classes $\mathcal{Z}_0$ and $\mathcal{Z}_1,$ drop the $\times$ symbol, and use the notation $\mathcal{A}^*$ for $\text{SEQ}(\mathcal{A}).$
Example: The expression $(\mathcal{Z}_0 \times \mathcal{Z}_1 + \mathcal{Z}_1) \times \text{SEQ}(\mathcal{Z}_0)$ is written $(01+1)0^*.$
Any element in a combinatorial class defined by a regular expression is composed of a nested series of tuples of $0$s and $1$s. We can thus view such a combinatorial class as a class of binary strings by “flattening” all nested tuples (i.e., writing an element as a single tuple generated by reading $0$s and $1$s left to right) and forgetting any colours put on objects in disjoint unions. We say that a regular expression produces the class of binary strings constructed in this way, and any such class is called a regular language. A regular expression is ambiguous if it can produce some binary string in at least two different ways and unambiguous if this does not happen. In particular, an unambiguous regular expression can never contain a sum of two sets of strings that share a common element.
Example: The regular expression $(1 + 10)(1 + 01)$ is ambiguous because the string $101$ is produced in two ways (by taking $1$ in the first factor and $01$ in the second, or by taking $10$ in the first factor and $1$ in the second).
We can enumerate a regular language by creating an unambiguous regular expression that produces the language and using our results above to translate the regular expression into a rational generating function. A block in a binary string is a maximal subsequence of adjacent elements that are all $0$s or all $1$s.
Example: The unambiguous regular expressions $0^*(11^*00^*)^*1^*$ and $1^*(00^*11^*)^*0^*$ generate all binary strings by uniquely decomposing a string into its blocks of $0$s and $1$s. For instance, the first expression uses the fact that any string can be uniquely decomposed into a (possibly empty) sequence of $0$s, followed by a sequence of non-empty blocks of $1$s and $0$s, followed by a (potentially empty) final sequence of $1$s.
Exercise: Verify that the unambiguous regular expressions $0^*(11^*00^*)^*1^*$ and $1^*(00^*11^*)^*0^*$ both yield the expected generating function $1/(1-2z)$ for the class of all binary strings.
Modifying these block decompositions allows for the study of classes with restrictions on the blocks that can appear.
Example: Find the number of binary strings of length $n\geq1$ without consecutive $1$s in terms of the Fibonacci sequence $(f_n)$ that satisfies the recurrence $f_{n+2} = f_{n+1} + f_n$ and has rational generating function $F(z) = \frac{1}{1-z-z^2}.$
Click for Answer
Any binary string without consecutive $1$s can be uniquely decomposed into at most one $1$ followed by a finite (possibly zero) number of blocks consisting of at least one $0$ followed a single $1,$ and then a final (possibly empty) sequence of $0\text{s.}$
The regular language $\mathcal{L}$ containing the binary strings without consecutive $1$s is thus produced by the unambiguous regular grammar $ \mathcal{L} = (\epsilon + 1)(00^*1)^*0^* ,$ which gives the generating function $$ L(z) = (1+z) \frac{1}{1-\frac{z^2}{1-z}} \frac{1}{1-z} = \frac{1+z}{1-z-z^2}. $$ Thus, $$ \begin{aligned} [z^n]L(z) &= [z^n]\frac{1}{1-z-z^2} + [z^n]\frac{z}{1-z-z^2} \\[+4mm] &= f_n + f_{n-1} \\[+3mm] &= f_{n+1} \end{aligned} $$ for all $n \geq 1.$
Exercise: Find the generating function for the number of binary strings where every block has size at most $2.$ Express the number of such binary strings of length $n$ in terms of the Fibonacci numbers $(f_n).$
Exercise: Find the generating function for the number of binary strings where every block of ones has even length.
Set Partitions #
A set partition of size $n$ is a decomposition of $[n]=\{1,\dots,n\}$ into a disjoint union of non-empty sets called blocks.
Example: The five set partitions of size 3 are $$ \begin{aligned} \{1,2,&3\} \qquad \{1,2\} \cup \{3\} \qquad \{1,3\} \cup \{2\}\\[+3mm] &\{1\} \cup \{2,3\} \qquad \{1\} \cup \{2\} \cup \{3\} \end{aligned} $$ One of these set partitions has a single block, three of the set partitions have two blocks, and one of the set partitions has three blocks.
Fix a positive integer $r.$ Let $\mathcal{S}_r$ be the class of set partitions with $r$ blocks, and let $\mathcal{T}_r$ be the class of strings $\sigma$ on the alphabet $\Omega = \{1,2,\dots,r\}$ such that
-
each element of $\Omega$ appears at least once in $\sigma,$ and
-
for all $1 \leq i \leq r$ the first occurrence of $i$ in $\sigma$ (when reading left-to-right) comes before the first occurrence of $i+1.$
If $P$ is a set partition with $r$ parts then we can uniquely sort its blocks $B_1,\dots,B_r$ according to their minimal elements, and given $i \in [n]$ we write $b_P(i)=j$ for the index $j$ such that $i \in B_j.$ Define the map $f:\mathcal{S}_r\rightarrow\mathcal{T}_r$ that takes a set partition $P \in \mathcal{S}_r$ of size $n$ to the string $f(S) = b_P(1) \cdots b_P(n).$
Example: If $r=4$ and $P = \{1,2\} \cup \{3\} \cup \{4,5,7\} \cup \{6,8\}$ is a set partition of size $8$ then $f(P)$ is the string $11233434.$
Exercise: Prove that $f$ is a bijection from $\mathcal{S}_r$ to $\mathcal{T}_r.$
The number of set partitions of size $n$ with $r$ blocks is known as the $(n,r)$-Stirling number of the second kind and denoted $\left\{ n \atop r \right\}.$ These numbers appear in a variety of applications, including the moments of discrete random variables with Poisson distributions and the number of rhyming schemes in poems or songs when the number of lines and rhyming syllables are fixed.
Exercise: (a) Prove that $\mathcal{T}_r$ admits the specification $$ \begin{aligned} \mathcal{T}_r =& \quad\;\mathcal{Z}_1 \times \text{SEQ}(\mathcal{Z}_1) \\[+2mm] &\times \mathcal{Z}_2 \times \text{SEQ}(\mathcal{Z}_1 + \mathcal{Z}_2) \\[+2mm] &\times \mathcal{Z}_3 \times \text{SEQ}(\mathcal{Z}_1 + \mathcal{Z}_2 + \mathcal{Z}_3) \\[+2mm] &\times \cdots \times \mathcal{Z}_r \times \text{SEQ}(\mathcal{Z}_1 + \cdots + \mathcal{Z}_r). \end{aligned} $$ (b) Prove that $$ S_r(z) = \sum_{n \geq 0} \left\{ n \atop r \right\} z^n = \frac{z^r}{(1-z)(1-2z)\cdots (1-rz)}. $$
(c) Using induction on $r,$ or a partial fraction decomposition of $S_r,$ prove that $$ \left\{ n \atop r \right\} = \frac{1}{r!} \sum_{j=0}^r (-1)^{r-j}\binom{r}{j} j^n $$
We will return to set partitions in Chapter 10, after we discuss exponential generating functions and labelled constructions. This additional technology will allow us to re-derive this expression for the Stirling numbers of the second kind in a more efficient manner, and then go much further in the study of set partitions.
Recursive Specifications #
Rational specification can only encode combinatorial classes with rational generating functions. Moving to recursive specifications thus allows a larger variety of combinatorial behaviour to be captured.
Example: Recall from Chapter 2 that a rooted planar binary tree of size $n$ is either empty or is a vertex followed by a left rooted planar binary tree and a right rooted planar binary tree (where the order of these subtrees matters). If $\mathcal{B}$ is the class of rooted planar binary trees then this definition implies the specification $$ \mathcal{B} = \underbrace{\epsilon}_{\text{empty tree}} \overbrace{+}^{\text{or}} \underbrace{\mathcal{Z}}_{\text{root vertex}} \overbrace{\times}^{\text{and}} \underbrace{\mathcal{B}}_{\text{left subtree}} \overbrace{\times}^{\text{and}} \underbrace{\mathcal{B}}_{\text{right subtree}}. $$ In particular, we see that the generating function $B(z)$ of $\mathcal{B}$ satisfies the algebraic equation $$ B(z) = 1 + zB(z)^2. $$ The quadratic formula implies that the equation $y=1+zy^2$ has two solutions $$y_{\pm}(z) = \frac{1 \pm \sqrt{1-4z}}{2z}. $$ Only one of these solutions $$ \begin{aligned} y_(z) &= 1 + z + 2z^2 + \cdots \\ y_+(z) &= z^{-1}-1-z-\cdots \end{aligned} $$ has a power series expansion at the origin (the factor of $z$ in the denominator cancels with a factor of $z$ in the numerator) so $$ B(z) = y_{-}(z) = \frac{1-\sqrt{1-4z}}{2z}.$$ The final example in Chapter 4 shows that $$ [z^n] \frac{1-\sqrt{1-4z}}{2z} = \frac{1}{n+1}\binom{2n}{n},$$ so that the number of rooted planar binary trees are counted by this sequence of Catalan numbers.
Remark: The fact that there is an empty rooted planar binary tree helped us set up a convenient specification. We often include, or don’t include, objects of size $0$ as necessary to simplify our arguments.
Example: Prove that for $n \geq 1$ there are $\frac{1}{n}\binom{2n-2}{n-1}$ rooted planar trees (where there is no restriction on the number of subtrees each vertex has but all subtrees are nonempty).
Click for Answer
Let $\mathcal{T}$ denote the class of rooted planar trees with no objects of size $0.$ Then we have the specification $$ \mathcal{T} = \mathcal{Z} \times \text{SEQ}(\mathcal{T}), $$ since an element of $\mathcal{T}$ is a root followed by a (possibly empty) sequence of subtrees. Note that we don’t let $\mathcal{T}$ contain the empty tree so that we can use the sequence construction.
This specification implies $$ T(z) = \frac{z}{1-T(z)}, $$ so that $$ T(z)^2 - T(z) + z = 0. $$ The quadratic formula implies that the polynomial equation $y^2-y+z=0$ has two solutions $$ \begin{aligned} y_-(z) = \frac{1-\sqrt{1-4z}}{2} &= z + z^2 + 2z^3 + \cdots \\[+4mm] y_+(z) = \frac{1+\sqrt{1-4z}}{2} &= 1-z-z^2 - \cdots \end{aligned} $$ with power series representations near the origin. Although both solutions to this polynomial equations are power series, only one has positive coefficients, and thus $$ B(z) = y_-(z) = \frac{1 - \sqrt{1-4z}}{2}.$$ In particular, the number of rooted planar trees with $n \geq 1$ vertices is $$ [z^n] \frac{1 - \sqrt{1-4z}}{2} = [z^{n-1}] \frac{1 - \sqrt{1-4z}}{2z} = \frac{1}{n}\binom{2n-2}{n-1}. $$
Exercise: Let $n \geq 1.$ Give a bijection between the set of rooted planar binary trees on $n$ nodes and the set of rooted planar trees on $n-1$ nodes.
Exercise: A Dyck path of length $n$ is a lattice path using the steps $(1,1)$ and $(1,-1)$ that starts at the origin $(0,0),$ ends at $(2n,0),$ and never moves to a point with negative $y$-coordinate. Prove that there are $\frac{1}{n+1}\binom{2n}{n}$ Dyck paths of length $n.$
The examples above led to quadratic equations, which were solved explicitly using the quadratic formula. However, this may not be possible: although algebraic equations of degree at most 4 can always be solved in radicals (with expressions getting more complicated as the degree of the equation increases) there are algebraic equations with degree 5 (and higher) that cannot be solved in radicals.
Example: The class $\mathcal{F}$ of rooted planar complete 5-ary trees has the specification $$ \mathcal{F} = \mathcal{Z} + \mathcal{Z} \times \mathcal{F}^5, $$ so its generating function satisfies $$ zF(z)^5 - F(z) + z = 0. $$ The generating function $F(z)$ cannot be solved explicitly using radicals.
Proof sketch that $F(z)$ cannot be solved in radicals
If $F(z)$ can be expressed explicitly using radicals, then so can every evaluation of $F(z)$ at values of $z$ where the generating series converges. We will determine the counting sequence $(f_n)$ exactly in the next chapter, but for now we take as given that $f_n \leq 2^n$ for all $n.$ The ratio test then implies the formal power series $F(z)$ converges whenever $|z|<1/2$ so, for instance, the value $y = F(1/4)$ exists and satisfies $$ y^5 - 4y + 1 = 0. $$ Running the Sage code
A.<y> = QQ['y'] F = y^5 - 4*y + 1 F.galois_group().is_solvable()gives
Out: Falseso that results in Galois theory imply that $F(1/4)$ cannot be expressed in radicals.
Although we may not always be able to solve for generating functions explicitly, our next chapter proves the Lagrange implicit function theorem which provides a powerful tool for extracting generating function coefficients directly from a defining equation.
Other Constructions #
We end by briefly summarizing some additional combinatorial constructions.
-
If $\mathcal{A}$ is a combinatorial class with no objects of size $0$ then the powerset class $\text{PSET}(\mathcal{A})$ defined by $\mathcal{A}$ is the combinatorial class whose objects consist of all finite sets of objects in $\mathcal{A}$ (without repetition). If $\mathcal{P} = \text{PSET}(\mathcal{A})$ then, since every element of $\mathcal{A}$ can either be included or not included in a subset, we have $$ P(z) = \prod_{\alpha \in \mathcal{A}}(1 + z^{|\alpha|}) = \prod_{n \geq 0} (1+z^n)^{a_n}. $$
Exercise: Use properties of the formal exponential and logarithm to prove that $$P(z) = \exp\left( \sum_{k\geq 1} \frac{(-1)^{k-1}}{k}A(z^k) \right).$$ -
If $\mathcal{A}$ is a combinatorial class with no objects of size $0$ then the multiset class $\text{MSET}(\mathcal{A})$ defined by $\mathcal{A}$ is the combinatorial class whose objects consist of all finite sets of objects in $\mathcal{A}$ (with repetition allowed). If $\mathcal{M} = \text{MSET}(\mathcal{A})$ then, since every element of $\mathcal{A}$ can be included any number of times in a multiset, we have $$ M(z) = \prod_{\alpha \in \mathcal{A}}\left(\frac{1}{1-z^{|\alpha|}}\right) = \prod_{n \geq 0} (1-z^n)^{-a_n}. $$
Exercise: Use properties of the formal exponential and logarithm to prove that $$M(z) = \exp\left( \sum_{k\geq 1} \frac{A(z^k)}{k} \right).$$ -
If $\mathcal{A}$ is defined by a rational specification then the pointed class $\mathcal{A}^\prime$ defined by $\mathcal{A}$ is the class consisting of copies of the objects in $\mathcal{A}$ where one atom is marked (think of giving it a special colour). For example, the class of rooted planar trees is the pointed class defined by the class of planar trees. Because there are $n$ ways to pick an atom to mark in an object of size $n,$ and objects of size $0$ cannot be marked, if $\mathcal{C} = \mathcal{A}^\prime$ then $$ C(z) = \sum_{n \geq 1} n a_n z^n = z A^\prime(z), $$ where $A^\prime(z)$ denotes the formal derivative of $A(z).$
Additional Problems #
Problem 1. A Motzkin path of length $n$ is a lattice path using the steps $(1,1),(1,-1),$ and $(1,0)$ that starts at the origin $(0,0),$ ends at $(n,0),$ and never moves to a point with negative $y$-coordinate. Find the generating function for the class of Motzkin paths.
Problem 2. Prove that for all $n \in \mathbb{N}$ the number of Motzkin paths from $(0,0)$ to $(n,0)$ equals the number of Dyck paths from $(0,0)$ to $(2n,0)$ that don’t have three consecutive $(1,1)$ steps.
Problem 3. Find the generating function for the class of lattice paths using the steps $(1,-1)$ or $(1,1)$ that start at the origin and never move to a point with negative $y$-coordinate (but don’t need to end on the $x$-axis).
Problem 4. (a) Find the number of compositions of size $n$ that have an even number of parts.
(b) Find the number of compositions of size $n$ that have an odd number of parts.
(c) Find the generating function of compositions whose parts alternate between being odd and even.
Problem 5. Find the generating function for the class of compositions with at least one part such that the first part is odd. Show that the probability that a composition of size $n$ has its first part odd approaches $2/3$ as $n\rightarrow\infty.$ Hint: Partial fraction decomposition will probably be useful.
Problem 6. Find the number of binary strings of length $n$ such that every block of 0s is followed by an even number of 1s.
Problem 7. (a) Find the generating function for the class $\mathcal{C}$ of rooted planar binary trees such that any node that is the right child of its parent is a leaf (meaning it has no children).
(b) Prove that for $n \geq 1$ the number of elements in $\mathcal{C}$ of size $n$ is given by the Fibonacci number $f_n$ (defined by the recurrence $f_{n+2} = f_{n+1} + f_n$ and initial conditions $f_0=f_1=1$).
Problem 8. Prove that the generating function $F(z)$ of non-planar rooted complete binary trees (where the left child and right child of a node are not distinguished) satisfies $$ F(z) = z + z\frac{F(z)^2 + F(z^2)}{2}. $$
Problem 9. An integer composition $(k_1,\dots,k_r)$ is a palindrome if $(k_1,k_2,\dots,k_r) = (k_r,k_{r-1},\dots,k_1),$ meaning the composition is the same when read backwards or forwards. Give a specification for the class of palindromic integer compositions and then give a formula for the number of palindromic integer compositions of size $n.$
Problem 10. Prove that the generating function $B_r(z)$ for the class of binary strings with blocks of size at most $r$ is $$ B_r(z) = \frac{1-z^{r+1}}{1-2z+z^{r+1}}. $$