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

组合数学课件第四章二项式系数第1页，共58页，2023年，2月20日，星期二目录（1）第1章什么是组合数学1.1引例 1.2组合数学研究对象、内容和方法第2章鸽巢原理2.1鸽巢原理：简单形式2.2鸽巢原理：加强形式2.3Ramsey定理2.4鸽巢原理与Ramsey定理的应用本章小结习题第3章排列与组合3.1两个基本的计数原理3.2集合的排列与组合3.3多重集的排列与组合本章小结习题第四章二项式系数4.1二项式定理4.2组合恒等式4.3非降路径问题4.4牛顿二项式定理4.5多项式定理4.6基本组合计数的应用本章小结习题第五章包含排斥原理5.1包含排斥原理5.2多重集的r-组合数5.3错位排列5.4有限制条件的排列问题5.5有禁区的排列问题本章小结习题目录第2页，共58页，2023年，2月20日，星期二目录（2）

第六章递推关系6.1Fibonacci数列6.2常系数线性齐次递推关系的求解6.3常系数线性非齐次递推关系的求解6.4用迭代和归纳法求解递推关系本章小结习题第七章生成函数7.1生成函数的定义和性质7.2多重集的r-组合数7.3正整数的划分7.4指数生成函数与多重集的排列问题7.5Catalan数和Stiring数本章小结习题

第八章Polya定理8.1置换群中的共轭类与轨道8.2Polya定理的特殊形式及其应用本章小结习题**********************课程总结第3页，共58页，2023年，2月20日，星期二第4章二项式定理教学目标：1．掌握二项式定理、证明方法及其应用；2．掌握推广的二项式定理；3．掌握多项式定理、证明方法及其应用；4．理解一些组合恒等式的意义及其证明方法；5．非降路径问题的组合意义及应用；重点：二项式定理、多项式定理证明方法及其应用；难点：一些组合恒等式证明方法，非降路径问题组合意义及应用。第4页，共58页，2023年，2月20日，星期二§4.1二项式定理1.二项式系数组合数C(n,k)或者也叫二项式系数.2.组合数的定义第4章二项式定理()nk第5页，共58页，2023年，2月20日，星期二3.组合数的一些恒等式（1）对称式（2）抽取式（3）Pascal公式§4.1二项式定理(4.1)(4.2)(4.3)第6页，共58页，2023年，2月20日，星期二§4.2组合恒等式及其含义抽取式(4.2)§4.1二项式定理抽取式（4.2）：如n,k∈N，有C(n,k)=(n/k)C(n-1,k-1)证明：从n个元素中取k个的组合可先从n个元素中取1个，再从剩下的n-1个元素中选择k-1个，组合数为C(n-1,k-1)。选出的k个元素都有可能被第一次选中，因是组合，故重复度为k。得证。或通过计算证明：证：某班有n名同学，要选出k位班委会成员，再选1名作书记，这名书记不可以是班委会成员，问有多少种不同的方案？证明：从n名同学中选出k位组成班委，在k位班委中选1人做班长，问有多少种方法？第7页，共58页，2023年，2月20日，星期二§4.1二项式定理§4.1二项式定理定理4.1证明：因为(x+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)又称二项式系数。第8页，共58页，2023年，2月20日，星期二§4.1二项式定理推论1§4.1二项式定理四个推论推论4.1.1：推论4.1.2：推论4.1.3：证明：在推论4.1.2中令x=1，即可得证。利用组合分析，等式左端相当于从A={an}中任意选择k(0≤k≤n)个元素的所有可能数目，即对n个元素，每一个都有被选择和不被选择的可能，总的可能数为2n。另外，该等式还表明A的所有子集个数为2n。(4.4)n元集合的所有子集个数是2n

第9页，共58页，2023年，2月20日，星期二§4.1二项式定理推论2§4.1二项式定理四个推论推论4.1.1：推论4.1.2：推论4.1.3：推论4.1.4：证明：在推论4.1.2中令x=-1，即可得证。另外，该等式还表明A={an}的偶数子集个数和奇数子集个数相等。(4.5)(4.5)’即n元集合的偶子集个数与奇子集个数相等

