{%hackmd @RintarouTW/About %}

# Combinatorics

## 2.1 Basic Counting Techniques

### 2.1.1 Tree

### 2.1.2 The Role of Products

$$
C=\{(a,b)|a\in A, b\in B\}\\
|C|=|A|\times|B|
$$

The choice of b are independent from choice of a, or the rule of products did not apply.

Example of dependent choices:
$$
|A| = n \implies |\mathcal{P}(A)| = \sum_\limits{i=0}^n \pmatrix{n\\i} = 2^n = 2^{|A|}
$$

:::info$
Power Set Cardinality Theorem
A is a set.
$$|\mathcal{P}(A)|=2^{|A|}$$
除了 $\sum_\limits{i=0}^n\pmatrix{n\\i}$ 的思路外，還有另一種更簡易的思路， $\mathcal{P}(A)$ 中的每個 element(set) 皆是由 A 中的 n 個元素中取得組合而成，也就代表 A 中的每個元素可取可不取兩種選擇，比如 $\emptyset \in \mathcal{P}(A)$ 就是 n 個元素皆不取所組成的，則 n 個元素就有 $2^n$ 種不同的選擇方式，組成 $2^n$ 種不同的集合。
:::

## 2.2 Permutaions

### 2.2.1 Ordering Things

$$A = \{a,b,c\}$$

digraph{
graph [bgcolor=transparent];              node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
rankdir=LR
A->a,b,c
a->ab->abc
a->ac->acb
b->ba->bac
b->bc->bcb
c->ca->cab
c->cb->cba
}

$$ 3\times 2\times 1 = 3! $$

The six orderings is called a permutaion of a set.

k slots and n choices, a choice can only be choosed once, then

$$
P(n, k) = \dfrac{n!}{(n-k)!}
$$

### 2.3 Partitions of Sets and the Law of Additionn

#### 2.3.1 Partitions

Partition: A partition of set A is a set of one or more nonempty subsets of A: $A_1, A_2,\cdots$, such that every element in A is exactly in one set.

- $A_1\cup A_2\cup\cdots=A$
- $i\neq j\implies A_i\cap A_j = \emptyset$

#### 2.3.2 Addition Law

:::info
The Basic Law of Addition Theorem
A is a finite set. ${A_1, A_2,\ldots,A_n}$ is a partition of A.
$$
|A| = |A_1| + |A_2| +\cdots+ |A_n| = \sum_\limits{i=1}^n |A_i|
$$
:::

#### 2.3.9 Law of Inclusion-Exclusion

:::info
a) Two Set Inclusion-Exclusion Law:
Given finite set $A$, $\cases{A_1, A_2 \subset A\\
A = A_1\cup A_2}$
$$
|A| = |A_1| + |A_2| - |A_1\cap A_2|
$$
a) Three Set Inclusion-Exclusion Law:
Given finite set $A$, $\cases{A_1, A_2, A_3 \subset A\\
A = A_1\cup A_2\cup A_3}$
$$
|A| = |A_1| + |A_2| + |A_3| - (|A_1\cap A_2| + |A_1\cap A_3| + |A_2\cap A_3|) + |A_1\cap A_2\cap A_3|
$$
:::

### 2.4 Combinations and Binomial Theorem

Unlike Cartesian product(permutation) which order matters, there are cases that order doesn't matter and multiple cases can be seen as the same case, so they can be "combined" as one case.

:::info
Binomial Theorem came from the coefficients of $(x+y)^n$
$$
C_n^k=\pmatrix{n\\k} = \dfrac{P(n,k)}{k!}=\dfrac{n!}{(n-k)!k!}
$$
read as "n choose k", where k! are the number of different combinations that could be seen(generated by the choosed k positions/elements) as one case.

$$
(x+y)^n = \sum_\limits{k=0}^n \pmatrix{n\\k}x^{n-k}y^{k}
$$
可參考[二項式定理 (Binomial Theorem) 研究](/@RintarouTW/二項式定理_Binomial_Theorem_研究)
:::

###### tags: `math` `discrete` `combinatorics` `binomial`