重複排列

用過的還可以再用

高一 · D-10-3

n×n×⋯×n⏟k 次=nk\underbrace{\co{n}\times \co{n}\times\cdots\times \co{n}}_{\cb{k}\ \text{次}}=\co{n}^{\cb{k}}

先觀察

一個四位數字的密碼鎖,每一格都可以轉到 0 到 9 的任一個數字,而且數字可以重複——0000、7777、1213 都是合法的密碼。

這把鎖一共有幾組密碼?如果改成「四格的數字都不能重複」,答案又會差多少?

一步一步推導

  1. 一顆一顆處理。第 1 顆球站在那裡,面前有 nn 個箱子,所以有 nn 種選擇。n 種\co{n}\ \text{種}
  2. 第 2 顆球登場。重點來了:第 1 顆球放過的箱子還能再放,所以第 2 顆球面前一樣是 nn 個箱子,還是 nn 種選擇。n×n\co{n}\times\co{n}
  3. 每一顆球都是獨立的一次選擇,用乘法原理接起來。kk 顆球就乘 kk 個 nn。nk\co{n}^{\cb{k}}
  4. 為什麼是 nkn^k 不是 knk^n?看這棵樹:每一層是一顆球(所以有 kk 層),每個節點分出 nn 條岔路。層數當指數,岔路數當底數。一句話:做選擇的當指數。層數=k (球),岔路=n (箱)\text{層數}=\cb{k}\ \text{(球)},\quad \text{岔路}=\co{n}\ \text{(箱)}
  5. 對照組:如果規定每個箱子最多一顆球,那放過的箱子就不能再用。選擇數會一個一個遞減,變成排列 PknP^n_k。Pkn=n(n−1)⋯(n−k+1)P^n_k=\co{n}(\co{n}-1)\cdots(\co{n}-\cb{k}+1)
  6. 兩者的差別只有一句話:「用過的還能不能再用」。能 → nkn^k;不能 → PknP^n_k。開頭的密碼鎖是前者:104=1000010^4=10000 組;若四格不可重複則是 P410=5040P^{10}_4=5040 組。nk vs Pkn\co{n}^{\cb{k}}\ \text{vs}\ P^{\co{n}}_{\cb{k}}

課綱與應用

10 年級共同必修,學測數 A、數 B 都在範圍內。單獨命題不多,但它是機率題分母的常客(例如「擲 kk 次骰子的所有結果有 6k6^k 種」),也常和排列組合放在同一題裡比較。最常見的失分就是把 nkn^k 寫成 knk^n。

練這間小屋的 5 題

相關單元