OI教程之组合数学

\author{张若天}
\institute{清华大学}
\date{\today}

附属于/oi

推荐网站projecteuler.net

一些例子

  • 从5名男士,6名女士,2名男孩与4名女孩中选择一男一女一男孩一女孩的方案数为 240;选取一个人的方案数为 17。
  • 使用数字0-9每个恰一次共能产生3628800个排列,其中有 3265920 个首位不为0。
  • 若有理数m/n是无限小数,则必然是无限循环小数。
  • 10000以内不能被4,5,6中任意一个数整除的自然数有5334个。
  • 字母a-f按顺序入栈,但随时可以出栈,形成的出栈序列有132种。
  • 将2*2的网格黑白染色,旋转不同构的染色方案有6种。

基础概念

  • 加法原理
  • 乘法原理
  • 鸽笼原理(抽屉原理)

排列组合

排列: n个元素的集合,写成一个序列的方式有$A(n)=n!$或$P(n)=n!$种。
乘法原理应用。$0! = 1$

组合:一个大小为n的集合,选出m个元素的方案数。$C(n,m)$
也记作${n \choose m}$,其中${n \choose m } = \frac{n!}{m!(n-m)!}$。

圆(环)排列

$$n!/n = (n-1)!$$

错位排列

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

多重集的全排列

多重集:元素可以重复的集合
$$\frac{n!}{n_1 ! n_2 ! \ldots}$$

隔板法

考虑n相同的球,放到m个不同的盒子里方案数。

  • 每个盒子至少有一个球
  • 盒子可以为空
  • 每个盒子至少两个球

捆绑法

BZOJ 2729
n名男生,m名女生,2名老师排成一行,老师和老师不能相邻,女生和女生不能相邻。
老师可以相邻数量 - 把两个老师捆绑起来的数量。

二项式定理

$$(a+b)^n = \sum_{i=0}^{n}{C(n,i)a^i b^{n-i} } $$
练习: NOIP2011 d2t1

Catalan数

1,1,2,5,14,42,132…
$C_n = \frac{ C(2n , n) }{n+1} = {2n \choose n} - {2n \choose n-1}$
$C_{n+1} = \sum_{i=0}^{n}{C_i C_{n-i} }$

例子:

  • 有n个+1,n个-1,每个前缀和都>=0的方案数。
  • n个左括号,n个右括号,合法的括号序列数。
  • n个节点构成的二叉树数量。
  • 进栈次序是1,2,3,…,n,出栈排列数。
  • 正n+1边形的三角剖分数量。

组合数的计算

求C(n,m) mod p,其中:

  • $n,m \le 10^3, p \le 10^9$
  • $n,m \le 10^6, p \le 10^9$
  • $n,m \le 10^{18}, p \le 10^3 $且p为素数
  • $n,m \le 10^9, p \le 10^5$

  • $n,m \le 10^3, p \le 10^9$
    递推 C(n,m) = C(n-1,m)+C(n-1,m-1)

  • $n,m \le 10^6, p \le 10^9$
    ${n \choose m} = \frac{n!}{m!(n-m)!}$
    除法?逆元
    逆元不存在? 将p分解,单独考虑每个$pi^{ai}$
    例题: 求${n \choose m}$后9位。

  • $n,m \le 10^{18}, p \le 10^3 $
    n,m很大,p很小
    Lucas定理: ${n \choose m} = {n\mod{p} \choose m\mod{p} } {n/p \choose m/p} \mod{p}$
    练习:BZOJ1951 古代猪文

  • $n,m \le 10^9, p \le 10^5$
    p小了些,n,m还是很大。
    review之前做法。
    递归做除法?

例题:tyvj 1298 分苹果

n个有区别的苹果,分到3个无区别的袋子中的方案数。
$\frac{3^{n-1}+1}{2}$
$\frac{3^{n}-3}{6}+1$

斯特林数

