二项式反演与错排问题
常见简单组合恒等式:
-
\(C_n^m=C_n^{n-m}\)
-
\(C_n^m=C_n^{m-1}+C_{n-1}^{m-1}\)
-
\(\sum_{i=0}^{n}C_n^i=2^i\)
-
\(\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^j\sum_{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\)
,显然
\(k\in[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}\\ \]
同样可以直接线性的递推出答案。
转载于:https://www.cnblogs.com/Bhllx/p/11562988.html