跳轉到

07.2 組合數學#

本節目標#

  • 理解階乘 \(n!\) 與二項式係數 \(\binom{n}{k}\) 的意義。
  • 用 SymPy 的 factorial()、binomial() 做排組計數，並驗證二項式定理。
  • 驗證 \(\sum_{k=0}^{n} \binom{n}{k} = 2^n\) ，印出巴斯卡三角形。
  • 實驗：計算各種賭局的勝率。

一、階乘與排列#

\(n! = 1 \times 2 \times \cdots \times n\) ，代表 \(n\) 個相異物全部排成一列的方法數（排列數 \(P_n = n!\) ）。從 \(n\) 個中取出 \(k\) 個排列則是

\[ P(n, k) = \frac{n!}{(n-k)!} \]
from sympy import factorial, binomial, symbols, simplify, expand, Rational

n, k = symbols('n k', integer=True, nonnegative=True)

print(factorial(5))          # 120
print(factorial(0))          # 1（定義 0! = 1）
print(factorial(n)/factorial(n - 3))   # P(n,3) 的符號式

二、組合數 binomial#

\(\binom{n}{k} = \frac{n!}{k!(n-k)!}\) 代表從 \(n\) 個中「不計順序」取 \(k\) 個的方法數：

print(binomial(5, 2))        # 10
print(binomial(n, k))        # 符號形式，保留 n、k

# 驗證公式
print(simplify(binomial(n, k) - factorial(n)/(factorial(k)*factorial(n - k))))   # 0

對稱性質： \(\binom{n}{k} = \binom{n}{n-k}\) ：

print(simplify(binomial(n, k) - binomial(n, n - k)))   # 0

三、二項式定理驗證#

二項式定理：

\[ (x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k \]

用 expand 展開左式，再與右式逐項對照：

from sympy import summation
x, y = symbols('x y')

for N in [3, 5, 7]:
    lhs = expand((x + y)**N)
    rhs = summation(binomial(N, kk) * x**(N - kk) * y**kk, (kk, 0, N))
    print(N, simplify(lhs - rhs) == 0)
# 全部印出 True

也觀察展開結果與係數的關係—— \(x^{n-k} y^k\) 項的係數正是 \(\binom{n}{k}\) ：

print(expand((x + y)**4))
# x**4 + 4*x**3*y + 6*x**2*y**2 + 4*x*y**3 + y**4
# 係數 1, 4, 6, 4, 1 就是 binomial(4, k)
print([binomial(4, kk) for kk in range(5)])   # [1, 4, 6, 4, 1]

四、排組計數應用#

應用 1：passcode 密碼數。4 位數密碼，每位可為 0–9（可重複），共 \(10^4\) 種；若不可重複則是排列數：

# 可重複：每位 10 種選擇
print(10**4)                                  # 10000

# 不可重複：P(10, 4)
print(factorial(10)/factorial(6))             # 5040

應用 2：撲克牌組合數。52 張牌發 5 張，不計順序：

total = binomial(52, 5)
print(total)                    # 2598960

應用 3：同花順的數目。4 種花色 × 10 種起點（A–10 連續五張）：

straight_flush = 4 * 10
print(Rational(straight_flush, total).evalf())   # 約 0.0000154，極稀有

應用 4：委員會問題。10 人中選 4 人，其中指定 2 人必須同時選入或都不選：

# 2 人都選入：剩下從 8 人選 2；2 人都不選：從 8 人選 4
ways = binomial(8, 2) + binomial(8, 4)
print(ways)                     # 28 + 70 = 98

五、驗證 sum C(n,k) = 2^n#

組合意義：從 \(n\) 個物品中「任意選取」的總方法數（選 0 個、1 個、…、全部），就等於每個物品「選或不選」的 \(2^n\) 種組合：

\[ \sum_{k=0}^{n} \binom{n}{k} = 2^n \]
from sympy import Eq, simplify

for N in [1, 5, 10, 20]:
    s = summation(binomial(N, kk), (kk, 0, N))
    print(N, s == 2**N)

# 符號層次的驗證（取幾個 n 檢查）
print(simplify(summation(binomial(7, kk), (kk, 0, 7)) - 2**7))   # 0

六、巴斯卡三角形#

巴斯卡三角形的第 \(n\) 列就是 \(\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}\) ，且滿足

