组合数学核心概念：第二类斯特林数与球盒模型

一、第二类斯特林数（$\left\{ n \atop m \right\}$ / $S_2(n,m)$）

1. 递推关系

$$\left\{ n \atop m \right\} = \left\{ n-1 \atop m-1 \right\} + m \cdot \left\{ n-1 \atop m \right\}$$

• 解释：第 $n$ 个元素单独放新盒（对应 $\left\{ n-1 \atop m-1 \right\}$ ），或放进已有 $m$ 个盒之一（对应 $m \cdot \left\{ n-1 \atop m \right\}$ ）

2. 容斥公式

$$\left\{ n \atop m \right\} = \frac{1}{m!} \sum_{i=0}^m (-1)^{m-i} \binom{m}{i} \cdot i^n$$

• 思路：用容斥原理计算“恰好 $m$ 个非空盒”的方案数（总放法 $-$ 至少空1盒 $+$ 至少空2盒 $\dots$ ）

3. 贝尔数（Bell Number）

$$B(n) = \sum_{i=0}^n \left\{ n \atop i \right\}$$

二、球盒模型汇总（$n$ 球，$m$ 盒）

三、补充关联

• 公式关联：$m^n = \sum_{i=0}^m \binom{m}{i} \cdot i! \cdot \left\{ n \atop i \right\}$
  （解释：球不同、盒不同的总放法 = 选 $i$ 个非空盒 $\times$ 排列球进盒 $\times$ 第二类斯特林数划分 ）
• 置换（Permutation）：与斯特林数共同用于组合计数（如划分后排列盒子场景）

欧拉函数

定义

例题：P1390 公约数的和

$$\large\sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(i, j)\\ =\large\sum_{i = 1}^n \sum_{j = i + 1}^n \sum_{d=1}^{n}d[\gcd(i, j)=d]\\ =\large\sum_{i = 1}^n \sum_{j = i + 1}^n \sum_{d=1}^{n}d[\gcd(\frac{i}{d}, \frac{j}{d})=1]\\ =\sum_{d=1}^{n}d\large\sum_{i = 1}^{\frac{n}{d}} \sum_{j = i + 1}^{\frac{n}{d}} [\gcd(i, j)=1]\\ =\sum_{d=1}^{n}d((\sum_{i=1} ^{\frac{n}{d}}\varphi(i))-1)$$

例题：P2303 [SDOI2012] Longge 的问题

$$枚举\gcd(i,n) 的 值:\\ \large\sum\limits_{i=1}^{n}\gcd(i,n)=\sum\limits_{d|n}d\sum\limits_{i=1}^{n}[\gcd(i,n)=d]\\ \large同除 d 得:\\ \large=\sum\limits_{d|n}d\sum\limits_{i=1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]\\ =\sum\limits_{d|n}d \varphi(\frac{n}{d})$$

例题：P1891 疯狂 LCM

$$\sum\limits_{i=1}^{n}lcm(i,n)=n\sum\limits_{i=1}^{n}\frac{i }{\gcd(i,n)} \\ =n\sum\limits_{d|n}\sum\limits_{i=1}^{n}\frac{i}{d\times[gcd(i,n)=d]}\\ =n\sum\limits_{d|n}\sum\limits_{i=1}^{n}\frac{i}{d}[gcd(i,n)=d]\\ =n\sum\limits_{d|n}\sum\limits_{i=1}^{\frac{n}{d}}i[gcd(i,\frac{n}{d})=1]\\ =n\sum\limits_{d|n}\sum\limits_{i=1}^{d}i[gcd(i,\frac{n}{d})=1]\\$$ $$n\sum\limits_{d|n}\sum\limits_{i=1}^{d}i[gcd(i,\frac{n}{d})=1]\\ =n\sum\limits_{d|n}\frac{\varphi(d)}{2}d$$

例题：P2398 GCD SUM

$$\large \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} \gcd(i,j)\\ =\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{d=1}^{n}d[\gcd(i,j)=d]\\ =\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{d=1}^{n}d[\gcd(\frac{i}{d},\frac{j}{d})=1]\\ =\sum\limits_{d=1}^{n}d\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd(\frac{i}{d},\frac{j}{d})=1]\\ =\sum\limits_{d=1}^{n}d(\sum\limits_{i=1}^{\frac{n}{d}}2\varphi(i))-1$$

