组合问题

n个人排成一排，选k个人，使他们两两不相邻，求方案数。

1⩽x1⩽x2−2⩽x3−4⋯⩽xk−2(k−1)⩽n−2(k−1)1\leqslant x_1\leqslant x_2-2\leqslant x_3-4 \dots\leqslant x_k -2(k-1)\leqslant n-2(k-1)

考虑转化为

1⩽y1⩽y2−1⩽y3−2⋯⩽yk−(k−1)1\leqslant y_1 \leqslant y_2-1\leqslant y_3-2 \dots \leqslant y_k-(k-1)

显然

yi=xi−(i−1)y_i=x_i-(i-1)

xk−2(k−1)⩽n−2(k−1)x_k -2(k-1)\leqslant n-2(k-1)

yk+(k−1)−2(k−1)⩽n−2(k−1)y_k+(k-1)-2(k-1)\leqslant n-2(k-1)

1⩽y1⩽y2−1⩽y3−2⋯⩽yk−(k−1)⩽n−2(k+1)1\leqslant y_1 \leqslant y_2-1\leqslant y_3-2 \dots \leqslant y_k-(k-1) \leqslant n-2(k+1)

$1\leqslant y_1<y_2<y_3 \dots < y_k\leqslant n-k+1 $

$ ans = C_{n-k+1}^{k}$

根据球是否本质 相同（00 否，11 是），盒子是否本质 相同（00 否，11 是 ），是否必须将盒子填满（00 不需要，11 必须），共 88 种情况，显然，每种情况恰好对应一个 0101 三元组 (x,y,z)(x,y,z)，下文会用类似的三元组来表示问题描述。

下文中，我们默认有 nn 个球，mm 个盒子，0<m≤n0<m\leq n，n,mn,m 均为整数。

八重计数法求法

Part1

  • (0,0,0)(0,0,0)，即球本质不同，盒子本质不同，不必填满。

    对于每一种球考虑，显然每一个球可以放在任意一个盒子中，有 mm 种方案，根据乘法原理，答案为 mnm^n。

  • (0,0,1)(0,0,1)，与上一问的区别仅在于 盒子必须填满。

    一个错误想法：先任选 mm 个球，把他们填到盒子中，转化成问题 (0,0,0)(0,0,0)，但这样是错的，因为球本质不同，盒子也本质不同。

    先补集转化，可以求至少一个盒子不满的方案数，再容斥，至少一个盒子不满的方案数即为 ∑k=1m(−1)k+1(mk)(m−k)n\sum\limits_{k=1}^m(-1)^{k+1}\tbinom{m}{k}(m-k)^n，再用总方案数 mnm^n 减掉即可，总式子可以写作∑k=0m(−1)k(mk)(m−k)n\sum\limits_{k=0}^m(-1)^{k}\tbinom{m}{k}(m-k)^n。

    当然，也可以写成二项式反演形式，也是容易证明的。

  • (0,1,1)(0,1,1)，与上一问的区别仅在于 盒子本质相同。

    那么记上一问答案为 ss，这一问答案就是 sm!\dfrac{s}{m!}，即 $ \dfrac{1}{m!}\sum\limits_{k=0}m(-1){k}\tbinom{m}{k}(m-k)^n$。

    上式也就是著名的第二类斯特林数，记做 S(n,m)S(n,m)。

    S(n,m)=S(n−1,m−1)+mS(n−1,m)S(n,m)=S(n-1,m-1)+mS(n-1,m)

    第 $ m$ 个放入第 nn 个新盒子 第 mm 个放入非空的盒子

    10个不同的球，放3个不同大盒子（不允许空）

    10=1+1+8=1+2+7=1+3+6=1+4+5=2+2+6=2+3+5=2+4+4=3+3+410=1+1+8=1+2+7=1+3+6=1+4+5=2+2+6=2+3+5=2+4+4=3+3+4

    ans=C101∗C912!+C101∗C92+…ans=\frac{C_{10}^{1}*C_{9}^1}{2!}+ C_{10}^{1}*C_{9}^{2}+\dots

  • (0,1,0)(0,1,0)，与上一问的区别仅在于 盒子不必填满。

    那么枚举几个盒子不满（假设 kk 个），就转化成了上一问，因为盒子本质相同，所以系数是 11，而不是组合数，这一问答案即为 ∑k=0m−1S(n,m−k)\sum\limits_{k=0}^{m-1} S(n,m-k)。

Part2

  • (1,0,0)(1,0,0)，即球本质相同，盒子本质不同，不必填满。

    经典插板法，加 mm 个球，现在共有 n+m−1n+m-1 空格，随意挑取 m−1m-1 个球作为板子，那么每一种挑选方案都对应一种球放入盒中的方案，故方案数为 (n+m−1m−1)\tbinom{n+m-1}{m-1}。

  • (1,0,1)(1,0,1)，与上一问的区别仅在于 盒子必须填满。

    与上一问类似，仍然插板，但这次是插 n−1n-1 个板子，在其中选 m−1m-1 个（这样才保证非空），故方案数 (n−1m−1)\tbinom{n-1}{m-1}。

Part3

  • (1,1,0)(1,1,0)，即球本质相同，盒子本质相同，不必填满。

    只会使用 dpdp 来解决，可以设 dp(i,j)dp(i,j) 为目前使用了 ii 个球，填了（可以不满）jj 个盒子的方案数，那么有转移方程 dp(i,j)=dp(i,j−1)+dp(i−j,j)dp(i,j)=dp(i,j-1)+dp(i-j,j) （分类讨论 jj 个盒子中是否有空盒子）。

  • (1,1,1)(1,1,1)，与上一问的区别仅在于 盒子必须填满。

    那么我们先每个盒子里都放一个球，答案就是 dp(n−m,m)dp(n-m,m)（dp 是上一问求出的数组）。

    整数无序分拆

至此，88 情况全部讨论完。

参考资料：