组合数学课件第四章二项式系数PPT.pptx

《组合数学课件第四章二项式系数PPT.pptx》由会员分享，可在线阅读，更多相关《组合数学课件第四章二项式系数PPT.pptx（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、组合数学课件第四章二项式系数目录(2)第六章 递推关系6、1 Fibonacci 数列6、2 常系数线性齐次递推关系得求解6、3 常系数线性非齐次递推关系得求解6、4 用迭代和归纳法求解递推关系本章小结 习题第七章 生成函数7、1 生成函数得定义和性质7、2 多重集得r-组合数7、3 正整数得划分7、4 指数生成函数与多重集得排列问题7、5 Catalan 数和Stiring 数本章小结 习题第八章 Polya 定理8、1 置换群中得共轭类与轨道8、2 Polya 定理得特殊形式及其应用本章小结 习题*课程总结教学目标:1、掌握二项式定理、证明方法及其应用;2、掌握推广得二项式定理;3、掌握多

2、项式定理、证明方法及其应用;4、理解一些组合恒等式得意义及其证明方法;5、非降路径问题得组合意义及应用;重点:二项式定理、多项式定理证明方法及其应用;难点:一些组合恒等式证明方法,非降路径问题组合意义及应用。4、1二项式定理1、二项式系数组合数C(n,k)或者 也叫二项式系数、2、组合数得定义()nk3、组合数得一些恒等式(1)对称式(2)抽取式(3)Pascal 公式(4.1)(4.2)(4.3)抽取式(4、2):如n,kN,有C(n,k)=(n/k)C(n-1,k-1)证 明：从n 个 元 素 中 取k个 的 组 合 可 先 从n 个 元 素 中 取1个，再 从剩 下 的n-1 个 元 素

3、 中 选 择k-1 个，组 合 数 为C(n-1,k-1)。选 出 的k个元素都有可能被第一次选中，因是组合，故重复度为k。得证。或通过计算证明：证 证:某班有 某班有 n n 名同学 名同学,要选出 要选出 k k 位班委会成员 位班委会成员,再选 再选1 1 名作书记 名作书记,这名书记不可以就是班委会 这名书记不可以就是班委会成员 成员,问有多少种不同得方案？问有多少种不同得方案？证明 证明:从 从 n n 名同学中选出 名同学中选出 k k 位组成班 位组成班委 委,在 在 k k 位班委中选 位班委中选1 1 人做班长 人做班长,问有多 问有多少种方法？少种方法？证 明：因 为(x+

4、y)n=(x+y)(x+y)(x+y)，等 式 右 端 有n 个 因 子，项xkyn-k是 从 这n 个 因 子 中 选 取k个 因 子，k=0,1,n。在 这k个(x+y)里 都 取x，而 从 剩 下 的n-k个 因 子(x+y)中 选 取y 作 乘 积 得 到，因 此xkyn-k的系数为上述选法的个数C(n,k)。故有证毕。注：可用数学归纳法证明，证明略；C(n,k)又称二项式系数。推论4、1、1:推论4、1、2:推论4、1、3:证明:在推论4、1、2中令x=1,即可得证。利 用 组 合 分 析,等 式 左 端 相 当 于 从A=an 中 任 意 选 择k(0kn)个 元素 得 所 有 可

5、 能 数 目,即 对n 个 元 素,每 一 个 都 有 被 选 择 和 不 被 选 择得可能,总得可能数为2n。另外,该等式还表明A 得所有子集个数为2n。(4、4)n n 元集合得所有子集个数就是 元集合得所有子集个数就是2 2n n 推论4、1、1:推论4、1、2:推论4、1、3:推论4、1、4:证明:在推论4、1、2中令x=-1,即可得证。另外,该等式还表明A=an 得偶数子集个数和奇数子集个数相等。(4、5)(4.5)即 n n 元集合得偶子集个数与 元集合得偶子集个数与奇子集个数相等 奇子集个数相等 恒等式(4、6):证 明:考 虑 盒 子1中 有n 个 有 区 别 得 球,从 中

