计数问题学习笔记

计数问题学习笔记

组合计数

插板法: 略

阶乘幂:

上升阶乘幂:

[(x)^{(n)} = x(x+1)(x+2)cdots(x+n-1) = frac{(x+n-1)!}{(x-1)!} ]

下降阶乘幂:

((x)_{(n)})

卡特兰数:

定义式

[h_n = displaystylesum^{n-1}_{k=0}h_kh_{n-1-k} ]

通项式

[h_n = binom{2n}{n}- binom{2n}{n-1} = frac{ binom{2n}{n}}{n+1} ]

应用: 括号序列数量, 方格行走数, 凸多边形划分数, 二叉树数量

通项证明:

2n步选n步向斜上走方案数为( binom{2n}{n})

如果走到负区域, 则一定与2n步选n-1步斜向上走的方案数相同

在一条路径第一次触到直线y=-1时, 将其以后的路径关于y=-1对称

走2n步最终到达点(2n, -2)

每一条到达点(2n, -2)的路径都可以如此转化

第一类斯特林数:

$ S_u(n, m)$表示n个不同元素构成恰好m个圆排列的方案数

(S_u(n,m) = S_u(n-1,m-1) + (n-1) * S_u(n-1,m))

有符号: (S_s(n, m) = (-1)^{n+m}S_u(n,m))

有符号的生成函数: ((x)_{(n)}) (x的n次下降幂)

第二类斯特林数:

(S(n,m))表示n个不同元素拆分成m个非空集合方案数

[S(n,m) = S(n-1,m-1) + m * S(n-1, m) ]

生成函数

[S(n,m) = frac{1}{m!}sum(-1)^k binom{m}{k}(m-k)^n ]

贝尔数为第二类斯特林数之和

拆分数:

(f_n)表示大小为n的正整数拆分成若干无序的正整数之和的方案数

dp求解

方案一:

f[i][j]表示拆分成若干不超过j的方案数

f[i][j] = f[i-j][j] +f[i][j-1]

方案二:

g[i][j]表示拆分j个数字的方案数

g[i][j] = g[i-1][j] + g[i-j][j]

优化:

易知任意一个复杂度都是(n^2)

结合两者, 复杂度为(nsqrt{n})

首先用方案一跑出所有用不超过(sqrt{n})数字大小拼出1~n的方案数

复杂度(nsqrt{n}) 存疑

生成函数

基础闭形式:

(sum_{n ge 0} x^n=frac{1}{1-x})

(sum_{n ge 1} x^n=frac{x}{1-x})

(sum_{n ge 1} x^n=x*(sum_{n ge 0} x^n))

(sum_{n ge 1} n x^n=)?

​ ((sum_{n ge 0} x^n)'=(frac{1}{1-x})')

​ (sum_{n ge 0} (n+1)x^n=frac{1}{(1-x)^2})

​ (sum_{n ge 0} (n+1)x^{n+1}=frac{x}{(1-x)^2})

​ ((sum_{n ge 0} x^n)*(sum_{n ge 0} x^n)=sum_{n ge 0} (n+1)x^n=frac{1}{(1-x)^2})

(sum_{n ge 0} frac{1}{n!}x^n=e^x)

• 加法意义: 合并

• 乘法意义:拼接

例: 求斐波那契数列的通项公式

因为F(x) = F(x-1) + F(x-2)

[~~~~~~F(0)~~~F(1)~~~~F(2)~~~~F(3)~~~~F(4)\~~~~~~~~~~~~~~~~~ F(0)~~~~F(1)~~~~F(2)~~~~F(3)\​~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~F(0)~~~~F(1)~~~~F(2) ]

发现最上面的生成函数由下面两个推出

所以(F(x) = x cdot F(x-1) + x^2 cdot F(x-2)) + 1

解得F(x)的闭形式为(frac{1}{1-x-x^2})

那么如何求通项公式呢?

前置:

(sum_{n ge 0} x^n=frac{1}{1-x})

(sum_{n ge 0} (kx)^n=frac{1}{1-kx}) (将x变为kx即可)

(sum_{n ge 0} ax^n=frac{a}{1-x})

发现如果把它化成类似(frac{a}{1-kx})的形式是再好不过了

所以将(1-x-x^2)因式分解, 再进行裂项

设(t_1, t_2)为其的两根

最后化成(frac{a}{1-t_1x} - frac{b}{1-t_2x})的形式

(A_n = a cdot t_1^n - b * t_2^n)

好像不是很难的鸭子

指数级生成函数:

处理有标号问题时, 通常使用指数级生成函数

生成函数: (displaystylesum _{nge0}frac{A_n}{n!}x^n)