容斥关系
$\quad\\$
并集容斥原理
$\quad\\$
若$X$为一有限集，任取其$n$个子集$X_1,X_2,\cdots,X_n$，记其中$k$个集合之交的势的所有加和为$\mathfrak{S}_k$，即
$$\mathfrak{S}_ {k}=\sum\limits_{1\leq {i_1}<{i_2}\cdots<{i_k}\leq n}\left|\bigcap\limits_{1\leq j\leq k}X_{i_j}\right|,1\leq k\leq n$$
使用此记号，可以将并集容斥原理表示如下
$$\left|\bigcup\limits_{i=1}^nX_{i}\right|=\sum\limits_{k=1}^n(-1)^{k-1}\mathfrak{S}_k$$
$\nabla$证
$$记\chi_k(x)=\sum\limits_{1\leq i_1< i_2\cdots< i_n\leq n}\chi_{\small{\bigcap\limits_{1\leq j\leq k}X_{i_j}}}(x)，则有\\\\ \quad\\\\ \left|\bigcup\limits_{i=1}^nX_{i}\right|=\sum\limits_{x\in X}\chi_{\bigcup\limits_{i=1}^nX_{i}}(x)\\\\ \quad\\\\ \begin{aligned}\mathfrak{S}_k&=\sum\limits_{1\leq i_1< i_2\cdots< i_n\leq n}\left[\sum_{x\in X}\chi_{\small{\bigcap\limits_{1\leq j\leq k}X_{i_j}}}(x)\right]\\\\ &=\sum_{x\in X}\chi_k(x)\end{aligned}\\\\ \quad\\\\ 若x\notin \bigcup\limits_{i=1}^nX_{i}则有\\\\ \quad\\\\ \chi_{\bigcup\limits_{i=1}^nX_{i}}(x)=0=\sum\limits_{k=1}^n(-1)^{k-1}\chi_k(x)\\\\ \quad\\\\ 若x\in \bigcup\limits_{i=1}^nX_{i}，不妨假设x只属于其中m个集合，则有\\\\ \quad\\\\ \chi_{\bigcup\limits_{i=1}^nX_{i}}(x)=1\\\\ \quad\\\\ \sum\limits_{k=1}^n(-1)^{k-1}\chi_k(x)=\left(\begin{array}&m\\\\1\end{array}\right)-\left(\begin{array}&m\\\\2\end{array}\right)+\cdots+(-1)^{m-1}\left(\begin{array}&m\\\\m\end{array}\right)=1\\\\ \quad\\\\ 于是\chi_{\bigcup\limits_{i=1}^nX_{i}}(x)=\sum\limits_{k=1}^n(-1)^{k-1}\chi_k(x)恒成立，即容斥恒等式成立 $$
$\quad\\$
至少在m个集合中的元素个数
$\quad\\$
并集容斥恒等式可以看作至少在$1$个集合中的元素个数表达式，现在来寻求其推广，若$X$为一有限集，任取其$n$个子集$X_1,X_2,\cdots,X_n$，将$X$中至少属于其中$m$个集合的元素归入一个集合$\mathfrak{U}_m(X_1,X_2,\cdots,X_n)$，此集合的势具有如下表达式
$$\left|\mathfrak{U}_m(X_1,X_2,\cdots,X_n)\right|=\sum\limits_{k=m}^n(-1)^{k-m}\left(\begin{array}&k-1\\m-1\end{array}\right)\mathfrak{S}_k$$
$\nabla$证
$$当m=1时，该式即为并集容斥恒等式\\\\ \quad\\\\ 对于一般情况，采用与上个证明同样的记号\chi_k(x)与方法，只需证明下式即可\\\\ \quad\\\\ \chi_{\mathfrak{U}_m(X_1,X_2,\cdots,X_n)}(x)=\sum\limits_{k=m}^n(-1)^{k-m}\left(\begin{array}&k-1\\\\m-1\end{array}\right)\chi_k(x)\\\\ \quad\\\\ 若x\notin \mathfrak{U}_m(X_1,X_2,\cdots,X_n)，即包含x的X_i个数小于m，则有\\\\ \quad\\\\ \chi_{\mathfrak{U}_m(X_1,X_2,\cdots,X_n)}(x)=0=\sum\limits_{k=m}^n(-1)^{k-m}\left(\begin{array}&k-1\\\\m-1\end{array}\right)\chi_k(x)\\\\ \quad\\\\ 若x\in \mathfrak{U}_m(X_1,X_2,\cdots,X_n)，不妨设x只属于其中s(m\leq s\leq n)个集合，则有\\\\ \quad\\\\ \chi_{\mathfrak{U}_m(X_1,X_2,\cdots,X_n)}(x)=1\\\\ \quad\\\\ \begin{aligned}\sum\limits_{k=m}^n(-1)^{k-m}\left(\begin{array}&k-1\\\\m-1\end{array}\right)\chi_k(x)&=\sum\limits_{k=m}^n(-1)^{k-m}\left(\begin{array}&k-1\\\\m-1\end{array}\right)\left(\begin{array}&s\\\\k\end{array}\right)\\\\ &=\sum\limits_{i=0}^{s-m}(-1)^{i}C((m,i))\left(\begin{array}&m+(s-m)\\\\(s-m)-i\end{array}\right)\\\\ &=1 \end{aligned}\\\\ \quad\\\\ 于是\chi_{\mathfrak{U}_m(X_1,X_2,\cdots,X_n)}(x)=\sum\limits_{k=m}^n(-1)^{k-m}\left(\begin{array}&k-1\\\\m-1\end{array}\right)\chi_k(x)恒成立，即需证等式成立 $$
$\quad\\$
交集容斥原理
$\quad\\$
由德摩根定律可以直接得到如下等式
$$\left|\bigcap\limits_{i=1}^nX_{i}^c\right|=|X|-\sum\limits_{k=1}^n(-1)^{k-1}\mathfrak{S}_k$$
$\quad\\$
包含前$n$个正整数的$I_q$的$k$序列个数
$\quad\\$
令$k,n,q\in \mathbb{N}$且$1\leq n\leq q$，则包含前$n$个正整数的$I_q$的$k$序列个数或前$n$个集合非空的$I_k$的$q$分享个数为
$$\sum\limits_{i=0}^n(-1)^i\left(\begin{array}&n\\i\end{array}\right)(q-i)^k$$
$$当k=0时，符合条件的序列个数为0\\\\ \quad\\\\ 又\sum\limits_{i=0}^n(-1)^i\left(\begin{array}&n\\\\i\end{array}\right)(q-i)^k=\sum\limits_{i=0}^n(-1)^i\left(\begin{array}&n\\\\i\end{array}\right)=0，满足等式 $$