6、取 一 个 球 放 入 盒 子2中,再 取 任 意 多 个 球 放 入 盒 子3中。等 式 左 端 表 示 先 从 盒 子1中 取k(k=1,2,n)个 球,再 从 中 取 一 个 放 入 盒 子2中,剩 下 得k-1 个 球 放入 盒 子3中。等 式 右 端 表 示 先 从 盒 子1中 取 一 个 放 入 盒 子2中,剩 下得n-1 个 球 就 是 否 放 入 盒 子3中 均 有 两 种 可 能。显 然 两 种 取 法 结 果就是一样得。得证。或通过计算证明:恒等式(4、6):证明：证法3由二项式定理有对上式两边微商得然后令x=1 得注:如令x=-1,可证明下面恒等式。类(4、6)恒等式(习

7、题4、7):证明：将等式两边对x微分得在上式中，令x=-1 得即得证。大家有疑问的，可以询问和交流可以互相讨论下，但要小声点 可以互相讨论下，但要小声点恒等式(习题4、8积分方法):证明：将等式两边对x从0到1积分得即得证。类恒等式(4、7):恒等式(4、7):证明：将等式两边对x微分得将等式两边同乘以x后再对x微分得在上式中，令x=1 得得证。注：如令x=-1，即可证明另一恒等式(4.7)。恒等式(4、8):如n,l,r N,lr,有C(n,l)C(l,r)=C(n,r)C(n-r,l-r)从 从 n n 个候选人中 个候选人中,选出 选出 l l 个常委 个常委,再选出 再选出 r r 位

8、政治 位政治局常委 局常委,选法得个数？选法得个数？证 明：等 式 的 左 端 可 看 作 是 先 从n 个 元 素 中 取l 个 元 素，然 后 再 从所 得 的l 个 元 素 中 再 选 择r 个 元 素 的 方 法 数。这 种 选 法 与 直 接 从n个 元 素 中 选 取r 个 元 素 的 选 法 不 同.因 为 同 样 的r 个 元 素 可 以 多 次出 现.例 如7元 集a,b,c,d,e,j,k，从 中 选5个 元 素，比 如 说a,b,c,d,e 和a,b,c,j,k，它 们 都 可 以 选 出 同 样 的3个 元 素a,b,c，不 难 看 出，某r 个 元 素 可 以 重 复

9、 出 现 的 次 数 就 是 包 含 它们 的l 元 子 集 的 个 数，而 这 种l 元 子 集 的 其 余l-r 个 元 素 可 以 取 自n元 集 的n-r 个 元 素,所 以 这 种l 元 子 集 有 个.综 上 所 述，通 过 先 选l 个 元 素 然 后 再 选r 个 元 素 的 选 法 应 该 有C(n,r)C(n-r,l-r)种。得证。或通过计算证明：恒等式(4、9):Vandermonde 恒等式,如n,m N 且rmin(m,n),有C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+C(m,r)C(n,0)证 明：设A=am,B=bn,且AB=，则A

10、 B=C 有m+n 个 元 素。C 的r 组 合 个 数 为C(m+n,r)，而C 的 每 个r 组 合 无 非 是 先 从A 中 取k个 元 素，再 从B 中 取 出r-k个 元 素 组 成(k=0,1,r)。由 乘 法 法则共有C(m,k)C(n,r-k)种取法，再由加法法则即可得证。或通过比较系数法证明：比较等式两边xr的系数即可得证。恒等式(4、10):恒等式(4、10特例):恒等式(4、9):Vandermonde 恒等式,如n,m N 且rmin(m,n),有C(m+n,r)=C(n,0)C(m,r)+C(n,1)C(m,r-1)+C(n,r)C(m,0)恒等式(4、10):恒等式

11、(4、11):证 明：利 用 组 合 分 析 法，在 集 合A=an+1 的n+1 个 不 同 元 素 选 出k+1 个 元 素 的 组 合 可 分 为 以 下 多 种 情 况：如k+1 个 元 素 中 包 含a1，相 当 于 从 除 去a1的n 个 元 素 中 选 出k个 元 素 的 组 合，组 合 数 为C(n,k)；如 不 包 含a1但 包 含a2，相 当 于 从 除 去a1,a2的n-1 个 元 素 中选 出k个 元 素 的 组 合，再 加 上a2而 得 到，组 合 数 为C(n-1,k),同理 如 不 包 含a1,a2,an-k+1，但 包 含an-k+2，相 当 于 从 剩 下 的

