第 14 章　排列組合與機率¶

（適用：台灣高中～大一；目標：用 SageMath 做「計數驗算、列舉、生成函數初步、機率計算與模擬」）

14.1 本章主旨：把「計數」變成可驗算的流程¶

排列組合與機率的常見困難：

  • 題目敘述一長串，容易漏條件或重複計數
  • 公式背得住，但不知道何時用
  • 機率算完不確定合理不合理

SageMath 可以做三種支援：

  1. 符號計數：排列、組合、二項式係數
  2. 列舉驗算：小規模暴力列出所有情況，檢查你是否漏算/重算
  3. 模擬（Monte Carlo）：用大量隨機試驗估計機率，檢查答案是否合理

建議工作流：先手算 → 用列舉/模擬驗算 → 再回頭修正推理。

14.2 基本計數工具：階乘、排列、組合¶

Sage 常用：

  • factorial(n) 或 n.factorial()
  • binomial(n,k)（組合數）
  • 排列數 $$ P(n,k)=\frac{n!}{(n-k)!} $$ 可以自己寫函數

先做幾個例子。

In [1]:
# 階乘與組合
factorial(6), binomial(10, 3)
Out[1]:
In [ ]:
def P(n, k):
    return factorial(n)/factorial(n-k)

P(10, 3)

二項式定理與係數¶

$$ (a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k}b^k $$

例：展開 $(x+1)^8$ 並查看係數。

In [3]:
var('x')
expr = expand((x+1)^8)
expr
Out[3]:
In [4]:
# 取出 x^k 的係數（例如 k=3）
expr.coefficient(x, 3), binomial(8, 3)
Out[4]:

14.3 排列：順序有沒有差？¶

(A) 線性排列（不重複）¶

n 個不同物件全排列：n!

(B) 選 k 個排成一列：P(n,k)¶

(C) 有重複的排列（多重集合）¶

例如字母 A A B B C 的排列數： $$ \frac{5!}{2!2!} $$

用 Sage 算算。

In [5]:
# AABBC 的排列數
factorial(5)/(factorial(2)*factorial(2))
Out[5]:

列舉驗算（小規模暴力）¶

用 Python 的 itertools 列出所有排列（注意：數量大會爆！只適合小問題）。

In [6]:
import itertools

letters = ['A','A','B','B','C']
perms = set(itertools.permutations(letters))
len(perms), list(perms)[:5]
Out[6]:

14.4 組合：只在乎選到誰，不在乎順序¶

$$ \binom{n}{k}=\frac{n!}{k!(n-k)!} $$

例：從 12 人選 5 人。

In [7]:
binomial(12, 5)
Out[7]:

重複組合（可重複選）初步：stars and bars¶

從 n 種物品中選 k 個，可重複、順序不計： $$ \binom{n+k-1}{k} $$

例：3 種口味冰淇淋選 7 球（可重複）。

In [8]:
binomial(3+7-1, 7)
Out[8]:

14.5 常見計數策略：補集、分情況、容斥（簡介）¶

(A) 補集法¶

直接數很難，就數「不符合」再用總數減掉。

例：長度 5 的二進位字串（0/1），至少有一個 1 的個數？

  • 總數：2^5
  • 全是 0：1
  • 所以答案：2^5-1

用 Sage：

In [9]:
2^5 - 1
Out[9]:

(B) 分情況¶

例：把 10 分成兩個正整數相加的方式數量？ (1,9),(2,8),...,(9,1) 共 9 種（若有序）。

用程式列舉驗算：

In [10]:
pairs = [(a, 10-a) for a in range(1, 10)]
pairs, len(pairs)
Out[10]:

14.6 機率的計算：古典機率 + 條件機率¶

古典機率（等可能）： $$ P(A)=\frac{|A|}{|\Omega|} $$

條件機率： $$ P(A|B)=\frac{P(A\cap B)}{P(B)} $$

Sage（或 Python）做的事：幫你算 |A|、|\Omega|，或列舉/模擬。

14.7 骰子與撲克牌：用列舉做機率（小規模）¶