这个稍作了解即可。

  • 第二类斯特林数
    $S_2(n,k)$
    n个数的集合的划分为k个非空集合方法的数目。(n个不同小球放到m个相同的盒子,每个盒子至少放一个球的种数)
    $S_2(3,2) = 3$,{ {a}, {b, c} }, { {b}, {a, c} }, { {c}, {a, b} }
    递推式:
    $S_2(n,k) = k S_2(n-1,k) + S_2(n-1,k-1)$
    把n个不同的小球分到k个可区分的盒子里且没有空盒子的划分个数? k! $S_2(n,k)$

  • 第一类斯特林数
    $S_1(n,k)$
    将n个不同元素排成k个非空环排列的方法数。
    $S_1(n,k) = (n-1) S_1(n-1,k) + S_1(n-1,k-1)$

划分数(整数划分)

给两个整数n和k。

Q:

  • 将n划分成若干正整数之和的划分数
  • 将n划分成k个正整数之和的划分数
  • 将n划分成最大数不超过k的划分数
  • 将n划分成若干奇正整数之和的划分数
  • 将n划分成若干不同整数之和的划分数

A:

  • 将n划分成若干正整数之和的划分数 $\sum_{i=1}^{n}{P(n,i)}$
  • 将n划分成k个正整数之和的划分数 $P(n,k)$
  • 将n划分成最大数不超过k的划分数 $\sum_{i=1}^{k}{P(n,i)}$
  • 将n划分成若干奇正整数之和的划分数
  • 将n划分成若干不同整数之和的划分数
  • 其中,$P(i,j) = P(i-1,j-1)+P(i-j,j)$
    练习:HEOI2014平衡

Burnside, Polya计数

需要了解一些群论。
群:一堆元素,一个运算,满足封闭性,结合律,幺元存在唯一,逆元存在唯一。
加法群,置换群为例。

Burnside引理

G为X的置换群,C(p)为X中满足在p作用下着色不变的着色集大小,
$C(p)$
$$ l = \frac{1}{|G|}\sum_{i=1}^{|G|}(C(p_i))$$
是不是很神奇.. 要知详情,可以看《组合数学》一书中的证明,应用了“算两遍”的技巧。

Polya定理

Polya定理为计算C(p)提供了一种方法,$p’$表示置换p的循环个数。
Polya定理告诉我们$C(p) = k^{p’}$。 (一种k种颜色)

例子

  • 将2*2的网格黑白染色,旋转不同构的染色方案有6种。
  • 有多少种用两种颜⾊色给正方形四个点染⾊的染⾊⽅案(通过旋转和翻转相同的算同⼀一种)
  • 3种颜色,n=6,本质有多少种项链。
    练习题: POJ 2409, 1286, 2154, 2888/ BZOJ 1004

生成函数

泰勒展开

泰勒展开: (在某个点附近)把一个函数展开成一个无限的多项式。
我们会的泰勒展开,等比求和。
$\sum_{i=0}^{\infty}{x^i} = \frac{1}{1-x} $
收敛?暂时不关心。

广义牛顿二项式定理

$(x+y)^{n} = \sum_{k=0}^{\infty} C(n,k) x^{n-k} y^k$
其中$C(n,k) = \Pi_{i=1}^{k}{(n-i+1)/i}$。
其中n对于分数,负数都对。

形式幂级数

对于一个序列$a_i$,可以定义一个多项式$A(x) = \sum_{i=0}^{\infty}{a_i x^i}$。
这个叫做原序列的生成函数,是一个形式幂级数。(因为我们不太关系收敛)

例子

1,1,1,$\ldots$ $\frac{1}{1-x}$
1,0,0,$\ldots$, 1,0,$\ldots$ $\frac{1}{1-x^m}$
1,2,3,$\ldots$ $\frac{1}{(1-x)^2}$
1,2,4,8,$\ldots$ $\frac{1}{1-2x}$
C(n,0),C(n,1),C(n,2),$\dots$ $(1+x)^n$

生成函数的运算

生成函数整体可以做多项式运算。(无论用封闭形式还是用多项式形式)
生成函数的乘法相当于做两个两个集合的组合。
微分、积分:形式推导。

解递推式(比如斐波那契)
练习:BZOJ 3028。

例子: Catalan

