组合数学

概念

C_n^m=\frac{n!}{(n-m)!m!}=C_{n-1}^{m}+C_{n-1}^{m-1}
信息学竞赛没有证明!加法原理和乘法原理等就不说了
圆排列 \frac{n!}{n}=(n-1)!


错位排列 设f[i]i个数错位排序 (1 \leq i \leq n,a[i]\neq i)
证:情况1:插入第i个元素时,前i-1个已经错位排好,则选择其中任意一个与第i个互换一定满足要求,选择方法共i-1种,前i-1位错排f[i-1]种,记f[i-1]*(i-1)

情况2:插入第i个元素时,前i-1个中恰有一个元素a[j]使得a[j]=j,其他i-2个错位排好,则将ij交换,ji-2位中的插入共i-1种,前i-2位错排f[i-2]种,记f[i-2]*(i-1)
得证f[i]=(i-1)\times (f[i-2]+f[i-1])
Catalan数列 Catalan_n=C_{2n}^{n}-C_{2n}^{n+1}

基操

Question1

n把椅子的圆桌,坐m个人,为防止作弊,两人中间要隔着不小于k把椅子。问总安排方案数的答案模1e9+7
n,m\leq 10^6,k\leq1000

sol

首先m\times(k+1)\leq n,我们可以考虑固定第一个人的位置,这样固定的方案就有n种,首先我们现在每两个人中间放k把椅子,因此还剩下n-m\times(k+1)把椅子,由于剩下的椅子还要插在两个人中间,于是问题就转化成了一个经典模型,无标号小球放在有区别的盒子里,且盒子可为空,因此有C_{n-m\times k-1}^{m-1},固定第一个人的方法有n种,循环下来会有重复,所以要除以m,即Ans=\frac{C_{n-m\times k-1}^{m-1}\times n}{m} \mod(1e9+7)

Question2

给定n个不同的元素,取m个。若每个元素可以重复取,则有多少种取法?

sol

设第i个元素取了x_i次,则原问题相当于x_1+x_2+...+x_n=m的非负整数解的个数,即y_1+y_2+...+y_n=n+m(y_i=x_i+1)的正整数解的个数。用隔板法,即将n+m个1分为m组,每组至少一个,相当于在所有1n+m-1个空里插m-1个板子,因此总的情况数是C_{n+m-1}^{m}=\frac{(n+m-1)!}{m!(n-1)!}

Questions set

球放入盒子问题 这个写的也可以。

n个相同的球放入m个相同的盒子,无空盒,求方案数。

sol1

f[i][j]为前i个盒子放了j个球且允许空盒g[i][j]为前i个盒子放了j个球且不允许空盒,可以递推得f[i][j]=g[i][j]+f[i][j-1],g[i][j]=f[i-j][j]


n个相同的球放入m个相同的盒子,允许空盒,求方案数。

sol2

sol1


n个相同的球放入m个不同的盒子,无空盒,求方案数。

sol3

C_{n-1}^{m-1}


n个相同的球放入m个不同的盒子,允许空盒,求方案数。

sol4

C_{n+m-1}^{m-1}


n个不同的球放入m个相同的盒子,无空盒,求方案数。

sol5

第二类斯特林数的定义S(n,m)=\frac{\displaystyle\sum_{k=0}^{m}{(-1)^k\times C_{m}^{k} \times (m-k)^n}}{m!}
此外,另有递推式推导:假设要把n+1个元素分成m个集合则分析如下:
1.如果n个元素构成了m-1个集合,那么第n+1个元素单独构成一个集合。方案数S(n,m-1)
2.如果n个元素已经构成了m个集合,将第n+1个元素插入到任意一个集合。方案数 m\times S(n,m)
则有S(n+1,m)=S(n,m-1)+m\times S(n,m)


n个不同的球放入m个相同的盒子,允许空盒,求方案数。

sol6

S(n,m)求个前缀和就好了。


n个不同的球放入m个不同的盒子,无空盒,求方案数。

sol7
S(n,m)\times m!

n个不同的球放入m个不同的盒子,允许空盒,求方案数。

sol8

显然n^m


Question 3

从原点(0,0)走到(n,m),每次可以向右或向上走一步,要求任意时刻位置(x,y)必须满足x\leq y。求有多少种路径? n,m\leq 10^6

sol

裸卡特兰数的推广。参见开头定义。

 


二项式定理

(a+b)^n=\sum_{k=0}^nC_n^ka_kb^{n-k}

多重集的全排列和组合数

例如一个多重集S=\{n_1\times a_1,\cdots,n_k\times a_k\}是由n_1a_1,\cdots,n_ka_k组成的可重集合,则S的全排列数有\frac{n!}{n_1!n_2!\cdots n_k!}r\leq n_i(\forall i\in[1,k]),从S中取出r个元素组成一个多重集(不考虑顺序),产生的不同多重集的数量为C_{k+r-1}^{r}=C_{k+r-1}^{k-1}

容斥原理

考虑上面那个问题,若r\leq n,则有产生的不同多重集的数量为C_{k+r-1}^{k-1}-\sum_{i=1}^kC_{k+r-n_i-2}^{k-1}+\sum_{1\leq i<j\leq k}C_{k+r-n_i-n_j-3}^{k-1}-\cdots+(-1)^kC_{k+r-\sum_{i=1}^kn_i-(k+1)}^{k-1}

证明:不考虑n_i的限制,从\{\infty\times a_1,\cdots,\infty\times a_k\}出发考虑,即可采用上面的上面的方案,即C_{k+r-1}^{k-1}

S_i(1\leq i \leq k)表示至少包含n_i+1a_i的多重集。我们先从S中取出n_i+1a_i,然后再任选r-n_i-1个元素,即可构成S_i。与上面同理,可以构成的不同S_i的数量为C_{k+r-n_i-2}^{k-1}

进一步地,先从S中取出n_i+1a_in_j+1a_j,然后再任选r-n_i-n_j-2个元素,即可构成S_i\cap S_j,方法数为C_{k+r-n_i-n_j-3}^{k-1}

根据容斥原理,即可得到结论。

 

One thought on “组合数学

发表评论

电子邮件地址不会被公开。 必填项已用*标注