例 1：兩顆公平骰子，和為 7 的機率¶

樣本空間 36 種。

In [11]:
outcomes = [(i,j) for i in range(1,7) for j in range(1,7)]
A = [(i,j) for (i,j) in outcomes if i+j == 7]
len(outcomes), len(A), len(A)/len(outcomes), A
Out[11]:

例 2：至少一顆是 6 的機率（用補集更快）¶

In [12]:
# 補集：沒有任何 6
no6 = [(i,j) for (i,j) in outcomes if i != 6 and j != 6]
1 - len(no6)/len(outcomes)
Out[12]:

14.8 超幾何分佈：不放回抽樣（高中到大一都常出）¶

例：盒子有 5 個紅球、7 個藍球，不放回抽 3 顆，剛好抽到 2 紅 1 藍的機率？

$$ P=\frac{\binom{5}{2}\binom{7}{1}}{\binom{12}{3}} $$

In [13]:
P_exact = binomial(5,2)*binomial(7,1)/binomial(12,3)
P_exact, N(P_exact)
Out[13]:

用模擬驗算（Monte Carlo）¶

大量隨機抽樣，估計機率（應該接近上面結果）。

In [14]:
import random

def trial():
    balls = ['R']*5 + ['B']*7
    sample = random.sample(balls, 3)  # 不放回抽 3
    return sample.count('R') == 2 and sample.count('B') == 1

N = 20000
est = sum(trial() for _ in range(N))/N
est
Out[14]:

14.9 二項分佈：放回/獨立重複試驗¶

例：投擲公平硬幣 10 次，正面恰好 3 次的機率： $$ \binom{10}{3}\left(\frac12 \right)^{10} $$

In [15]:
reset() # 清除之前的變數
P = binomial(10,3)*(1/2)^10
P, N(P)
Out[15]:

用模擬驗算¶

In [16]:
import random
def coin_trial(n=10):
    heads = sum(1 for _ in range(n) if random.random() < 0.5)
    return heads == 3

N = 30000
est = sum(coin_trial() for _ in range(N))/N
est
Out[16]:

14.10 期望值（期望）初步：把隨機變數看成加權平均¶

離散隨機變數 X： $$ E[X]=\sum x\cdot P(X=x) $$

例：公平骰子的期望值。

In [17]:
# 骰子期望
E = sum(k*(1/6) for k in range(1,7))
E
Out[17]:

也可以用模擬估計期望：

In [18]:
import random
N = 50000
est = sum(random.randint(1,6) for _ in range(N))/N
est
Out[18]:

14.11 本章小結：計數與機率的可靠工作流¶

你現在應該能：

  • 用 factorial、binomial 做基本排列組合計算
  • 用列舉（itertools）驗算小規模計數題
  • 用補集、分情況等策略組織推理
  • 用組合數寫出古典機率（骰子/抽球/硬幣）
  • 用 Monte Carlo 模擬檢查你的機率答案是否合理
  • 初步理解期望值是「加權平均」並能用模擬驗算

練習題（附提示）¶

  1. 計數：字母 A A A B B C 的不同排列有多少？
    提示：$\frac{6!}{3!2!}$，也可用 set(permutations) 小規模驗算。

  2. 補集：長度 8 的二進位字串中，至少有一個 0 的個數？
    提示：總數 2^8 減掉全 1。

  3. 抽球（超幾何）：箱中 4 白 6 黑，不放回抽 5 顆，抽到恰好 3 白的機率。
    提示：$\binom{4}{3}\binom{6}{2}/\binom{10}{5}$。

  4. 二項：某題命中率 0.3，做 8 次，恰好命中 2 次的機率。
    提示：$\binom{8}{2}0.3^2 0.7^6$。

5.（挑戰）條件機率：兩顆骰子，已知至少一顆是 6，求和為 7 的機率。
提示：用列舉：B=「至少一顆 6」，A=「和為 7」，算 |A∩B|/|B|。

下一章（第 15 章）我們會進入「資料分析：平均數、變異數與標準差」：
會把「期望」的概念延伸到資料，並用 Sage/Python 做統計量計算與視覺化。