排列组合：计数的艺术

排列与组合的直觉

从 n 个元素中有序选 k 个：第一步 n 种选法，第二步 n-1 种……第 k 步 n-k+1 种，乘起来是 P(n,k) = n!/(n-k)!。若不关心顺序，k 个元素有 k! 种排列方式，所以 C(n,k) = P(n,k)/k! = n!/(k!(n-k)!)。

package main

import "fmt"

// 阶乘（小心溢出，n>20 就超 int64）
func factorial(n int) int64 {
    if n <= 1 { return 1 }
    return int64(n) * factorial(n-1)
}

// 排列数 P(n,k)
func perm(n, k int) int64 {
    if k > n { return 0 }
    result := int64(1)
    for i := n; i > n-k; i-- {
        result *= int64(i)
    }
    return result
}

// 组合数 C(n,k)：用帕斯卡 DP，避免阶乘溢出
func combDP(n, k int) [][]int64 {
    C := make([][]int64, n+1)
    for i := range C {
        C[i] = make([]int64, n+1)
        C[i][0] = 1
        for j := 1; j <= i; j++ {
            C[i][j] = C[i-1][j-1] + C[i-1][j]  // 帕斯卡公式
        }
    }
    return C
}

func main() {
    // 密码强度：8 位字母数字密码有多少种
    chars := 26 + 26 + 10  // 62 个字符
    space := perm(62, 62)   // 实际是 62^8 = 218 trillion
    _ = space
    fmt.Printf("8 位密码空间: %.2e\n", float64(218_340_105_584_896))

    // 组合：从 10 道题选 3 道有几种
    C := combDP(10, 10)
    fmt.Println("C(10,3) =", C[10][3])  // 120

    // 杨辉三角前 6 行
    for i := 0; i <= 5; i++ {
        for j := 0; j <= i; j++ {
            fmt.Printf("%3d ", C[i][j])
        }
        fmt.Println()
    }
}

组合数取模（竞赛常见）

C(n,k) 很快就会超过 int64，竞赛和工程里常要求 C(n,k) % p（p 是大素数）。此时用卢卡斯定理或预计算阶乘逆元。

package main

import "fmt"

const MOD = 1_000_000_007

func powMod(base, exp, mod int64) int64 {
    result := int64(1)
    base %= mod
    for exp > 0 {
        if exp&1 == 1 { result = result * base % mod }
        exp >>= 1
        base = base * base % mod
    }
    return result
}

// 预计算阶乘和逆元，O(n) 预处理，O(1) 查询
func buildFactorial(n int) (fac, inv []int64) {
    fac = make([]int64, n+1)
    inv = make([]int64, n+1)
    fac[0] = 1
    for i := 1; i <= n; i++ {
        fac[i] = fac[i-1] * int64(i) % MOD
    }
    inv[n] = powMod(fac[n], MOD-2, MOD)  // 费马小定理
    for i := n - 1; i >= 0; i-- {
        inv[i] = inv[i+1] * int64(i+1) % MOD
    }
    return
}

func main() {
    fac, inv := buildFactorial(1000)
    comb := func(n, k int) int64 {
        if k < 0 || k > n { return 0 }
        return fac[n] * inv[k] % MOD * inv[n-k] % MOD
    }
    fmt.Println(comb(100, 50))  // C(100,50) mod 1e9+7
    fmt.Println(comb(10, 3))    // 120
}

实战：A/B 测试的样本量计算

A/B 测试需要估算「至少需要多少用户才能区分 1% 的转化率差异」。这是统计功效分析的问题，底层用到二项分布，而二项分布的系数正是 C(n,k)。工程里的公式：n ≈ 2 × (z_α/2 + z_β)² × p(1-p) / Δ²，其中 z 值来自正态分布表（概率论内容将在第 8 章展开）。

排列组合是把无限的可能性折叠成有限的数字——每个数字背后都是一片宇宙。

— 具体数学