考研相關文章參考資料為 wjungle 大神提供的筆記

L3 排列組合與排容原理

L3-2~3 排列 & 組合

定義

$n$ 件相異物不允許重複取 $r$ 件排列: $P_{r}^{n}$
$n$ 件相異物允許重複取 $r$ 件排列: $n^r$
$n$ 件相異物不允許重複取 $r$ 件組合: $\binom{n}{r}$
$n$ 件相異物允許重複取 $r$ 件組合: $\binom{n+r-1}{r}$ ，且等價於
- $r$ 個相同球放至 $n$ 個相異箱子，允許空箱之方法數
- $x_1 + x_2 + \cdots + x_n = r$ 之非負整數解個數
$x_1 + x_2 + \cdots + x_n = r$ 之正整數解個數: $\binom{r-1}{n-1}$

Note

$|A|=m, |B|=n$

$A$ 至 $B$ 之 function 個數: $n^m$
$A$ 至 $B$ 之 1-1 function 個數: $P_{m}^{n}$

L3-4 排容原理

定理

Principle of Inclusion and Exclusion (排容原理):

$\begin{aligned} N(\bar a_1\bar a_2\cdots\bar a_n) &=|U|-\sum_{i=1}^{n}N(a_i)+\sum_{1\leq i<j\leq n}N(a_i a_j)-\sum_{1\leq i<j<k\leq n}N(a_i a_j a_k)+\cdots+(-1)^nN(a_1a_2\cdots a_n)\\ &=S_0-S_1+S_2-\cdots+(-1)^nS_n \end{aligned}$

其中 $S_r$ 為所有 $r$ 個性質同時成立之數量總和， $S_0=|U|$ 。

定義

若 $|A|=m, |B|=n, m\geq n$ ，則 $A$ 至 $B$ 的 onto function 個數為:

\operatorname{onto}(m,n)=\sum_{i=0}^{n}(-1)^i\binom{n}{i}(n-i)^m

$m$ 個相異物放至 $n$ 個相異箱子，不允許空箱之方法數

證明

令 $U$ 為所有 $A\to B$ 的 function，故 $|U|=n^m$ ；令 $a_i$ 表示 $B$ 中第 $i$ 個元素沒有原像。

onto function 須讓所有 $a_i$ 都不成立，因此套用排容原理。任選 $i$ 個元素沒有原像時，每個 $A$ 中元素只剩 $n-i$ 個像可選，共有 $(n-i)^m$ 種；選這 $i$ 個元素有 $\binom ni$ 種。

故 $\operatorname{onto}(m,n)=\displaystyle\sum_{i=0}^{n}(-1)^i\binom ni(n-i)^m$ 。

定義

$m$ 個相異物分成 $n$ 個相同箱子，不允許空箱之方法數，稱為 Stirling number of the second kind: $S(m,n)=\frac{\operatorname{onto}(m,n)}{n!}$

Note

$m$ 個相異物分成 $n$ 個相同箱子，允許空箱之方法數: $S(m,n)+S(m,n-1)+\cdots+S(m,1)$

定理

$S(m+1,n)=S(m,n-1)+nS(m,n)$

證明

固定其中一物 $A$ ，分成兩種情況:

$A$ 單獨一箱: 其餘 $m$ 個相異物分成 $n-1$ 箱，共 $S(m,n-1)$ 種
$A$ 不單獨一箱: 先將其餘 $m$ 個相異物分成 $n$ 箱，再選一箱放入 $A$ ，共 $nS(m,n)$ 種

L3-5 亂序及禁位問題

定理

derangement (亂序): $\{1,2,\ldots,n\}$ 的排列中，每個元素皆不在原本位置之排列數為:

$D_n=n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}$

證明

令 $U$ 為所有排列，故 $|U|=n!$ ；令 $a_i$ 表示元素 $i$ 位於自然位置。

指定 $i$ 個元素位於自然位置時，其餘元素可任意排列，有 $(n-i)!$ 種，選定這 $i$ 個元素有 $\binom ni$ 種。由排容原理:

$D_n=\sum_{i=0}^{n}(-1)^i\binom ni(n-i)!=n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}$

又 $e^{-1}=\displaystyle\sum_{i=0}^{\infty}\frac{(-1)^i}{i!}$ ，因此當 $n\to\infty$ 時， $D_n\sim n!e^{-1}$ 。