第10页，共58页，2023年，2月20日，星期二§4.2组合恒等式及其含义恒等式(4.6)§4.2组合恒等式及其含义恒等式(4.6)

：证明：考虑盒子1中有n个有区别的球，从中取一个球放入盒子2中，再取任意多个球放入盒子3中。等式左端表示先从盒子1中取k(k=1,2,…,n)个球，再从中取一个放入盒子2中，剩下的k-1个球放入盒子3中。等式右端表示先从盒子1中取一个放入盒子2中，剩下的n-1个球是否放入盒子3中均有两种可能。显然两种取法结果是一样的。得证。或通过计算证明：第11页，共58页，2023年，2月20日，星期二§4.2组合恒等式及其含义恒等式(4.6)§4.2组合恒等式及其含义恒等式(4.6)

：证明：证法3

由二项式定理有对上式两边微商得然后令x=1得注：如令x=-1，可证明下面恒等式。第12页，共58页，2023年，2月20日，星期二§4.2组合恒等式及其含义恒等式(4.6)§4.2组合恒等式及其含义类（4.6）恒等式(习题4.7)：证明：将等式两边对x微分得在上式中，令x=-1得即得证。第13页，共58页，2023年，2月20日，星期二§4.2组合恒等式及其含义恒等式(4.6)§4.2组合恒等式及其含义恒等式(习题4.8积分方法)：证明：将等式两边对x从0到1积分得即得证。第14页，共58页，2023年，2月20日，星期二§4.2组合恒等式及其含义恒等式(4.7)§4.2组合恒等式及其含义类恒等式(4.7)’

：恒等式(4.7)：证明：将等式两边对x微分得将等式两边同乘以x后再对x微分得在上式中，令x=1得得证。注：如令x=-1，即可证明另一恒等式(4.7)’

。第15页，共58页，2023年，2月20日，星期二§4.2组合恒等式及其含义恒等式(4.8)§4.2组合恒等式及其含义恒等式(4.8)：如n,l,r∈N,l≥r，有C(n,l)C(l,r)=C(n,r)C(n-r,l-r)从n个候选人中，选出l个常委，再选出r位政治局常委，选法的个数？证明：等式的左端可看作是先从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个元素可以重复出现的次数就是包含它们的l元子集的个数，而这种l元子集的其余l-r个元素可以取自n元集的n-r个元素,所以这种l元子集有个.综上所述，通过先选l个元素然后再选r个元素的选法应该有C(n,r)C(n-r,l-r)种。得证。或通过计算证明：第16页，共58页，2023年，2月20日，星期二恒等式(4.9)：Vandermonde恒等式，如n,m∈N且r≤min(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)§4.2组合恒等式及其含义恒等式(4.9)§4.2组合恒等式及其含义证明：设A={am},B={bn},且A∩B=Φ，则A∪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的系数即可得证。第17页，共58页，2023年，2月20日，星期二§4.2组合恒等式及其含义恒等式(4.10)§4.2组合恒等式及其含义恒等式(4.10)：恒等式(4.10特例)：恒等式(4.9)’：Vandermonde恒等式，如n,m∈N且r≤min(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)’：第18页，共58页，2023年，2月20日，星期二§4.2组合恒等式及其含义恒等式(4.11)§4.2组合恒等式及其含义恒等式(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，相当于从剩下的k个元素中选出k个元素的组合，再加上an-k+2而得到，组合数为C(k,k)；注意，i＜k时，C(k,k)=0。由加法法则得或对固定的k，对n使用归纳法，当n=0时，有可见，当n=0时，等式成立。如对任意n等式成立，则有可见等式对n+1也成立。由归纳原理，得证。第19页，共58页，2023年，2月20日，星期二§4.2组合恒等式及其含义恒等式(4.12)§4.2组合恒等式及其含义恒等式(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个元素中不包含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)+…+C(n+1,1)+C(n,0)第20页，共58页，2023年，2月20日，星期二§4.2组合恒等式及其含义恒等式(4.12)§4.2组合恒等式及其含义恒等式(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的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)第21页，共58页，2023年，2月20日，星期二§4.2组合恒等式证明方法§4.2组合恒等式及其含义常用的证明方法

数学归纳法二项式系数公式，特别是Pascal公式比较级数展开式中的系数（二项式定理或母函数法）积分微分法组合分析法第22页，共58页，2023年，2月20日，星期二§4.2组合恒等式及其含义例4.1§4.2组合恒等式及其含义例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).第23页，共58页，2023年，2月20日，星期二在式（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.

