◆比较对应项的系数,得: (m+n, 1=C(m, IxC(n,0+C(m, OxC(n, (m+n, 2)=C(m, 2)xC(n, 0)+C(m, 1)XC(n, 1+ C(m, OXC(n, 2) 一般有: oC(m+n, r)=C(m, 0)C(n,r)+(m, I)C(n, r- 1)+…+C(m,r)Cmn,O ◆/ Vandermonde恒等式
比较对应项的系数，得： C(m+n, 1)=C(m, 1) C(n, 0)+ C(m, 0) C(n, 1) C(m+n, 2)= C(m, 2) C(n, 0)+ C(m, 1) C(n, 1)+ C(m, 0) C(n, 2) …………… 一般有： C(m+n, r)=C(m, 0)C(n, r)+C(m, 1)C(n, r- 1)+……+C(m, r)C(n, 0) /*Vandermonde恒等式*/
◆2.生成函数(母函数)的定义 对于序列 do,ai,a…,定义 a0+ax+ax2+….序列aoa,a2…生成 函数(母函数)。 ◆例如:(1+x是C(mn,O),C(m,1,Cm, 2,,C1m,m)的生成函数(母函数)
2. 生成函数 (母函数 )的定义 对于序列 a 0, a 1, a 2, ……，定义 a 0 + a 1x+a 2x 2+……为序列 a 0, a 1, a 2, …… 的生成 函数 (母函数 ) 。 例如： (1+x) n 是C(n, 0), C(n, 1), C(n, 2), ……, C(n, n) 的生成函数 (母函数 )
◆3.生成函数(母函数)的实例 有红球两只,白球、黄球各一只, 有多少种不同的组合方案?设;,w,y分别 代表红球,白球和黄球
3. 生成函数 (母函数 )的实例 有红球两只，白球、黄球各一只， 有多少种不同的组合方案？设r, w, y分别 代表红球，白球和黄球
◆解题思想: 红球不取(0=1),取1只(r=),取2只(r2); 中黄球不取(y2=1),取1只(y=y) 白球不取(w0=1),取1只(1l=) ◆根据乘法原理: 1+r+n2)(1+)(1+y =1+(r++y)+(r2+ny+n+y)+(y+r+ny) ◆歌一个球的组合数为3:r,,y ◆取两个球的组合数为4;p2,my,m, ◆取三个球的组合数为:r3y,F,my ◆取四个球的组合数为1:r2
解题思想： 红球不取（r0=1），取1只（r1=r），取2只（r2）； 黄球不取（y0=1），取1只（y1=y）， 白球不取（w0=1），取1只（w1=w）， 根据乘法原理： (1+r+r2)(1+w)(1+y) =1+(r+w+y)+(r2+ry+rw+yw)+(r2y+r2w+rwy) +r2yw 取一个球的组合数为3： r，w，y 取两个球的组合数为4： r2，ry，rw，yw 取三个球的组合数为3： r2y，r2w，rwy 取四个球的组合数为1： r2yw
许多组合学计数间题依赖于一个整数参数n。 这个参数n常常表示问题中某个基本集或多重 集的大小、组合的大小、排列中的位置等。因 此一个计数问题常常不是一个孤立的问题而是 系列的单个问题。 ◆例:令h表示{1,2,…,n的排列数。h2=n 于是得到数列 hh. h hn…。对于这个数 列,一般项hn=n!,通过选择n为一个特定的整 数可以得到这个问题的一个实例。如:h5=5
许多组合学计数问题依赖于一个整数参数 n 。 这个参数 n常常表示问题中某个基本集或多重 集的大小、组合的大小、排列中的位置等。因 此一个计数问题常常不是一个孤立的问题而是 一系列的单个问题。 例：令 h n表示{1, 2, …, n}的排列数。 h n=n! ， 于是得到数列 h 0, h 1, h 2, …, h n, …。对于这个数 列，一般项 h n=n!，通过选择 n为一个特定的整 数可以得到这个问题的一个实例。如： h 5=5!