1、8.3二项式定理与组合恒等式二项式定理与组合恒等式8.3.1 二项式定理二项式定理8.3.2 组合恒等式组合恒等式8.3.3 非降路径问题非降路径问题1/261二项式定理二项式定理定理定理8.5 设设 n 是正整数，对一切是正整数，对一切 x 和和 y 证实方法证实方法:数学归纳法、组合分析法数学归纳法、组合分析法.证证 当乘积被展开时其中项都是下述形式：当乘积被展开时其中项都是下述形式：xi yn i,i=0,1,2,n.而组成形如而组成形如 xiyn i 项，必须从项，必须从n 个个和和(x+y)中选中选 i 个提供个提供 x，其它，其它 n i 个提供个提供 y.所以，所以，xiyn i
2、 系数是系数是 ，定理得证，定理得证.2/262二项式定理应用二项式定理应用例例1 求在求在(2x3y)25展开式中展开式中x12y13系数系数.解解 由二项式定理由二项式定理令令i=13 得到展开式中得到展开式中x12y13系数，即系数，即 3/263组合恒等式组合恒等式递推式递推式证实方法：公式代入、组合分析证实方法：公式代入、组合分析应用：应用：1式用于化简式用于化简2式用于求和时消去变系数式用于求和时消去变系数3式用于求和时拆项（两项之和或者差），然后合并式用于求和时拆项（两项之和或者差），然后合并4/264组合恒等式组合恒等式变下项求和变下项求和证实公式公式4.方法：二方法：二项式定
3、理或者式定理或者组合分析合分析.设S=1,2,n，下面，下面计数数S 全部子集全部子集.一个方法就是分一个方法就是分类处理，理，n元集合元集合 k子集个数是子集个数是依据加法法则，子集总数是依据加法法则，子集总数是另一个方法是分步处理，为组成另一个方法是分步处理，为组成 S 子集子集A，每个元素有，每个元素有 2 种选择，依据乘法法则，子集总数是种选择，依据乘法法则，子集总数是2n.5/265恒等式求和恒等式求和变系数和变系数和证实方法：证实方法：二项式定理、级数求导二项式定理、级数求导 其它组合恒等式代入其它组合恒等式代入6/266证实公式证实公式6(二项式定理二项式定理+求导求导)7/26
4、7证实公式证实公式7(已知恒等式代入已知恒等式代入)8/268恒等式恒等式变上项求和变上项求和证实 组合分析合分析.令令S=a1,a2,an+1为n+1元集合元集合.等式右等式右边是是 S k+1子集数子集数.考考虑另一个分另一个分类计数方数方法法.将全部将全部k+1元子集分成以下元子集分成以下n+1类：第第1类：含：含a1,剩下剩下 k个元素取自个元素取自a2,an+1 第第2类：不含：不含a1,含含a2,剩下剩下k个元素取自个元素取自 a3,an+1 不含不含a1,a2,an,含含an+1,剩下剩下k个元素取自空集个元素取自空集由加法法则公式得证由加法法则公式得证9/269恒等式恒等式乘积
5、转换式乘积转换式证实方法：组合分析证实方法：组合分析.n 元集中选取元集中选取 r 个元素，然后在这个元素，然后在这 r 个元素中再选个元素中再选 k个个元素元素.不一样不一样 r 元子集可能选出相同元子集可能选出相同 k子集，比如子集，比如 a,b,c,d,e a,b,c,d b,c,d b,c,d,e b,c,d 重复度为：重复度为：应用：将变下限应用：将变下限 r 变成常数变成常数 k，求和时提到和号外面，求和时提到和号外面.10/2610恒等式恒等式积之和积之和关系关系证明思明思绪：考：考虑集合集合A=a1,a2,am，B=b1,b2,bn.等等式右式右边计数了从数了从这两个集合中两个
6、集合中选出出r个元素方法个元素方法.将将这些些选法按照含有法按照含有A中元素个数中元素个数 k 进行分行分类，k=0,1,r.然后使用加法法然后使用加法法则.11/2611组合恒等式解题方法小结组合恒等式解题方法小结证实方法：证实方法：已知恒等式带入已知恒等式带入 二项式定理二项式定理 幂级数求导、积分幂级数求导、积分 归纳法归纳法 组合分析组合分析 求和方法：求和方法：Pascal公式公式 级数求和级数求和 观察和结果，然后使用归纳法证实观察和结果，然后使用归纳法证实 利用已知公式利用已知公式12/2612非降路径问题非降路径问题基本计数模型基本计数模型限制条件下非降路径数限制条件下非降路径
7、数非降路径模型应用非降路径模型应用证实恒等式证实恒等式单调函数计数单调函数计数栈输出栈输出 13/2613基本计数模型基本计数模型(0,0)到到(m,n)非降路径数：非降路径数：C(m+n,m)(a,b)到到(m,n)非降路径数：非降路径数：等于等于(0,0)到到(m a,n b)非降路径数非降路径数(a,b)经过经过(c,d)到到(m,n)非降路径数：乘法法则非降路径数：乘法法则14/2614限制条件非降路径数限制条件非降路径数从从(0,0)到到(n,n)不接触对角线非降路径数不接触对角线非降路径数 NN1：从从(0,0)到到(n,n)下不接触对角下不接触对角 线非降路径数线非降路径数N2：
8、从从(1,0)到到(n,n 1)下不接触对角下不接触对角 线非降路径数线非降路径数N0:从从(1,0)到到(n,n 1)非降路径数非降路径数N3:从从(1,0)到到(n,n 1)接触对角线接触对角线 非降路径数非降路径数关系关系:N=2N1=2N2=2N0 N3 15/2615一一对应一一对应N3:从从(1,0)到到(n,n 1)接触对角线接触对角线 非降路径数非降路径数N4:从从(0,1)到到(n,n 1)无限制条件无限制条件 非降路径数非降路径数关系关系:N3=N4 16/2616应用应用证实恒等式证实恒等式例例2 证实证实 证：证：计数计数(0,0)到到(m+n r,r)非降路径数非降路
9、径数按照按照 k分类，再分步分类，再分步.(0,0)到到(m k,k)路径数，路径数，(m k,k)到到(m+n r,r)路路径数径数17/2617应用应用单调函数计数单调函数计数例例3 A=1,2,m,B=1,2,n，N1:B上单调递增函数个上单调递增函数个 数是数是(1,1)到到(n+1,n)非降路径数非降路径数N:B上单调函数个数上单调函数个数 N=2N1N2:A到到B单调递增函数个单调递增函数个 数是从数是从(1,1)到到(m+1,n)非降路径数非降路径数 N:A到到B单调函数个数，单调函数个数，N =2N2 严格单调递增函数、递减函数个数都是严格单调递增函数、递减函数个数都是C(n,
10、m)18/2618函数计数小结函数计数小结A=1,2,m,B=1,2,nf:AB19/2619应用应用栈输出计数栈输出计数例例4 将将1,2,n按照次序输入栈按照次序输入栈,有多少个不一样输出序列？有多少个不一样输出序列？解：将进栈、出栈分别记作解：将进栈、出栈分别记作 x,y,出栈序列是出栈序列是n个个x，n个个y排列，排列，排列中任何前缀排列中任何前缀 x 个数不少于个数不少于y 个数个数.等于从等于从(0,0)到到(n,n)不穿过对角线非降路径数不穿过对角线非降路径数.实例：实例：n=5 x,x,x,y,y,x,y,y,x,y 进进,进进,进进,出出,出出,进进,出出,出出,进进,出出
11、3,2,4,1,520/2620应用应用栈输出计数栈输出计数(续续)N:堆栈输出个数堆栈输出个数N:(0,0)到到(n,n)不不 穿过对角线穿过对角线 非降路径数非降路径数N0:(0,0)到到(n,n)非降路径总数非降路径总数N1:(0,0)到到(n,n)穿过对角线穿过对角线 非降路径数非降路径数N2:(1,1)到到(n,n)非降路径数非降路径数.关系：关系：N=N =N0 N1,N1=N221/26218.4.1 多项式定理多项式定理8.4.2 多项式系数多项式系数8.4 多项式定理多项式定理22/2622多项式定理多项式定理.定理定理8.6 设设n为正整数，为正整数，xi为实数，为实数，i
12、=1,2,t.求和是对满足方程求和是对满足方程n1+n2+nt=n一切非负整数解求一切非负整数解求在在n个因式中个因式中选n1个因式个因式贡献献x1,从剩下从剩下n n1个因式个因式选n2个因式个因式贡献献x2,从剩下从剩下n n1 n2 nt 1个因式中个因式中选 nt个因式个因式贡献献 xt.证实证实 展开式中项展开式中项是以下组成是以下组成:23/2623推论推论推论推论1 多项式展开式中不一样项数为方程多项式展开式中不一样项数为方程 非负整数解个数非负整数解个数 C(n+t 1,n)推论推论2 例例1 求求(2x1 3x2+5x3)6 中中 x13x2x32 系数系数.解解 由多项式定理得由多项式定理得24/2624多项式系数多项式系数组合意义组合意义 多项式系数多项式系数 多重集多重集 S=n1 a1,n2 a2,nt at 全排列数全排列数 n个不一样球放到个不一样球放到 t 个不一样盒子使得第一个盒子个不一样盒子使得第一个盒子 含含n1个球，第二个盒子含个球，第二个盒子含n2个球，个球，第，第 t 个盒子个盒子 含含 nt 个球方案数个球方案数25/2625多项式系数多项式系数(续续)恒等式恒等式推论推论2 2定理定理8.68.6组合证实组合证实26/2626
