记录CS2304：计算机科学中的数学基础课程中的组合数学部分。

Review

教材：
An invitation to discrete mathematic

Inclusion-Exclusion Principle

通用公式：

proved by induction.

完全错排

记 D(n) 为 n 个元素的完全错排数。

递推公式

D(n) = (n-1)[D(n-1) + D(n-2)]

initial condition: D(1) = 0, D(2) = 1

通项公式

or written as:

容斥原理推导过程

设 A_i 表示”第 i 个元素在原位置上”的排列集合。则完全错排数就是 $|\overline{A_1 \cup A_2 \cup ... \cup A_n}|$，即所有元素都不在原位置的排列数。

补集转化

• $|A{i_1} \cap A{i2} \cap … \cap A{i_k}|$ 表示恰好有 k 个元素在原位置的排列数
• 选择这 k 个位置的方法有 种
• 剩下的 n-k 个位置可以任意排列，有 种方法
• 因此 $|A_{i_1} \cap A_{i_2} \cap ... \cap A_{i_k}| = \binom{n}{k}(n-k)!$

当 n → ∞ 时， 收敛于 ，这就解释了为什么 $D(n) \approx \frac{n!}{e}$

欧拉函数

欧拉函数 表示小于 n 且与 n 互质的正整数的个数。

计算方法

1. 乘法性质：若 a, b 互质，则

2. 质数的欧拉函数：若 p 为质数，则

3. 质数幂的欧拉函数：若 p 为质数，k ≥ 1，则

4. 通用公式：对于任意正整数 n，若 n 的质因数分解为：

   $$n = p_1^{k_1} \cdot p_2^{k_2} \cdot ... \cdot p_m^{k_m}$$

   由容斥原理：

   $$\phi(n) = n - \sum_{i} \frac{n}{p_i} + \sum_{i<j} \frac{n}{p_ip_j} - \sum_{i<j<k} \frac{n}{p_ip_jp_k} + ...$$ $$\phi(n) = n \prod_{i=1}^m (1-\frac{1}{p_i})$$

Generation Function

生成函数是将一个序列 转化为函数形式的强大工具，通常表示为幂级数：

其中， 是序列中的第 项， 是形式变量。

用于排列组合问题：

用于离散随机变量的概率分布：

3. 生成函数的应用

3.1 求解递推关系

1
2
3
4
5
6
7
8
9
10
11
12

# 示例：使用生成函数求解斐波那契数列
def fibonacci_generating_function(n):
    # 斐波那契数列的生成函数：G(x) = x/(1-x-x^2)
    # 展开为幂级数可求第n项
    import numpy as np
    
    # 使用递推关系直接计算
    fib = [0, 1]
    for i in range(2, n+1):
        fib.append(fib[i-1] + fib[i-2])
    
    return fib[n]

3.2 计数问题

例：有多少种方式将 个相同物体放入 个不同盒子中？

• 生成函数：
• 展开后 的系数就是答案

3.3 概率论应用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 使用生成函数计算两个骰子和的概率分布
def dice_sum_probability(sum_value):
    # 单个骰子的生成函数：P(x) = (x^1 + x^2 + ... + x^6)/6
    # 两个骰子和的生成函数：P(x)^2
    
    # 初始化概率计数
    counts = [0] * 13  # 索引0不使用，可能的和为2-12
    
    # 暴力计算所有可能结果
    for i in range(1, 7):
        for j in range(1, 7):
            counts[i + j] += 1
    
    # 计算概率
    return counts[sum_value] / 36

4. 生成函数的性质

• 加法：序列加法对应生成函数加法
• 乘法：序列卷积对应生成函数乘法
• 微分：
• 积分：

5. 常见生成函数

6. 示例：计算组合数

1
2
3
4
5
6
7
8
9
10
11
12

# 使用生成函数计算组合数 C(n,k)
def binomial_coefficient(n, k):
    # 使用二项式定理: (1+x)^n = Σ(k=0 to n) C(n,k) * x^k
    if k < 0 or k > n:
        return 0
    
    # 计算组合数
    result = 1
    for i in range(1, k+1):
        result = result * (n - i + 1) // i
    
    return result