數學英文

排列

$n$ 個相異物 ($n$ different objects) 有 $n!$ 種排列方式， 讀作 n 階乘 (n factorial)：

There are $n!$ permutations of $n$ different objects.

從 $n$ 個相異物中任取 $r$ 個，有 $P_r^n$ 種排列方式， 這時候當然 $r$ 不超過 $n$ ($r$ is at most $n$)， 記作 $r\le n$ 或 $r\ngtr n$。 排列數 $P_r^n$ 也常寫成 $P(n,r)$ 或 $P_{n,r}$ 或 ${}_n{P}_r$。

所謂 n 中取 k 的重複排列 (permutation with repetitions) 意思是從 $n$ 個相異物中，可重複地 (repetition is allowed) 選 $k$ 個出來， 排成 $k$ 項的序列 $$⟨a_1,a_2,\cdots ,a_k⟩$$ 因為每一項 $a_i$ 都有 $n$ 種可能的選擇，共有 $k$ 次彼此獨立的選擇， 運用乘法原理得知：一共有 ${\displaystyle n^k}$ 種不同的序列。 這時候 $n$ 和 $k$ 沒有大小關係的限制； 因為可以重複選取，所以 $k$ 可能大於 $n$。 典型的例子是：計算機的 1 byte 由 8 bits 組成：$b_0{b}_1{b}_2{b}_3{b}_4{b}_5{b}_6{b}_7$， 每個 bit $b_i$ 不是 0 就是 1；也就是每個 $b_i$ 都是從集合 $\{0,1\}$ 中選出的元素， 這是 2 中選 8 的重複排列，一共有 $2^8=256$ 種排列，也就是有 256 種 bytes。

所謂不盡相異物排列 (permutation of multi-sets) 是指 $n$ 個物件可以分為 $r$ 類，類與類之間不同，同類之中是不可分辨的全等物件。 如果各類有 $p_1,p_2,\cdots ,p_r$ 個相同物， 則這 $n$ 個物件有 $$\frac{n!}{p_1!p_2!\cdots p_r!}$$ 種排列方式。例如「舊時王謝堂前燕」這七個字有 $7!=5040$ 種排列， 但「尋尋覓覓聲聲慢」這七個字只有 $$\frac{7!}{2!2!2!}=\frac{5040}{8}=630$$ 種排列。

所謂 multiset 是容許重複元素的集合──a set with repeated elements。 例如在「正常」的集合定義之下， $$\{\text{尋},\text{尋},\text{覓},\text{覓},\text{聲},\text{聲},\text{慢}\}$$ 只有 4 個元素，它等於 $\{\text{尋},\text{覓},\text{聲},\text{慢}\}$。 但是在 multiset 的定義之下，它就有 7 個元素。 高中數學沒有正式介紹 multiset，但是在排列組合之中夾帶了它。 某些電腦程式語言 (programming language) 支援 multiset， 這是程式設計的一種資料結構 (data structure)。