12、k个 元素 中 选 出k个 元 素 的 组 合，再 加 上an-k+2而 得 到，组 合 数 为C(k,k)；注意，i k时，C(k,k)=0。由加法法则得或对固定的k，对n 使用归纳法，当n=0 时，有可见，当n=0 时，等式成立。如对任意n 等式成立，则有可见等式对n+1 也成立。由归纳原理，得证。恒等式(4、12):如n,r N,有C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0)证明I:反复利用Pascal 公式,即可证明。或利用组合分析法,在集合A=an+r+1 得n+r+1 个不同元素选出r 个元素得组合可分为以下多种情况:如r 个元素

13、中不包含a1,相当于从除去a1得n+r 个元素中选出r 个元素得组合,组合数为C(n+r,r);如r 个元素中包含a1但不包含a2,相当于从除去a1,a2得n+r-1 个元素中选出r-1个元素得组合,再加上a1而得到,组合数为C(n+r-1,r-1),同理如r 个元素中包含a1,a2,ar-1,但不包含ar,相当于从剩下得n+1 个元素中选出1个元素得组合,再加上a1,a2,ar-1而得到,组合数为C(n+1,1);如r 个元素中包含a1,a2,ar,相当于从剩下得n 个元素中选出0个元素得组合,组合数为C(n,0)。由加法法则得C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)

14、+C(n+1,1)+C(n,0)恒等式(4、12):如n,r N,有C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0)证 明II:等 式 得 左 端 可 看 作 就 是 在 集 合A=an+2 得n+2 个 不 同 元 素允 许 重 复 得 选 出r 个 元 素 得 组 合,可 分 为 以 下 多 种 情 况:如r 个 元 素中 不 包 含a1,相 当 于 从 除 去a1得n+1 个 元 素 中 允 许 重 复 得 选 出r 个元 素 得 组 合,组 合 数 为C(n+r,r);如r 个 元 素 中 只 包 含 一 个a1,相 当 于从 除 去a1

15、得n+1 个 元 素 中 允 许 重 复 得 选 出r-1个 元 素 得 组 合,再 加上a1而 得 到,组 合 数 为C(n+r-1,r-1);如r 个 元 素 中 包 含 两 个a1,相 当于 从 除 去a1得n+1 个 元 素 中 允 许 重 复 得 选 出r-2 个 元 素 得 组 合,再加 上 两 个a1而 得 到,组 合 数 为C(n+r-2,r-2),同 理 如r 个 元 素 中 包含r 个a1,其组合数为C(n,0)。由加法法则得C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0)数学归纳法二项式系数公式,特别就是Pascal 公式比

16、较级数展开式中得系数(二项式定理或母函数法)积分微分法组合分析法例4、1如n,r N,r n,有C(n,r+1)=C(r,r)+C(r+1,r)+C(n-1,r)证明在上面得等式中,用n+r 代替n,得恒等式(4、13):C(n+r,r+1)=C(r,r)+C(r+1,r)+C(r+n-1,r)、在式(4、13)中,如果令r=1,就得到 1+2+3+n=C(n+1,2)=n(n+1)/2、这就是等差级数得求和公式、如果令r=2,则有 1+C(3,2)+C(4,2)+C(n+1,2)=C(n+2,3)=n(n+1)(n+2)/6、在这个等式中每相邻两项之差就就是等差级数得项,称这个等式叫做二阶等

17、差级数求和公式、如果令r=3,则有1+C(4,3)+C(5,3)+C(n+2,3)=C(n+3,4)、其中每相邻两项之差就就是二阶等差级数得项,把这个 等式叫做三阶等差级数得求和公式、例4、2计算12+22+32+n2,13+23+33+n3、解对任何正整数k,有k2=2C(k,2)+C(k,1),k3=6C(k,3)+6C(k,2)+C(k,1)、所以有12+22+n2=2C(1,2)+C(2,2)+C(n,2)+C(1,1)+C(2,1)+C(n,1)=2(n+1)n(n-1)/6+(n+1)n/2=n(n+1)(2n+1)/6、13+23+n3=6C(1,3)+C(2,3)+C(n,3)

