Add combinatorics summary until topic 3
Change-Id: Iad09497c56db0301b7b4f25a1de4192ab1b1929c
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}