【OI之路】02数论算法-3组合数学

前半部分为自己的创作
后半部分为转载,因为并没有去理解

普通排列(在乎顺序)

全排列

n个人全部来排队,队长为n。第一个位置可以选n个,第二个位置可以选n-1个,以此类推得:
$$
P(n,n)=n\times (n-1)\times (n-2)……3\times 2\times 1=n! (规定0!=1)
$$

部分排列

n个人选m个来排队(m<=n)。第一个位置可以选n个,第二位置可以选n-1个,以此类推,第m个(最后一个)可以选(n-m+1)个,得:
$$
P(n,m)=n\times (n-1)\times (n-2)……(n-m+1)=\frac{n!}{(n-m)!}
$$

普通组合(不在乎顺序)

n个人m(m<=n)个出来,不排队,不在乎顺序C(n,m)。如果在乎排列那么就是P(n,m),如果不在乎那么就要除掉重复,那么重复了多少?同样选出的来的m个人,他们还要”全排”得到P(m,m),所以得:
$$
C(n,m)=\frac{P(n,m)}{P(m,m)}=\frac{n!}{m!(n-m)!}
$$
组合数的性质1:
$$
C(n,m)=C(n-1,m)+C(n-1,m-1)
$$
组合数的性质2: n&k==k 则c(n,k)为奇数,否则为偶数

组合数与11与杨辉三角与二项式定理(原创)

(做题碰到二项式定理,然后猜了一些,再上网验证)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
……
这是经典的杨辉三角(Pascal’s Triangle),哪怕是小学时也见过吧
然后我从初三学生的角度看看这玩意

特点:

  1. 对称
  2. 从1开始,在1结束
  3. 第i行第j个(从0开始)=$C(i,j)$
  4. 如果把空格隔开的数看作数字,成为一个无限进制数,则转化为10进制后,
    第i行=$11^{i-1}$
  5. 因为是组合数三角,所以也是二项式定理三角(据说这就是初衷)
    然后这些是我没想到的:
  6. 第i行数字和为$2^{i-1}$ 【这其实就是组合数的和,选和不选两种情况】
  7. $C(i,j)=C(i-1,j-1)+C(i-1,j)$

多重集

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

全排列

$\frac{n!}{n_1! \times n_2! … \times n_k!}$

组合

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

例题:Counting Swaps

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

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

因为状态的重复,联想一下小学的时候学的简单容斥,不难算出
如果非法数量num是奇数,就减去,偶数就补回去
具体实现可以枚举二进制数来搞

例题:CF451E Devu and Flowers

Catalan数

问题

有多少个01序列满足【任意前缀中,0的个数不少于1的个数】

通项公式

$Cat_n=\frac{C_{2n}^n}{n+1}$

性质

  1. $Cat_n=C_{2n}^n-C_{2n}^{n-1}$,可以由定义得出

应用

  1. 简单应用,例如【合法括号序列】、【出栈序列】

错排

问题

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

递推式

考虑元素1,找到2~n中的k,使$a_k=1$,k有n-1种取值
① $a_1=k$,此时相当于剩下n-2个元素,进行错排
② otherwise,此时相当于剩下n-1个元素,进行错排
所以$D_n=(n-1)(D_{n-1}+D_{n-2})$

通项公式

考虑容斥原理
首先,总排列数=$n!$
假设固定1个在正确位置上,有 $C_n^1$ 个选择,而其他人的排列为 $(n-1)!$ 个
但不难发现,此时2个的情况,会在1固定和2固定的时候计算两次,所以要补回来
补回来的话,3个的情况,会在12固定和23固定的时候计算两次,又要减回去……
大概意会一下……
按照这样的思路,不难得出通项公式
$D_n=\sum (-1)^i C_n^i (n-i)!=\sum (-1)^i \frac{n!}{i!}$


(下文不保证正确性,因为我也不会)

2.3.3其他排列与组合

(1)圆排列

n个人全部来围成一圈为Q(n,n),其中已经排好的一圈,从不同位置断开,又变成不同的队列。所以:
$$
Q(n,n)=\frac{P(n,n)}{n}=(n-1)!
$$
由此可知,部分圆排:
$$
Q(n,r)=\frac{P(n,r)}{r}=\frac{n!}{r\times (n-r)!}
$$

(2)重复排列(有限)

k种不一样的球,每种球的个数分别是a1,a2,…ak,
设n=a1+a2+…+ak,这n个球的全排列数,为
$$
\frac{n!}{a1!\times a2!\times …\times ak!}
$$

(3)重复组合(无限)

n种不一样的球,每种球的个数是无限的,从中选k个出来,
不用排列,是组合,为C(n+k-1,k)
证明:假设选出来的数(排好序)
$$
1<=b1<=b2<=b3……<=bk<=n
$$
这题的难点就是=号,现在去掉=号,所以有:
$$
1<=b1<b2+1<b3+2<b4+3……<bk+k-1<=n+k-1
$$
中间还是k个数!不过已经不是b系列,而是c系列假设c[i]:=b[i]+i-1,所以
$$
1<=c1<c2<c3<c4……<ck<=n+k-1
$$
所以问题就开始转换为无重复组合问题,即在n+k-1个元素中选中k个的组合数C(n+k-1,k)。

(4)不相邻排列

1~n这n个自然数中选k个,这k个数中任何两个数不相邻数的组合有C(n-k+1,k)证明和(3)相同。

(5) stirling数(子集划分)

性质:
① S(n,m)= m*S(n-1,m) + S(n-1,m-1)
② S(n,1)=1,S(n,0)=0, S(n,n)=1
例:将n个数(1,2,…,n)分成r个部分。每个部分至少一个数。将不同划分方法的总数记为S(n,r)。例如,S(4,2)=7,这7种不同的划分方法依次为 { (1) , (234) },{ (2) , (134) },{ (3) , (124)},{ (4) , (123) },{ (12) , (34) },{ (13) ,(24) },{ (14) ,(23) }。当n=6,r=3时,S(6,3)=?
题解:先固定一个数,对于其余的5个数考虑S(5,3)与S(5,2),再分这两种情况对原固定的数进行分析。最后得到:S(6,3)=90。

写得也不错的:
组合数学

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

哪怕是一杯奶茶,也将鼓励我继续创作!
0%