组合数学

第8章 特殊计数序列

8.1 Catalan 数

定义

Catalan 数列是序列 C0,C1,,Cn,, 其中

Cn=1n+1(2nn)n=0,1,2,...

是第 n 个 Catalan 数。

n+1 边形被在其内部不相交的对角线划分成三角形区域的方法数为 Cn1

Cn1=hn 得递推为:

Cn=C0Cn1+C1Cn2+...+Cn1C0

另一个递推:

Cn=4n2n+1Cn1(n1),C0=1

应用

  1. 括号化问题
  2. 出栈次序问题
  3. n 个结点构成得二叉树数

定理

8.1.1

考虑由 n+1n1 构成的 2n 项序列

a1,a2,...,a2n,

其部分和总满足:

a1+a2+...+ak0(k=1,2,...,2n)

的序列的个数等于第 n 个Catalan数

可解决的问题

  • 买票找零问题
  • 走方格问题

拟 Catalan 数

定义一个新数列:

C1,C2,...,Cn,....

其中, Cn=n!Cn1,n=1,2,...,n,...

得到:

Cn=(n1)!(2n2n1)

将 Catalan 数的递推关系代入得到拟 Catalan 数的递推
关系:

Cn=(4n6)Cn1(n1)

初值为:

C1=1

8.2 差分序列

定义

h0,h1,h2,,hn, 是一个序列。定义新序列:

Δh0,Δh1,Δh2,,Δhn,

称为 h0,h1,h2,,hn, 的(一阶)差分序列,其中 Δhn=hn+1hn(n0) ,是序列的相邻项的差。

递归定义

0 阶差分序列: h0,h1,h2,,hn,,

1 阶差分序列: Δ1hnhn+1hn(n0,1,2,)

2 阶差分序列:

Δ2hn=Δ(Δ1hn)=Δ1hn+1Δ1hn=(hn+2hn+1)(hn+1hn)=hn+22hn+1+hn(n0)

k 阶差分序列:

Δkhn=Δ(Δk1hn)=Δk1hn+1Δk1hn(n=0,1,2,...)
差分表

设序列 hn(n=0,1,2,...) ,最上面一行是第 0 行!!!

h0h1h2h3h4...Δ1h0Δ1h1Δ1h2Δ1h3...Δ2h0Δ2h1Δ2h2...Δ3h0Δ3h1......
  • Δphn=Δp1hn+1Δp1hn
  • 序列 hn(n0,1,2,) 的差分表由第 0 行确定

定理

8.2.1

设序列的通项 hnnp 次多项式:

hn=apnp+ap1np1+ap2np2++a1n+a0,

则对于所有的 n0 ,必有: p+1hn=0

8.2.2

差分表的第 0 条对角线等于

c0,c1,c2,,cp,0,0,0,cp0

的序列的通项满足:

hn=c0(n0)+c1(n1)+c2(n2)+...+cp(np)

的关于 np 次多项式。

证明思路

线性性+简单差分表

8.2.3

假设序列 h0,h1,,hn, 的差分表的第 0 条对角线等于

c0,c1,,cp,0,0,

那么:

Σk=0nhk=c0(n+11)+c1(n+12)+...+cp(n+1p+1)

