Блог пользователя adamant

Автор adamant, история, 2 года назад, По-английски

Hi everyone!

The usage of generating functions is quite common in competitive programming these days. But it seems to happen so, that they're mostly presented as a way to simplify formal manipulation with polynomial coefficients, rather than something meaningful. But there actually is a meaning to all of this, and today I'm going to shed a light on it.

Alongside the blog post we'll uncover the combinatorial meaning of

  • The addition $$$F(x)+G(x)$$$,
  • The multiplication $$$F(x)G(x)$$$,
  • The exponent $$$\exp F(x)$$$,
  • The logarithm $$$\log F(x)$$$,
  • The sum of the infinite geometric progression $$$\frac{1}{1-F(x)}=1+F(x)+F^2(x)+\dots$$$,
  • The general composition $$$F(G(x))$$$

for the generating functions $$$F(x)$$$ and $$$G(x)$$$ and the underlying structures they represent.

Prerequisites

  • Basic notion of set theory (cardinality of sets, mappings, bijections, cartesian product, disjoint union, etc);
  • Polynomials and formal power series (representation, convolution formula, power series definitions of $$$\exp$$$ and $$$\log$$$);
  • Elementary combinatorics (combinations, partitions, etc).

Although combinatorial species are defined with category theory concepts, I will try to avoid them for simplicity. However, knowledge of some category theory concepts would greatly simplify the reading experience.

Some of definitions use pretty dense mathematical notation, I will follow up with informal explanation right away when it is the case.

Commutative diagrams

I will also use commutative diagrams to illustrate complicated identities. You may use the explanation below as a reference.

Explanation

Every diagram is also provided with a more verbose text description, so don't be afraid if the concept seems complicated.


Definitions

A mapping $$$F$$$ that maps elements of $$$A$$$ to elements of $$$B$$$ is denoted as $$$F : A \to B$$$.

Def. 1. The identity map $$$\operatorname{Id}_A : A \to A$$$ is defined as $$$\operatorname{Id}_A(a) = a$$$ for $$$a \in A$$$.

Def. 2. Let $$$F : A \to B$$$ and $$$G : B \to C$$$. Then the composition $$$G \circ F$$$ is defined as $$$(G \circ F)(a) = G(F(a))$$$ for $$$a \in A$$$.

In the definition below we use a notion of a class. Informally, it is a collection of sets joined by some property, which does not have to be a set of its own, but for which we may still consider some mappings (functions) on top of it. It is also possible to formalize the concept or to bypass the need for it to not be a set, see the comment below.

Alternatively, if you're really uncomfortable working with proper classes (which requires the addition of new axioms to the Zermelo-Fraenkel set theory), you may assume that the work is done in the set of hereditarily finite sets rather than the class of finite sets.

Def. 3. Let $$$U$$$ be a class of finite sets. A combinatorial species is a mapping $$$F : U \to U$$$ and a family of bijections $$$F_\sigma : F(A) \to F(B)$$$ defined for every bijection $$$\sigma : A \to B$$$ between $$$A,B \in U$$$ in such way that

  1. If $$$\sigma : A \to B$$$ and $$$\tau : B \to C$$$ are bijections, then $$$F_{\tau \circ \sigma} = F_\tau \circ F_\sigma$$$;
  2. For $$$B=A$$$ and $$$\operatorname{Id}_A : A \to B$$$ it holds that $$$F_{\operatorname{Id}_A} = \operatorname{Id}_{F(A)}$$$.

The elements of $$$F(A)$$$ are called the $$$F$$$-structures and the bijection $$$F_\sigma$$$ is called the transport of $$$\sigma$$$ along $$$F$$$-structures.


In category theory terms, a combinatorial species is a functor on the category of finite sets.

Informally, $$$F(A)$$$ is a set of combinatorial structures (graphs, trees, sequences, etc) that are defined by the species $$$F$$$ and labeled by the elemenets of $$$A$$$. The bijections $$$F_\sigma$$$ define the rules in which structures change after re-labeling. In this terms, the rules are read as

  1. Re-labeling from $$$A$$$ to $$$B$$$ using $$$\sigma$$$ and then from $$$B$$$ to $$$C$$$ using $$$\tau$$$ should be same as re-labeling directly from $$$A$$$ to $$$C$$$ using $$$\tau \circ \sigma$$$;
  2. Re-labeling from $$$A$$$ to $$$A$$$ using the identity map should not change $$$F(A)$$$.

For example, let $$$F$$$ be a species of labeled trees. Then, $$$F(A)$$$ should map $$$A$$$ to a set of all labeled trees that can be build on $$$|A|$$$ vertices, such that each vertex is labeled by an element from $$$A$$$. On the picture below, you see $$$F(A_2)$$$, $$$F(A_3)$$$ and $$$F(A_4)$$$:


Labeled trees on sets $$$A_2 = \{{\color{red} \bullet}, {\color{blue} \bullet}\}$$$, $$$A_3 = \{{\color{red} \bullet}, {\color{blue} \bullet}, {\color{green} \bullet}\}$$$ and $$$A_4 = \{{\color{red} \bullet}, {\color{blue} \bullet}, {\color{green} \bullet}, {\color{goldenrod} \bullet}\}$$$.
The image by Júlio Reis is distributed under CC BY-SA 3.0 license.

Correspondingly, if you were to change labels from $$$A_4 = \{{\color{red} \bullet}, {\color{blue} \bullet}, {\color{green} \bullet}, {\color{goldenrod} \bullet}\}$$$ to $$$X_4 = \{1,2,3,4\}$$$ with a mapping $$$\sigma : A_4 \to X_4$$$, the bijection $$$F_\sigma : F(A_4) \to F(X_4)$$$ would map each tree from $$$F(A_4)$$$ to $$$F(X_4)$$$ according to the way labels are changed from $$$A_4$$$ to $$$X_4$$$ by $$$\sigma$$$.

