\chapter{Combinatorial}

\section{Permutations}
	\subsection{Factorial}
		\import{factorial.tex}
		\kactlimport{IntPerm.h}

	\subsection{Cycles}
		Let $g_S(n)$ be the number of $n$-permutations whose cycle lengths all belong to the set $S$. Then
		$$\sum_{n=0} ^\infty g_S(n) \frac{x^n}{n!} = \exp\left(\sum_{n\in S} \frac{x^n} {n} \right)$$

	\subsection{Derangements}
		Permutations of a set such that none of the elements appear in their original position.
		\[ \mkern-2mu D(n) = (n-1)(D(n-1)+D(n-2)) = n D(n-1)+(-1)^n = \left\lfloor\frac{n!}{e}\right\rceil \]

	\subsection{Burnside's lemma}
		Given a group $G$ of symmetries and a set $X$, the number of elements of $X$ \emph{up to symmetry} equals
		 \[ {\frac {1}{|G|}}\sum _{{g\in G}}|X^{g}|, \]
		 where $X^{g}$ are the elements fixed by $g$ ($g.x = x$).

		 If $f(n)$ counts ``configurations'' (of some sort) of length $n$, we can ignore rotational symmetry using $G = \mathbb Z_n$ to get
		 \[ g(n) = \frac 1 n \sum_{k=0}^{n-1}{f(\text{gcd}(n, k))} = \frac 1 n \sum_{k|n}{f(k)\phi(n/k)}. \]

\section{Partitions and subsets}
	\subsection{Partition function}
		Number of ways of writing $n$ as a sum of positive integers, disregarding the order of the summands.
		\[ p(0) = 1,\ p(n) = \sum_{k \in \mathbb Z \setminus \{0\}}{(-1)^{k+1} p(n - k(3k-1) / 2)} \]
		\[ p(n) \sim 0.145 / n \cdot \exp(2.56 \sqrt{n}) \]

		\begin{center}
		\begin{tabular}{c|c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c@{\ }c}
			$n$    & 0 & 1 & 2 & 3 & 4 & 5 & 6  & 7  & 8  & 9  & 20  & 50  & 100 \\ \hline
			$p(n)$ & 1 & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 30 & 627 & $\mathtt{\sim}$2e5 & $\mathtt{\sim}$2e8 \\
		\end{tabular}
		\end{center}

	\subsection{Lucas' Theorem}
		Let $n,m$ be non-negative integers and $p$ a prime. Write $n=n_kp^k+...+n_1p+n_0$ and $m=m_kp^k+...+m_1p+m_0$. Then $\binom{n}{m} \equiv \prod_{i=0}^k\binom{n_i}{m_i} \pmod{p}$.

	\subsection{Binomials}
		\kactlimport{multinomial.h}

\section{General purpose numbers}
	\subsection{Bernoulli numbers}
		EGF of Bernoulli numbers is $B(t)=\frac{t}{e^t-1}$ (FFT-able).
		$B[0,\ldots] = [1, -\frac{1}{2}, \frac{1}{6}, 0, -\frac{1}{30}, 0, \frac{1}{42}, \ldots]$

		Sums of powers:
		\small
		\[ \sum_{i=1}^n n^m = \frac{1}{m+1} \sum_{k=0}^m \binom{m+1}{k} B_k \cdot (n+1)^{m+1-k} \]
		\normalsize

		Euler-Maclaurin formula for infinite sums:
		\small
		\[ \sum_{i=m}^{\infty} f(i) = \int_m^\infty f(x) dx - \sum_{k=1}^\infty \frac{B_k}{k!}f^{(k-1)}(m) \]
		\[ \approx \int_{m}^\infty f(x)dx + \frac{f(m)}{2} - \frac{f'(m)}{12} + \frac{f'''(m)}{720} + O(f^{(5)}(m)) \]
		\normalsize

	\subsection{Stirling numbers of the first kind}
		Number of permutations on $n$ items with $k$ cycles.
		\begin{align*}
			&c(n,k) = c(n-1,k-1) + (n-1) c(n-1,k),\ c(0,0) = 1 \\
			&\textstyle \sum_{k=0}^n c(n,k)x^k = x(x+1) \dots (x+n-1)
		\end{align*}
		$c(8,k) = 8, 0, 5040, 13068, 13132, 6769, 1960, 322, 28, 1$ \\
		$c(n,2) = 0, 0, 1, 3, 11, 50, 274, 1764, 13068, 109584, \dots$

	\subsection{Eulerian numbers}
		Number of permutations $\pi \in S_n$ in which exactly $k$ elements are greater than the previous element. $k$ $j$:s s.t. $\pi(j)>\pi(j+1)$, $k+1$ $j$:s s.t. $\pi(j)\geq j$, $k$ $j$:s s.t. $\pi(j)>j$.
		$$E(n,k) = (n-k)E(n-1,k-1) + (k+1)E(n-1,k)$$
		$$E(n,0) = E(n,n-1) = 1$$
		$$E(n,k) = \sum_{j=0}^k(-1)^j\binom{n+1}{j}(k+1-j)^n$$

	\subsection{Stirling numbers of the second kind}
		Partitions of $n$ distinct elements into exactly $k$ groups.
		$$S(n,k) = S(n-1,k-1) + k S(n-1,k)$$
		$$S(n,1) = S(n,n) = 1$$
		$$S(n,k) = \frac{1}{k!}\sum_{j=0}^k (-1)^{k-j}\binom{k}{j}j^n$$

	\subsection{Bell numbers}
		Total number of partitions of $n$ distinct elements. $B(n) =$
		$1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, \dots$. For $p$ prime,
		\[ B(p^m+n)\equiv mB(n)+B(n+1) \pmod{p} \]

	\subsection{Labeled unrooted trees}
		\# on $n$ vertices: $n^{n-2}$ \\
		\# on $k$ existing trees of size $n_i$: $n_1n_2\cdots n_k n^{k-2}$ \\
		\# with degrees $d_i$: $(n-2)! / ((d_1-1)! \cdots (d_n-1)!)$

	\subsection{Catalan numbers}
		\[ C_n=\frac{1}{n+1}\binom{2n}{n}= \binom{2n}{n}-\binom{2n}{n+1} = \frac{(2n)!}{(n+1)!n!} \]
		\[ C_0=1,\ C_{n+1} = \frac{2(2n+1)}{n+2}C_n,\ C_{n+1}=\sum C_iC_{n-i} \]
		${C_n = 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, \dots}$
		\begin{itemize}[noitemsep]
			\item sub-diagonal monotone paths in an $n\times n$ grid.
			\item strings with $n$ pairs of parenthesis, correctly nested.
			\item binary trees with with $n+1$ leaves (0 or 2 children).
			\item ordered trees with $n+1$ vertices.
			\item ways a convex polygon with $n+2$ sides can be cut into triangles by connecting vertices with straight lines.
			\item permutations of $[n]$ with no 3-term increasing subseq.
		\end{itemize}