在这个等式中每相邻两项之差就是等差级数的项，称这个等式叫做二阶等差级数求和公式.如果令r=3，则有

1+C(4,3)+C(5,3)+…+C(n+2,3)=C(n+3,4).其中每相邻两项之差就是二阶等差级数的项，把这个等式叫做三阶等差级数的求和公式.§4.2组合恒等式及其含义第24页，共58页，2023年，2月20日，星期二§4.2组合恒等式及其含义例4.2§4.2组合恒等式及其含义例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=2[C(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=6[C(1,3)+C(2,3)+…+C(n,3)]+6[C(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)/2]2.第25页，共58页，2023年，2月20日，星期二§4.2组合恒等式及其含义例4.3§4.2组合恒等式及其含义例4.3证明若p是不等于2的素数，则当C(2p,p)被p除时余数是2.证明在恒等式(4.10)中令m=n=p得可以证明，如果p为素数且0<k<p，则p|C(p,k).因为由组合数C(p,k)的计算公式知k!整除p(p-1)…(p-k+1).又由于p是素数且k<p，若k>1,则k!|(p-1)…(p-k+1)；若k=1,也有k!|(p-1)…(p-k+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，故当p>2时，C(2p,p)除以p的余数是2.(4.14)第26页，共58页，2023年，2月20日，星期二例4.4证明：从n名女同学和n名男同学中，选出n名同学组成一个社团，其中一人担任社团主席，且必须由女同学担任，问有多少种选法？§4.2组合恒等式及其含义第27页，共58页，2023年，2月20日，星期二§4.3非降路径问题引例§4.3非降路径问题非降路径问题引例、非降路径问题从(0,0)点出发沿X轴或Y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？解：设从(0,0)点水平方向向前进一步为x，垂直方向向上进一步为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)。Y(m-1,n)(m,n)(m,n-1)(0,0)X≈≈≈…≈多重集S={∞*a1,∞*a2,…,∞*ak}的r−组合数F(k,r)=C(k+r-1,r)第28页，共58页，2023年，2月20日，星期二§4.3非降路径问题例2§4.3非降路径问题非降路径问题

由引例，我们已经知道，从(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)=C(m+n-1,m)+C(m+n-1,m-1)这是Pascal公式的另一种形式。例2、非降路径问题从(0,0)点出发沿X轴或Y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？Y(m-1,n)(m,n)(m,n-1)(0,0)X≈≈≈…≈第29页，共58页，2023年，2月20日，星期二§4.3非降路径问题例3§4.3非降路径问题格路问题证明：这是上一小节的组合恒等式。等式左端表示从(0,0)点到(n+1,r)点的非降路径数，右端第1项表示从(0,0)点到(n,r)点的路径数，右端第2项表示从(0,0)点到(n,r-1)点的非降路径数，…，右端最后1项表示从(0,0)点到(n,0)点的非降路径数。这说明从(0,0)点到(n+1,r)点的非降路径根据是否经过(n,i)到(n+1,i)(i=0,1,…,r)，可分为r+1类，根据加法法则即可得证。Y(n,r)(n+1,r)

(0,0)(n,0)

X≈≈≈…≈例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)第30页，共58页，2023年，2月20日，星期二

≈≈…≈Y

P(0,n)

P1(1,n-1)X(0,0)Q(n,0)§4.3非降路径问题例4§4.3非降路径问题非降路径问题例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项表示从(0,0)点到Q(n,0)点的非降路径数。这说明从(0,0)点到PQ上各格子点的非降路径总和为2n。也说明2n个人从(0,0)点出发，每到一个十字路口便分成两组，直至到达PQ线为止，能保证每个人所走的非降路径不同。第31页，共58页，2023年，2月20日，星期二§4.3非降路径问题例5§4.3非降路径问题非降路径问题例5、Vandermonde恒等式如n,m∈N,r≤min(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-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)，再由加法法则，即可得证。Y

P(m-r,r)(m+n-r,r)

(0,0)Q(m,0)X≈

≈≈…≈(m-l,l)第32页，共58页，2023年，2月20日，星期二§4.3非降路径问题例6-1§4.3非降路径问题非降路径问题例6、求从(0,0)点到(n,n)点的除端点外不接触直线y=x的非降路径数？解：先考虑对角线下方的路径.这种路径都是从(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)点的非降路径.

Y

(n,n-1)

(0,1)

(0,0)(1,0)Q(n,0)X≈

≈≈…

≈(n,n)A第33页，共58页，2023年，2月20日，星期二§4.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).由对称性可知，所求的路径数是