Further examples

  • Set species is defined as $$$E(A) = \{A\}$$$, combinatorial structure is a set of $$$|A|$$$ elements labeled by $$$A$$$;
  • $$$n$$$-set species is defined as $$$E_n(A)= \{A\}$$$ if $$$|A|=n$$$ and $$$E_n(A)=\varnothing$$$ otherwise;
  • Singleton species $$$X$$$ is defined as $$$X(A)=E_1(A)$$$;
  • Subset species is defined as $$$F(A) = 2^A$$$, combinatorial structure is a subset of $$$A$$$;
  • Permutation species $$$S$$$ is defined as $$$S(A) = S_{A}$$$, combinatorial structures are permutations (bijections to itself) of $$$A$$$;
  • Graph species is defined as $$$F(A) = \{(A, E) : E \subset A \times A\}$$$, combinatorial structures are graphs with $$$A$$$ as vertices;
  • Cycle species $$$C$$$ corresponds to combinatorial structures being cycles of $$$|A|$$$ elements labeled by $$$A$$$;
  • Partition species $$$\operatorname{Par}$$$ corresponds to combinatorial structures being partitions of $$$A$$$;
  • Linear order species $$$L$$$ corresponds to combinatorial structures being ordered $$$|A|$$$-tuples of distinct elements from $$$A$$$.

Species isomorphism

Def. 4. Let $$$F$$$ and $$$G$$$ be two species. Species isomorphism $$$\alpha$$$ is a family of bijections $$$\alpha_A : F(A) \to G(A)$$$ for $$$A \in X$$$, such that for every bijection $$$\sigma : A \to B$$$, and every $$$f \in F(A)$$$ it holds that $$$G_\sigma(\alpha_A(f)) = \alpha_B(F_\sigma(f))$$$.


In category theory terms, the mapping $$$\alpha$$$ is a natural transformation.

Informally, $$$\alpha_A$$$ tells us how to transform any combinatorial structure of the species $$$F(A)$$$ into the one of $$$G(A)$$$, so that the transform is consistent with any re-labeling from $$$A$$$ to $$$B$$$.

Further on, when writing $$$F=G$$$ for species $$$F$$$ and $$$G$$$ we will mean that the species are isomorphic.

Examples

Let $$$X_n = \{1, 2, \dots, n\}$$$.

  • Species of subsets is isomorphic to the species of ordered possibly empty partitions into two blocks.
    • E.g. the subset $$$\{1, 3, 4\}$$$ of $$$X_5$$$ corresponds to the partition $$$(\{1,3,4\}, \{2, 5\})$$$.
  • Species of permutations is isomorphic to the species of sets of cycles.
    • E.g. the permutation $$$\sigma = \binom{1~2~3~4}{2~1~4~3}$$$ corresponds to the set of cycles $$$\{(1 \to 2), (3 \to 4)\}$$$.

Note that the species of linear orders $$$G$$$ (orderings of $$$A$$$) are not isomorphic to the species of permutations $$$F$$$, even though $$$|F(X_n)|=|G(X_n)|=n!$$$. Consider $$$F(X_2) = \left\{\binom{1~2}{1~2},\binom{1~2}{2~1}\right\}$$$ and $$$G(X_2) = \{(1,2), (2, 1)\}$$$. If we relabel with $$$\sigma(1)=2$$$ and $$$\sigma(2)=1$$$, elements of $$$F(X_2)$$$ will not change, while elements of $$$G(X_2)$$$ will get swapped. Hence, there is no $$$\alpha$$$ consistent with such $$$\sigma$$$.

Operations on species

The operations defined below are the core ones that are related to generating functions.

This section uses the concept of the disjoint union of two sets. For sets $$$A$$$ and $$$B$$$, their disjoint union $$$A \sqcup B$$$ is constructed in such way that every element that belongs to both $$$A$$$ and $$$B$$$ appears twice: once as an element of $$$A$$$ and once as an element of $$$B$$$. This is unlike the regular union in which elements from the intersection appear once. You can define the disjoint union formally as

$$$ A \sqcup B = A \times \{\circ \} \cup B \times \{\bullet\}, $$$

where $$$\circ$$$ marks the elements from $$$A$$$ and $$$\bullet$$$ marks the elements from $$$B$$$.


The disjoint union of $$$A$$$ and $$$B$$$ is formed by the union of elements labeled by the set they came from.
The image by Kismalac is distributed under CC BY-SA 3.0 license.

Def. 5. The addition $$$F+G$$$ of species $$$F$$$ and $$$G$$$ is defined as their disjoint union:

$$$ \boxed{(F+G)(A) = F(A) \sqcup G(A)} $$$

Informally, $$$(F+G)$$$-structure is either an $$$F$$$-structure or a $$$G$$$-structure.

Def. 6. The cartesian product $$$F \times G$$$ of species $$$F$$$ and $$$G$$$ is defined as

$$$ \boxed{(F \times G)(A) = F(A) \times G(A)} $$$

Informally, $$$(F \times G)$$$-structure is a pair of an $$$F$$$-structure and a $$$G$$$-structure, both constructed on the set $$$A$$$.

Def. 7. The ordinary product $$$F \cdot G$$$ of species $$$F$$$ and $$$G$$$ is defined as

$$$ \boxed{(F \cdot G)(A) = \bigsqcup\limits_{\substack{B \cup C = A\\ B \cap C = \varnothing}} F(B) \times G(C)} $$$

Informally, $$$(F \cdot G)$$$-structure on $$$A$$$ is a pair of an $$$F$$$-structure on $$$B$$$ and a $$$G$$$-structure on $$$C$$$ such that $$$(B, C)$$$ is an ordered partition of $$$A$$$.


