---
tags: Advanced Discrete Structure
---

{%hackmd BkVfcTxlQ %}

# Advanced Discrete Structure Note 1

## Combination w/ repetition

$k$-combination with repetition, or $k$-multicombination, is equivalent to **Diophantine equation** $x_1+x_2+\cdots+x_k=n$.

$\left(\binom{n}{k}\right)=\binom{n+k-1}{k}$ stands for the multiset coefficient, "$n$ **multichoose** $k$".

- $\left(\binom{n}{k}\right)=\frac{n^\overline{k}}{k!}$, whereas $\binom{n}{k}=\frac{n^\underline{k}}{k!}$
- $$\left(\binom{n}{k}\right)=(-1)^k\binom{-n}{k}=\left(\binom{k+1}{n-1}\right)$$
- $$\left(\binom{n}{k}\right)=\left(\binom{n}{k-1}\right)+\left(\binom{n-1}{k}\right)$$, for a particular type of objects, we could either not select any of that type, $\left(\binom{n}{k-1}\right)$, or select one of that type and then we should still **multichoose** $n-1$ out of $k$ types of objects, $\left(\binom{n-1}{k}\right)$.
- $$\sum_{i=0}^\infty\left(\binom{n}{i}\right)x^i=\frac{1}{(1-x)^n}=(1-x)^{-n}$$

## Permutation w/ repetition

\# ways to $k$-permutation of $n$ objects: $n^k$.

## Partition a set into non-empty subsets

\# ways to $k$-non-empty-partition of a set of cardinality $n$ is denoted by $S(n,k)$ or $\begin{Bmatrix}n\\k\end{Bmatrix}$, which is called **Stirling number of the second kind**.

Since by **Inclusion-Exclusion Principle** \# $k$ disjoint sets $S_1,S_2,\cdots,S_k$ is $\sum_{i=0}^k(-1)^i\binom{k}{i}(k-i)^n$, we have $\begin{Bmatrix}n\\k\end{Bmatrix}=\frac{1}{k!}\sum_{i=0}^k(-1)^i\binom{k}{i}(k-i)^n$.

- $$\begin{Bmatrix}n\\k\end{Bmatrix}=k\begin{Bmatrix}n-1\\k\end{Bmatrix}+\begin{Bmatrix}n-1\\k-1\end{Bmatrix}$$, for a particular item, we could either divide the remaining $n-1$ elements into $k$ non-empty subsets and then put it into one of the $k$ ones, $\begin{Bmatrix}n-1\\k\end{Bmatrix}k$, or let it be a subset alone and then divide the remaining $n-1$ elements into $k-1$ non-empty subsets, $\begin{Bmatrix}n-1\\k-1\end{Bmatrix}$.
- $$\sum_{i=0}^\infty\begin{Bmatrix}n\\i\end{Bmatrix}x^\underline{i}=x^n$$

### Partition a set into subsets

\# ways to partition a $n$-cardinality set is known as the **Bell number** $B_n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}$, considering that we could have another non-empty subset containing all elements not selected.

Its _EGF_ is $e^{e^x-1}$. Furthermore, $B_{n+1}=\sum_{i=0}^n\binom{n}{i}B_i$.

### ◎ Stirling number of the 1^st^ kind

Signed
: $s(n,k)$
: $\sum_{i=0}^ns(n,k)x^k=x^\underline{n}$

Unsigned
: $\begin{bmatrix}n\\k\end{bmatrix}$
: $\sum_{i=0}^n\begin{bmatrix}n\\k\end{bmatrix}x^k=x^\overline{n}$
: \# ways to $k$-circular-permutation of $n$ objects

...

## Ordinary Generating Function _(OGF)_

Geometry Series
: $$1+x+x^2+\cdots+x^n=\sum_{i=0}^nx^i=\frac{1-x^{n+1}}{1-x}$$
: $$1+x+x^2+\cdots=\sum_{i=0}^\infty x^i=\frac{1}{1-x}$$

Binomial Theorem
: $$(1+x)^n=\sum_{i=0}^n\binom{n}{i}x^i$$
: $$(1-x)^n=\sum_{i=0}^n\binom{n}{i}(-x)^i$$

Since $\binom{-n}{i}=(-1)^i\binom{n+i-1}{i}$, $$(1+x)^{-n}=\sum_{i=0}^\infty\binom{-n}{i}x^i=\sum_{i=0}^\infty(-1)^i\binom{n+i-1}{i}x^i\\(1-x)^{-n}=\sum_{i=0}^\infty\binom{-n}{i}(-x)^i=\sum_{i=0}^\infty(-1)^i\binom{n+i-1}{i}(-x)^i$$, we have $$(1-x)^{-n}=\sum_{i=0}^\infty\binom{n+i-1}{i}x^i$$.

