美丽的项链经典容斥解法

这个也算是组合数学里面的一个经典容斥了，在组合数学第5版第六章第二节带重复的组合中的某个例题就讲到了这个问题的排容方法。
首先，对于该问题没有限制条件的版本:从无限集合$\{a_1\cdot \mathrm{\infty },a_2\cdot \mathrm{\infty },a_3\cdot \mathrm{\infty },\dots ,a_k\cdot \mathrm{\infty }\}\backslash \{a\_1\backslash cdot\backslash infty,a\_2\backslash cdot\backslash infty,a\_3\backslash cdot\backslash infty,\backslash dots,a\_k\backslash cdot\backslash infty\backslash \}$中选取n个对象的方案数,该问题可以转换成方程：

的解的数量。其中$x_1,x_2,\dots ,x_{k}x\_1,x\_2,\backslash dots,x\_k$的值就对应着选择元素$a_1,a_2,\dots ,a_{k}a\_1,a\_2,\backslash dots,a\_k$的数量，而这个方程的解的数量又可以转换成集合$\{1\cdot n,\ast \cdot k-1\}\backslash \{1\backslash cdot\; n,*\; \backslash cdot\; k-1\backslash \}$的排列的数量，即用k-1个*号将n个1划分成k份。又由于*和1都没有区别。所以该排列的数量就是

即从n+k-1个位置中选k-1个位置给*号的方案数。
已知在无限制的情况下选取的的方法之后现在就可以讨论有下限的情况了，即对于类型$a_{i}a\_i$的元素，至少要选$b_{i}b\_i$个，这种情况下我依旧可以采用如上的转换，只不过这里设$y_i=x_i-b_{i}y\_i=x\_i-b\_i$,这样对于$y_{i}y\_i$的求解便没有限制了，于是得到方程

利用如上的隔板法得到该问题的方案数为

这样便解决了下界的限制，然后就是上界，对于上界目前我并不知道直接求解的方式，但可以利用容斥原理的经典容斥来解。
什么是经典的容斥呢，给出如下问题有3个相互之间都有交集的集合$A_1,A_2,A_{3}A\_1,A\_2,A\_3$,已知$\mathrm{\mid }{A}_1\mathrm{\mid }=30,\mathrm{\mid }{A}_2\mathrm{\mid }=50,\mathrm{\mid }{A}_3\mathrm{\mid }=40,\mathrm{\mid }{A}_1\bigcap A_2\mathrm{\mid }=20,\mathrm{\mid }{A}_2\bigcap A_3\mathrm{\mid }=10,\mathrm{\mid }{A}_1\bigcap A_3\mathrm{\mid }=10,\mathrm{\mid }{A}_1\bigcap A_2\bigcap A_3\mathrm{\mid }=5|A\_1|\; =\; 30,|A\_2|\; =\; 50,|A\_3|=40,|A\_1\backslash bigcap\; A\_2|=20,|A\_2\backslash bigcap\; A\_3|=10,|A\_1\backslash bigcap\; A\_3|=10,|A\_1\backslash bigcap\; A\_2\backslash bigcap\; A\_3|=5$，问你$A_1\bigcup A_2\bigcup A_3=?A\_1\backslash bigcup\; A\_2\backslash bigcup\; A\_3\; =\; ?$.答案如下：

接下来来看看本题的限制条件已知无限集合$\{a_1\cdot \mathrm{\infty },a_2\cdot \mathrm{\infty },a_3\cdot \mathrm{\infty },\dots ,a_k\cdot \mathrm{\infty }\}\backslash \{a\_1\backslash cdot\backslash infty,a\_2\backslash cdot\backslash infty,a\_3\backslash cdot\backslash infty,\backslash dots,a\_k\backslash cdot\backslash infty\backslash \}$，我们要从中选取n个元素，设这些元素的选取个数分别如下$x_1,x_2,\dots x_{k}x\_1,x\_2,\backslash dots\; x\_k$，并且，我们规定$\mathrm{\forall }{x}_i,l_i\le x_i\le r_i\backslash forall\{x\_i\},l\_i\backslash leq\; x\_i\backslash leq\; r\_i$,在这里我们可以设$P_i\mathrm{为}{y}_i\ge r_i+1P\_i\; 为y\_i\; \backslash geq\; r\_i\; +\; 1$的性质，设$A_i\mathrm{表}\mathrm{示}\mathrm{满}\mathrm{足}\mathrm{性}\mathrm{质}{P}_i\mathrm{的}\mathrm{解}\mathrm{组}\mathrm{成}\mathrm{的}\mathrm{子}\mathrm{集}A\_i表示满足性质P\_i的解组成的子集$。并设全集$\bigcup \backslash bigcup$为满足$\mathrm{性}\mathrm{质}{x}_i\ge l_i\mathrm{的}\mathrm{解}\mathrm{的}\mathrm{集}\mathrm{合}性质x\_i\backslash geq\; l\_i的解的集合$，于是原问题的解变成了计算集合${\bigcap }_{i=1}^k\overline{A_i}\backslash bigcap^\{k\}\_\{i=1\}\backslash overline\{A\_i\}$的大小，也就是$\mathrm{\mid }\bigcup \mathrm{\mid }-\mathrm{\mid }{\bigcup }_{i=1}^k{A}_i\mathrm{\mid }|\backslash bigcup|\; -|\{\backslash bigcup^\{k\}\_\{i=1\}A\_i\}|$。这里便将所有计算都变成了只有下界的计算，接下来便是枚举性质$P_{i}P\_i$的选取方案来求$A_1\bigcup A_2\bigcup A_3\bigcup \cdots \bigcup A_{k}A\_1\backslash bigcup\; A\_2\backslash bigcup\; A\_3\backslash bigcup\; \backslash dots\; \backslash bigcup\; A\_k$​的大小了，这里可以采用2进制状态压缩来枚举，因为对于每一个子集的每一个元素，都只有两种状态，具备性质$P_i(y_i\ge r_i+1)P\_i(y\_i\backslash geq\; r\_i+1)$或者$\overline{P_i}(y_i\ge l_i)\backslash overline\{P\_i\}(y\_i\backslash geq\; l\_i)$。同时二进制中1的个数代表具备性质$P_{i}P\_i$的子集的个数决定了该方案的符号。