二项式反演与错排问题

二项式反演与错排问题

常见简单组合恒等式：

1. (C_n^m=C_n^{n-m})

2. (C_n^m=C_n^{m-1}+C_{n-1}^{m-1})

3. (sum_{i=0}^{n}C_n^i=2^i)

4. (sum_{i=0}^{n}(-1)^i*C_n^i=[n=0])

3.4.证明：由二项式定理易证。

令(x=1,y=1)，可得3式

令(x=1,y=-1)， 可得4式

二项式反演：

假设存在两个函数f，g。满足：

[f_n=sum_{i=0}^{n}C_n^i*g_i ]

那么考虑如何反求得(g_n)关于(f_n)的等式。

[g_n=sum_{i=0}^{n}[n-i=0]*C_n^i*g_i\ g_n=sum_{i=0}^{n}sum_{j=0}^{n-i}(-1)^j*C_{n-i}^j*C_n^i*g_i\ g_n=sum_{i=0}^{n}sum_{j=0}^{n-i}(-1)^j*C_{n}^j*C_{n-j}^i*g_i\ g_n=sum_{j=0}^{n}(-1)^j*C_n^jsum_{i=0}^{n-j}C_{n-j}^i*g_i\ g_n=sum_{i=0}^{n}(-1)^i*C_n^i*f_{n-i}=sum_{i=0}^{n}(-1)^{n-i}*C_n^i*f_{i} ]

所以得到二项式反演的结论：

[f_n=sum_{i=0}^{n}C_n^i*g_i\ g_n=sum_{i=0}^{n}(-1)^{n-i}*C_n^i*f_{i}\ ]

形式上真的很优美！

下面就用二项式反演来解决一个经典的问题！

错排问题

问题描述：

有(n)个人编号为(1, ..., n)，问这(n)个人站成一排全都站错位置的方案数。

上述站错的定义是：第(i)个人没有站在位置(i)上。

方法1： 递推

设(f_n)表示答案，假设现在考虑到了前(i)个人的方案，即(f_i)。

考虑第(i)个人站位情况：

显然第(i)个人的不能站在位置(i)，假设他站到了位置(k)，显然(kin[1,i-1])，那么继续考虑(k)的站位。

​ ①、(k)站到了位置i，那么剩下的(i-2)个人仍然构成一个原问题，方案数为(f_{i-2})。

​ ②、(k)没站到位置i，也即(k)不能站在位置(i)，那么剩下的(i-1)个人仍然构成一个原问题，方案数为(f_i-1)。

所以可以得到(f)的递推关系：

[f_1=0 , f_2=1\f_i=(i-1)*(f_{i-1}+f_{i-2}) i≥3 ]

方法2：二项式反演

设(f_n)表示(n)个人随便站位的方案数，(g_n)表示(n)个人的都站错的方案数。

容易得到：

[f_n=n!\ f_n=sum_{i=0}^nC_n^i*g_i ]

直接二项式反演可以得到：

[g_n=sum_{i=0}^{n}(-1)^{n-i}*C_n^i*f_{i}\ ]

同样可以直接线性的递推出答案。