组合数学

第6章 容斥原理及应用

6.1 容斥原理

定义

计数函数: σx(A)
σx(A)={1,xA0,xA

定理和推论

设集合 Ai 是集合S中满足性质 Pi 的所有物体的子集, i=1,2,,m , 则

6.1.1

集合 S 不具有性质 P1,P2,,Pm 的物体的个数:

|A1...Am|=|S||Ai|+|AiAj||AiAjAk|+...+(1)m|A1A2...Am|
6.1.2

集合 S 至少具有性质 P1,P2,,Pm 之一的物体的个数:

|A1A2...Am|=|Ai||AiAj|+|AiAjAk|+...+(1)m+1|A1A2...Am|

其中,第一个和对 {1,2,,m} 的所有的 1 子集 {i} 进行, 第二个和对 {1,2,,m} 的所有的 2 集合 {i,j} 进行, 依此类推

特别情况

若:

α1=|A1|=|A2|==|Am|()α2=|A1A2|==|Am1Am|()α3=|A1A2A3|==|Am2Am1Am|()αk=|A1Ak|==|Amk+1Am|αm=|A1A2Am|

则,

A1...An=α0(m1)α1+(m2)α2(m3)α3+...+(1)k(mk)αk+...+(1)mαm

6.2 带重复的组合

多重集组合与方程整数解个数

6.2 带重复的组合
回顾一下2.5

多重集 T={n1×a1,n2×a2,,nk×ak}r 组合数等于方程

x1+x2++xk=r,0x1n1,0x2n2,,0xknk

的整数解的个数。

6.3 错位排列

定义

1.

X={1,2,,n} , 它的排列用 i1i2in 表示。错位排列是使得 i11,i22,,inn 的排列。用 Dn 表示错位排列个数

定理

6.3.1

n1

Dn=n!(111!+12!13!+...+(1)n1n!)

性质

错位排列的递推关系
1
Dn=(n1)(Dn2+Dn1),(n=3,4...)D2=1;D1=0
2
Dn=nDn1+(1)n

6.4 带有禁止位置的排列

定义

(1) 带有禁止位置的排列

X1,X2,,Xn{1,2,,n} 的子集 (可以为空集),用 P(X1,X2,,Xn) 表示 {1,2,,n} 的排列 i1i2in 的集合,使得: i1X1i2X2inXn

p(X1,X2,,Xn)=|P(X1,X2,,Xn)| ,表示 P(X1,X2,,Xn) 中排列的个数。

(2) 带禁止位置的“非攻击性车”

{1,2,,n} 的排列 i1i2in 对应于棋盘上以方格

(1,i1),(2,i2),,(n,in)

为坐标的n个车的位置

满足第 j 行的车不在 Xj 中的列, j=1,2,,n ,共有多少种放置非攻击型车的方法。

定理

6.4.1

n 个非攻击型不可区分的车放到带有禁止位置的 n×n 的棋盘中,放法总数等于:

n!r1(n1)!+r2(n2)!+(1)krk(nk)!++(1)nrn

所以 r1,r2,,rn 的计算依赖于具体的问题!

  • 任意两个车不在同一行或同一列
  • 所有的 k 个车放置在其禁止位置上的放置方法数, k=1,2,,n
  • rk 的计算不考虑剩下的 nk 个车的放置

6.5 另一个禁止位置问题

定义

相对禁止位置排列计数 Qn

Qn{1,2,,n} 的排列中没有 12,23,,(n1)n 这些 模式出现的排列的个数

定理

6.5.1

对于 n1

Qn=n!+Σk=1n1(1)k(n1k)(nk)!=n!(n11)(n1)!+(n12)(n2)!+...+(1)n1(n1n1)1!

例题

旋转木马问题

看ppt去

相对禁止 QN 与错位排列 Dn 的关系

Qn=Dn+Dn1

第7章 递推关系和生成函数

生成函数(也称母函数)核心思想:

  • 把离散数列和幂级数一一对应起来,

    把离散数列间的相互结合关系对应成为幂级数间的运算关系

  • 由幂级数形式来确定 离散数列 的构造

7.1 若干数列

定义

斐波那契数列

设有数列 f0,f1,f2,,fn, 。如果 f0=0,f1=1 , 且满足递推关系 fn=fn1+fn2n2
称该数列为斐波那契(Fibonacci)数列,这个数列的项称为斐波那契数

定理

7.1.1

斐波那契数 fn 满足公式

fn=15(1+52)n15(152)n,n0
7.1.2

沿 Pascal 三角形从左下到右上的对角线上的二项式系数和是斐波那契数, 即

fn=(n10)+(n21)+(n32)+...+(ntt1)

其中, t= m+12

性质

斐波那契数列
斐波那契数列的项的部分和
sn=f0+f1+f2+...+fn=fn+21
斐波那契数是偶数当且仅当n被3整除
斐波那契数能被3整除当且仅当n可被4整除
斐波那契数能被4整除当且仅当n可被6整除
Fibonacci数列与黄金分割数
limxfnfn+1=5120.618

7.2 生成函数

涉及一个整数参数 n 的某些计数问题的代数求解方法:生成函数(母函数)

*常见展开式

(1+x)n=Σk=0n(nk)xk(1x)n=Σk=0n(1)k(nk)xk

对满足 |x|<1 的任意 x ,有:

1(1+x)n=Σk=0(1)k(n+k1k)xk1(1x)n=Σk=0(n+k1k)xk

n=1 时,得:

11+x=Σk=0(1)kxk(|x|<1)11x=Σk=0xk(|x|<1)

x=ym ,得:

11+ym=Σk=0(1)kymk(|y|<1)11ym=Σk=0ymk(|y|<1)

生成函数的定义

h0,h1,,hn, 为一无穷数列, 其生成函数 g(x) 定义为:

g(x)=h0+h1x+h2x2++hnxn+=Σk=0hkxk

有限数列 h0,h1,,hn 可以看作是无限数列 h0,h1,,hn,0,...,0,...

适合多重集组合

生成函数——多重集组合

求生成函数

k 是正整数, hn 等于方程

e1+e2++ek=n

的非负整数解个数,

hn 为多重集 S={a1,a2,,ak}n 组合个数, ei 表示在一个 n 组合中 ai 出现的次数。

g(x)=Σn=0(n+k1n)xn=1(1x)k=(Σe1=0xe1)(Σe2=0xe2)...(Σek=0xek)(2)=Σe1+...+ek=n=0xe1xe2...xek

n 组合中 ai 的出现次数有约束时,将反映到 (2) 式的第 i 个因子中。

求通项

把生成函数向根本形式: Σk=0hkxk 化简

排列逆序

π 中的逆序的数目为 inv(π)

h(n,t) 表示 {1,2,,n} 的排列中有 t 个逆序的排列的数目,则:

  • 对于 0tn(n1)/2 ,有 h(n,t)1
  • t>n(n1)/2 ,有 h(n,t)=0

定理

7.2.1

n 是正整数,则数列 h(n,0),h(n,1),,h(n,n(n1)/2) 的生成函数为

gn(x)=1(1+x)(1+x+x2)(1+x++xn1)=Πj=1n(1xj)(1x)n(1)

7.3 指数生成函数

指数生成函数的定义

数列 h0,h1,h2,,hn, 的指数生成函数定义为

g(x)=h0+h1x+h2x22!+...+hnxnn!+...=Σk=0hkxkk!

P(n,k)

n 是正整数。确定下面数列的指数生成函数:

P(n,0),P(n,1),P(n,2),,P(n,n)

其中, P(n,k) 表示 n 元素集合的 k 排列的数目,即

P(n,k)=n!(nk)!
ex

求数列 1,1,1,,1, 的指数生成函数

g(x)=Σn=0xnn!=ex()

多重集排列

考虑由n个元素组成的多重集

S={n1a1,n2a2,,nkak}

其中 n=n1+n2++nk 。从中取 r 排列。

r=n ,则考虑 n 个元素的全排列,不同的排列数为

n!n1!n2!...nk!

r<n

由组合生成排列——即先选后全排列

有限重数

已知 S={n1a1,n2a2,n3a3}r 排列数 hrr=0,1,2,,n1+n2+n3

h0,h1,h2,...,hn1+n2+n3 的指数生成函数:

(1+x1!+x22!+...++xn1n1!)(1+x1!+x22!+...++xn2n2!)(1+x1!+x22!+...++xn3n3!)

展开后 xr 前的系数为:

e1+e2+e3=r0e1n1,0e2n2,0e3n3xe1xe2xe3e1!e2!e3!=(e1+e2+e3=r0e1n1,0e2n2,0e3n3r!e1!e2!e3!)xrr!

此处:

hr=(e1+e2+e3=r0e1n1,0e2n2,0e3n3r!e1!e2!e3!)

故指数生成函数为:

r=0n1+n2+n3(e1+e2+e3=r0e1n1,0e2n2,0e3n3r!e1!e2!e3!)xrr!

定理

7.3.1

S 是多重集 {n1a1,n2a2,,nkak} ,其中 n1,n2,,nk 是非负整数。设 hnSn 排列数,那么数列 h1,h2,,hk 的指数生成函数 g 为:

g=fn1(x)fn2(x)...fnk(x)

其中,对于 i=1,2,..,k ,有

fni(x)=1+x+x22!+...+xnini!
推广到无穷重数

S 是多重集 {a1,a2,,ak} 。设 hnSn 排列数,那么数列 h0,h1,h2,,hk 的指数生成函数 g 为:

g(x)=h0+h1x+h2x22!+...+hnxnn!+...=f(x)f(x)...f(x)(k)

其中:

f(x)=1+x+x22!+...+xnn!+...=ex

n 排列中 ai 的出现有约束时,将反映到第 i 个因子中

*常用展开式

ex=Σn=0xnn!=1+x+x22!+...+xnn!+...ex=Σn=0(1)nxnn!=1x+x22!+...+(1)nxnn!+...12(ex+ex)=1+x22!+x44!+...+x2n2n!+...12(exex)=x+x33!+x55!+...+x2n+1(2n+1)!+...

7.4 求解线性齐次递推关系

定义

线性齐次递推关系

h0,h1,h2,,hn, 是一个数列。若存在量 a1,a2,,ak(ak0) 和量 bn (每个量是常数或依赖于 n 的数)使得:

hn=a1hn1+a2hn2++ak1hnk+1+akhnk+bn(nk)

则称该数列满足 k 阶线性递推关系。
bn=0 ,则称该数列是 k 阶线性齐次递推关系。
a1,a2,,ak 都为常数,则称该数列是 k常系数线性递推关系。

解法

本节重点讨论 k常系数线性齐次递推关系

  • 特征方程法
  • 生成函数法

定理

7.4.1(特征方程法)

q 为一个非零数, 则 hn=qn 是常系数线性齐次递推关系

hn=a1hn1+a2hn2++akhnk(ak0,nk)(1)

的解当且仅当 q 是多项式方程(特征方程)

xka1xk1a2xk2ak1xak=0(2)

的一个根。(特征根)

若多项式方程 (2) 有 k个不同的根 q1,q2,,qk ,则

hn=c1q1n+c2q2n++ckqkn(3)

是下述意义下 (1) 的通解:任意给定初始值 h0,h1,,hk1 , 都存在 c1,c2,,ck 使得 (3) 式是满足 $ (1)$ 式和初始条件的唯一的数列。

7.4.2(通解)

q1,q2,...,qt 为常系数线性齐次递推关系:

hn=a1hn1+a2hn2++akhnk(ak0,nk)(1)

的特征方程的互异的根

如果 qi(1) 的特征方程的 si 重根,那么该递推关系的通解中对应于 qi 的部分为:

Hn(i)=c1qin+c2nqin+...+csinsi1qin

且该递推关系的通解为:

hn=Hn(1)+Hn(2)+...+Hn(t)
7.4.3

h0,h1,h2,,hn, 为满足 k 阶常系数线性齐次递推关系:

hn+c1hn1++ckhnk=0(ck0,nk)(1)

的数列, 则它的生成函数 g(x) 形如:

g(x)=p(x)/q(x)(2)

其中,
q(x) 是具有非零常数项的 k 次多项式,
p(x) 是小于 k 次的多项式。
反之, 给定这样的多项式 p(x)q(x) , 则存在序列 h0,h1,,hn, 满足 (1) 式的 k 阶常系数线性齐次递推关系, 其生成函数由 (2) 式给出.

方法

特征方程法

详见定理7.4.1、7.4.2

特征方程有重根

定理7.4.1不适用于特征方程有重根的情况

生成函数法

(1)利用递推关系求出序列的生成函数: p(x)q(x) ,其中, p(x)$$k 的多项式,而 q(x) 是常数项等于 1 的 k 阶多项式;
(2)用部分分式法,把 p(x)q(x) 表示为如下代数分式的和: c(1rx)t
(3)利用牛顿二项式展开 c(1rx)t ,并把所有项求和,得到生成函数的幂级数。

  • 如何得到生成函数:

    • 先设出生成函数的通项
    • 利用递推关系加减消除法到只剩初始项
      • 加减消除法的系数为递推关系的系数!!!
      • 最终是含 x 项系数尽量为 0
  • 牛顿二项式:

    • 如果 n 是正整数,而 r 是非零实数, |rx|<1 时,则有

    • (1rx)n=Σk=0(nk)(rx)k=Σk=0(1)k(nk)(rx)k=Σk=0(n+k1k)(rx)k

联系

设特征方程为 r(x) ,生成函数 g(x)=p(x)q(x)

设相应特征方程 r(x)=0 ,其中 q(x)=xkr(1x)

不想写了,详见PPT~~~

小结

利用特征方程求解常系数线性齐次递推关系:

  • 写出相应的特征方程
  • 求解特征方程
    • 如果没有重根,则直接给出通解(定理7.4.1)
    • 如果有重根,根据重根求出通解(定理7.4.2)
  • 将初始条件代入通解,得到满足初始条件的解

利用生成函数求解:使得 xj(jk) 前的系数为 0

7.5 非齐次递推关系

定义:

对于常系数线性递推关系

hn=a1hn1+a2hn2+...+akhnk+bn(ak0,nk)

bn0 ,则称该递推关系为常系数线性非齐次递推关系。

汉诺塔问题

递推关系
hn=2hn1+1(n1)h0=0h1=1h2=3
迭代求解

就嗯迭代

但是迭代完了一定要数学归纳法证明结果的正确性

通解

生成函数法

不一定可行,若 bn 为带 n 的多项式则可能出问题。

特征方程法

假设有非齐次递推关系

hn=a1hn1+a2hn2+...+akhnk+bn(1)

fn 是对应齐次递推关系

hn=hnbn=a1hn1+a2hn2+...+akhnk(2)

的通解, 而 cn 是原非齐次递推关系(1)的一个特解,
那么: hn=cfn+cn 是原非齐次递推关系(1)的通解。

小结
  1. 求对应的齐次递推关系的通解;
  2. 求该非齐次递推关系的一个特解;
  3. 将一般解和特解结合得到该非齐次递推关系的
    通解;
  4. 通过初始条件确定通解中出现的常系数值.

难点:

  • 特征方程求解
  • 找出一个特解

尝试特解的方法:

根据非齐次项 bn 来尝试某些类型的特解(不绝对):

  • 如果 bnnk 次多项式,尝试 hn 也是 nk 次多项式

    • bn=d() , 尝试 hn=r()
    • bn=dn+c(d,c) , 尝试 hn=rn+s(r,s)
    • bn=an2+dn+c(a,d,c) , 尝试 $ hn = rn^2+sn+t (r, s, t是常数) $
  • bn=dn(d) 是指数形式,尝试 hn=pdn(p) 也是指数形式。

如:

hn=p3n 不对,则可以尝试 hn=pn3n

7.6 一个几何例子

定义

定义1

设有平面或空间中的点集 K , 若 K 中任意两点 pq 的连线上的所有点都在 K 内,称 K 是凸集

定理

定理7.6.1

hn 表示用下面方法把凸多边形区域分成三角形区域的方法数:
在有 n+1 条边的凸多边形区域内通过插入不相交的对角线,而把它分成三角形区域。
定义 h1=1
hn 满足如下递推关系:

hn=h1hn1+h2hn2+...+hn1h1=Σk1n1hkhnk(n2)

该递推关系解为: hn=1n(2n2n1)(n=1,2,3...)

其中: 1n(2n2n1) 为 Catalan数 Cn1