$$$A$$$ is partitioned in $$$A = B \sqcup C$$$, then an $$$F$$$-structure is constructed on top of $$$B$$$ and a $$$G$$$-structure is constructed on top of $$$C$$$.
The image by Brent Yorgey is distributed under CC BY-SA 3.0 license.

Def. 8. Let $$$\pi$$$ be an unordered partition of $$$A$$$. The composition $$$F \circ G$$$ of species $$$F$$$ and $$$G$$$ is defined as

$$$ \boxed{(F \circ G)(A) = \bigsqcup\limits_{\pi} \left(F(\pi) \times \prod\limits_{B \in \pi} G(B) \right)} $$$

Here $$$\prod$$$ denotes the cartesian product over all elements of $$$\pi$$$.

Informally, $$$(F \circ G)$$$-structure on $$$A$$$ is an $$$F$$$-structure built on top of $$$G$$$-structures that are constructed on each element of the partition.


$$$A$$$ is partitioned by $$$\pi$$$, a $$$G$$$-structure is formed on top of each element of $$$\pi$$$, then an $$$F$$$-structure is formed on top of $$$\pi$$$.
The image by Brent Yorgey is distributed under CC BY-SA 3.0 license.

Examples

Species of sets and sequences as a sum of simpler species.

  • The set species can be represented as a sum of all $$$n$$$-set species:
$$$ E = \sum\limits_{n=0}^\infty E_n. $$$
  • The species $$$L_n$$$ of linear orders of $$$n$$$-sets is isomorphic to $$$X^n=E_1^n$$$ and
$$$ L = \sum\limits_{n=0}^\infty X^n. $$$
  • The non-empty sets species $$$E^+$$$ is represented as
$$$ E^+ = \sum\limits_{n=1}^\infty E_n. $$$

Neutral elements for operations.

  • Empty species $$$0 = G$$$ such that $$$G(A)=\varnothing$$$ for any $$$A$$$ is the neutral element of the species addition. That is, $$$0 + G = G + 0 = G$$$.
  • Empty set species $$$1 = E_0$$$ is the neutral element of the species ordinary product. That is, $$$1 \cdot F = F \cdot 1 = F$$$.
  • Singleton species $$$X = E_1$$$ is the neutral element of the species composition. That is, $$$X \circ F = F \circ X = F$$$.

Species as compositions of simpler species.

  • $$$E \circ G$$$ is a species of sets of $$$G$$$-structures, $$$E_n \circ G$$$ is a species of $$$n$$$-sets of $$$G$$$-structures;
  • $$$S = E \circ C$$$: a species of permutations is isomorphic to the species of sets of cycles;
  • $$$\operatorname{Par} = E \circ E^{+}$$$: a species of partitions is a species of sets of non-empty sets;

Function species is a set of cycles of rooted trees
An illustration from Combinatorial Species article by François Bergeron
  • $$$f = S \circ T$$$: a species $$$f$$$ of functions from $$$A$$$ to $$$A$$$ can be represented as a permutation (set of cycles) of rooted tree species $$$T$$$.

Recursively defined species.


An ordered tree may be represented as a root, followed by a sequence of ordered trees.
An illustration from Binomial species and combinatorial exponentiation article by Gilbert Labelle.

A species $$$\triangle$$$ of ordered trees is described as a tree, in which the children of each node are ordered. In other words, ordered tree is a pair $$$(x, L)$$$, where $$$x$$$ is a node of the tree and $$$L$$$ is a possibly empty ordered tuple of its subtrees. Therefore, in terms of species operations,

$$$ \triangle = X \cdot (1+\triangle + \triangle^2 + \triangle^3 + \dots) = X \cdot (L \circ \triangle), $$$

where $$$X=E_1$$$ is a node of the tree and $$$1=E_0$$$ is the empty sequence.

In the picture above, the set $$$A=\{a,b,c,d,e,f,g,h,i,j,k, 0,1,2,3,4,5,6,7,8,9\}$$$ is first split in a pair

$$$ (X, L(T)) = (\{e\}, \{a,b,c,d,f,g,h,i,j,k,0,1,2,3,4,5,6,7,8,9\}), $$$

which corresponds to the ordinary product of singleton species and the sequence of ordered trees. The label $$$e$$$ from the first set is given to the root and the set of remaining labels then is given to the "list of trees". Then the later set is partitioned with

$$$ \pi = \{\{a,1,9,5,g,j,c,7\}, \{f,d,0\}, \{b,4,3,2,i,h,6,8,k\}\}. $$$

At last, another tree species is constructed on each set from $$$\pi$$$ and then the sequence species constructed on $$$\pi$$$ itself to make it ordered, which corresponds to the composition of the sequence species and ordered tree species.

Cardinalities of species operations

