數學英文

排列

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

There are \(n!\) permutations of \(n\) different objects.

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

所謂 n 中取 k 的重複排列 (permutation with repetitions) 意思是從 \(n\) 個相異物中，可重複地 (repetition is allowed) 選 \(k\) 個出來， 排成 \(k\) 項的序列 \[\langle a_1, a_2, \cdots, a_k\rangle\] 因為每一項 \(a_i\) 都有 \(n\) 種可能的選擇，共有 \(k\) 次彼此獨立的選擇， 運用乘法原理得知：一共有 \(\displaystyle n^k\) 種不同的序列。 這時候 \(n\) 和 \(k\) 沒有大小關係的限制； 因為可以重複選取，所以 \(k\) 可能大於 \(n\)。 典型的例子是：計算機的 1 byte 由 8 bits 組成：\(b_0b_1b_2b_3b_4b_5b_6b_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\) 個物件有 \[{n!\over p_1!\;p_2!\;\cdots\;p_r!}\] 種排列方式。例如「舊時王謝堂前燕」這七個字有 \(7!=5040\) 種排列， 但「尋尋覓覓聲聲慢」這七個字只有 \[{7!\over 2!\;2!\;2!}={5040\over8}=630\] 種排列。

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