组合数学笔记

待更新

计数原理

加法原理

又称分类计数原理

完成一个工作共有(n)类方法。在第一类方法中有(m_1)种不同的方法，在第二类方法中有(m_i)种不同的方法，……，在第(n)类方法中有(m_n)种不同的方法，那么完成这个工作共有(m_1+m_2+……+m_n)种不同的方法。

乘法原理

又称分步计数原理

完成一件工作共需(n)个步骤，完成第一个步骤有(m_1)种方法，完成第二个步骤有(m_2)种方法，……，完成第(n)个步骤有(m_n)种方法，那么完成这个工作共有(m_1 imes m_2 imes… imes m_n)种方法。

排列组合

排列数

用(A_n^m)表示从(n)个不同元素中依次取出(m)个元素排成一列，产生的不同排列的数量

(A_n^m=dfrac{n!}{(n-m)!}=n imes (n - 1) imes(n-2) imes… imes(n-m+1))

组合数

用(C_n^m)或(dbinom{n}{m})表示从(n)个不同元素种取出(m)个组成一个集合（不考虑顺序），产生的不同集合的数量

(dbinom{n}{m}=dfrac{n!}{m!(n-m)!}=dfrac{n imes(n-1) imes… imes(n-m+1)}{m imes(m-1) imes… imes2 imes1})

组合恒等式

证明百年之后补

(dbinom{n}{m}=dbinom{n}{n-m};)
(dbinom{n}{m}=dbinom{n-1}{m-1}+dbinom{n-1}{m})
(sumlimits_{i=0}^{n}dbinom{n}{i}=2^n;)
$sumlimits_{i=0}^{n}dbinom{n}{i}[2mid i]=sumlimits_{i=0}^{n}[2 mid i]=2^{n-1} $
(k)个非负整数变量和为(n)的方案数（插板法）：(dbinom{n+k-1}{k-1})
(sumlimits_{i=0}^mdbinom{n+i}{n}=dbinom{n+m+1}{m})
(sumlimits_{i=m}^ndbinom{i}{m}=dbinom{n+1}{m+1})
(dbinom{n}{m}dbinom{m}{k}=dbinom{n}{k}dbinom{n-k}{m-k})
(sumlimits_{i=0}^kdbinom{n}{i}dbinom{m}{k-i}=dbinom{n+m}{k})

二项式定理

((x+y)^n=sumlimits_{k=0}^ndbinom{n}{k} x^ky^{n-k})

自然数幂之和

[S_k(n)=sumlimits_{i=1}^ni^k ]

小结论

(S_k(n))是关于(n)的(k+1)次多项式。

归纳&&证明

对(k)归纳：

(k=0,S_k(n)=n)，是关于(n)的一次多项式
(kleq d-1),是关于(n)的(d)次多项式
~~前置：谔项式定理~~
( (i+1)^{d+1}-i^{d+1}\=sumlimits_{j=0}^{d+1}dbinom{d+1}{j}i^j-i^{d+1}\=sumlimits_{j=0}^ddbinom{d+1}{j}i^j)
~~然而上面这些并没有用~~，这样并不能求出(S_k(n))的值，所以考虑再加一层求和符号（因为可以交换/cy）
( sumlimits_{i=1}^{n}((i+1)^{d+1}-i^{d+1})\=sumlimits_{i=1}^nsumlimits_{j=0}^ddbinom{d+1}{j}i^j\=sumlimits_{j=0}^ddbinom{d+1}{j}sumlimits_{i=1}^ni^j\=sumlimits_{j=0}^ddbinom{d+1}{j}S_j(n))
上面那个(sumlimits_{i=1}^{n}((i+1)^{d+1}-i^{d+1}))其实又等于((n+1)^{d+1}-1)
所以现在我们就得到了((n+1)^{d+1}-1=sumlimits_{i=0}^ddbinom{d+1}{i}S_i(n))
把(S_d(n))提出来再除一下，胡乱化一下就能发现(S_d(n))的确是(n+1)次的多项式……得证（因为懒所以不想写了，~~而且是小学知识……~~）

