Add combinatorics summary until topic 3
Change-Id: Iad09497c56db0301b7b4f25a1de4192ab1b1929c
diff --git a/quad9/combinatorics/combinatorics_defs.tex b/quad9/combinatorics/combinatorics_defs.tex
index 0cb107c..31add62 100644
--- a/quad9/combinatorics/combinatorics_defs.tex
+++ b/quad9/combinatorics/combinatorics_defs.tex
@@ -1 +1,4 @@
\newcommand*{\Seq}[0]{\text{Seq}}
+\newcommand*{\Set}[0]{\text{Set}}
+\DeclareRobustCommand{\stirlingsec}{\genfrac\{\}{0pt}{}}
+\DeclareRobustCommand{\stirlingfirst}{\genfrac[]{0pt}{}}
diff --git a/quad9/combinatorics/summary/.gitignore b/quad9/combinatorics/summary/.gitignore
new file mode 100644
index 0000000..120e611
--- /dev/null
+++ b/quad9/combinatorics/summary/.gitignore
@@ -0,0 +1,2 @@
+*.pdf
+figures/
diff --git a/quad9/combinatorics/summary/main.tex b/quad9/combinatorics/summary/main.tex
new file mode 100644
index 0000000..c91d68a
--- /dev/null
+++ b/quad9/combinatorics/summary/main.tex
@@ -0,0 +1,26 @@
+\documentclass[12pt,english]{notes}
+
+\input{../combinatorics_defs.tex}
+
+\usepackage{apuntsgenerics}
+\usepackage{pgfplots}
+
+\setlength{\parskip}{1em}
+
+% Tensor commands:
+\newcommand*{\TT}[1]{\bar{\bar{#1}}}
+
+\title{\vspace{-.5em}Combinatorics and Graph Theory summary}
+\author{Adrià Vilanova Martínez\vspace{-2em}}
+
+\titlemonth{Semestre tardor curs 2021-22}
+
+\begin{document}
+
+\makecover
+
+\input{topic1.tex}
+\input{topic2.tex}
+\input{topic3.tex}
+
+\end{document}
diff --git a/quad9/combinatorics/summary/topic1.tex b/quad9/combinatorics/summary/topic1.tex
new file mode 100644
index 0000000..45dbc4d
--- /dev/null
+++ b/quad9/combinatorics/summary/topic1.tex
@@ -0,0 +1,113 @@
+% !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}
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}
diff --git a/quad9/combinatorics/summary/topic3.tex b/quad9/combinatorics/summary/topic3.tex
new file mode 100644
index 0000000..6c14b08
--- /dev/null
+++ b/quad9/combinatorics/summary/topic3.tex
@@ -0,0 +1,67 @@
+% !TEX root = main.tex
+
+\chapter{Enumerations with symmetries}
+\section{Group actions}
+
+\begin{defi}
+ Let $X$ be a set. We say \underline{$G$ acts on $X$} if for all $\sigma \in G$ $\exists$ a map $X \to X$ such that:
+ \[ \sigma(\tau(x)) = (\sigma \tau)(x), \quad \forall x \in X, \quad \forall \sigma, \tau \in G, \]
+ \[ \text{id}(x) = x. \]
+\end{defi}
+
+\begin{defi}
+ For $x \in X$, we define the \underline{stabliser subgroup}:
+ \[ G_x = \{ \sigma \in G : \sigma(x) = x \}. \]
+\end{defi}
+
+\begin{lema}
+ If $G$ acts transitively on $X$, then $|G_x| \cdot |X| = |G|$.
+\end{lema}
+
+\section{Group action on functions}
+
+\begin{defi}
+ Suppose $G$ acts on $X$. Let $C^x$ denote a set of functions $f: X \to C$ where $C$ is a finite set of colors. For $\sigma \in G$, and $f \in C^X$, we define $\sigma(f) \in C^X$ by:
+ \[ \sigma(f)(x) := f(\sigma^{-1}(x)). \]
+\end{defi}
+
+\section{The cycle-index polynomial}
+Let $G$ act on $X$, a set of size $n$. For each $\sigma \in G$, $\sigma$ has a cyclic decomposition in its action on $X$ (since its action is a permutation on $X$).
+
+\begin{defi}
+ Let \[ \begin{cases}
+ C_i^X(\sigma) = \# \; i\text{-cycles in the cyclic decomposition of } \sigma \text{ acting on } X, \\
+ C^X(\sigma) = \# \; \text{cycles in the cyclic decomposition of } \sigma \text{ acting on } X = \sum_i C_i^X(\sigma).
+ \end{cases} \]
+
+ The \underline{cycle-index polynomial} for the action is:
+ \[ Z_G^X (X_1, \ldots, X_n) = \frac{1}{|G|} \sum_{\sigma \in G} \prod_{i = 1}^n X_i^{C_i^X(\sigma)}. \]
+\end{defi}
+
+\begin{teo}[Polya's theorem]
+ Suppose $G$ acts on $X$ and $C$ is a set of $r$ colors. The number of orbits of $G$ acting on $C^X$ (i.e. the number of $r$-colorings of $X$ distinct under $G$) is:
+ \[ Z_G^X(r, \ldots, r) = \frac{1}{|G|} \sum_{\sigma \in G} r^{C^X(\sigma)}. \]
+\end{teo}
+
+\section{General version of Polya's theorem}
+Let $X$ be a set, let $C$ be a set of colors, and let $f: X \to C$ be a function. To each color $c_i \in C$, we associate an indeterminate $t_i$.
+
+Let $m_i(f) := \# \; \text{elements of } X \text{ that } f \text{ maps to the } i\text{-th color}$.
+
+Then, we define a function $w: C^X \to \z[t_1, \ldots, t_k]$ by:
+\[ w(f) := \prod_{i = 1}^r t_i^{m_i(f)} = \prod_{x \in X} h(f(x)), \]
+where $h$ maps the $i$-th color to $t_i$.
+
+\begin{teo}[General version of Polya]
+ Suppose that $G$ acts on $X$ and let $C$ be a set of $r$ colors. Let $R$ be a set of representatives of the orbits of the action $G$ on $C^X$. Then:
+ \[ Z_G(t_1 + \cdots + t_r, \ldots, t_1^n + \cdots + t_r^n) = \sum_{f \in R} w(f). \]
+\end{teo}
+
+\begin{obs}
+ The coefficient of $t_1^{k_1} \ldots t_r^{k_r}$ is:
+ \[ \# \; \text{of distinct } r\text{-colorings with } \left\{\begin{array}{ccc}
+ k_1 & \text{colors} & c_1, \\
+ \vdots & & \vdots \\
+ k_r & \text{colors} & c_r.
+ \end{array}\right. \]
+\end{obs}