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

第8章 特殊计数序列

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

  
  
  

  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阶差分的定义：

  
  
  

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

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

的序列的通项满足：

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

等价于

式子后面的括号来标记式子的序号，没办法简书不支持mathjax很遗憾。
由(2)式可以得到差分表：
可以看得出来每一项关于c的系数都是pascal三角中的系数，不妨设

易得