求法

暴力

(O(nlog k))
~~rank1，~~呼呼呼，好快

拉格朗日插值

待补充

对于(k)次多项式函数(mathbf F)以及(k+1)个点值((x_0,y_0),(x_1, y_1),...,(x_k, y_k))，有(mathbf　F(x)=sumlimits_{i=0}^jy_iprodlimits_{i e j}dfrac{x-x_j}{x_i-x_j})

可以做到(O(klog k))

局限性：模数必须是大于(n)的质数

斯特林数

(S_k(n)=dfrac{(n+1)^{underline{k+1}}}{k+1}-sumlimits_{i=0}^{k-1}(-1)^{k-i}cdotegin{bmatrix}k\iend{bmatrix}cdot S_i(n))

证明

一个组合恒等式（先不讲为啥）：

[n^{underline{k}} = sum_{i=0}^{k}(-1)^{k-i}{ left[{egin{matrix}k\iend{matrix}} ight]}n^{i} ]

其中(n^{underline k})表示(n)的(k)次下降幂
我们一般的(n^k)是(k)个(n)相乘，但是这里是每次乘都减一
展开就是(n imes(n-1) imes(n-2)… imes(n-k+1))

(i=k) 时，有 ((-1)^{k-i} egin{bmatrix}k\iend{bmatrix} n^i=n^k)，则

[n^k = n^{underline{k}} - sumlimits_{i=0}^{k-1}(-1)^{k-i}{ left[{egin{matrix}k\iend{matrix}} ight]}n^{i} ]

是不是想到了什么？
没错，我们可以把(1)到(n)的(k)次方求和，显然这就是(S_k(n))，展开式子就是

[S_k(n) = sum_{i=1}^{n}i^k = sum_{i=1}^{n}left({i^{underline{k}}-sum_{j=0}^{k-1}(-1)^{k-j}{ left[egin{matrix}k\jend{matrix} ight]}i^j} ight) ]

显然的想法拆开求和符号。
对于第一项，转化为组合数。
使用组合恒等式合并，再展开组合数，有：

[egin{aligned} &sumlimits_{i=1}^{n}i^{underline{k}}\ =&k!sum_{i=1}^{n}dfrac{i^{underline{k}}}{k!}\ =&k!sum_{i=1}^{n}{left(egin{matrix}i\kend{matrix} ight)}\ =&k!{left(egin{matrix}n+1\k+1end{matrix} ight)}\ =&dfrac{(n+1)^{underline{k+1}}}{k+1} end{aligned}]

对于第二项，只有 (i^j) 与 (i) 有关，交换求和符号，有：

[egin{aligned} &sum_{j=0}^{k-1}(-1)^{k-j}{ left[egin{matrix}k\jend{matrix} ight]}sum_{1}^{n}i^j \= &sum_{i=0}^{k-1} cdot { left[{egin{matrix}k\iend{matrix}} ight]\,} cdot S_i(n) end{aligned}]

这样就得到了上面的式子。

摆脱了质数的限制，时间复杂度(O(k^2))

伯努利数伯努利多项式

？？？果断抄式子走人

~~先求伯努利数，暴力算暴力算暴力算，多项式求逆~~

他们在说什么？不知道，走了

~~灾难始终慢我一步~~

(dfrac{x}{e^x-1}=sumlimits_{i=0}^{infty}dfrac{B_i}{i!}x^i)

(sumlimits_{i=0}^infty dfrac{largeeta_i(t)}{i!}cdot x^i=dfrac{x}{e^x-1}cdot e^{tx})

(S_k(n)=dfrac{1}{k+1}sumlimits_{i=0}^kdbinom{k+1}{i}cdot(n+1)^icdot B_{k+1-i})

斯特林数

挪出去了，见此处斯特林数

第一类斯特林数
第二类斯特林数
上升幂和下降幂

容斥原理

挪出去了，见此处容斥原理

容斥原理
min-max容斥

写在最后

( exttt{gyh})也太神了吧

为什么我这么菜/kk

哆啦诶喂梦，爱了爱了！