\[ \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k} \]
def pascal_triangle(rows):
    for r in range(rows):
        row = [binomial(r, kk) for kk in range(r + 1)]
        print(' '.join(str(v) for v in row).center(rows * 4))

pascal_triangle(8)
#          1
#         1 1
#        1 2 1
#       1 3 3 1
#      1 4 6 4 1
#     1 5 10 10 5 1
#  1 6 15 20 15 6 1
# 1 7 21 35 35 21 7 1

驗證巴斯卡恆等式：

print(simplify(binomial(n + 1, k) - binomial(n, k - 1) - binomial(n, k)))   # 0

每一列總和恰好是 \(2^n\) ，與上一節的恆等式互相呼應：

for r in range(8):
    print(r, sum(binomial(r, kk) for kk in range(r + 1)))

七、動手實驗：算各種賭局勝率#

實驗 1：樂透 45 取 6，頭獎機率：

lotto = binomial(45, 6)
print(Rational(1, lotto))                    # 1/8145060
print(Rational(1, lotto).evalf())            # 約 1.23e-7

實驗 2：骰子——擲兩顆，點數和為 7 的機率。樣本空間 \(6^2 = 36\) ，和為 7 有 6 種：

from sympy import Rational
print(Rational(6, 36))          # 1/6

實驗 3：擲 10 次硬幣，恰好 6 次正面的機率（二項分布）：

p = binomial(10, 6) * Rational(1, 2)**10
print(p)                        # 105/512
print(p.evalf())                # 0.2051
# 至少 6 次正面的機率
p_at_least_6 = sum(binomial(10, kk) for kk in range(6, 11)) * Rational(1, 2)**10
print(p_at_least_6, float(p_at_least_6))    # 385/512 ≈ 0.7539

實驗 4：德州撲克拿到一對的機率（5 張中恰有一對）：

# 選點數 13 種 × 從 4 張選 2 × 其餘 3 張點數互異且不同於對子
one_pair = 13 * binomial(4, 2) * binomial(12, 3) * 4**3
print(one_pair)                                   # 1098240
print(Rational(one_pair, binomial(52, 5)).evalf())  # 約 0.4226

實驗 5：蒙特卡羅驗證——隨機發 5 張牌模擬一對的頻率：

import random
random.seed(42)
deck = list(range(52))
hits = 0
trials = 100000
for _ in range(trials):
    hand = random.sample(deck, 5)
    ranks = [h % 13 for h in hand]
    if sorted(ranks) and max(ranks.count(r) for r in set(ranks)) == 2 \
       and sorted(ranks.count(r) for r in set(ranks)) == [1, 1, 1, 2]:
        hits += 1
print(hits / trials)   # 應接近 0.4226

觀察重點： 1. 精確的分數（Rational）比浮點數更能表達機率的真值。 2. 組合數是所有「從有限集合選取」機率問題的基石。 3. 模擬結果會在精確值附近浮動， trials 越多越接近。

小結與練習#

本節我們學會了： - factorial(n) 與 binomial(n, k) 的用法與組合意義。 - 用 expand 驗證二項式定理 \((x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k\) 。 - \(\sum_{k=0}^{n} \binom{n}{k} = 2^n\) 及巴斯卡恆等式 \(\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}\) 。 - 用組合數計算密碼數、撲克牌型與各種賭局勝率。

練習： 1. 驗證 \(\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0\) （對 \(n \geq 1\) ），並用 \((1-1)^n\) 展開解釋。 2. 5 位英文字母密碼（不分大小寫、字母可重複），其中至少有一個字母重複出現的方法數有多少？ 3. 計算橋牌（52 張發 13 張）的總組合數，並求拿到 13 張全是同一花色的機率。 4. 擲 20 次硬幣，正面次數最可能是幾次？用二項分布的組合數逐一算出機率找最大值。