斯特林数
第一类斯特林数
- s(n, m)表示将n个元素分成m个圆排列的方案数
- 也可以记作(egin{bmatrix}n\mend{bmatrix})
递推式
- (egin{bmatrix}n\mend{bmatrix} = egin{bmatrix}n - 1\m - 1end{bmatrix} + (n - 1)egin{bmatrix}n - 1\mend{bmatrix})
- 表示可以自己单独拿出来成为一个环， 也可以放在任意一个元素的前面
性质1
[sum_{i=0}^n egin{bmatrix}n\iend{bmatrix} = n!
]
- 证明：每个排列实际上对应着一个置换
- 考虑s(n,i)分成的i个环， 实际上就是对应着循环节个数为i的一种置换， 一一对应过去就是所有置换方案就是全排列了
性质2
[displaystyle x^{underline{n}}=sum_{i=0}^negin{bmatrix}n\iend{bmatrix}(-1)^{n-i}x^i
]
- 证明：使用数学归纳法
- 对于(n == 1)的情况， 显然成立
- 对于(n > 1)的情况
[egin{aligned}x^{underline{n+1}}&=(x-n)x^{underline n}\
&=(x-n)*sum_{i=0}^negin{bmatrix}n\iend{bmatrix}(-1)^{n-i}x^i\
&=sum_{i=0}^{n+1}egin{bmatrix}n\i-1end{bmatrix}(-1)^{n-i-1}x^i+nsum_{i=0}^{n+1}egin{bmatrix}n\iend{bmatrix}(-1)^{n-i+1}x^i\
&=sum_{i=0}^{n+1}(egin{bmatrix}n\i-1end{bmatrix}+n*egin{bmatrix}n\iend{bmatrix})(-1)^{n+1-i}x^i\
&=sum_{i=0}^{n+1}egin{bmatrix}n+1\iend{bmatrix}(-1)^{n+1-i}x^i
end{aligned}
]
- 同理
[displaystyle x^{overline n}=sum_{i=0}^n egin{bmatrix}n\iend{bmatrix}x^i
]
- 证明
[egin{aligned}
x^{overline {n + 1}}&=(x + n) sum_{i = 0}^n
egin{bmatrix}n\iend{bmatrix} x ^ i\
&= sum_{i = 0}^{n + 1}
egin{bmatrix}n\i - 1end{bmatrix} x ^ i + nsum_{i = 0}^{n + 1}
egin{bmatrix}n\iend{bmatrix} x ^ i\
&=sum_{i = 0}^{n + 1}(
egin{bmatrix}n\i - 1end{bmatrix} + negin{bmatrix}n\iend{bmatrix})x ^ i\
&= sum_{i = 0} ^ {n + 1}egin{bmatrix}n + 1\iend{bmatrix} x ^ i
end{aligned}
]
自然幂数和问题
- 记录(S_k(n) = sum_{i = 1} ^ n i ^ k)
- 那么考虑
[egin{aligned}
x^{underline{n}}&=sum_{i=0}^negin{bmatrix}n\iend{bmatrix}(-1)^{n-i}x^i\
x ^n&=x^{underline{n}} - sum_{i = 0}^{n - 1}egin{bmatrix}n\iend{bmatrix}(-1) ^ {(n - i)} x^i\
end{aligned}
]
- 把这个带进式子求得
[egin{aligned}
S_k(n) &= sum_{i = 1}^n i ^ k\
&= sum_{i = 1} ^ n (i^{underline{k}} - sum_{j = 0}^{k - 1} egin{bmatrix}k\jend{bmatrix} (-1) ^ {k - j}i^j)\
&=sum_{i = 1} ^ n i ^{underline{k}} - sum_{j = 0} ^ {k - 1} egin{bmatrix}k\jend{bmatrix} (-1) ^ {k - j}(sum_{l = 1} ^ {n} l ^ j)\
&= frac{(n + 1) ^ {underline{k + 1}}}{k + 1}- sum_{j = 0} ^ {k - 1} egin{bmatrix}k\jend{bmatrix} (-1) ^ {k - j}s_{l}(n)
end{aligned}
]
- 递推即可
预处理方法
- 分治fft
- 构造第一类斯特林数生成函数
[sum_{i=0}^negin{bmatrix}n\iend{bmatrix} x^i=prod_{i=0}^{n-1}(x+i)
]
- 显然可行
- 倍增法
- 记(displaystyle F_n(x)=prod_{i=0}^{n-1}(x+i))
- 那么存在(F_{2n}(x)=F_n(x)F_{n}(x+n))
- 递归求解(F_n(x)), 然后考虑快速求解(F_n(x + n))
- 考虑设
[F_n(x) = sum_{i = 0} ^ {n - 1} a_i x ^ i
]
[egin{aligned}
F_n(x+n)&=sum_{i=0}^{n-1}a_i (x+n)^i\
&=sum_{i=0}^{n-1}a_isum_{j=0}^i{ichoose j}n^{i-j}x^j\
&=sum_{i=0}^{n-1}(sum_{j=i}^n {jchoose i}n^{j-i}a_j)x^i
end{aligned}
]
- 后面显然可以卷积
[]
第二类斯特林数
- S(n,m)表示把n个元素划分成m个子集的方案数
- 记作(egin{Bmatrix}n\mend{Bmatrix})
递推式
[egin{Bmatrix}n\mend{Bmatrix}=egin{Bmatrix}n-1\m-1end{Bmatrix}+m*egin{Bmatrix}n-1\mend{Bmatrix}
]
- 组合意义是放到任意一个集合中或者新建一个集合
性质1
[egin{aligned}
egin{Bmatrix}n\mend{Bmatrix} &= frac{1}{m!} sum_{i = 0} ^ m (-1) ^ i inom{m}{i}(m - i) ^ n\
&= sum_{i = 0}^m frac{(-1) ^ i}{i!} frac{(m - i) ^ n}{(m - i) !}
end{aligned}
]
- 可以看做进行容斥， 枚举多少个集合不放置， 其余的集合随便放置， 最后每一种情况会统计m！次
- 显然可以卷积求解
性质2
[m ^ n = sum_{i = 0}^m egin{Bmatrix}n\iend{Bmatrix} m^{underline{i}}
]
- 证明：可以看作将n个求放到m个带标号的盒子内， 那么我们枚举哪些盒子不为空， 则
[egin{aligned}
m ^ n &= sum_{i = 0}^m egin{Bmatrix}n\iend{Bmatrix} inom{m}{i} i!\
&=sum_{i = 0}^m egin{Bmatrix}n\iend{Bmatrix} m^{underline{i}}
end{aligned}
]
容斥
经典容斥系数的解
- 证明每个地方只要被覆盖了就会被统计1次答案， 假如这个地方被覆盖了n次， 那么
[egin{aligned}
ans&=sum_{i = 1} ^ n (-1) ^{ (i - 1)} inom{n}{i}\
&= sum_{i = 1} ^ n (inom{n - 1}{i} + inom{n - 1}{i - 1}) (-1)^{i - 1}\
&= sum_{i = 1} ^ {n - 1} inom{n - 1}{i} (-1) ^{i - 1} + sum_{i = 1} ^ n inom{n - 1}{i - 1} (-1) ^{i - 1}\
&= sum_{i = 1} ^ {n - 1} inom{n - 1}{i} (-1) ^{i - 1} + sum_{i = 1} ^ {n - 1} inom{n - 1}{i} (-1) ^{i} + inom{n}{0}\
&=1
end{aligned}
]
错排问题
- 考虑枚举那些地方强制相同， 然后其余地方随便放置，
[egin{aligned}
f[n] &= sum_{i = 0} ^ n inom{n}{i} (-1)^i(n - i)!\
&=sum_{i = 0} ^ n (-1) ^i frac{n!}{i!}\
&= (-1) ^ n + nsum_{i = 0} ^ {n - 1}(-1) ^ i frac{(n - 1)!}{i!}\
&= (-1) ^ n + nf[n - 1]
end{aligned}
]
min-max容斥
- 设S是一个可重集合，max(S)和min(S)分别表示集合中的最大值和最小值，则有如下式子成立:
[egin{aligned}
max(S) &= sum_{Tsubseteq S} (-1) ^ {|T| + 1} min(T)\
min(S) &= sum_{Tsubseteq S} (-1) ^ {|T| + 1} max(T)
end{aligned}
]
- 证明
- 以第一个式子为例，设max(S)=x，那么只有T={x} 时的min(T) 为x（可能有多个相同的最大值，这时候随便钦点一个就可以了;
- 对于除此之外的所有T，肯定至少存在一个集合A∩T = ?, 使得min(T和A每个子集的并)等于min(T)，
- 然后由于从A中选择奇数偶数个元素的方案数相同， 所以正负抵消， 最后只剩下了x
推广1
- 在期望下该式子也是成立的， 即
[egin{aligned}
E[max(S)] &= sum_{Tsubseteq S} (-1) ^ {|T| + 1} E[min(T)]\
E[min(S)] &= sum_{Tsubseteq S} (-1) ^ {|T| + 1} E[max(T)]
end{aligned}
]
反演
反演本质
- 给定数列({f_i}) 和({g_i})存在
[g_n = sum_{i = 0} ^ n a[n][i] f_i
]
- 这里使用f推出了g， 那么我们反演的过程就是使用g推出f
- 也就是找到系数数组b，使得
[f_n = sum_{i = 0} ^ n b[n][i] g_i
]
- 引入克罗内克函数（为了好写）
[delta(i,j)=egin{cases}1&i=j\0&i
eq jend{cases}
]
- 整合两个式子得到
[egin{aligned}f_n&=sum_{i=0}^n b[n][i]g_i\&=sum_{i=0}^n b[n][i]sum_{j=0}^ia[i][j]f_j\&=sum_{i=0}^n f_isum_{j=i}^nb[n][j]*a[j][i]end{aligned}
]
- 同理
[g[n] = sum_{i = 0} ^ n g_i sum_{j = i} ^ n a[n][j] * b[j][i]
]
- 显然， 这里能够反演的前提条件是
[egin{cases}
sum_{j = i} ^ n b[n][j] * a[j][i] &= delta(n, i)\
sum_{j = i} ^ n a[n][j] * b[j][i] &= delta(n,i)
end{cases}
]
二项式反演
[f_n=sum_{i=0}^n {n choose i}g_iiff g_n=sum_{i=0}^n (-1)^{n-i}{n choose i}f_i
]
- 证明， 即要证明
[egin{cases}
sum_{j = i} ^ n inom{n}{j}(-1) ^ {j - i}inom{j}{i} &= delta(n, i)\
sum_{j = i} ^ n (-1) ^ {n - j} inom{n}{j} inom{j}{i} &= delta(n,i)
end{cases}
]
- 仅证第一个， 第二个类似
[egin{aligned}
sum_{j=i}^n{n choose j}(-1)^{j-i}{j choose i}&=delta(n, i)\
sum_{j=i}^n(-1)^{j-i}{n choose i}{n-i choose j-i}&=delta(n,i)\
{n choose i}sum_{d=0}^{n-i}(-1)^{d}{n-i choose d}&=delta(n, i)\
end{aligned}
]
- 后面这堆式子仅当n等于i的时候取值为1， 否则取值为0， 故得证
- 另一种形式是
[egin{aligned}f_n&=sum_{i=0}^n(-1)^i{n choose i}g_i\g_n&=sum_{i=0}^n(-1)^i{nchoose i}f_iend{aligned}
]
- 证明
[egin{aligned}
sum_{j = i} ^ n (-1) ^ j inom{n} {j} (-1) ^ i inom{j}{i}&= delta(n, i)\
sum_{j = i} ^ n (-1) ^{i + j} inom{n}{i} inom{n - i}{j - i}&=delta(n,i)\
inom{n}{i} sum_{j = i} ^ {n}(-1) ^{j - i}inom{n - i}{j - i} &= delta(n,i)
end{aligned}
]
- 得证
斯特林反演
- 式子是
[egin{aligned}
f(n)=sum_{i=1}^n egin{Bmatrix}n\iend{Bmatrix}g(i)iff g(n)=sum_{i=0}^n(-1)^{n-i}egin{bmatrix}n\iend{bmatrix}f(i)end{aligned}
]
- 需要证明
[egin{cases}sum_{j=i}^n(-1)^{n-j}egin{bmatrix}n\jend{bmatrix}egin{Bmatrix}j\iend{Bmatrix}=delta(n,i)\sum_{j=i}^n(-1)^{j-i}egin{bmatrix}j\iend{bmatrix}egin{Bmatrix}n\jend{Bmatrix}=delta(n,i)end{cases}
]
- 首先容易得到
[egin{aligned}
x^{underline{n}}=(-1)^n(-x)^{overline{n}}\
x^{overline{n}}=(-1)^n(-x)^{underline{n}}
end{aligned}
]
- 那么
[egin{aligned}
displaystyle m^n&=sum_{i=0}^{n}egin{Bmatrix}n\iend{Bmatrix}(-1)^i(-m)^{overline{i}}\
&=sum_{i=0}^{n}egin{Bmatrix}n\iend{Bmatrix}(-1)^isum_{j=0}^iegin{bmatrix}i\jend{bmatrix}(-m)^j\
&=sum_{i=0}^n m^isum_{j=i}^{n}egin{Bmatrix}n\jend{Bmatrix}egin{bmatrix}j\iend{bmatrix}(-1)^{j-i}
end{aligned}
]
莫比乌斯反演
- 式子是
[f_n=sum_{d|n}g_diff g_n=sum_{d|n}mu_{frac{n}{d}}f_d
]
- 需要证明
[egin{cases}
sum_{j = i} ^ n [j | n] mu(frac{n}{j})[i | j] = delta(i, n)\
sum_{j = i} ^ n [j | n] [i | j] mu(frac{j}{i}) = delta(i, n)
end{cases}
]
- 我们来证明
[sum_{j = i} ^ n [j | n] [i | j] mu(frac{j}{i}) = delta(i, n)
]
- 首先n不是i倍数的时候答案一定是0
- 假设n是i的倍数， 那么
[egin{aligned}
& sum_{j = i} ^ n [j | n] [i | j] mu(frac{j}{i})\
&=sum_{d = 1} ^ {frac{n}{i}}[d | frac{n}{i}] mu(d)\
&=delta(n,i)
end{aligned}
]
- 同理可证另一个