Combinatorial species: An intuition behind generating functions

Правка en1, от adamant, 2022-06-17 20:06:37

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.

Prerequisites

  • Basic notion of set theory (cardinality of sets, mappings, bijections, cartesian product, disjoint union, etc);
  • Polynomials and formal power series (representation, convolution formula);
  • 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 \mapsto B$$$.

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

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

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

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

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)$$$.

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) \mapsto G(A)$$$ for $$$A \in X$$$, such that for every bijection $$$\sigma : A \mapsto 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$$$.

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.

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 both an $$$F$$$-structure and a $$$G$$$-structure, constructed on the same 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$$$.

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 broduct 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.

Examples

  • 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. $$$
  • $$$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.

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:
$$$ |(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)|$$$.

With this definition, we can show that - The disjoint union of species yields the summation 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). $$$

Examples

  • 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 iverse transform from disjoint sets of $$$G$$$ to $$$G$$$ itself. The result more commonly known as the exponential formula.

  • 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 can be represented as sets of cycles. It means that $$$\frac{1}{1-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. $$$
  • 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$$$.
  • 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}. $$$
  • 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.

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 \mapsto 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)$$$.

Further reading

Теги tutorial, combinatorics, generating function

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en55 Английский adamant 2022-07-19 19:45:47 23
en54 Английский adamant 2022-07-19 19:44:59 12
en53 Английский adamant 2022-07-19 19:44:31 1125
en52 Английский adamant 2022-07-19 16:54:10 169
en51 Английский adamant 2022-07-19 12:58:52 45
en50 Английский adamant 2022-07-19 12:56:28 18
en49 Английский adamant 2022-07-19 12:55:41 29
en48 Английский adamant 2022-07-19 12:54:42 284
en47 Английский adamant 2022-06-30 11:10:54 11
en46 Английский adamant 2022-06-30 11:09:24 10
en45 Английский adamant 2022-06-30 11:03:11 389
en44 Английский adamant 2022-06-30 10:56:22 82 Tiny change: 's:\n\n$$\nf:A→B,h:B→D,g:A→C,k:C→D.\begin{mat' -> 's:\n\n$$\n\begin{mat'
en43 Английский adamant 2022-06-30 10:50:10 984
en42 Английский adamant 2022-06-20 03:52:15 555 Tiny change: 's:\n\n$$\nf:A↦B,g:A↦C,h:B↦D,k:C↦D.\begin{mat' -> 's:\n\n$$\n\begin{mat'
en41 Английский adamant 2022-06-19 13:48:26 30
en40 Английский adamant 2022-06-19 13:47:27 772
en39 Английский adamant 2022-06-19 13:35:08 2
en38 Английский adamant 2022-06-19 13:34:37 1037
en37 Английский adamant 2022-06-19 13:25:53 1126
en36 Английский adamant 2022-06-19 12:51:19 759 Tiny change: 's:\n\n$$\nf:A↦B,h:B↦D,g:A↦C,k:C↦D.\begin{mat' -> 's:\n\n$$\n\begin{mat'
en35 Английский adamant 2022-06-19 12:47:55 394
en34 Английский adamant 2022-06-19 04:25:34 201
en33 Английский adamant 2022-06-19 04:22:27 480
en32 Английский adamant 2022-06-19 04:15:47 4
en31 Английский adamant 2022-06-19 04:14:45 75
en30 Английский adamant 2022-06-19 04:07:57 836
en29 Английский adamant 2022-06-18 23:33:18 143
en28 Английский adamant 2022-06-18 23:32:00 391
en27 Английский adamant 2022-06-18 23:30:46 451
en26 Английский adamant 2022-06-18 23:25:43 643
en25 Английский adamant 2022-06-18 14:40:30 955
en24 Английский adamant 2022-06-18 11:53:49 23
en23 Английский adamant 2022-06-18 11:40:52 2
en22 Английский adamant 2022-06-18 11:27:30 419
en21 Английский adamant 2022-06-18 04:32:26 480
en20 Английский adamant 2022-06-18 04:21:45 654
en19 Английский adamant 2022-06-18 04:11:08 4
en18 Английский adamant 2022-06-18 04:10:21 167
en17 Английский adamant 2022-06-18 03:39:15 192 Tiny change: 's:\n\n$$\nf:A↦B,h:B↦D,g:A↦C,k:C↦D.\begin{mat' -> 's:\n\n$$\n\begin{mat'
en16 Английский adamant 2022-06-18 03:35:14 41
en15 Английский adamant 2022-06-17 23:26:41 3
en14 Английский adamant 2022-06-17 21:44:54 43
en13 Английский adamant 2022-06-17 21:43:02 121
en12 Английский adamant 2022-06-17 21:41:00 67
en11 Английский adamant 2022-06-17 21:40:04 396
en10 Английский adamant 2022-06-17 21:33:18 362
en9 Английский adamant 2022-06-17 21:27:54 17
en8 Английский adamant 2022-06-17 21:27:08 2
en7 Английский adamant 2022-06-17 21:24:01 152
en6 Английский adamant 2022-06-17 21:19:18 10 Tiny change: 's:\n\n$$\nf:A↦B,h:B↦D,g:A↦C,k:C↦D.\begin{mat' -> 's:\n\n$$\n\begin{mat'
en5 Английский adamant 2022-06-17 21:17:41 798
en4 Английский adamant 2022-06-17 20:46:38 638
en3 Английский adamant 2022-06-17 20:33:34 1128 Tiny change: 's:\n\n$$\nf:A↦B,h:B↦D,g:A↦C,k:C↦D.\begin{mat' -> 's:\n\n$$\n\begin{mat'
en2 Английский adamant 2022-06-17 20:13:38 193
en1 Английский adamant 2022-06-17 20:06:37 16446 Initial revision (published)