「OI之路」03数学-7组合数学

组合数学

组合数

  1. 除n=0,奇数和偶数项之和相等,证明:$\sum_{i=0}^n(-1)^iC_n^i=[n=0]$,把奇数i移到等式右边即可;也可以考虑组合意义,想要某个奇偶性,前面任选最后一个看情况行事,即$2^{n-1}$

  2. $\sum_{i=j}^n C_i^j=C_{n+1}^{j+1}(也可写成\sum_{i=0}^r C_{m+i}^m=C_{m+r+1}^r)$,证明可以考虑组合意义:表格路径计数

  3. $\sum_{i=a}^n C_i^a C_{n-i}^b = C_{n+1}^{a+b+1}$,证明:组合意义,有n+1个位置a+b+1个球,枚举第a+1个球在第i+1个格子

  4. $C_n^i C_i^j=C_n^j C_{n-j}^{i-j}$,证明:组合意义

  5. 范德蒙德卷积: $\sum_{i=0}^k C_n^i C_m^{k-i} = C_{n+m}^k$ 证明:组合意义考虑n个红球和m个蓝球;
    可以用来处理$\sum_{i=0}^n (C_n^i)^2=\sum_{i=0}^n C_n^iC_n^{n-i}=C_{2n}^n$

  6. $\sum_{i=0}^n i*C_n^i=\sum_{i=1}^n n*C_{n-1}^{i-1}=n2^{n-1}$,这个技巧非常常用,例如里面还有别的东西的时候

  7. $\sum_{i=1}^n \frac{(-1)^{i-1}}{i} C_n^i=\sum_{i=1}^n \frac{1}{i}$,不知道咋证明,不过看这里是对的,不知道有没有用

「Arc102E」Stop. Otherwise「SHOI2017」组合数问题

多重集

也就是允许元素重复的广义集合,表示为$S={a_1 \cdot n_1,a_2 \cdot n_2,…a_k \cdot n_k}$,其中a表示元素

全排列=$\frac{n!}{n_1! \times n_2! … \times n_k!}$,也就是取消同种元素间的顺序关系

组合:
设选r个,先考虑较为特殊的$r \leq n_i (\forall i \in [1,k])$,例题:Counting Swaps
然后我们就能直接把问题转化为求 $S={r \cdot 0,(k-1) \cdot 1}$ 的全排列,所以得到 $\frac{ (r+k-1)! }{r! \times (k-1)!}=C_{r+k-1}^{r}$

那如果不是这样特殊的r个呢?对问题取补,$ans=C_{r-k+1}^{r}-非法数量$而非法数量,就是说存在一个i,取的数量达到了$n_i+1$

那么我们枚举出每个数的非法情况,然后每个非法的数字,都先定向删除$n_i+1$个,然后照常取「$r-已经删除的数量$」个

因为状态的重复,容斥,如果非法数量num是奇数,就减去,偶数就补回去;具体实现可以枚举二进制数来搞

例题:CF451E Devu and Flowers

二项式定理

$$
(a+b)^n=
\sum_{i=0}^{\infty} C_n^i \times a^i \times b^{n-i}
$$
深入运用

当n是实数,称之为牛顿广义二项式定理,此时要求 $|a|<|b|$,其中组合数$C_{x}^y,y \in N=x^{\underline y}/{y!}$。显然这个广义是兼容狭义的

Catalan数与拓展

组合意义:有多少个「1和-1都是n个」的序列满足「任意前缀$\ge0$」、不同形态二叉树

$Cat_n=C_{2n}^n-C_{2n}^{n-1}=\frac{C_{2n}^n}{n+1}=\sum Cat_a \times Cat_{n-a-1}$

左边推中间下面讲,右边推过去我只会生成函数搞,并不会怎么组合意义(本身意义为枚举第一个左括号所在括号包括了多少对括号)

Catalan数

首先总量是 $C_{2n}^n$ ,然后考虑对于每个非法方案,一定存在一个最小的m使得$[1]-[-1]<0$(其实一定是-1),将m后面部分符号反转,一定唯一对应一个$(n+1,n-1)$的序列,而且反过来考虑这个序列最小的m,你会发现它是个双射,所以非法方案总数就是$C_{n+n}^{n-1}$

拓展:n个1m个-1,求多少个方案满足存在一个最小x使得$[1]-[-1]\ge k$

即当前是$(x+k,x)+(n-x-k,m-x)$同样考虑翻转左边 $(x,x+k)+(n-x-k,m-x)=(n-k,m+k)$

和上面类似做翻转,也是个双射,故非法方案数为 $C_{n+m}^{m+k}$ (另需特判特殊情况)

这个拓展主要是做CF1204E Natasha, Sasha and the Prefix Sums收获的

斯特林数

Stirling数各种性质(不知道有没有用)

然后洛谷的4个板子都可以写一写

第一类Stirling数(斯特林轮换数)

组合意义:n个不同的人,放入m个圆排列(内部顺序不同为不同方案,但起点无区别),不能有空,$S_1(i,0)=[i=0]$

递推式可考虑n放入新的圆排列,或者放在前面n-1个人中某个的右边 $S_1(n,m)=S_1(n-1,m-1)+(n-1)S_1(n-1,m)$