18、+6C(1,2)+C(2,2)+C(n,2)+C(1,1)+C(2,1)+C(n,1)=6(n+1,4)+6(n+1,3)+(n+1,2)=2(n+1)n(n-1)/6+(n+1)n/2=n(n+1)/22、例4、3证明若p就是不等于2得素数,则当C(2p,p)被p除时余数就是2、证明在恒等式(4、10)中令m=n=p得可 以 证 明,如 果p为 素 数 且0kp,则p|C(p,k)、因 为 由 组 合 数C(p,k)得 计 算 公 式 知k!整 除p(p-1)(p-k+1)、又 由 于p就 是 素数 且 k1,则 k!|(p-1)(p-k+1);若 k=1,也 有 k!|(p-1)(p-k+

19、1)、所以C(p,k)就是p得倍数、在 等 式(4、14)中,C(p,1)2+C(p,2)2+C(p,p-1)2一 定 就 是p得 倍 数,而C(p,0)2+C(p,p)2=1+1=2,故 当p2 时,C(2p,p)除 以p得余数就是2、(4、14)例4、4证明:从n名女同学和n名男同学中,选出n名同学组成一个社团,其中一人担任社团主席,且必须由女同学担任,问有多少种选法？引 例、非 降 路 径 问 题 从(0,0)点出 发 沿X 轴 或Y 轴 得 正 方 向 每 步走 一 个 单 位,最 终 走 到(m,n)点,有多少条路径？解:设 从(0,0)点 水 平 方 向 向 前 进 一 步 为x,

20、垂 直 方 向 向 上 进 一 步 为y。于 就 是 从(0,0)点 到(m,n)点,水 平 方 向 走m 步,垂 直 方 向 走n 步。一 条 从(0,0)点 到(m,n)点 得 非 降 路 径 与 重 集m*x,n*y 得 一 个 全排列一一对应,故所求非降路径数为(m+n)!/(m!n!)=C(m+n,m)。另 外,垂 直 方 向 需 要 走n 步,相 当 于 在X 轴0,1,m 共m+1 个 端 点 处重 复 得 选 择n 个 位 置 向 上 走,与 一 条 从(0,0)点 到(m,n)点 得 非 降路径一一对应,故所求非降路径数为F(m+1,n)=C(m+n,n)。多重集S=*a1,

21、*a2,*ak 得r 组合数F(k,r)=C(k+r-1,r)由 引 例,我 们 已 经 知 道,从(0,0)点 到(m,n)点 得 非 降 路 径 数 就就 是 组 合 数C(m+n,m),而 且 从(0,0)点 到(m,n)点 得 非 降 路 径 数 等于从(0,0)点到(n,m)点得非降路径数,即C(m+n,m)=C(m+n,n)、另 外,一 条 从(0,0)点 到(m,n)点 得 路 径 可 分 为 两 类 情 况,一 种就 是 从(0,0)点 到(m,n-1)点 得 非 降 路 径,另 一 种 就 是 从(0,0)点 到(m-1,n-1)点得非降路径,根据上述结论,有C(m+n,n)

22、=C(m+n-1,m)+C(m+n-1,m-1)这就是Pascal 公式得另一种形式。例2、非 降 路 径 问 题 从(0,0)点出 发 沿X 轴 或Y 轴 得 正 方 向 每 步走 一 个 单 位,最 终 走 到(m,n)点,有多少条路径？证 明:这 就 是 上 一 小 节 得 组 合 恒 等 式。等 式 左 端 表 示 从(0,0)点 到(n+1,r)点 得 非 降 路 径 数,右 端 第1项 表 示 从(0,0)点 到(n,r)点 得路 径 数,右 端 第2项 表 示 从(0,0)点 到(n,r-1)点 得 非 降 路 径 数,右端最后1项表示从(0,0)点到(n,0)点得非降路径数。这

23、 说 明 从(0,0)点 到(n+1,r)点 得 非 降 路 径 根 据 就 是 否 经 过(n,i)到(n+1,i)(i=0,1,r),可分为r+1 类,根据加法法则即可得证。例3、如n,r N,有C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0)例4、如n N,有C(n,0)+C(n,1)+C(n,n)=2n组 合 含 义:这 就 是 推 论4、1、3。等 式 左 端 第1项 表 示 从(0,0)点 到P(0,n)点 得 非 降 路 径 数,第2项 表 示 从(0,0)点 到P1(1,n-1)点 得 非降 路 径 数,左 端 最 后1项 表 示

