quad9/combinatorics/summary/topic2.tex

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