另一种意义是$x^{\overline{n}} = \sum_{i=0}^{n} S_1(n,i) x^i$,因为平时下降幂较多所以也有$x^{\underline{n}} = \sum_{i=0}^{n} (-1)^{n-i} S_1(n,i) x^i$(显然等价,因为相当于n个括号中i次选了x,n-i次选了其他)

并不知道怎么简洁理解这两个问题等价

一个引理:$\sum_k S_1(n,k)C_k^m=S_1(n+1,m+1)$,在SRM686 CyclesNumber用过

求一行:用分治FFT求上升幂求系数,$T(n)=2T(n/2)+nlogn=nlog^2n$

然后存在一个log的做法,主要思路是 $T(n)=T(n/2)+nlogn=nlogn$ ,也就是通过倍增,只分治一边,那么我们的目标就是用$f_{2n}(n)=f_n(n)f_n(n+x)$ 中前者求出后者,code
$$
\begin{aligned}
F_n(x+n)&=\sum_{i=0}^{n}a_i (x+n)^i=\sum_{i=0}^{n}a_i\sum_{j=0}^i{i\choose j}n^{i-j}x^j=\sum_{j=0}^{n} ( b_j=\sum_{i=j}^{n} n^{i-j} {i \choose j} a_i ) x^j\\
A[i-j]&=\frac{n^{i-j}}{(i-j)!},B[n-i]=i!a_i,C[n-j]=j!b_j
\end{aligned}
$$

求一列:正所谓斯特林轮换数,考虑轮换,$S_1(?,m)的EGF为=\frac{1}{m!} (\sum_{i=1}^{\infty} (i-1)! \frac{x^i}{i!})^m,O(nlogn)$,注意要平移符合ln的定义域,code

第二类Stirling数(斯特林子集数)

n个不同的球,进入m个相同的盒子中,不可有空盒子的方案数
递推式可考虑n放入新排列,或者放在已有的盒子中,$S_2(n,m)=m S_2(n-1,m)+S_2(n-1,m-1)$
非递推式的话,考虑容斥即可,为了方便处理先假设m个盒子互不相同

求一行:考虑空盒子直接容斥$S_2(n,m)=\frac{1}{m!} \sum (-1)^k {m \choose k} (m-k)^n$
还有一种理解,也是枚举颜色数,发现是一个下降幂多项式,二项式反演,殊途同归
$$
x^n = \sum_{i=0}^{n} {n \brace i} x^{\underline{i}}=\sum_{i=0}^n {n \brace i} C_x^i i!,m!{n \brace m} = \sum_{i=0}^{m} (-1)^{m-i} {m \choose i} i^n
$$

前面两种理解都有各自的组合意义,不过可能后面那个组合数的比较常用

求一列:同理,其EGF=$(e^x-1)^m /m!$

例题

loj2058 「TJOI / HEOI2016」求和,把容斥的式子放进去就做完了,也可以推一下生成函数

$ans=\sum_{i=0}^{n}\sum_{j=0}^{i}S_2(i,j)2^j j!=\sum_{i=0}^nf(i)$

$f(n)=2\sum_{i=1}^nC_n^if(n-i),设EGF为F,F=1+2e^x*F,O(nlogn)$

bzoj2159 Crash的文明世界、HDU4625 JZPTREE,bzoj太麻烦HDU的code

$S(i)=\sum_{j=1}^ndis(i,j)^k,不好二项式定理考虑斯特林把它展开=\sum_{t=0}^kS_2(k,t)t!(\sum_{1}^n C_{dis}^t)$

然后利用组合数的递推式就可以$O(nk)$了

CF932E Team Work,组合数比次幂友善,把次幂展开,code

$\sum_{i=1}^nC_n^ii^k=\sum_{j=0}^kS_2(k,j)j! \sum_{i=j}^n C_n^iC_{n-j}^{i-j}=\sum_{j=0}^k S_2(k,j)P_n^j max(2^{n-j},1)$

错排问题

问题本身没啥,但有启发性思想

原问题

求有多少个n的排列,满足每个$a_i \neq i$

本质:两组各n个数配对,n个ban满足相互独立

直接容斥:不是本文重点,$D_n=\sum (-1)^i C_n^i (n-i)!=\sum (-1)^i \frac{n!}{i!}$

递推:设在$b_1=a(n-1种)$,若$b_a=1$,转化为$D_{n-2}$;

否则$b_a \ne 1$,此时这个新条件与其他条件独立,转化为$D_{n-1}$

故$D_n=(n-1)(D_{n-1}+D_{n-2})$

当然考虑1放哪里,或者考虑n,都是同构的

变例

luogu4931 情侣?给我烧了!(加强版),code

先转化一下题意,$ans_k=(C_n^kP_n^k)2^kg(n-k)$,g为变例错排数,注意到只和n与k的差有关,试图预处理

考虑$左1=a(2n种),右1=b(2n-2种)$,若$rev(a)与rev(b)$配对,转化为$g(n-2)$,有(n-1)个位置且可互换;否则要求$rev(a)不与rev(b)$配对,这是独立的条件,转化为$g(n-1)$;综上所述,$g(n)=(2n)(2n-2)(g(n-2)*2(n-1)+g(n-1))$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/5905.html
转载请注明出处,谢谢!