24、 从(0,0)点 到Q(n,0)点 得 非 降 路 径数。这 说 明 从(0,0)点 到PQ 上 各 格 子 点 得 非 降 路 径 总 和 为2n。也 说 明2n个 人 从(0,0)点 出 发,每 到 一 个 十 字 路 口 便 分 成 两 组,直 至 到 达PQ 线为止,能保证每个人所走得非降路径不同。例5、Vandermonde 恒等式如n,m N,rmin(m,n),有C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+C(m,r)C(n,0)证 明:等 式 左 端 表 示 从(0,0)点 到(m+n-r,r)点 得 非 降 路 径 数。从(0,0)点 到(m+n

25、-r,r)点 得 每 一 条 路 径 均 穿 过PQ 线 上 得 格 子 点(m-l,l),l=0,1,r,从(0,0)点 到(m-l,l)点 得 非 降 路 径 数 为C(m,l),再 从(m-l,l)点 到(m+n-r,r)点 得 非 降 路 径 数 为C(n,r-l),由 乘 法 法 则,从(0,0)点 出 发 经 过(m-l,l)点 到(m+n-r,r)点 得 非 降 路 径 数 为C(m,l)C(n,r-l),再由加法法则,即可得证。(m-l,l)例6、求从(0,0)点到(n,n)点得除端点外不接触直线y=x 得非降路径数？解:先 考 虑 对 角 线 下 方 得 路 径、这 种 路

26、径 都 就 是 从(0,0)点 出 发经 过(1,0)点 及(n,n-1)点 到 达(n,n)得、我 们 可 以 把 她 看 作 就 是从(1,0)点出发到达(n,n-1)点得不接触对角线得非降路径、从(1,0)点 到 达(n,n-1)点 得 所 有 得 非 降 路 径 数 就 是C(2n-2,n-1),对 其 中 得 任 意 一 条 接 触 对 角 线 得 路 径,我 们 可 以 把 她 从 最 后 离开 对 角 线 得 点(如A 点)到(1,0)点 之 间 得 部 分 关 于 对 角 线 作 一 个反 射,就 得 到 一 条 从(0,1)点 出 发 经 过A 点 到 达(n,n-1)点 得

27、 非 降 路径、(n,n)A4、3 非降路径问题例6-2反 之,任 何 一 条 从(0,1)点 出 发,穿 过 对 角线 而 到 达(n,n-1)点 得 非 降 路 径,也 可 以 通 过这 样 得 反 射 对 应 到 一 条 从(1,0)点 出 发 接 触 到对 角 线 而 到 达(n,n-1)点 得 非 降 路 径、从(0,1)点 到 达(n,n-1)点 得 非 降 路 径 数 就 是C(2n-2,n),从 而 在 对 角 线 下 方 得 路 径 数 就 是C(2n-2,n-1)-C(2n-2,n)、由 对 称 性 可 知,所 求得路径数就是2C(2n-2,n-1)-C(2n-2,n)=2

28、C(2n-2,n-1)/n=C(2n,n)/(2n-1)、例6、求从(0,0)点到(n,n)点得除端点外不接触直线y=x得非降路径数？例6、求从(0,0)点到(n,n)点得除端点外不穿过直线y=x 得非降路径数？解:采用分类处理得方法。将 所 有 从(0,0)点 到(n,n)得 非 降 路 径 分 成 两 类:穿 过 对 角 线 得 与不 穿 过 对 角 线 得。只 要 求 出 穿 过 对 角 线 得 路 径 数N1,那 么 从 总 数 中减去N1就得到所求得路径条数。任 何 一 条 从(0,0)点 到(n,n)得 穿 过 对 角 线 得 路 径 一 定 要 接 触 直线y=x+1,有 可 能

29、 接 触 多 次,但 最 后 离 开 这 条 直 线 上 得 一 点P,沿 直 线y=x+1 下 方 得 一 条 非 降 路 径 到 达(n,n)点。把 这 条 路 径 得 前 半 段,即(0,0)点 到P 点 得 部 分,以 直 线y=x+1 为 轴 进 行 翻 转,生 成 一 段 新 得 从(-1,1)点 到P 点 得 部 分 非 降 路 径。用 这 段 新 路 径 替 换 原 来 路 径 得 前半 段,就 得 到 一 条 从(-1,1)点 到(n,n)点 非 降 路 径、而 这 种 路 径 与 从中 间 穿 过 对 角 线 得 非 降 路 径 之 间 就 是 一 一 对 应 得。因 此,

