quad9/combinatorics/summary/topic1.tex

% !TEX root = main.tex
\chapter{The symbolic method}

\section{Introduction}
\begin{defi}[combinatorial class]
  A \underline{combinatorial class} is a pair $(A, |\cdot|)$, where $A$ is a countable class of objects together with a \underline{size} function
  \[ \begin{array}{rccc}
    H: & A & \longrightarrow & \n \\
    & \alpha & \longmapsto & |\alpha|
  \end{array} \]
  such that $A_n := \{ \alpha \in A : \; |\alpha| = n \}$ is finite for every $n$.
\end{defi}

\begin{defi}[generating function of a!combinatorial class]
  The \underline{generating function} of a class $A$ is:
  \[ A(z) = \sum_{\alpha \in A} z^{|\alpha|} = \sum_{n \geq 0} a_n z^n, \quad a_n = |A_n|. \]
\end{defi}

\begin{defi}
  The \underline{sum} $\mathcal{C} = A + B$ (disjoint union) is such that $C(z) = A(z) + B(z)$.
\end{defi}

\begin{defi}
  The \underline{product} $\mathcal{C} = A \times B$ (cartesian product) is such that $|(\alpha, \beta)|_\mathcal{C} = |\alpha|_A + |\beta|_A$, so $\mathcal{C}(z) = A(z) \cdot B(z)$.
\end{defi}

\begin{defi}
  The \underline{sequence} of a combinatorial class is defined as the combinatorial class with class
  \[ \mathcal{C} = S(A) = \{ \varepsilon \} + A + A \times A + \cdots + A^n + \cdots, \]
  where $\varepsilon$ is the combinatorial class with 1 element of size 0. Its generating function is:
  \[ C(z) = 1 + A(z) + A^2(z) + \cdots = \frac{1}{1 - A(z)}. \]
\end{defi}

\section{Some examples}
\subsection{Composition of numbers}
\begin{example}[Composition of numbers into parts in $\{1, 2\} = B$]
  \[ I_{\{1, 2\}} = \Seq(\{1, 2\}) = \Seq(B), \]
  \[ I_{\{1, 2\}}(z) = \frac{1}{1 - B(z)} = \frac{1}{1 - z - z^2} = \sum_{n \geq 1} F_n z^n. \]
\end{example}

\begin{example}[Composition of numbers into odd numbers]
  Let $O$ be the class of odd numbers. Then:
  \[ O(z) = z + z^3 + z^5 + \cdots = \frac{z}{1 - z^2}, \]
  \[ \Gamma_O = \Seq(O), \quad \Gamma_O(z) = \frac{1 - z^2}{1 - z - z^2}. \]
\end{example}

\begin{example}[Composition of numbers into an even number of parts]
  Let $\n$ be the class of natural numbers with the natural size function. Then:
  \[ N(z) = \frac{z}{1 - z}, \quad \Gamma^{(E)} = \varepsilon + \n^2 + \n^4 + \cdots, \quad \Gamma^{(E)} (z) = \frac{1}{1 - \left( \frac{z}{1 - z} \right)^2}. \]
\end{example}

\subsection{Partitions of numbers}
\begin{example}[Partitions of numbers]
  In this case, the objects of the class of integer partitions $P$ are $k$-tuples of positive integers $(a_1, a_2, \ldots, a_k), \, a_1 \leq a_2 \leq \cdots \leq a_k$.
  \[ P = \Seq(\{1\}) \times \Seq(\{2\}) \times \cdots, \quad P(z) = \prod_{n \geq 1} \frac{1}{1 - z^n}. \]
\end{example}

\begin{example}[Partitions of numbers into 1s and 2s]
  \[ P = \Seq(\{1\}) \times \Seq(\{2\}). \]
\end{example}

\subsection{Partitions of sets}
\begin{defi}
  The \underline{Stirling number of second kind} denotes the number of partitions of $[n]$ into $k$ parts:
  \[ \stirlingsec{n}{k} = \frac{1}{k!} \sum_{j = 1}^k \binom{k}{j} j^n (-1)^{k - j}. \]
\end{defi}

This result comes from describing the partitions as $n$-tuples of letters from an alphabet which consists of $k$ letters, and considering the following symbolic description:
\[ P = \{ b_1 \} \times \Seq(\{ b_1 \}) \times \{ b_2 \} \times \Seq(\{ b_1 \times b_2 \}) \times \cdots \times \{ b_k \} \times \Seq(\{ b_1, b_2, \ldots, b_k \}). \]

\section{Formal power series}
\begin{prop}
  Let $A(z)$ be a formal power series with $a_0 = 0$, and let $B(z)$ be its functional inverse ($B(A(z)) = z$). Then:
  \[ [z^n] B(z) = b_n = [z^{-1}] \left( \frac{1}{n A^n(z)} \right). \]
\end{prop}

\begin{prop}[Lagrange inversion formula]
  Let $\phi(z) = \sum_{n \geq 0} a_n z^n$, $a_0 \neq 0$.

  If $A(z) = z \phi(A(z))$, then:
  \[ [z^n] A(z) = \frac{1}{n} [z^{n - 1}] (\phi(z))^n. \]
\end{prop}

\section{Dyck paths}
Let $D$ be the paths in the integer plane $\z^2$ with steps:
\[ \begin{cases}
  (x, y) \rightarrow (x + 1, y + 1) \quad (\{ \nearrow \}), \\
  (x, y) \rightarrow (x + 1, y - 1) \quad (\{ \searrow \}),
\end{cases} \]
starting at $(0, 0)$, ending at $(2n, 0)$ without crossing the line $\{ y = 0 \}$. Then:
\[ D = \{ \varepsilon \} + \{ \nearrow \} \times D \times \{ \searrow \} \times D, \]
and
\[ [z^{2m}] D(z) = C_m, \]
the $m$-th Catalan number.

\begin{defi}
  The \underline{m-th Catalan number} is:
  \[ C_m := \frac{1}{m + 1} \binom{2m}{m}. \]
\end{defi}

\section{Plane trees}
Let $\tau$ be the class of rooted trees embedded in the plane such that that there is a root, and the order of the subtrees branching from each node is relevant. Then:
\[ \tau = N \times \Seq(\tau), \quad [z^n] T(z) = C_{n - 1}. \]

\begin{example}[Binary trees]
  \[ \beta = \varepsilon + N \times \beta \times \beta, \quad [z^n] B(z) = C_n. \]
\end{example}

\section{Lagrange-Bürman formula}
\begin{teo}[Lagrange-Bürman formula]
  Generalization of Lagrange's formula: let $g \in \cx[[x]]$ ($g$ can also be any analytic function). Then:
  \[ [z^n] g(A(z)) = \frac{1}{n} [z^{n - 1}] g'(z) (\phi(z))^n. \]
\end{teo}