有关容斥的知识及题目解析

小目录:

一,容斥原理

二,子集反演

三,最值反演($\textit{Min_Max}$容斥)

四,斯特林反演

五,单位根反演


前置概念

一,第一类斯特林数:

$\begin{bmatrix}n\\k\end{bmatrix}$

那个大的中括号叫做 轮换 ,意思是将$n$个元素划分成$k$集合,每个集合进行 圆排列 的方案数。

圆排列:将长度为$n$的序列连成一个环,不同的排列数。其实就是$P_n=(n-1)!$,这里P是圆排列

关于其有一个递推式

$\begin{bmatrix}n\\k\end{bmatrix}=\begin{bmatrix} n-1\\k-1 \end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}$

证明可以类似用组合数的方法,原来有$n-1$个元素,划分了$k-1$个集合的方案加上一个新加的集合贡献的方案。

有三个性质:

一,

$\sum_{i=0}^{n} \begin{bmatrix}n\\i\end{bmatrix}=n!$

写两种不同的排列,然后映射连边,组成环的个数就是划分集合的个数,然后依次类推,组成一个环的排列,两个环的排列。。。。

有关容斥的知识及题目解析

 

 

 

 如图就是$\begin{bmatrix}7\\3\end{bmatrix}$的图示了,其他的加和推广可以yy,比较好想。

二,

$x^{\underline{n}}=\sum_{i=0}^{n}(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}x^i$

此柿子可以用归纳法证明,详见我的学长链接里Lrerain的博客。

其中$\underline{n}$是表示降幂,同理$\overline{n}$表示升幂

三,

x^{\overline{n}}=\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i

同样的,这里就不证明了。

这几条性质可以解决升幂变化通幂再变化升幂或者降幂等等的转化,比较好用

有其是组合数里面的那种降幂。

二,第二类斯特林数:

$\begin{Bmatrix}n\\k\end{Bmatrix}$

表示$n$个元素划分为$k$个集合的方案数。

比上一个好理解。。。。

通项公式:

$\begin{Bmatrix}n\\m\end{Bmatrix}=\sum_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!}$

递推式:

$\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\k\end{Bmatrix}$

同样有几个性质。

一,

$k^n=\sum_{i=0}^{k}\begin{Bmatrix}n\\i\end{Bmatrix}i!\binom{k}{i}=\sum_{i=0}^{k}\begin{Bmatrix}n\\i\end{Bmatrix}k^{\underline{i}}$

有关容斥的知识及题目解析

 

 

 二,

有关容斥的知识及题目解析

 

有关容斥的知识及题目解析

 

 

 这两个过于难打,就直接粘贴了,上面的柿子化简可得下式。


前置知识完毕,$L_AT^EX$显然已经打废了。。。。

 

有关容斥的知识及题目解析

上一篇:codeforces two buttons


下一篇:jmeter之数据驱动