30、从 点(0,0)点到(n,n)得穿过对角线得非降路径数N1=C(2n,n-1)。从点(0,0)点到(n,n)得非降路径总数为C(2n,n)条,从而得到不穿过对角线得非降路径数就是N=C(2n,n)-C(2n,n-1)=例6、求从(0,0)点到(n,n)点得除端点外不穿过直线y=x 得非降路径数？例7、求集合1,2,n上得单调递增函数得个数、解:任 给 集 合1,2,n 上 得 一 个 单 调 递 增 函 数,我 们可 以 作 一 条 对 应 得 折 线、以 横 坐 标 代 表x,纵 坐 标 代 表f(x),在 图 中 可 以 得 到n 个 格 点:(1,f(1),(2,f(x),(n,f(n)

31、、从(1,1)点 出 发 向 上 作 连 线 到(1,f(1)点、如果f(2)=f(1),则 继 续 向 右 连 线 到(2,f(2);如 果f(2)f(1),则 由(1,f(1)点 向 右 经 过(2,f(1)再 向 上 连 线 到(2,f(2)点、按照这种方法一直将折线连到(n,f(n)点、例7、求集合1,2,n上得单调递增函数得个数、解:若f(n)=n,就 将 折 线 向 右 连 到(n+1,n)点,若f(n)n,则 向 右 经(n+1,f(n)点 再 向 上 到(n+1,n)点。这 样 就得到一条从(1,1)点到(n+1,n)点得非降路径。不 难 看 出,所 求 得 单 调 递 增 函

32、 数 与 这 种 非 降 路 径 之间 存 在 着 一 一 对 应,因 此 集 合1,2,n 上 得 单 调 函数有C(2n-1,n)个、例8、从(0,0)点到(m,n)点(m n)得,要求中间经过得每一个格子点(a,b)恒满足ab关系,问有多少条路径？解:从(0,0)点 到(m,n)点 得 路 径 数 为C(m+n,m),但 需 要 排 除 碰 到 或穿 过y=x格 子 点 得 路 径 数,即 去 掉ab得 情 况。第 一 步 必 须 从(0,0)点 到(1,0)点,因 此 问 题 等 价 于 求 从(1,0)点 到(m,n)点 得 路 径 数。因 为m n,故 从(0,1)点 到(m,n)

33、点 得 路 径 必 然 穿 过y=x上 得 格 子 点。下 面 建 立 从(0,1)点 到(m,n)点 得 每 一 条 路 径,与 从(1,0)点 到(m,n)点但经过y=x上得格子点得路径时一一对应得。若 从(0,1)点 到(m,n)点 得 路 径 与y=x得 交 点 从 左 往 右 数 最 后 一个 就 是P,作 从(1,0)点 到P 点 关 于y=x得 与 上 述(0,1)点 到P 点 得 路径 对 称 得 一 条 路 径,于 就 是 从(0,1)点 到(m,n)点 得 一 条 路 径,就 有一 条 从(1,0)点 到(m,n)点 但 经 过y=x上 得 格 子 点 得 路 径 与 之

34、对 应。反 之,一 条 从(1,0)点 到(m,n)点 但 经 过y=x上 得 格 子 点 得 路 径,必存在一条从(0,1)点到(m,n)点得一条路径与之对应。故所求得路径数为C(m+n-1,n)-C(m+n-1,n-1)=(m-n)(m+n-1)!/(m!n!)例8、从(0,0)点到(m,n)点(m n)得,要求中间经过得每一个格子点(a,b)恒满足ab关系,问有多少条路径？牛顿 牛顿恒等式(4、15):恒等式(4、16):恒等式(4、17):恒等式(4、18):证 明:注 意,这 个 恒 等 式 与 前 面 得 有 一 个 很 不 一 样 得 地 方,就 就 是C(+j,j),C(+k+

35、1,k)就 是 广 义 得 二 项 式 系 数。根 据 广 义 得 二 项 式系 数 得 定 义,Pascal 公 式C(,k)=C(-1,k)+C(-1,k-1)对 实 数 和 整数k同样成立。与恒等式1类似,反复使用Pascal 公式即可得证。推论4、2、1:推论4、2、2:证明：(4、19)(4、19)(4、20)(4、21)(4、22)推论1、10、1:推论1、10、2:推论1、10、3:推论1、10、4:推论1、10、5:证明：当=1/2 时，C(,0)=1，而对于k0，有将上式代入推论4.2.1即可得证。推论4、2、1:推论4、2、2:推论4、2、3:推论4、2、4:推论4、2、5

36、:推论4、2、6:(4、19)(4、20)(4、21)(4、22)4、5多项式定理 定理4、3(多项式定理)设n就是正整数,则对一切实数x1,x2,xt有多项式定理证明 对于n 个因子中得每一个,选取m 个数x1,x2,xt中得一个并形成乘积。用这种方法得到得结果共有t n项,并且每一项都可以写成得形式,其中n1,n2,nt就是非负数,且其和为n。通过选择n 个因子中得n1个为x1,剩下得n-n1个因子中得n2个为x2,剩下得n-n1-nt-1个因子中得nt个为xt,得到项。由乘法原理得到该项出现得次数为4、5多项式定理有多少个不同得乘积项?乘积项得系数和就是多少？推论1 的展开式在合并同类项

37、以后不同的项数是证明：的展开式中每一项都可以写成 的形式，其中n1+n2+nt=n.每一项对应于该方程的一组非负整数解，所以合并同类项后不同的项数等于这个方程的非负整数解的个数推论2,其中求和就是对方程得一切非负整数解求和、证明：在多项式定理中令 即可.4、5多项式定理多项式系数 得组合意义:1、她就是多项式 中 项得系数;2、她就是多重集合SS=n1a1+n2a2+ntat 得排列数;3、如果我们把n个不同得球放到t 个不同得盒子里并且使得第一个盒子里有n1个球,第二个盒子里有n2个球,第t 个盒子里有nt个球,那么放球得方案数就是、例4、6 在(2x-3y+5z)6 得展开式中,x3yz2

38、项得系数就是多少？解:4、5多项式定理4、5多项式定理例4、7 试用组合学论证法证明恒等式 试用组合学论证法证明恒等式证明:左边就是把n个不同得球放到t 个不同得盒子里并且使得第一个盒子里有n1个球,第二个盒子里有n2个球,第t 个盒子里有nt个球得方案数、任取一个球n1,然后把放球得方法进行分类:a1放到第一个盒子得放法数就是;a1放到第二个盒子得放法数就是;a1放到t 第二个盒子得放法数就是、由加法法则等式得证、4、6基本组合计数得应用例1某保密装置须同时使用若干把不同得钥匙才能打开。现有人,每人持若干钥匙。须人到场,所备钥匙才能开锁。问至少有多少把不同得钥匙？每人至少持几把钥匙？4、6基

39、本组合计数得应用解:每人至少缺把钥匙,且每人所缺钥匙不同。故至少共有=35 把不同得钥匙。任一人对于其她人中得每人,都至少有把钥匙与之相配才能开锁。故每人至少持 20把不同得钥匙。为加深理解,举一个较简单得例子:人中人到场,所求如上。共有=6 把不同得钥匙。每人有=3 把钥匙。钥匙1 2 3 4 5 6人A B C D 4、6基本组合计数得应用例2脱氧核糖核酸(DNA)得分子由A(腺嘌呤),G(鸟嘌呤),C(胞嘧啶)和T(胸腺嘧啶)4 种碱基核糖核苷酸,以不同数目和种类排列成两条多核苷酸单链,这两条单链之间通过氢键把配对得碱基连接起来,形成双螺旋结构。连接过程总就是A 和T 配对,G 和C 配对。显然长度为n得核苷酸链共有4n 种不同方式。生物遗传信息就是由DNA 分子中4个碱基核苷酸象电报密码似得以不同得排列顺序记录下来,她载着人类得全部基因或全部遗传信息。所谓基因就就是DNA 上一小段,平均长度为900-1500 个碱基对。人得DNA 约有3109 碱基对。核糖核酸(RNA)也就是一种遗传物质,她就是由A,G,C,U(尿嘧啶)4 种碱基核苷酸排列而成得多核苷酸单链。