$$D(x)=\sum_{i=0}^{\infty}{d_ix^i} $$
$$d_n = \sum_{1 \le k \le n}{d_{k-1}d_{n-k} } $$
Then, $$D(x)=\sum_{i=0}^{\infty}{(\sum_{k=0}^{i-1}{d_kd_{i-k-1} }) x^i} $$
$$(D(x))^2=\sum_{i=0}^{\infty}{(\sum_{k=0}^{i}{d_kd_{i-k} })x^i}$$
Therefore, $$D(x) = x(D(x))^2+d_0 $$ $$D(x) = x(D(x))^2+1 $$
Then, $$D(x) = \frac{1 \pm \sqrt{1-4x} }{2x} $$
$D(0) = 1$, so $D(x) = \frac{1 - \sqrt{1-4x} }{2x} $.

D(x) = $\frac{1 - \sqrt{1-4x} }{2x}$
= $\frac{1}{2x}(1-(1-4x)^{\frac{1}{2} })$
= $\frac{1}{2x}(1-\sum_{i=0}^{\infty}{ {\frac{1}{2} \choose i}(-4x)^i})$
$d_i$ = $-\frac{1}{2} {\frac{1}{2} \choose i+1}(-4)^{i+1}$
= $-\frac{1}{2} \frac{1}{2} (\frac{1}{2}-1) (\frac{1}{2} -2) \ldots (\frac{1}{2}-i) (-4)^{i+1} /(i+1)!$
= $1 (1-2) (1-4) ( 1-6) \ldots ( 1-2i) (-2)^i/(i+1)!$
= $(-1) (-3) (-5) \ldots(-2i+1) (-2)^i/(i+1)!$
= $(-1) (-3) (-5) \ldots(-2i+1) (-2)^i/(i+1)!$
= $1 \times 3 \times 5 \times (2i-1) 2^i/(i+1)!$
= $\frac{(2i)!}{(i+1)!i!} $
= $\frac{(2i)!(i+1-i)}{(i+1)!i!}$
= $\frac{(2i)!(i+1)}{(i+1)!i!} -\frac{(2i)!(i)}{(i+1)!i!}$
= $\frac{(2i)!}{i!i!} -\frac{(2i)!}{(i+1)!(i-1)!}$
= ${2i \choose i} - {2i \choose i+1}$

例题: number

求这样的n位数个数:数字的各个数字都是奇数,而且1和3必须出现且出现偶数次。

递推?考虑n位数的结尾。

令$a_n$ 为这样的n位数,每个数的各个数字都是奇数,而且1和3出现偶数次。
令$b_n$ 为这样的n位数,每个数的各个数字都是奇数,1出现奇数次,3出现偶数次。(由对称性,也可表示3出现奇数次,1出现偶数次)
令$c_n$ 为这样的n位数,每个数字的各个数字都是奇数,1和3都出现奇数次。

$$a_n = 3 a_{n-1} + 2 b_{n-1} $$
$$b_n = 3 b_{n-1} + c_{n-1} + a_{n-1}$$
$$c_n = 3 c_{n-1} + 2 b_{n-1} $$

加速递推

  • 矩阵乘法
  • 求解递推式(特征值、生成函数)

等等,上面式子不对。还需要考虑1和3没出现的情况。

现在需要减去1和3没有同时出现的,需要减去1没出现、3出现偶数次,减去3没出现、1出现偶数次(由对称性与前一项相等),加上1没出现、3没出现的数量。
1没出现、3出现偶数次(3没出现、1出现偶数次)的数量为$ 2^{n-1} + 2 \times 4^{n-1} $。
1没出现、3没出现的数量为$ 3^n $。

直接使用指数型生成函数

$$(e^x)^3\left(\frac{e^x+e^{-x} }{2}-1\right)^2 $$

指数型生成函数

对于序列$a_i$,定义生成函数$\sum_{i=0}^{\infty}{\frac{a_i}{i!} x^i}$。
这样1,1,1,1,$\ldots$ 对应 $e^x$。
表示偶数?
表示3的倍数?(x)
生成函数的乘法表示了两个集合的排列。(why?

推荐

  • 图书:《具体数学》
  • 图书:《组合数学》 Richard
  • 网站: http://oeis.org

任何形式的使用、转载请注明出处!

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框