2[C(2n-2,n-1)-C(2n-2,n)]=2C(2n-2,n-1)/n=C(2n,n)/(2n-1).§4.3非降路径问题非降路径问题例6、求从(0,0)点到(n,n)点的除端点外不接触直线y=x的非降路径数？第34页，共58页，2023年，2月20日，星期二§4.3非降路径问题非降路径问题例6、求从(0,0)点到(n,n)点的除端点外不穿过直线y=x的非降路径数？解：采用分类处理的方法。将所有从(0,0)点到(n,n)的非降路径分成两类：穿过对角线的与不穿过对角线的。只要求出穿过对角线的路径数N1，那么从总数中减去N1就得到所求的路径条数。任何一条从(0,0)点到(n,n)的穿过对角线的路径一定要接触直线y=x+1,有可能接触多次，但最后离开这条直线上的一点P，沿直线y=x+1下方的一条非降路径到达(n,n)点。把这条路径的前半段，即(0,0)点到P点的部分，以直线y=x+1为轴进行翻转，生成一段新的从(-1,1)点到P点的部分非降路径。用这段新路径替换原来路径的前半段，就得到一条从(-1,1)点到(n,n)点非降路径.而这种路径与从中间穿过对角线的非降路径之间是一一对应的。因此，从点(0,0)点到(n,n)的穿过对角线的非降路径数N1=C(2n,n-1)。第35页，共58页，2023年，2月20日，星期二

从点(0,0)点到(n,n)的非降路径总数为C(2n,n)条，从而得到不穿过对角线的非降路径数是N=C(2n,n)-C(2n,n-1)=§4.3非降路径问题非降路径问题例6、求从(0,0)点到(n,n)点的除端点外不穿过直线y=x的非降路径数？第36页，共58页，2023年，2月20日，星期二§4.3非降路径问题例7-1§4.3非降路径问题非降路径问题例7、求集合{1,2,…,n}上的单调递增函数的个数.解：任给集合{1,2,…,n}上的一个单调递增函数，我们可以作一条对应的折线.以横坐标代表x,纵坐标代表f(x),在图中可以得到n个格点：(1,f(1)),(2,f(x)),…,(n,f(n)).从(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))点.第37页，共58页，2023年，2月20日，星期二§4.3非降路径问题例7-2§4.3非降路径问题非降路径问题例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)点的非降路径。

不难看出，所求的单调递增函数与这种非降路径之间存在着一一对应，因此集合{1,2,…,n}上的单调函数有C(2n-1,n)个.

第38页，共58页，2023年，2月20日，星期二§4.3非降路径问题例8-1§4.3非降路径问题非降路径问题例8、从(0,0)点到(m,n)点(m≥n)的，要求中间经过的每一个格子点(a,b)恒满足a＞b关系，问有多少条路径？解：从(0,0)点到(m,n)点的路径数为C(m+n,m)，但需要排除碰到或穿过y=x格子点的路径数，即去掉a≤b的情况。第一步必须从(0,0)点到(1,0)点，因此问题等价于求从(1,0)点到(m,n)点的路径数。因为m≥n，故从(0,1)点到(m,n)点的路径必然穿过y=x上的格子点。下面建立从(0,1)点到(m,n)点的每一条路径，与从(1,0)点到(m,n)点但经过y=x上的格子点的路径时一一对应的。

