关于Pascal和二项式系数

关于Pascal和二项式系数

《Introductory Combinatorics Fifth Edition》学习笔记：

关于pascal三角形：

Pascal三角形递推函数：

将n,k值看做dp数组的二维，由此得到动态规划转移式。

将

也可以看做是从

的点(0,0)走到其所在位置(n,k)。

不过，走法只有两种：

从这种图的角度也能理解为什么一行的和是上一行数字和的2倍。

同时我们也可以理解为什么一行的数字和是

，所以我们得到：

二项式定理：

当我们设x=1,y=x，有：

有一个改变n的大小的重要等式：

证明：

有了它之后，可以得到这样的式子：

不难看懂吧

另一个重要的变n等式：

这玩意儿用公式不好推导，用组合原理想：假设将2n个苹果分成2份各n个，现在到2个果篮里拿够n个，那么就是：

我们知道二项式系数是一个山峰序列，同时它具有这样的性质：当n是奇数时存在两个同高的最高峰，当n是偶数时仅存在一个最高峰。

通过数学推论：

如果n是一个奇数，那么存在着n+1=2k <--- n+1-k=k 即

一点其他的东西：关于x, 令floor函数是

，它满足

与之对应的是ceiling函数：

函数值保证是整数

在计算机内：如果n是一个整数，折半后，统一向上取整：(n+1)/2，统一向下取整：n/2。

多项式定理：

定义

其中

那么，pascal中的元素可以写成：

由Pascal的递推关系进一步得到多项式系数的递推式：

定理：设n是一个正整数，有：

其中，

例如：对于

展开后，

的系数对应：

接下来简单的说说当n是负数的情况：

当n<0，我们仍然按照计算原则进行下去。

所以有以下等式成立：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。