(证明中间有一段: Σk=0n(kp)=(n+1p+1)

应用
  • 一般项为多项式的序列的部分和
8.2.4

1kp1 ,则:

S(p,k)=kS(p1,k)+S(p1,k1)

类比二项式公式中:

(nk)=(n1k)+(n1k1)

Pascal 三角形:

直接上方的元素乘以 k 再加上其左上方的元素

8.2.5

第二类 StirlingS(p,k) 计数的是把 p 元素集合划分到 k 个不可区分的盒子且没有空盒子的划分的个数。

8.2.6

对每一个满足 0kp 的整数 k ,都有

S(p,k)=Σt=0k(1)t(kt)(kt)p

从而 S(p,k)=1k!Σt=0k(1)t(kt)(kt)p

8.2.7

如果 p1 ,则:

Bp=(p10)B0+(p11)B1+(p12)B2+...+(p1p1)Bp1
8.2.8

1kp1 ,则:

s(p,k)=(p1)s(p1,k)+s(p1,k1)
8.2.9

第一类 StirlingS1(p,k) 是将 p 个物品排成 k 个非空的循环排列的方法数

性质

  • 差分表由第 0 行上元素的值就能决定
  • 差分表也可由第 0 条对角线决定

例子

简单差分表1

若第 0 条对角线全为 0

简单差分表1

0 条对角线除一个 1 外都是 0

首先 1 在第 p 行,前 p 个元素就都为 0 ,从 p+1 行开始的所有行的元素都是 0

其次hp=1h0=0,h1=0,...,hp1=0 ,故 hn 有因子 n(n1)...(n(p1)) ,再代入 hp=1 ,得到:

hn=n(n1)...(n(p1))p!=(np)

差分表的线性性

gnfn 分别是两个序列的通项,若 hn=gn+fn

  • 一般的: Δphn=Δpgn+Δpfn,p0
  • 更一般的,对于任何常数 c,d 来说,Δp(cgn+dfn)=cΔpgn+dΔpfn(p0,n0)

差分表的第0条

组合意义

(由定理8.2.2)

对于序列 hn=np ,设其差分表中第 0 条对角线上的元素为 c0,c1,,cp,0,0, 引入标记:

c(p,0)=c0,c(p,1)=c1,,c(p,p)=cp,0,0,...

则有:

hn=np=c0(n0)+c1(n1)+...+cp(np)=c(p,0)(n0)+c(p,1)(n1)+...+c(p,p)(np)
特殊值1: c(p,0)
c(p,0)={1p=00p1
特殊值2:

np 项系数相等,得: 1=c(p,p)p!

c(p,p)=p!
特殊值3:
[n]k={n(n1)...(nk+1),k11,k=0

则, [n]k = n 个不同元素中取 k 个元素的排列数 P(n,k)

递推关系:

[n]k=(nk)[n]k

且:

[n]k=k!(nk)

故:

hn=np=c(p,0)[n]00!+c(p,1)[n]11!+...+c(p,p)[n]pp!=k=0pc(p,k)[n]kk!=k=0pc(p,k)k![n]k

S(p,k)=c(p,k)k! (0kp) ,成为第二类 Srirling

所以 hn=np 的展开式变为: hn=np=k=0pS(p,k)[n]k

第二类 Srirling

特殊值:
S(p,0)=c(p,0)={1p=00p1S(p,p)=1(p1)
递推公式:

定理8.2.4

组合解释:

投球入盒

定理8.2.5

Bell

S(p,k)=k!S(p,k) 表示把 {1,2,,p} 分到 k非空可区分
盒子的划分个数,则

S(p,k)=k!S(p,k)

公式:定理 8.2.6

所以 S(p,k) :把 {1,2,,p} 分到 k非空可区分的盒子的划分个数。

p 个物品 k 个盒子 空盒
有区别 无区别 没有 S(p,k)
有区别 有区别 没有 S(p,k)
定义

定义 Bell 数是将 p 个元素的集合划分到非空、不可区分的盒子(盒子数 p )的划分数,记为 Bp ,则:

Bp=S(p,0)+S(p,1)+...+S(p,p)

是第二类 Stirling 数三角形的一行的元素和

递推

定理 8.2.7

第一类 Srirling

对比

第二类 SrirlingS(n,p)

  • 指出如何用 [n]0,[n]1,[n]2,...,[n]p 写出 np
  • p 个元素的集合划分到 k 个不可区分的盒子且没有空盒的划分的个数

第一类 Srirlings(n,p)

  • 如何用 n0,n1,n2,...,np 写出 [n]p
  • p 个物品排成 k 个非空的循环排列方法数
定义

一般地, [n]p 展开式有 p 个因子
乘开后得到 n 的幂多项式, np,np1,...,n1,n0
其系数的符号正负相间。故:

[n]p=anpnpanp1np1+......++(1)p1an1n1+(1)pan0n0nk$$$$ank$$$$Stirling$$$$s(p,k)
特殊值
s(p,0)=0(p1)s(p,p)=1(p0)
递推式

定理 8.2.8

组合意义

定理 8.2.9

小结

p 个球 k 个盒 是否为空 方案个数
有区别 有区别 有空盒 kp
有区别 无区别 无空盒 S(p,k) S2(p,k)
有区别 有区别 无空盒 k!S(p,k) S(p,k)
有区别 无区别 有空盒 S(p,1)+S(p,2)+...S(p,k)pk Bell
有区别 无区别 有空盒 S(p,1)+S(p,2)+...S(p,p)pk Bell
有区别 k 个循环序列 非空 s(p,k) S1(p,k)