Y

(m,n)

(0,1)(0,0)(1,0)Q(m,0)X≈

≈≈…

≈第39页，共58页，2023年，2月20日，星期二§4.3非降路径问题例8-2§4.3非降路径问题非降路径问题

Y

(m,n)

(0,1)(0,0)(1,0)Q(m,0)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上的格子点的路径与之对应。反之，一条从(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)恒满足a＞b关系，问有多少条路径？第40页，共58页，2023年，2月20日，星期二§4.4牛顿二项式定理§4.4牛顿二项式定理定理4.2定义4.1广义二项式系数为：牛顿二项式定理：牛顿第41页，共58页，2023年，2月20日，星期二§4.4牛顿二项式定理

§4.4牛顿二项式定理恒等式恒等式(4.15)：恒等式(4.16)：恒等式(4.17)：第42页，共58页，2023年，2月20日，星期二§4.4牛顿二项式定理

§4.4牛顿二项式定理恒等式恒等式(4.18)：证明：注意，这个恒等式与前面的有一个很不一样的地方，就是C(α+j,j),C(α+k+1,k)是广义的二项式系数。根据广义的二项式系数的定义，Pascal公式C(α,k)=C(α-1,k)+C(α-1,k-1)对实数α和整数k同样成立。与恒等式1类似，反复使用Pascal公式即可得证。第43页，共58页，2023年，2月20日，星期二§4.4牛顿二项式定理推论1§4.1牛顿二项式定理六个推论推论4.2.1：推论4.2.2：证明：(4.19)第44页，共58页，2023年，2月20日，星期二(4.19)(4.20)(4.21)(4.22)§4.4牛顿二项式定理推论2§4.1牛顿二项式定理六个推论推论1.10.1：推论1.10.2：推论1.10.3：推论1.10.4：推论1.10.5：证明：当α=1/2时，C(α,0)=1，而对于k＞0，有将上式代入推论4.2.1即可得证。第45页，共58页，2023年，2月20日，星期二§4.4牛顿二项式定理推论3§4.1牛顿二项式定理六个推论推论4.2.1：推论4.2.2：推论4.2.3：推论4.2.4：推论4.2.5：推论4.2.6：(4.19)(4.20)(4.21)(4.22)第46页，共58页，2023年，2月20日，星期二§4.5多项式定理定理4.3（多项式定理）设n是正整数，则对一切实数x1,x2,…,xt有§4.5多项式定理第47页，共58页，2023年，2月20日，星期二多项式定理证明

对于n个因子中的每一个，选取m个数x1,x2,…,xt中的一个并形成乘积。用这种方法得到的结果共有tn项，并且每一项都可以写成的形式，其中n1,,n2,,…，nt是非负数，且其和为n。通过选择n个因子中的n1个为x1，剩下的n-n1个因子中的n2个为x2,…,剩下的n-n1-…-…-nt-1个因子中的nt个为xt,得到项。由乘法原理得到该项出现的次数为§4.5多项式定理第48页，共58页，2023年，2月20日，星期二§4.5多项式定理有多少个不同的乘积项?乘积项的系数和是多少？§4.5多项式定理推论1的展开式在合并同类项以后不同的项数是证明：的展开式中每一项都可以写成的形式，其中n1+n2+…+nt=n.每一项对应于该方程的一组非负整数解，所以合并同类项后不同的项数等于这个方程的非负整数解的个数推论2，其中求和是对方程的一切非负整数解求和.证明：在多项式定理中令即可.第49页，共58页，2023年，2月20日，星期二§4.5多项式定理多项式系数的组合意义：1.它是多项式中项的系数；2.它是多重集合S={n1·a1+n2·a2+…+nt·at}的排列数；3.如果我们把n个不同的球放到t个不同的盒子里并且使得第一个盒子里有n1个球，第二个盒子里有n2个球，…，第t个盒子里有nt个球，那么放球的方案数是.§4.5多项式定理第50页，共58页，2023年，2月20日，星期二