For a sequence $a_n=\binom{n+m}{n}$, where $m$ is a constant, then its _OGF_ is $F(x)=(1-x)^{-1-m}$.

- $C(x)=A(kx)$ is the _OGF_ of $c_n=k^na_n$
- $C(x)=A(x)+B(x)$ is the _OGF_ of $c_n=a_n+b_n$
- $C(x)=A(x)B(x)$ is the _OGF_ of $c_n=\sum_{i=0}^na_ib_{n-i}$ (Convolution)
- $C(x)=A(x)^k$ is the _OGF_ of $c_n=\sum_{i_1+i_2+\cdots+i_k=n}a_{i_1}a_{i_2}\cdots a_{i_k}$
- $C(x)=xA(x)'$ is the _OGF_ of $c_n=na_n$
- $C(x)=\frac{A(x)}{1-x}$ is the _OGF_ of $c_n=\sum_{i=0}^na_i$

## Exponential Generating Function _(EGF)_

Maclaurin Series
: $$1+x+2\frac{x^2}{2}+3!\frac{x^3}{3!}+\cdots=\sum_{i=0}^\infty i!\frac{x^i}{i!}=\frac{1}{1-x}$$
: $$1+x+\frac{x^2}{2}+\frac{x^3}{3!}+\cdots=\sum_{i=0}^\infty\frac{x^i}{i!}=e^x$$
: $$(1+x+\frac{x^2}{2}+\frac{x^3}{3!}+\cdots)^n=\sum_{i=0}^\infty\frac{n^ix^i}{i!}=e^{nx}$$

Since $x+\frac{x^2}{2}+\frac{x^3}{3!}+\cdots=\sum_{i=1}^\infty\frac{x^i}{i!}=e^x-1$ and $\frac{x^2}{2}+\frac{x^3}{3!}+\cdots=\sum_{i=2}^\infty\frac{x^i}{i!}=e^x-x-1$, we have $$1+\frac{x^2}{2}+\frac{x^4}{4!}+\cdots=\sum_{i=0}^\infty\frac{x^{2i}}{(2i)!}=\frac{e^x+e^{-x}}{2}$$ and $$x+\frac{x^3}{3!}+\frac{x^5}{5!}+\cdots=\sum_{i=0}^\infty\frac{x^{2i+1}}{(2i+1)!}=\frac{e^x-e^{-x}}{2}$$.

For a sequence $a_n=\prod_{i=0}^n(a_0+id)$, then its _EGF_ is $\hat{F}(x)=a_0(1-dx)^\frac{-a_0-d}{d}$.

- $\hat{C}(x)=\hat{A}^{(k)}(x)$ is the _EGF_ of $c_n=a_{n+k}$
- $\hat{C}(x)=\hat{A}(x)+\hat{B}(x)$ is the _EGF_ of $c_n=a_n+b_n$
- $\hat{C}(x)=\hat{A}(x)\hat{B}(x)$ is the _EGF_ of $c_n=\sum_{i=0}^n\binom{n}{i}a_ib_{n-i}$ (Convolution w/ combination and factorial)
- $\hat{C}(x)=\hat{A}(x)^k$ is the _EGF_ of $c_n=\sum_{i_1+i_2+\cdots+i_k=n}\binom{n}{i_1,i_2,\cdots i_k}a_{i_1}a_{i_2}\cdots a_{i_k}$
- $\hat{C}(x)=x\hat{A}(x)$ is the _EGF_ of $c_n=na_n$

### Stirling number of the 2^nd^ kind

The _OGF_ of partitioning a $n$-cardinality set into non-empty $j$ subsets is
$$
F(x)=(x+\frac{x^2}{2}+\frac{x^3}{3!}+\cdots)^n=(\sum_{i=1}^\infty\frac{x^i}{i!})^n=(e^x-1)^n\\
=\sum_{i=0}^n\binom{n}{i}(-1)^ie^{x(n-i)}=\sum_{i=0}^n\binom{n}{i}(-1)^i(\sum_{j=0}^\infty\frac{(n-i)^jx^j}{j!})
$$

So $[x^k]F(x)=\sum_{i=0}^n\binom{n}{i}(-1)^i\frac{(n-i)^kx^k}{k!}=\begin{Bmatrix}n\\k\end{Bmatrix}$.

## ◎ Burnside's lemma

\# orbits ($G_x={g\cdot x|\forall g\in G}$): $$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|$$, where $G$ is the group of acts on the set $X$, $X^g$ represents the set of element in $X$ fixed by an act $g$, i.e., $X^g=\{x|x\in X\land g\cdot x=x\}$.

E.g., a rotation of a permutation could be deemed an act on the permutation.

{%hackmd @nevikw39/signature %}