quad9/combinatorics/summary/topic3.tex

% !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}