10.3 二项式定理与组合恒等式
本章目录 · 1 节
本章导读
【定理10.3.1:二项式定理】对非负整数n,有
展开时从n个因子中选k个贡献x,其他贡献y,选择位置的方式为 ,因此得到系数。 时两边均为1。令 得推论10.3.1:。所有求和在这里都是有限和,不需要级数收敛条件。
【命题10.3.1:对称与递推】对应教材式10.3.1至10.3.3:
第一式用补集,第二式可数“选k人并在其中指定一人”,第三式按是否含指定元素分类。越界的非负上项组合数取0,含除数k的式子不用于 。
【命题10.3.2:变下项求和】对应式10.3.4、10.3.5:
分别在二项式定理中取 和 。第一式还可用“n元集的全部子集”双重计数:按大小分类得左边,每个元素选或不选得右边。教材第二式若把自然数0也包括进去,必须补上例外: 时该和是1,不能写0;此处已修正适用范围。
【命题10.3.3:变上项求和与嵌套选择】对应式10.3.6、10.3.7:
第一式按 元子集的最大元素 分类,剩下k点取自前l点,方式数为 ; 的项为0。第二式数一对嵌套集合 :可先选r元R再选其中k元K;也可先选K,再从其余 点选 点扩成R。例如从五点中先选四点再选三点,某个固定三点集恰被两个四点集包含,重复次数不能忽略。
【命题10.3.4:Vandermonde恒等式】对应式10.3.8、10.3.9:
第一式从两个互不相交、大小m和n的集合中共选r点,按从第一集合选了k点分类;约定越界组合数为0后,对全部非负 都适用,不必限制 。第二式取第一式的 ,再用 与右端补集对称性得到,因此不再存在“代入参数超出先前限制”的问题。
【例10.3.1:两个带权和】对 ,
【解】对 求导再令 得第一式。第二式可用 ,两次求导给出 ,再加第一式。 时直接检查为1; 时两个加权和都为0,另行理解即可。也可先用 消去变系数,再拆项求和。证明组合恒等式常用已知式变形、比较系数、求导或积分、归纳及双重计数,应说明采用哪一种依据。
【非降格路模型】在整数网格中每步只许向右或向上一单位。从 到 的路径共有 :在总共 步中选择m个右步位置。
从 到 ,若 ,路径数为 ;若有坐标反向则为0。经过 时,前提 ,分别数两段再相乘,得 。
【例10.3.2:单调函数】求 的单调非递减函数个数。
【解】这里教材的“单调递增”按允许相等,即 理解。每个这样的数列是从n类值中可重复选n个,故数目为 。格路解释为:在横坐标i处到达高度 ,向右一单位后再向上到下一高度,从 起,最后到 ,恰有n个右步和 个上步;按每个右步所在高度可唯一恢复函数。
若“递增”指严格递增, 只有恒等函数一种,不能混用前面的组合数。一般 ,,非递减函数有 个;非递增也一样,二者交集为n个常值函数,故两个方向合起来有 个。
【例10.3.3:栈输出与Catalan数】固定输入为依次进栈的 ,允许在任意合法时刻弹出,求不同输出排列数。
【解】把进栈记R、出栈记U,共n个R与n个U,每个前缀必须有R数不少于U数,正对应从 到 始终满足 的非降路径。固定输入顺序后,每种输出反推唯一的操作序列:为输出下一元素,先推入尚未入栈且位于它之前的输入,再将它弹出。因此这里计操作路径也恰在计不同输出。
全部路径为 。对越到 的坏路径,取首次到达 的点P,把起点到P的前缀关于这条直线反射;反射公式为 ,起点变成 ,右步与上步互换,后缀保持。反向取新路径首次遇到该直线之点再反射,唯一恢复原坏路径,所以坏路径数为从 到 的路径数 。
合法输出数于是为
时输出为123、132、213、231、321,共5种;312无法由该栈产生。 时空操作、空输出各一种,。本例还可用下一章的生成函数处理。
