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

作者: kirai | 来源:发表于2016-11-02 19:56 被阅读78次

《组合数学》读书笔记 kirai 16.11.3（第八章特殊计
组合数学
《组合数学》读书笔记 kirai 16.11.1（第七章递推关
16.11.3
《具体数学》读书笔记 kirai 16.11.2（前言部分）
离散数学第五版：第八章知识点概要
程序员的数学 - 读书笔记目录
特殊日月组合
程序员的数学 - 归纳与递归
程序员的数学 - 排列组合

第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}$

网友评论

Daily Reading 群的分享

本文标题：《组合数学》读书笔记 kirai 16.11.3（第八章特殊计

本文链接：https://www.haomeiwen.com/subject/vsxbuttx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

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

第8章特殊计数序列

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

相关文章