combinatorics

Combinatorics deals with finite sets and belongs to the subfield of discrete maths.

For two disjoint sets, the cardinality of the union is the sum of the cardinalities.

$A,B,|A|=n,|B|=m,A\cap B=\varnothing ⟹|A\cup B|=n+m$

The product of the cardinalities of two sets is the cardinality of the cartesian product.

$|A|=n,|B|=m⟹|A\times B|=n\cdot m$

If there is a bijection between two sets, they have the same cardinality.

$A,B,\exists f:A\to B$ bijective $⟹|A|=|B|$

Proof of the product of cardinalities:

$A=\{a_1,\dots a_n\}$, gesucht: $|2^A|$
$f:2^A\mapsto \{0,1{\}}^n=\{0,1\}\times \{0,1\}\times ,\dots ,\times \{0,1\}$ (→ n-tuple)
$$\begin{gathered} B\mapsto (b_1,b_2,\dots ,b_n),b_j\text{cases}0,\text{ if }{a}_j\notin B \\ 1,\text{ else} \end{gathered}$$
If $f$ is injective: $B\subseteq 2^A,B^{\prime }\subseteq 2^A,B\ne B^{\prime }⟹\text{WLOG }\exists j:a_j\in B,a_j\notin B^{\prime }$ (if the resulting images are different, the underlying inputs are different)
$⟹b_j=1,b_j^{\prime }=0⟹f(B)\ne f(B^{\prime })$ (since different inputs lead to different outputs, it’s injective $✓$)
If $f$ is surjective, we need to show: $\forall (b_1,\dots ,b_n)\in \{0,1{\}}^n\exists B\subseteq A:f(B)=(b_1,\dots ,b_n)$
$B=\{a_j\mid b_j=1\}⟹f(B)=(b_1,\dots ,b_n)⟹f\text{ bijective }✓$
$|2^A|=|\{0,1{\}}^n|=2^n$

Sampling $k$ elements from $n$ choices

When order matters:

With replacement: $\#=n^k$
Without replacement: $\#=\frac{n!}{(n-k)!}=n(n-1)\dots (n-k+1)$ (pool gets smaller with each sample)

When order doesn’t matter:
$\#=\frac{n!}{(n-k)!k!}=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ (binomial coefficient = “selection from a partial multiset”)

The above but with more words:

With replacement vs. without replacement

$A=\{a_1,\dots ,a_n\}$
(i) Arrangement without constraints “with replacement”: How many ways are there to arrange $k$ elements of $A$?
$\underset{\in A^k}{\underbrace{(x_1,x_2,\dots ,x_k)}},x_i\in A$, Note: $(1,2,3)\ne (2,1,3)$, order matters, as we’re dealing with ordered tuples.
→ $|A^k|=|A{|}^k=n^k$
(ii) Arrangement with unique elements “without replacement”: How many ways are there to arrange $k$ elements of $A$ without repetition?
$(\underset{n}{\underbrace{x_1}},\underset{n-1}{\underbrace{x_2}},\dots ,\underset{n-k+1}{\underbrace{x_k}}),x_i\in A,\forall i\ne j:x_i\ne x_j$
In underbraces $\uparrow$ are the number of possibilities for choosing $x_1,x_2,\dots ,x_k$ → $n(n-1)\dots (n-k+1)=k!\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

(further explanation) $n\cdot (n-1)\cdot (n-2)\dots (n-k+1)$ … starts from $n$ choices, always one less until we reach $k$ terms. We want to know the permutations of $k$ elements, so the product should stop after $k$ terms, hence the $+1$. e.g. for $n=5,k=3$, with … $5\cdot 4\cdot 3$ … without … $5\cdot 4\cdot 3\cdot 2$. Note also, that dividing $n!$ by $(n-k)!$ is is like crossing out the last $n-k$ terms, keeping exactly $k$. So that’s why we can rewrite this with factorials, which looks very similar to the binomial coefficient: $\frac{n!}{(n-k)!}$, just that it doesn’t divide by $k!$ to allow for repetitions.

permutations: How many ways are there to arrange all elements of $A$?

$\pi :A\to A$, bijective permutation function
$f:x_1,x_2,\dots x_n\mapsto (x_1,\dots ,x_n),x_i=\pi (a_i)$
$f:S_A\to \{x\in A^n:\forall i\ne j:x_{i\ne x_j}\}$
$|S_A|=\#(x_1,\dots ,x_n):\forall i\ne j:x_i\ne x_j$ (exactly what we had in (ii) above)
$=n!\left(\genfrac{}{}{0ex}{}{n}{n}\right)=n!$
→ $|A!|=n!$

Permutation notation

$M=\{1,2,3\}$

We can denote the permutation in three ways:
(1) Two rows – the first row is the original order, the second row is the new order:
$\left(\begin{array}{ccc}1& 2& 3\\ \pi (1)& \pi (2)& \pi (3)\end{array}\right)$, e.g.: $\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)⟺1\to 2,2\to 1,3\to 3$
(2) or we just take the second row: $213$,
(3) or we take the cycle notation: $(12)(3)$, i.e. $(1\to 2\to 1)(3\to 3)$.
Each group is its own cycle – no duplicates / loops (else it wouldn’t be bijective which is a requirement for a permutation).

Link to original

^b4a0f0

Transclude of inclusion-exclusion-principle