Add combinatorics summary until topic 3
Change-Id: Iad09497c56db0301b7b4f25a1de4192ab1b1929c
diff --git a/quad9/combinatorics/summary/topic2.tex b/quad9/combinatorics/summary/topic2.tex
new file mode 100644
index 0000000..2fe7754
--- /dev/null
+++ b/quad9/combinatorics/summary/topic2.tex
@@ -0,0 +1,112 @@
+% !TEX root = main.tex
+
+\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
+ \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
+
+\chapter{Labeled combinatorial classes}
+\section{Introduction}
+
+\begin{defi}
+ Let $a = (a_0, a_1, \ldots)$. Then, the \underline{EGF} of $a$ is:
+ \[ A(z) = \sum_{n \geq 0} \frac{a_n}{n!} z^n. \]
+\end{defi}
+
+\begin{obs}
+ Observe that if $A(z)$ and $B(z)$ are EGF of $a$ and $b$, then:
+
+ \begin{itemize}
+ \item $\mathcal{C}(z) = A(z) + B(z)$ is the EGF of $a + b$.
+ \item $\mathcal{C}(z) = A(z) \cdot B(z)$ is the EGF of $c_n = \sum \binom{n}{k} a_k b_{n - k}$ (the binomial convolution).
+ \end{itemize}
+\end{obs}
+
+\begin{defi}
+ A combinatorial class $A$ is \underline{labeled} if the objects are classes of graphs (directed graphs). The size of an object is the number of nodes.
+
+ The nodes of a graph with $n$ nodes are labelled with $\{ 1, 2, \ldots n \}$.
+\end{defi}
+
+\begin{example}[Class of urns]
+ Let $\mathcal{U}$ be the class of edgeless labeled graphs. Then:
+ \[ \mathcal{U} = \{ \varepsilon, \circled{1}, \circled{1} \circled{2}, \circled{1} \circled{2} \circled{3}, \ldots \}. \]
+ The EFG is:
+ \[ U(z) = \sum_{n \geq 0} \frac{z^n}{n!} = e^z. \]
+\end{example}
+
+\begin{example}[Class of permutations]
+ Let $\mathcal{P}$ be the class of directed paths:
+ \[ \mathcal{P} = \{ \varepsilon, \circled{1}, \circled{1} \rightarrow \circled{2}, \circled{2} \rightarrow \circled{1}, \circled{1} \rightarrow \circled{2} \rightarrow \circled{3}, \ldots \}. \]
+ The EFG is:
+ \[ A(z) = \sum_{n \geq 0} z^n = \frac{1}{1 - z}. \]
+\end{example}
+
+\begin{example}[Class of cycles]
+ Let $\mathcal{C}$ be the class of directed cycles. Then, $c_n = \frac{n!}{n} = (n - 1)!$, so the EFG is:
+ \[ A(z) = \sum_{n \geq 0} \frac{z^n}{n} = - \log (1 - z). \]
+\end{example}
+
+\section{Operations on labeled classes}
+\begin{defi}
+ The \underline{sum} $\mathcal{C} = A + B$ is such that its EGF is $C(z) = A(z) + B(z)$.
+\end{defi}
+
+\begin{defi}
+ The \underline{labeled product} $\mathcal{C} = A * B = \{ \alpha * \beta : (\alpha, \beta) \in A \times B \}$, where
+ \[ \alpha * \beta = \left\{ (\alpha', \beta') : \substack{
+ \alpha' \text{ labeled with } |\alpha| \text{ numbers in } [|\alpha| + |\beta|] \\
+ \beta' \text{ labeled with } |\beta| \text{ numbers in } [|\alpha| + |\beta|]
+ } : \rho(\alpha') = \alpha, \rho(\beta') = \beta \right\}, \]
+ with $\rho(d)$ being the reduction of sequence $d$.
+
+ Its EFG is $C(z) = A(z) \cdot B(z)$.
+\end{defi}
+
+\begin{defi}
+ The \underline{sequence} of a labeled class is $\mathcal{C} = \text{SEQ}(A) = \varepsilon + A + A * A + A * A * A + \ldots$, whose EFG is $C(z) = \frac{1}{1 - A(z)}$.
+\end{defi}
+
+\begin{defi}
+ The \underline{set} of a labeled class is
+ \[ \mathcal{C} = \text{SET}(A) = \cup_k \text{SET}(A, \text{card} = k), \]
+ with
+ \[ \text{SET}(A, \text{card} = k) = \frac{\overbrace{A * A * \cdots * A}^{k}}{\sim} \]
+ where $\sim$ is the equivalence relation ``up to ordering''. Every equivalence class of an ordered object has $k!$ elements. Thus, the EFG is:
+ \[ C(z) = e^{A(z)}. \]
+\end{defi}
+
+\begin{example}[Class of permutations]
+ \[ \mathcal{P} = \Set(\mathcal{C}). \]
+\end{example}
+
+\begin{example}[Class of derangements]
+ Let $\mathcal{D}$ be the class of permutations with no fixed points (derangements). Then:
+ \[ D = \Set(\mathcal{C} - \mathcal{C}_1), \quad d_n = n! \sum_{k = 1}^n \frac{(-1)^k}{k!}. \]
+\end{example}
+
+\begin{example}[Class of convolutions]
+ Let $\Gamma$ be the class of convolutions: $\{ \sigma \in \mathcal{S}_n : \sigma^2 = Id \}$. Then:
+ \[ \Gamma = \Set(\mathcal{C}_1 + \mathcal{C}_2), \quad I(z) = e^z e^{z^2/2}, \quad I_n = \sum_{k = 0}^{\lfloor n/2 \rfloor} \frac{n!}{k! (n - 2k)! 2^k}. \]
+\end{example}
+
+\begin{example}[Class of permutations with $k$ cycles]
+ Let $P^{(k)}$ be such class. Then:
+ \[ P^{(k)} = \Set(\mathcal{C}, \text{card} = k), \quad P_n^{(k)} = \stirlingfirst{n}{k}. \]
+\end{example}
+
+\begin{defi}
+ The \underline{Stirling number of the first kind} (signless stirling number) is:
+ \[ \stirlingfirst{n}{k} := \frac{n!}{k!} \sum_{\substack{i_1 + \ldots + i_k = n \\ i_1, \ldots, i_k \geq 1}} \frac{1}{i_1 \cdot \cdots \cdot i_k}. \]
+\end{defi}
+
+\begin{obs}
+ Observe that, if we separate the cases in which $n + 1$ is not or is a single cycle, then:
+ \[ \stirlingfirst{n + 1}{k} = n \cdot \stirlingfirst{n}{k} + \stirlingfirst{n}{k - 1}. \]
+\end{obs}
+
+\section{Set partitions}
+\[ \mathcal{P} = \Set(\mathcal{U} - \varepsilon), \quad p_n = B_n = \sum_{k = 1}^n \stirlingsec{n}{k} = \frac{1}{e} \sum_{k \geq 0} \frac{k^n}{k!}. \]
+
+\begin{example}[Partitions of a set into $k$ parts]
+ Let's revisit this example. We have
+ \[ \mathcal{P}^{(k)} = \Set(\mathcal{U} - \varepsilon, \text{card} = k), \quad P_n^{(k)} = \stirlingsec{n}{k}. \]
+\end{example}