莫比乌斯反演专题

公式 & 性质

$$\large\large[\gcd(i,j)=1]=\sum\limits_{d|gcd(i,j)}\mu(d)\\$$ $$\Large\large\sum\limits_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n}\\ \\ \Large\large\sum\limits_{i=1}^{n}\sum\limits_{d|i}\mu(d)=\sum\limits_{d=1}^{n}\lfloor\frac{n}{d}\rfloor\mu(d)\\$$

套路

$$\Large 对于形如\sum\limits_{i=1}^{n}\sum\limits_{d|i}\mu(d)可以直接枚举d\\ 变为\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}\mu(d)=\sum\limits_{d=1}^{n}{\lfloor \frac{n}{d} \rfloor}\mu(d)$$

板子 1

$$\Large\large\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=1]\\ =\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{d|gcd(i,j)}\mu(d)\\ =\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{d|i}\sum\limits_{d|j}\mu(d)\\ =\sum\limits_{d=1}^{n}\lfloor\frac{n}{d}\rfloor\sum\limits_{j=1}^{m}\lfloor\frac{m}{d}\rfloor\mu(d)\\ =\sum\limits_{d}^{\min(n,m)}\mu(d)×\lfloor\frac{n}{d}\rfloor×\lfloor\frac{m}{d}\rfloor\\ \sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)=1]=\sum_{d=1}^{n}\mu (d) × \left \lfloor \frac{n}{d} \right \rfloor ^2$$

板子 2

$$f(x)=\large\large\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=k]\\ \large\large 当 \gcd(i,j)=k 时 [gcd(i,j)=k]=1 \\ \large\large 这未免有点太啰嗦了，所以离散化一下，变成:\\ \large\large f(x)=\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1]\\ \large\large可得\\ \large\large f(x)=\sum\limits_{d}^{\min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}\mu(d)×\lfloor\frac{n}{kd}\rfloor×\lfloor\frac{m}{kd}\rfloor$$

板子 3

$$\large\large\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}ij[gcd(i,j)=k]= \large\large\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}ij[gcd(i,j)=1]×k^2\\$$ $$因为 n 和 m 都为原来的\frac{1}{k}了所以 i, j也为原来的\frac{1}{k}，要把 ij 项补回去所以乘k^2\\ \large\large\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}ij\sum\limits_{d|gcd(i,j)}\mu(d)×k^2\\ \sum\limits_{d=1}^{\lfloor\frac{\min(n,m)}{k}\rfloor} \mu(d)×d^2\sum\limits_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{kd}\rfloor}ij×k^2\\ 整理一下\\ k^2×\sum\limits_{d=1}^{\lfloor\frac{\min(n,m)}{k}\rfloor} \mu(d)×d^2\sum\limits_{i=1}^{\lfloor\frac{n}{kd}\rfloor}i\sum\limits_{j=1}^{\lfloor\frac{m}{kd}\rfloor}j\\ 后两项\sum\limits_{i=1}^{\lfloor\frac{n}{kd}\rfloor}i\sum\limits_{j=1}^{\lfloor\frac{m}{kd}\rfloor}j为等差数列直接求$$

杜教筛

狄利克雷卷积

$$\mu*I=\epsilon\\ \varphi*I=id\\ \mu*id=\varphi\\$$

后记

微积分

计算 $\pi$

$$\Large f(x)=\sqrt{1-x^2}\\ \frac{\pi}{4}=\int_{0}^{1}f(x)dx\\ =\lim_{n \to \infty}\sum\limits_{i=1}^{n} f(\frac{i}{n}) \cdot\frac{1}{n}\\ =\lim_{n \to \infty}\sum\limits_{i=1}^{n} \sqrt{1-\frac{i^2}{n^2}} \cdot\frac{1}{n}\\ =\lim_{n \to \infty}\frac{1}{n}\sum\limits_{i=1}^{n} \sqrt{\frac{n^2-i^2}{n^2}} \\ =\lim_{n \to \infty}\frac{1}{n^2}\sum\limits_{i=1}^{n} \sqrt{n^2-i^2} \\ \therefore \frac{\pi}{4}=\lim_{n \to \infty}\frac{1}{n^2}\sum\limits_{i=1}^{n} \sqrt{n^2-i^2}$$