Note that the cardinality of $$$F(A)$$$ is determined by the cardinality of $$$A$$$ (otherwise $$$F_\sigma$$$ wouldn't be a bijection).

Let $$$f_i = |F(A)|$$$ for $$$|A|=i$$$ and $$$g_j = |G(A)|$$$ for $$$|A|=j$$$. What can we say about $$$|(F+G)(A)|$$$ and $$$|(F\cdot G)(A)$$$ for $$$|A|=k$$$?

  • For disjoint union, the formula is simple:
$$$ |(F+G)(A)| = |F(A) \sqcup G(A)| = |F(A)|+|G(A)| = f_k + g_k. $$$
  • Correspondingly, for the cartesian product:
$$$ |(F \times G)(A)| = |F(A) \times G(A)| = |F(A)| \cdot |G(A)| = f_k \cdot g_k. $$$
  • For the ordinary product:
$$$ |(F \cdot G)(A)| = \left|\bigsqcup\limits_{\substack{B \cup C = A \\ B \cap C = \varnothing}} F(B) \times G(C)\right| = \sum\limits_{\substack{B \cup C = A \\ B \cap C = \varnothing}}|F(B)| \cdot |G(C)| = \sum\limits_{i+j=k} \binom{k}{i} f_i g_j. $$$
  • And for the composition (assuming $$$g_0=0$$$):
$$$ |(F \circ G)(A)| = \sum\limits_{\pi}|F(\pi)|\prod\limits_{B \in \pi} |G(B)| = \sum\limits_{i=0}^\infty \frac{f_i}{i!}\sum\limits_{j_1+\dots+j_i=k} \binom{k}{j_1 ~ j_2 ~ \dots ~ j_i} g_{j_1} \dots g_{j_i}. $$$

In the last two formulas we have used the fact that there are $$$\binom{k}{i}$$$ ways to partition a set $$$A$$$ of size $$$k$$$ into sets $$$B$$$ and $$$C$$$ of sizes $$$i$$$ and $$$k-i$$$. Similarly for the composition, there are

$$$ \binom{k}{j_1 ~ j_2 ~ \dots ~ j_i} = \frac{k!}{j_1! \dots j_i!} $$$

ways to partition a set into $$$i$$$ sets of sizes $$$j_1, \dots, j_i$$$. The division by $$$i!$$$ here is needed to account for partitions being unordered, as every unordered partitions is counted for every permutation of $$$(j_1, \dots, j_i)$$$ and there are $$$i!$$$ such permutations.

Generating functions

The idea behind generating functions is to define a class of objects with operations of sum, product and composition that is consistent with a way these operations are defined above for species. The formulas above for the ordinary product and the composition could be rewritten in the following way:

  • For $$$h_k = |(F \cdot G)(A)|$$$ with $$$|A|=k$$$:
$$$ \frac{h_k}{k!} = \sum\limits_{i+j=k} \frac{f_i}{i!} \frac{g_j}{j!}. $$$
  • For $$$h_k = |(F \circ G)(A)|$$$ with $$$|A|=k$$$:
$$$ \frac{h_k}{k!} = \sum\limits_{i=0}^\infty \frac{f_i}{i!} \sum\limits_{j_1 + \dots + j_i = k} \frac{g_{j_1}}{j_1!} \dots \frac{g_{j_i}}{j_i!}. $$$

These formulas are consistent with the following definition:

Def. 9. The exponential generating function (EGF) of a species $$$F$$$ is defined as a formal power series

$$$ F(x) = \sum\limits_{k=0}^\infty \frac{f_k}{k!} x^k, $$$

where $$$f_k = |F(X_k)|$$$ is the number of $$$F$$$-structures you could build on a set of $$$k$$$ elements.

With this definition, we can show that

  • The addition of species yields the addition of the generating functions:
$$$ F(x)+G(x) = \sum\limits_{k=0}^\infty \frac{f_k+g_k}{k!}x^k = (F+G)(x). $$$
  • The cartesian product of species yields something similar to the Hadamard product of the generating functions:
$$$ F(x) \star G(x) = \sum\limits_{k=0}^\infty \frac{f_k g_k}{k!}x^k = (F \times G)(x). $$$
  • The ordinary product of species yields the product of the generating functions:
$$$ F(x) G(x) = \sum\limits_{k=0}^\infty x^k \sum\limits_{i+j=k} \frac{f_i}{i!} \frac{g_{j}}{j!} = \sum\limits_{k=0}^\infty \frac{h_k}{k!} x^k = (F \cdot G)(x). $$$
  • The composition of species yields the composition of the generating functions:
$$$ F(G(x)) = \sum\limits_{i=0}^\infty \frac{f_i}{i!} G^i(x) = \sum\limits_{k=0}^\infty x^k \sum\limits_{i=0}^\infty \frac{f_i}{i!} [x^k]G^i(x) = \sum\limits_{k=0}^\infty x^k \sum\limits_{i=0}^\infty \frac{f_i}{i!} \sum\limits_{j_1+\dots+j_i=k} \frac{g_{j_1}}{j_1!} \dots \frac{g_{j_i}}{j_i!} = (F \circ G)(x). $$$

The last formula is only valid for $$$G(0)=g_0=0$$$, that is $$$G(\varnothing)=\varnothing$$$, as all sets in the partition are non-empty.

Examples

EGF of sets. The EGF of sets species is

$$$ E(x) = \sum\limits_{k=0}^\infty \frac{x^k}{k!} = e^x. $$$

The expression above provides the combinatorial meaning to $$$\exp F(x)$$$ and $$$\log F(x)$$$ operations on the generating functions. Specifically, $$$\exp F(x)$$$ is the generating function for the disjoint sets of $$$F$$$ structure, while $$$\log F(x)$$$ makes the inverse transform from disjoint sets of $$$G$$$ to $$$G$$$ itself. The result more commonly known as the exponential formula.

The EGF of $$$n$$$-sets species is $$$E_n(x)=\frac{x^n}{n!}$$$. In particular, the EGF of a singleton species is $$$X(x)=E_1(x) = x$$$.

EGF of permutations. The EGF of permutations species is

$$$ S(x) = \sum\limits_{k=0}^\infty \frac{k!}{k!} x^k = \sum\limits_{k=0}^\infty x^k = \frac{1}{1-x}. $$$

Permutations species is isomorphic to sets of cycles, that is $$$S = E \circ C$$$. It means that

$$$ \frac{1}{1-x} = S(x) = E(C(x)) = e^{C(x)}, $$$

where $$$C(x)$$$ is the generating function of cycles. Therefore,

$$$ C(x) = \log S(x) = \log \frac{1}{1-x} = \sum\limits_{k=1}^\infty \frac{x^k}{k} = \sum\limits_{k=1}^\infty \frac{(k-1)!}{k!} x^k. $$$

Indeed, there are $$$(k-1)!$$$ ways to make a cycle out of $$$k$$$ distinct elements.

EGF of sequences. Species of linear orders is an ordered tuple of $$$k$$$ singletons for some $$$k$$$, hence

$$$ L(x) = \sum\limits_{k=0}^\infty E_1^k(x) = \sum\limits_{k=0}^\infty x^k = \frac{1}{1-x}. $$$

Another way to get it is to note that $$$L = E_0 + X \cdot L$$$, that is any sequence is either empty (corresponds to $$$E_0$$$) or can be represented as a pair of the first element (corresponds to $$$X$$$) and the sequence constructed from remaining elements (corresponds to $$$L$$$ in $$$X \cdot L$$$). This yields an equation $$$L(x) = 1+xL(x)$$$.

EGF of partitions. The partition is a set of non-empty sets: $$$\operatorname{Par} = E \circ E^+$$$. Therefore, the EGF of the partition species is

$$$ \operatorname{Par}(x) = e^{E^+(x)} = e^{e^x - 1}. $$$

EGFs related to Catalan numbers. In the examples below we work with labeled versions of balanced bracket sequences and trees. Informally, it means that each vertex of the tree has a label (e.g. a number from $$$1$$$ to $$$n$$$) and each pair of brackets in the bracket sequence is also associated with some label.

Changing labels on the same tree/bracket sequence generally leads to a different object with the same underlying structure. For "unlabeled" case see the next section.

Balanced bracket sequence species $$$B$$$ is a (possibly empty) sequence (linear order) of balanced bracket sequences, each of them wrapped in a pair of brackets. The generating function for the balanced bracket sequence wrapped in a pair of brackets is $$$X \cdot B$$$ (as it can be represented as a pair of the outer brackets, perceived as a singleton, and the underlying sequence). Correspondingly, a sequence of wrapped bracket sequences is $$$L \circ (X \cdot B)$$$ and it has a generating function $$$L(xB(x))$$$. Therefore:

$$$ B(x) = \frac{1}{1-xB(x)}. $$$

Solving the equation above for $$$B(x)$$$ yields $$$xB^2(x) - B(x) + 1 =0$$$, hence

$$$ B(x) = \frac{1\pm\sqrt{1-4x}}{2x}, $$$

which corresponds to the genfunc of the Catalan numbers.

Ordered tree species $$$\triangle$$$ adheres to the identity $$$\triangle = X \cdot (L \circ \triangle)$$$. Thus,

$$$ \triangle(x) = x \cdot L(\triangle(x)) = x \cdot \frac{1}{1-\triangle(x)}. $$$

Solving the equation for $$$\triangle(x)$$$ yields $$$\triangle^2(x) - \triangle(x) + x = 0$$$, hence

$$$ \triangle(x) = \frac{1\pm \sqrt{1-4x}}{2}, $$$

which is also the generating function for the Catalan numbers.

Functions and rooted trees. Recall the species of functions $$$f$$$ and rooted trees $$$T$$$ that were introduced in the previous section. Counting rooted trees is not a trivial task, but we know that there are $$$n^n$$$ functions from a set of size $$$n$$$ onto itself. That means that

$$$ f(x) = \sum\limits_{k=0}^\infty \frac{k^k}{k!} x^k, $$$

but on the other hand $$$f = S \circ T$$$, so

$$$ f(x) = \frac{1}{1-T(x)}, $$$

from which we get

$$$ T(x) = 1-\frac{1}{f(x)}. $$$

Unlabeled species

The techniques and concepts developped above also can be used to deal with unlabeled objects.

Def. 10. Two structures $$$\alpha, \beta \in F(A)$$$ are equivalent if there is a bijection $$$\sigma: A \to A$$$ such that $$$F_\sigma(\alpha) = \beta$$$.

Informally, the structures are equivalent if one is obtainable from another via re-labeling to the same set $$$A$$$.

Def. 11. An unlabeled structure is an equivalence class on $$$F(A)$$$ under the equivalence relation defined above.

Informally, unlabeled structure is what we get if we "erase" labels in $$$F(A)$$$ (e.g. erase labels of vertices in graphs, etc).


On the left and on the right are equivalent trees. In the middle is the representation of their unlabeled structure.

Def. 12. The ordinary generating function (OGF) of a species $$$F$$$ is defined as a formal power series

$$$ \widetilde F(x) = \sum\limits_{k=0}^\infty \tilde f_k x^k, $$$

where $$$\tilde f_k$$$ is the number of unlabeled $$$F$$$-structures on $$$X_k$$$.

One can prove that $$$\widetilde{(F \cdot G)}(x) = \widetilde F(x) \widetilde G(x)$$$ and $$$\widetilde{(F+G)}(x) = \widetilde F(x) + \widetilde G(x)$$$. The ordinary product formula stands, as you do not have to multiply by $$$\binom{k}{i}$$$ to account for the distribution of labels between the first and the second sets of the partition.

At the same time, $$$\widetilde{(F \circ G)}(x)$$$ generally can't be computed just from $$$\widetilde F(x)$$$ and $$$\widetilde G(x)$$$.

Examples

The OGF of $$$L$$$ species is

$$$ \widetilde L(x) = \sum\limits_{k=0}^\infty x^k = \frac{1}{1-x}, $$$

as all ordered $$$n$$$-tuples are equivalent under re-labeling.

The OGF of $$$S$$$ species is

$$$ \widetilde S(x) = \prod\limits_{k=1}^\infty \frac{1}{1-x^k}, $$$

which is the generating function of partitions, as permutations are equivalent under re-labeling if and only if they have the same cycle type, and the number of distinct cycle types of permutations of size $$$n$$$ amounts for the number of partitions of $$$n$$$.

As you see, although $$$L(x)=S(x)$$$, at the same time $$$\widetilde L(x) \neq \widetilde S(x)$$$, which highlights the fact that $$$S$$$ and $$$L$$$ are not isomorphic species.

Exercises

Composition formula for sequences. Show that $$$\widetilde{(L \circ F)}(x) = \widetilde L(\widetilde F(x))=\frac{1}{1-\widetilde F(x)}$$$ for any species $$$F$$$.

Counter-example to general composition formula. Find species $$$A$$$ and $$$B$$$ such that $$$\widetilde{(A \circ B)}(x) \neq \widetilde A(\widetilde B(x))$$$.

General formula for multisets of species. Show that $$$\widetilde{(E \circ F)}(x) = \exp\left(\widetilde F(x)+\frac{\widetilde F(x^2)}{2}+\frac{\widetilde F(x^3)}{3}+\dots\right)$$$ for any species $$$F$$$.

General formula for sets of species. Note that erasing labels would possibly allow repeated structures in sets. To get a generating functions for unlabeled sets, in which repeated structures are disallowed, one may use the following formula:

$$$ \operatorname{PSET} \widetilde F(x) = \exp\left(\widetilde F(x)-\frac{\widetilde F(x^2)}{2}+\frac{\widetilde F(x^3)}{3}-\dots\right). $$$

Here, $$$\operatorname{PSET} \widetilde F(x)$$$ denotes the generating function that enumerates sets of unlabeled $$$F$$$-structures, in which structures are not allowed to repeat. In this terms, $$$\widetilde{E \circ F}$$$ may also be represented as $$$\operatorname{MSET} \widetilde F(x)$$$, which is computed as

$$$ \operatorname{MSET} \widetilde F(x) = \exp\left(\widetilde F(x)+\frac{\widetilde F(x^2)}{2}+\frac{\widetilde F(x^3)}{3}+\dots\right). $$$

Unlike $$$\operatorname{MSET}$$$, it is hard to express $$$\operatorname{PSET}$$$ only in species terms, hence this approach is more commonly used in the symbolic method.

OGF for ordered trees and balanced bracket sequences. Show that $$$B(x) = \widetilde{B}(x)$$$ and $$$\triangle(x) = \widetilde{\triangle}(x)$$$ for the ordered trees and the balanced bracket sequences.


All unlabeled ordered trees on $$$n \in \{1,2,3,4\}$$$ vertices.

The structure of the composition on unlabeled structures is a topic of interest in itself and can be found in a more or less general form with the so-called cycle index series, which in turn leads to the Pólya enumeration theorem (which generalizes Burnside's lemma). But to avoid math overload we'll leave this topic for another time.

Further reading

  • Проголосовать: нравится
  • +380
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

great blog thanks for helping the community

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

There is also combinatorial meaning in some other operations.

Let $$$F^\bullet$$$ be a species defined as $$$F^\bullet(A) = A \times F(A)$$$. In other words, it generates pairs of an element of $$$A$$$ and an $$$F$$$-structure on top of $$$A$$$. For example, if $$$F$$$ is a species of trees, then $$$F^\bullet$$$ is a species of rooted trees.

From generating functions perspective, $$$F^\bullet(x) = x \frac{\partial}{\partial x} F(x) = xF'(x)$$$.

Generally, the derivative $$$F'$$$ corresponds to the species $$$F$$$ with a hole. That is, $$$F'(A) = F(A\sqcup \{\star \})$$$, where $$$\star$$$ is a distinguished element not present in $$$A$$$ (a hole, or "virtual" element). Informally, in the definition of $$$F^\bullet$$$, multiplying $$$F'(x)$$$ with $$$x$$$ kind of fills the hole with a newly added singleton element.

»
2 года назад, # |
  Проголосовать: нравится +81 Проголосовать: не нравится

Thanks for the nice introduction! I really liked the approach using commutative diagrams. There is a ton of literature on using category theory related ideas with generating functions (or, more generally, analysis or what seems to be like high school algebra). Digressing a bit, a couple of examples are:

  1. In type theory, for instance, a small part of the basic structure is as follows: $$$+$$$ and $$$\times$$$ are well known to correspond to unions (what you'd call enums in Rust or sum types in Haskell) and structs respectively. Using these, you can construct a lot of recursive structures (like lists, trees, graphs and so on). There's a pretty cool paper that shows that in such a system, you can take "derivatives" of types, and it corresponds to one-hole context of types (which is basically the state you need to maintain to go from one state to another -- think tree rerooting). Similarly, noting that recursive types have a definition that can be mapped directly to objects of that type, we can even try to enumerate those types using such methods (for instance, see this). Some more cool stuff that I can't fit within this comment is here, about infinitesimal types, and here, about Taylor series for types. Some of the comments link to more related mathematical stuff which is pretty cool too.

  2. Matrix representations of certain categories like posets: This leads to some "computation-friendly" structure on such structures, for instance, Mobius inversion on posets. A closely related idea is that of presentations of a category (for instance, see this). Just another digression: representations are very useful in looking at "computation-friendly" structures, and there has been stuff like combinatorial representation theory that studies representations in a combinatorial context. Even stuff like Fourier transform is just an application of characters, which is related to representation of a group by complex functions (and naturally enough, you can do Fourier transforms on finite groups using this idea as well).

Coming back to the content of the original post, there is a nice (and very similar) theory related to this, which also comes in handy while translating problems into the language of generating functions, called the symbolic method: https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics). This is essentially isomorphic to the approach in the blog, but goes in much more detail and has very rich theory, so I would recommend reading up on that. Flajolet and Sedgewick's Analytic Combinatorics is a good reference.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Now that I think of it, I was taught about genfuncs in terms of both combinatorial species and SET/CYC/SEQ operators on "atoms" and so on. It seemed so natural and intertwined that I though it's just a part of a one whole theory. Especially given that operators like SET, CYC, SEQ are just composition with set, cycles or linear orders species. I'm surprised to see they're even deemed to be different concepts.

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +30 Проголосовать: не нравится

    A little 1000‰ rigorous corollary of $$$\texttt{List<T>} = \frac{1}{1 - T}$$$ in the $$$+$$$ is union and $$$\cdot$$$ is struct system:

    We can define a rooted tree with ordered subtrees like this: $$$\texttt{Tree = List<Tree>}$$$. This has only one type of leaf. How boring! Let's change the definition to $$$\texttt{Tree = List< Optional<Tree> >}$$$. This tree is better because it has 2 kinds of leaf nodes: nullopt and empty list.

    Now what does it look like in the $$$+$$$, $$$\cdot$$$ thing? $$$\texttt{Optional<T>} = T+1$$$ since it's like having a $$$T$$$ or a thing that can only have $$$1$$$ state ($$$\texttt{std::optional<T>} = \texttt{std::variant<std::monostate, T>}$$$).

    $$$\texttt{Tree} = \texttt{List< Optional<Tree> >}$$$
    $$$\texttt{Tree} = \frac{1}{1 - \texttt{Optional<Tree>}}$$$
    $$$\texttt{Tree} = \frac{1}{1 - (\texttt{Tree} + 1)}$$$
    $$$-\texttt{Tree}^2 = 1$$$
    $$$\texttt{Tree} = \pm i$$$

    Huh. How neat! The type of trees with two kinds of leaf nodes is plus or minus the imaginary unit. That makes sense since basically nothing changes if you swap them everywhere. Q.E.D.

»
2 года назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

why should i know this

»
2 года назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

Yeah, you definitely need WAY MORE background than what you claim to need to formally understand any of this. You already lost me at

Let U be a class of finite sets

  • »
    »
    2 года назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    I don't really expect people to formally (in terms of seeing how everything is formally proven in ZF set theory from axioms) understand it. Yes, there are some problems when we're speaking about collections of sets joined by arbitrary property (like being finite, being an ordinal etc). Those collections in itself are sometimes not sets, but we still need to work with them in some informal way.

    In this particular case, the actual underlying object is the category of sets. There are several ways to bypass the problems that arise with proper classes, for example one may add as an axiom that Grothendieck universes exist, and then say that we're actually working in one of them. Or to use an alternative axiom system for the set theory which formally defines proper classes. But I really didn't feel like going in all the formal low-level details of it, as I don't think it's crucial to understand the article as a whole.

    Anyway, I've added some clarification to it to the place where the notion of class is used, thanks!

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    oh okay so it wasn't just me then phew

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Okay, based on discussion with adamant, it is sufficient to set $$$U$$$ to be the set of hereditarily finite sets. Then, everything works as usual without assuming anything outside standard ZF.

    I think I understand everything in the blog now, it's a great explanation of GFs, thanks.

»
2 года назад, # |
  Проголосовать: нравится +115 Проголосовать: не нравится

I am sitting in a class surrounded by many students and I am pretending in front of them that I actually know all this stuff written and getting attention(from opposite gender) way more than I deserve.

Thank you adamant

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Here's another view of why $$$\texttt{List}(T) = \frac{1}{1-T}$$$, thinking about it from a "linked list" perspective. A linked list can be in one of two states, either it is null (empty list), or it contains a $$$T$$$ and a pointer to another linked list. The empty list can only be in one state, so it is the species $$$E_0$$$ with generating function $$$1$$$. The non-empty list has generating function $$$T \cdot \texttt{List}(T)$$$. So, we get $$$\texttt{List}(T) = 1+T \cdot \texttt{List}(T)$$$ which has the solution $$$\frac{1}{1-T}$$$.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there something wrong with these statements?

  • E(A) = {A} is set species. For example E({1, 2, 3}) = {{1, 2, 3}}

  • E_n(A) = if |A| == n then {A} else $$$\emptyset$$$ is n-set species. For example E_3({1, 2, 3}) = {{1, 2, 3}}, E_4({1, 2, 3}) = $$$\emptyset$$$

  • (F + G)(A) = F(A) |_| G(A) is addition of species. For example (E_3 + E_4) ({1, 2, 3}) = { ({{1, 2, 3}}, E_3) , ($$$\emptyset$$$, E_4) }

  • $$$E = \sum_{n = 0}^{\inf}E_n$$$ is set species representions as sum of n-set species. For example E({1, 2, 3}) = E_0({1, 2, 3}) |_| E_1({1, 2, 3}) |_| ... = { ($$$\emptyset$$$, E_0) , ($$$\emptyset$$$, E_1), ($$$\emptyset$$$, E_2), ({{1, 2, 3}}, E_3), ($$$\emptyset$$$, E_4), ...} $$$\neq$$$ {{1, 2, 3}}

* How to write here braces {} in formulas?

** Is there any reason trying to understand this?

  • »
    »
    2 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

    If we write it formally, we'd get

    $$$(E_3+E_4)(A) = E_3(A) \sqcup E_4(A) = \{(\{1,2,3\}, E_3)\} \cup \varnothing = \{(\{1,2,3\}, E_3)\}$$$, because $$$\varnothing \times E_4 = \varnothing$$$.

    Therefore, indeed

    $$$ \left(\sum\limits_{k=0}^\infty E_k\right)(A) = \{(A, E_{|A|})\} \neq \{A\} = E(A). $$$

    But when we write $$$F = G$$$ for species $$$F$$$ and $$$G$$$, what we really mean is that $$$F$$$ and $$$G$$$ are isomorphic, but not that $$$F(A)=G(A)$$$ for any set $$$A$$$.

    Braces in Codeforces inline formulas (with a single $) are written as \\{A\\} and in block formulas (with a double $$) are written as \{A\}. I don't know why.

    As for the reasons to understand this — in my opinion, it is mostly important to understand how things works on the high level (in terms of set operations, etc), rather than on low-level (in terms of concrete sets like $$$\{1,2,3\}$$$).

    Of course, you could work with concrete sets if it is easier for you, but, in my opinion, things are much simpler and the structure is more clear when you work with them abstractly.

    On the high-level, for example, $$$E_n(A)$$$ is a set of sets of size n, such that all elements of these sets are all elements from $$$A$$$. Of course, if $$$|A| \neq n$$$, there are $$$0$$$ such sets, so $$$E_n(A)=\varnothing$$$. And if $$$|A|=n$$$, then there is $$$1$$$ such set, which is $$$A$$$ itself, hence $$$E_n(A) = \{A\}$$$.

    Correspondingly, $$$E(A)$$$ is a set of sets of any size, such that all elements of these sets are all elements from $$$A$$$. There is exactly one such set — $$$A$$$ itself, therefore $$$E(A) = \{A\}$$$.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

thank you for such a great blog

»
2 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Some things I'm confused about:

  • Why is $$$\widetilde{S}(x)=\sum_{k=0}^{\infty}k!x^k$$$? Permutations aren't invariant under relabeling. Shouldn't $$$\widetilde{S}(x)$$$ be the partition function instead?

  • General formula for sets of species. Is it true that $$$(\widetilde{E\circ F})(x)=1+\widetilde F(x)=\exp(\ln(1+\widetilde F(x)))$$$? This isn't equal to the right hand side of the equality in the blog though.

  • »
    »
    2 года назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
    1. Oh, I think you're right. Permutations are sets of cycles. That being said, two permutations are equivalent if they have the same cycle type. And the number of cycle types is, indeed, the number of partitions of $$$n$$$.
    2. I don't think it's generally true. It's specifically true for $$$F = X$$$ and, indeed,
    $$$ \exp(x - \frac{x^2}{2}+\frac{x^3}{3}-\dots) = \exp \ln (1 + x) = 1+x. $$$

    The later is because there is exactly $$$1$$$ distinct structure of type $$$X$$$. However, if e.g. $$$F=E_1 + E_2$$$, we will see that $$$\widetilde{E \circ F}$$$ consists of sets $$$\varnothing$$$, $$$\{E_1\}$$$, $$$\{E_2\}$$$ and $$$\{E_1, E_2\}$$$, hence $$$\widetilde{E \circ F}(x) = 1+x+x^2+x^3$$$ and not $$$1+x+x^2$$$.

    • »
      »
      »
      2 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Followup on 2: now I'm confused about why $$$\widetilde{(E\circ X)}(x)=1+x$$$ when $$$(E\circ X)(x)=e^x$$$. In general, why isn't $$$[x^k]\widetilde F(x)$$$ zero if and only if $$$[x^k]F(x)$$$ is (that is, the number of unlabeled structures on a set of $$$k$$$ elements is zero if and only if the number of labeled structures on the same set is zero)?

      • »
        »
        »
        »
        2 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Now, that I think of it, $$$\widetilde{E \circ F}$$$ should actually be perceived as multisets of $$$F$$$, rather than sets of $$$F$$$... That being said, a proper formula would actually be

        $$$ \widetilde{E \circ F}(x) = \exp(\widetilde F(x)+\frac{\widetilde F(x^2)}{2}+\frac{\widetilde F(x^3)}{3}+\dots). $$$

        This corresponds to $$$\operatorname{MSET} F(x)$$$, while the initial formulas was for $$$\operatorname{SET} F(x)$$$ from the symbolic method. Perhaps, there is actually no way to represent $$$\operatorname{SET} F(x)$$$ as a species composition, unless defined specifically for unlabeled species.

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        So, $$$[x^k]\widetilde{(E \circ F)}(x)$$$ for $$$F = E_1 + E_2$$$ would actually be the number of ways to split $$$k$$$ into summands, such that each summand is either $$$1$$$, or $$$2$$$. That is, $$$\lceil \frac{k+1}{2} \rceil$$$, I think...

      • »
        »
        »
        »
        2 года назад, # ^ |
        Rev. 4   Проголосовать: нравится +16 Проголосовать: не нравится

        Thanks for the remarks! By the way, you may prove the result about $$$\operatorname{MSET}$$$ as

        $$$ \widetilde{E \circ F}(x) = \prod\limits_{k=1}^\infty \left(\frac{1}{1-x^k}\right)^{a_k} = \exp\left(\sum\limits_{k=1}^\infty a_k \log \frac{1}{1-x^k}\right), $$$

        for $$$\widetilde F(x) = a_0 + a_1 x + a_2 x^2 + \dots$$$. This in turn rewrites as

        $$$ \exp\left(\sum\limits_{k=1}^\infty a_k \sum\limits_{j=1}^\infty \frac{x^{kj}}{j} \right) = \exp\left(\widetilde F(x) + \frac{\widetilde F(x^2)}{2}+\frac{\widetilde F(x^3)}{3}+\dots\right). $$$
      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I asked about the topic on mathoverflow and was redirected to this article.

        So, with "unlabeling" we have

        $$$ \widetilde{(E \circ F)}(x) = \exp\left(\widetilde F(x) + \frac{\widetilde F(x^2)}{2} + \frac{\widetilde F(x^3)}{3}+\dots\right). $$$

        And for the $$$\operatorname{PSET}$$$ we may introduce "asymmetric" structures as those $$$t$$$ for which

        $$$ F_\sigma(t) = t \iff \sigma = \operatorname{Id}_A $$$

        In other words, an $$$F$$$-structure is asymmetric if it doesn't have non-trivial automorphisms. Then, we may introduce assymetric (flat) part of any species as

        $$$ \overline F(A) = \{t \in F(A) : t\text{ is asymmetric}\}. $$$

        Finally, with this notion, we have the following formula:

        $$$ \overline{(E \circ F)}(x) = \exp\left(\overline F(x) - \frac{\overline F(x^2)}{2} + \frac{\overline F(x^3)}{3} - \dots\right), $$$

        as

        $$$ \overline{(E \circ F)}(x) = \prod\limits_{k=1}^\infty (1+x^k)^{a_k}, $$$

        for $$$\overline F(x) = a_0 + a_1 x + a_2 x^2 + \dots$$$.