这是台湾清华赵启超教授离散数学10A10B课程的笔记。

• Enumeration 10A
  *
  • Multinomail Theorem
  • Unordered Selections with Repetition
• Enumeration 10A
  *
  • Principle of Inclusion and Exclusion

Enumeration 10A

Multinomail Theorem

Example 1
How many wats can we permute the word "MISSISSIPPI"?
There are 4 I's, 4 S's, 2 P's, 1M.
number of ways$=\frac{11!}{4!4!2!1!}$

The number of distinguishable arrangements of $n$ objects, in which there are $n$ objects of type1, $n_2$ objects of types 2,...,$n_k$ objects of type $k$.
where $n_1+n_2\dotsc n_k=n$

$\begin{pmatrix}n \\ n_1,n_2,\dotsc ,n_k\end{pmatrix}=\frac{n!}{n_1!n_2!\dotsc n_k!}$

Theorem: $(x_1+x_2+\dotsc + x_k)^n=\sum_{n_1+n_2+\dotsc +n_k=n} \begin{pmatrix}n \\ n_1,n_2,\dotsc ,n_k\end{pmatrix}x_1^{n_1}x_2^{n_2}\dotsc x_k^{n_k}$

Unordered Selections with Repetition

The number of unordered selections, repetition allowed,
of $m$ things from a set of size $n$ is $\begin{pmatrix}n+m-1 \\ m\end{pmatrix}$

Enumeration 10A

Principle of Inclusion and Exclusion

Two sets' Principle of Inclusion and Exclusion $|A\cup B|=|A|+|B|-|A\cap B|$
Three sets' Principle of Inclusion and Exclusion $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|A\cap C|+|A\cap B\cap C|$
$|A\cup B\cup C|=\alpha _1-\alpha _2, \alpha _3$
where $\alpha _1=|A|+|B|+|C|,\alpha _2=|A\cap B|-|B\cap C|-|A\cap C|, \alpha _3=|A\cap B\cap C|$

Theorem: If $A_1,A_2,\dotsc ,A_n$ are finite sets,
then

$|A_1\cup A_2\cup \dotsc \cup A_n|=\alpha _1-\alpha _2 +\alpha _3 - \dotsc +(-1)^{n-1}\alpha _n$

where $\alpha _i$ is the sum of the cardinaltities of the intersections of the sets taken $i$ at a time, $1\le i \le n$