《组合数学》读书笔记 kirai 16.11.3（第八章特殊计数序列）

第8章特殊计数序列

卡特兰数
卡特兰数的定义式：

$C_{n}=\frac{1}{n+1}\binom{2n}{n}$

n个+1和n个-1构成的2n项序列这个例子看得我头昏眼花啊，好在最后还是懂了一点点。看来需要刷二周目了，留个坑先…
关键在于找到前k项，使得k是最小的并且满足前k项和等于-1，这个时候将前k-1项（注意，k-1是偶数，并且这里面的+1和-1的数量是一样多）翻转（+1变-1，-1变+1）,加上第k项的-1也翻转为+1，那么+1恰好多了一个，此时序列变成了(n+1)个+1和(n-1)个-1。但是最后的为什么(n+1)个+1和(n-1)个-1的序列数量就和不可接受序列数量等价，#还要再考虑一下。
差分序列
构造了一个差分表，p阶差分的定义：

$\Delta^{p}h_{n}=\Delta^{p-1}h_{n+1}-\Delta^{p-1}h_{n}$

看得出来是两两合并成了一项，那么差分表的形式就是一个三角阵。它有线性性：两个多项式的差分表可以加减；并且对角线上的元素由前一条对角线上的元素确定（把上式编程加和形式就能看出来了）。
至于定理8.2.2：

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

$c_{0},c_{1},c_{2},...,c_{p},0,0,0$

的序列的通项满足：

$h_{n}=c_{0}\binom{n}{0}+c_{1}\binom{n}{1}+c_{2}\binom{n}{2}+...+c_{p}\binom{n}{p}$

没太理解为什么根据上两个性质就可以获得这个等价关系，试着推了一下：

$h_{n}=c_{0}\binom{n}{0}+c_{1}\binom{n}{1}+c_{2}\binom{n}{2}+...+c_{p}\binom{n}{p}\emph{(1)}$

等价于

$h_{n}=c_{p}n^{p}+c_{p-1}n^{p-1}+...+c_{1}n+c_{0}\emph{(2)}$

式子后面的括号来标记式子的序号，没办法简书不支持mathjax很遗憾。
由(2)式可以得到差分表：
![](http://latex.codecogs.com/svg.latex?\begin{pmatrix} c_{0}&c_{0}+c_{1}&c_{0}+2c_{1}+c_{2}&c_{0}+3c_{1}+3c_{2}+c_{3}&...\ c_{1}&c_{1}+c_{2}&c_{1}+2c_{2}+c_{3}&...\ \vdots&\vdots&\vdots&\ddots \end{pmatrix})
可以看得出来每一项关于c的系数都是pascal三角中的系数，不妨设

$\Delta^{0}h_{n}=k_{0}c_{0}+k_{1}c_{1}+k_{2}c_{2}+...+k_{p}c_{p}$

易得

$k_{i}=\binom{n}{i}$

《组合数学》读书笔记 kirai 16.11.3（第八章 特殊计数序列）

第8章 特殊计数序列

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

推荐阅读更多精彩内容

《组合数学》读书笔记 kirai 16.11.3（第八章特殊计数序列）

第8章特殊计数序列