3-2. 排列

Permutation Formula

• $n$ 件相異物不允許重複取 $r$ 件排列的方法數: $\text{P}^n_r$ = $\text{P}$($n$, $r$) = $n$($n$ - $1$)...($n$ - $r$ + $1$) = $\dfrac{n!}{(n - r)!}$, $n \ge r$
  • 全相異物排列 $\rightarrow$ 取 $n$ 件放在 $n$ 個不同位置作排列: $\text{P}^n_n$ = $\dfrac{n!}{(n - n)!}$ = $n!$
  • 不全相異物排列 $\rightarrow$ 取 $n$ 件分為 $k$ 種的不全相異物，放在 $n$ 個不同位置作排列: $\dfrac{n!}{(n_1)!(n_1)!...(n_k)!}$

    分組貼標籤: $\dfrac{\footnotesize\text{全相異物排列}}{k \footnotesize\text{ 種的組內相異物排列}}$

  • 環狀排列 $\rightarrow$ 取 $n$ 件放在 $n$ 個位置，圍成環形作排列: $\dfrac{n!}{n}$ = $(n - 1)!$

    $n$ 件轉一圈算一次:
    $^{ex.} n$ = $4$, $\begin{pmatrix} 1 & 2 \\ 4 & 3 \end{pmatrix}$ = $\begin{pmatrix} 4 & 1 \\ 3 & 2 \end{pmatrix}$ = $\begin{pmatrix} 3 & 4 \\ 2 & 1 \end{pmatrix}$ = $\begin{pmatrix} 2 & 3 \\ 1 & 4 \end{pmatrix}$

• $n$ 件相異物允許重複取 $r$ 件排列的方法數: $n^r$

$Example$: $A$, $B$: sets, $|A|$ = $m$, $|B|$ = $n$

1. $A \rightarrow B$ 之 function 個數?
2. $A \rightarrow B$ 之 1-1 function 個數?
3. $A \rightarrow B$ 之 onto function 個數?

$solution$:

1. 等同於: $m$ 個相異球放入 $n$ 個相異箱子，允許空箱之方法數 $\Rightarrow n^m$
2. 等同於: $m$ 個相異球放入 $n$ 個相異箱子，不允許空箱且每個箱子最多一個球之方法數 $\Rightarrow \text{P}^n_m$
3. 等同於: $m$ 個相異球放入 $n$ 個相異箱子，不允許空箱之方法數，詳見「3-4. 排容原理」之Theorem of Onto Function Amount