第二章多项式定理及其应用 复的组合我们用Cn表示这种组合的种数,其个数为m (n-m)m 事实上,我们可以把这种组合看作是从n个元素中不重复地取出m个元素,然后再把其中只是排列顺 序不同的排列看成一个元素即可.又m个元素的排列数是m!,所以我们考察的组合数为 m!(n-m)!m! 例如,设S={2,3,4}.计算从中取出2个不同的元素进行组合的方法数直接列出 12,13,14,23,24,34, 共有6种 2、从n个不相同的元素里,每次取出m个元素(可以重复)的组合.这样的组合叫做相异元素可重复 的组合,其个数为Cnm 例如,设S={,2,3,4}.计算从中取出2个元素进行组合的方法数.直接列出 12,13,14,23,24,34,11,22,33,44 共有10种 下面我们证明从n个不相同的元素里,每次取出m个元素(可以重复)的组合个数为Cmm=1 事实上,我们只须指出从集合{1,2,…,n}中取出m个整数可重复的组合所构成的集合与从集合 1,2,…,n+m-1}中取出m个整数不可以重复的组合所构成的集合之间有一个一一映射即可 设从集合{,2…,川}中取出的一个可重复的组合为{a1,a2,am},并且由于组合与取出的元素顺序 无关,所以不妨设它满足a1≤a2≤…≤an,则我们可以如下定义映射 f:{a1,a2…,am}{a1+0,a2+1…,an+m-1} 容易验证a1+0<a2+1<…<an+m-1,即集合{a1+0,a2+1,…,am+m-1}是从集合 1,2,…,n+m-1}中取出m个整数不可以重复的一个组合 另一方面,我们也可以如下定义映射∫的逆映射 g:{b:b2灬…,bn}→{b1-0,b2-1,,bn-(m-1)}, 其中{b1,b2灬…,bn}∈1,2,…,n+m-1},并且有b<b2<…<bn,则我们容易验证有 b1-0,b2-1,…,bm-(m-1)}c{2…,n},而且它满足b1-0≤b2-1≤…≤bn-(m-1),即应该有集 合{b-0,b2-1,…,bn-(m-1)}是从集合{12,…,m中取出的一个可重复的组合 最后,由于=gf=1,所以,从集合{,2,…,n}中取出m个整数可重复的组合所构成的集合,与从集 18
第二章 多项式定理及其应用 复的组合.我们用 表示这种组合的种数,其个数为 m Cn ( ) !! ! mmn n − . 事实上,我们可以把这种组合看作是从 个元素中不重复地取出 个元素,然后再把其中只是排列顺 序不同的排列看成一个元素即可.又 个元素的排列数是 ,所以我们考察的组合数为 n m m m! ! ! ( )! ! m Pn n m n mm = − . 例如, 设 S = }4,3,2,1{ .计算从中取出 2 个不同的元素进行组合的方法数.直接列出 12,13,14,23,24,34, 共有 6 种. 2、从 n 个不相同的元素里,每次取出 m 个元素（可以重复）的组合.这样的组合叫做相异元素可重复 的组合,其个数为 . m C mn −+ 1 例如, 设 S = }4,3,2,1{ .计算从中取出 2 个元素进行组合的方法数.直接列出 12,13,14,23,24,34,11,22,33,44, 共有 10 种. 下面我们证明从 n 个不相同的元素里,每次取出 m 个元素（可以重复）的组合个数为 . m C mn −+ 1 事实上,我们只须指出从集合{1,2,…, }中取出 个整数可重复的组合所构成的集合与从集合 {1,2,…, }中取出 个整数不可以重复的组合所构成的集合之间有一个一一映射即可. n m n m+ −1 m 设从集合{1 中取出的一个可重复的组合为{ },并且由于组合与取出的元素顺序 无关,所以不妨设它满足 ,2, , } " n aaa m ,...,, 21 ≤ ≤≤ aaa m ... 21 .则我们可以如下定义映射 f : { } { aaa m ,...,, 21 6 1 + 2 + ,...,1,0 m + maaa −1}. 容易验证 ,即集合{ 1 2 0 1 m a a am + < +< < + − " 1 1 + 2 + ,...,1,0 m maaa −+ 1 }是从集合 {1,2,…, n m+ −1}中取出 m 个整数不可以重复的一个组合. 另一方面,我们也可以如下定义映射 f 的逆映射 g :{ } { bbb m ,...,, 21 6 1 − 2 − m − mbbb − )1(,...,1,0 }, 其中{ 21 ,...,, bbb m } ⊂ {1,2,…, n m+ −1 }, 并 且 有 1 2 m bb b < < < " ,则我们容易验证有 { 1 2 m −−− mbbb − )1(,...,1,0 }⊂ {1,2, , } " n ,而且它满足 1 − ≤ bb 2 − ≤ ≤ m mb −− )1(...10 ,即应该有集 合{ 1(,...,1,0 ) }是从集合{1 中取出的一个可重复的组合. 1 2 m mbbb −−−− ,2, , } " n 最后,由于 = gffg =1,所以,从集合{1,2, , } " n 中取出 m 个整数可重复的组合所构成的集合,与从集 - 18 -
第二章多项式定理及其应用 合{1,2,…,n+m-1}中取出m个整数不可以重复的组合所构成的集合之间有一个一一映射 我们研究组合的主要目的之一是求出根据已知条件所能作出的不同组合的种数.下面我们不加证明地 列出两个经常用到的组合数的简单关系等式 (1) Cn=C Ck+C 例1.1从8×8的棋盘中取出一个由三个小方格组成的“L”型如图 问共有多少种不同的取法 解一个由四个小方格组成的“田”字形中可以取出4个“L”形,因此我们只需考察棋盘上可以取出 多少个“田”字形由于每个“田”字形的中心是棋盘内横线与纵线的一个交点(不包括边界点);反过来 每个位于棋盘内部的交点,它四周的小方格恰好形成一个“田”字形图案,因此映射∫:“田”字形→“田” 字形中心,它是棋盘上所有可取出的小方格组成的“田”形集合到棋盘内每个横线与纵线的交点集的双射 (一一映射).易知,棋盘内的交点数共有(9-2)×(9-2)=49(个),所以棋盘上可取出49个“田”字形 而一个“田”字形对应着4个“L”形,故棋盘上共可取出49×4=196个“L”形 例1.2在直角坐标平面的第一象限中,把坐标都是整数的点按以下方法编号:(00)点第一号;(1,0) 点第2号;(1,1)点第3号;(0,1)点第4号;(0,2)点第5号;(1,2)点第6号;(2,2)点第7号;(2,1) 点第8号:(2,0)点第9号…(如图),按图中箭头的顺序问第2000号点的坐标是什么? 解区域0≤x≤k0≤y≤k上的格点个数为(k+1)2.又442=1936<2000<2025=452所以编号为 2000的点的纵、横坐标中至少有一个是44因为44是偶数所以应从点(044)往右,又因为 2000-442=64>44所以编号为2000的点的横坐标是44坐标是44-(64-45)=25即所求的点的坐标 是(44,25) 例13我们知道从含n个元素的集合S={2…m中取出2个元素的组合数为C2=m(n-1)如果 2
第二章 多项式定理及其应用 合{1,2,…, n m+ −1}中取出 m 个整数不可以重复的组合所构成的集合之间有一个一一映射. 我们研究组合的主要目的之一是求出根据已知条件所能作出的不同组合的种数.下面我们不加证明地 列出两个经常用到的组合数的简单关系等式: (1) ; kn n k n CC − = (2) . k n k n k n CCC 1 1 1 − − − += 例 1.1 从 ×88 的棋盘中,取出一个由三个小方格组成的“L”型,如图 问共有多少种不同的取法. 解 一个由四个小方格组成的“田”字形中可以取出 4 个“L”形,因此我们只需考察棋盘上可以取出 多少个“田”字形.由于每个“田”字形的中心是棋盘内横线与纵线的一个交点（不包括边界点）；反过来, 每个位于棋盘内部的交点,它四周的小方格恰好形成一个“田”字形图案,因此,映射 “田”字形→“田” 字形中心,它是棋盘上所有可取出的小方格组成的“田”形集合到棋盘内每个横线与纵线的交点集的双射 （一一映射）.易知,棋盘内的交点数共有 f : − × − = 49)29()29( （个）,所以棋盘上可取出 49 个“田”字形. 而一个“田”字形对应着 4 个“L”形,故棋盘上共可取出 × = 196449 个“L”形. 例 1.2 在直角坐标平面的第一象限中,把坐标都是整数的点按以下方法编号：（0,0）点第一号；（1,0） 点第 2 号；（1,1）点第 3 号；（0,1）点第 4 号；（0,2）点第 5 号；（1,2）点第 6 号；（2,2）点第 7 号；（2,1） 点第 8 号；（2,0）点第 9 号,…（如图）,按图中箭头的顺序,问第 2000 号点的坐标是什么？ 解 区域 0≤x≤k,0≤y≤k 上的格点个数为 .又 .所以编号为 2000 的点的纵、横坐标中至少有一个是 44.因为 44 是偶数,所以应从点（0,44）往右.又因为 所以编号为 2000 的点的横坐标是 44,纵坐标是 44-（64-45）=25.即所求的点的坐标 是（44,25）. 2 k + )1( 2 2 193644 2000 =<<= 452025 4464442000 2 >=− 例 1.3 我们知道从含 个元素的集合 n S n ={1,2, , } " 中取出 2 个元素的组合数为 2 ( 1) 2 n n n C − = .如果 - 19 -
第二章多项式定理及其应用 我们具体考虑取出元素的形式即取出的两个元素的组合之中分别含有1,2,…,n,则对应的取法数分别为 1,0,所以 (n-1)+(n-2)+…+1+0=C 实际上这给出了组合数与前n个自然数求和之间的关系! 2、组合数的整数性质 这节我们将指出组合数C"一定是整数.为此,先讨论整数n!的素因子分解式 Gauss函数[x],记号[x]表示不大于x的最大整数例如 [3]=3,[2.6]=2,[-]=0,[-4.75]=-5,[x]=[x] 我们定义函数{x}=x-[x],称其为x的分数部分.例如 x}=0.14159…,{√2}=0.414…,{-r}=0.95840 由函数[x],{x}的定义我们容易得到下面的性质 [x]≤x<[x]+1,x-1<[x]≤x,0≤{x}<1 [n+x]=n+[x],n为整数 4.[x]+[y≤[x+y{x}+{y}≥{x+y 5.-x--x1-1当x不是整数 -{x],当x是整数 6.如果a,b是两个整数,b>0,则 a=b2」+b{},0≤b(a}≤b-1 7.如果a,b是任意两个正整数,则不大于a而为b的倍数的正整数的个数为[2 在此,我们仅证明性质7 事实上,当a<b时,性质7的结论显然成立.设m是任一不大于a而为b的倍数的正整数,则 0<m=bm1≤a
第二章 多项式定理及其应用 我们具体考虑取出元素的形式,即取出的两个元素的组合之中分别含有1, ,则对应的取法数分别为 ,所以 2, , " n n n − − 1, 2, ,1,0 " 2 ( 1) ( 2) 1 0 n n n − + − + ++ = " C . 实际上,这给出了组合数与前 个自然数求和之间的关系 n ! 2、组合数的整数性质 这节我们将指出组合数 一定是整数.为此,先讨论整数 的素因子分解式. k Cn n! Gauss 函数[ x ],记号[x]表示不大于 x 的最大整数.例如 [3]=3, [2.6]=2, [ 3 1 ]=0, [-4.75]=-5, [x]=[[x]]. 我们定义函数{ }x = −x x[ ],称其为 x 的分数部分.例如 { 5 3 − }= 5 2 , {π }=0.14159…, { 2 }=0.414…, {-π }=0.95840…. 由函数[ ] x ,{ }x 的定义我们容易得到下面的性质: 1. x = + [] {} x x ; 2. [ ] [ ] 1, 1 [ ] , x ≤ < + −< ≤ xx x xx 0 {} 1 ≤ x < ; 3. [] [ nx n x + =+ ] , n 为整数; 4. [ ] [ ] [ ],{ } { } { } x + ≤+ + ≥+ y xy x y xy ; 5. ; [ ] 1, [ ] [ ], x x x x x ⎧− − − = ⎨ ⎩− 当 不是整数； 当 是整数. 6. 如果 a , 是两个整数, b b > 0 ,则 a = [] {} a a b b b b + , 0 ≤ b { b a } ≤ b -1. 7. 如果 a ,b 是任意两个正整数,则不大于 a 而为 b 的倍数的正整数的个数为[ b a ]. 在此,我们仅证明性质 7. 事实上, 当 a b < 时,性质 7 的结论显然成立.设 m 是任一不大于 而为 a b 的倍数的正整数,则 0 < m bm = 1 ≤ a , 0 1 a m b < ≤ . - 20 -
第二章多项式定理及其应用 所以满足以上条件的m的个数等于满足式0<m1≤,的m1的个数,即其为[ 定理2.1在n!的素因子分解式中,素因数p的最高次幂为 p(n!)=[-]+-2]+…+[-m 其中p"≤n<p 证明因为p是素数,如果P能够整除n!,那么p必定能够整除1,2,…,n中的某个数,但是1,2,…,n 中p的倍数是下面[]个数 P,2p, p 于是n!中P的最高次幂就是下式 P 中p的最高次幂,因此 p(m!)=[]+p([]) 再同理,我们有 P([一]) P 所以,P(n!) "2]+p([-"2]) 因为pm1>n,所以这样继续进行下去,最后得到[]=0,于是 p(n!)=[-]+[2]+…+[n] 特别地,当n=P时, 21
第二章 多项式定理及其应用 所以,满足以上条件的 m 的个数等于满足式 0 1 a m b < ≤ 的 的个数,即其为[ m1 b a ]. 定理 2.1 在 n!的素因子分解式中,素因数 p 的最高次幂为 p( !) n = ][][][ 2 m p n p n p n "+++ , 其中 m m 1 p n p + ≤ < . 证明 因为 p 是素数,如果 p 能够整除 n!,那么 p 必定能够整除 1,2,…, n 中的某个数,但是 1,2,…, 中 n p 的倍数是下面 ][ p n 个数 p ,2 p ,…, ][ p n p , 于是 中n! p 的最高次幂就是下式 p .2 p .…. ][ p n p = ] p n [ p ]![ p n 中 p 的最高次幂,因此 p( !) n = ][ p n + )]!([ p n p . 再同理,我们有 ] ][ [)]!([ p p n p n p = + )]! ][ ([ p p n p = )]!([][ 2 2 p n p p n + , 所以, p( !) n = ][ p n + )]!([][ 2 2 p n p p n + . 因为 m 1 p n + > ,所以这样继续进行下去,最后得到 ][ m+1 p n =0,于是 p( !) n = ][][][ 2 m p n p n p n "+++ . 特别地,当 时, r = pn - 21 -
第二章多项式定理及其应用 p(p)=p-4+p-2+…+1=P 例2.1求50中2的最高次幂 解因为[-]=25,[,]=12,[]=6, =3,[]=1,[]=0,所以,所求的最高次幂是 2(50!)=25+12+6+3+1=47 由定理2.1,我们很容易得到下面的推论 ∑" 推论22n∏p=”,其中Ⅱ表示取遍不超过n的一切素因数上的乘积式 推论2.3组合数C=川 是整数,0<k<n k!(n-k) 证明由 Gauss函数的性质4,有 ]≥[-]+[] 2[122[1+2l-1 所以,∏p 于是由推论2.2,我们得到k!(n-k)川n,即组合数Ck=m 是 k!(n-k)! 整数. 在下一节我们就会知道组合数Cn 恰好是二项式的系数.这种数的发现应归属于我国古代 k!(n-k)! 数学家贾宪,宋朝数学家杨辉在他的详解九章算术里指出贾宪用过下面的数字图形: 11 15101051 1615201561 因此,我们可以看出二项式的系数早在杨辉之前就已经知道了,这比欧洲至少早两百多年 3、二项式定理及其应用
第二章 多项式定理及其应用 1 1 )!( 1 1 2 − − =+++= − − p p pppp r r rr " . 例 2.1 求 50!中 2 的最高次幂. 解 因为 ] 2 50 [ =25, ] 4 50 [ =12, ] 8 50 [ =6, ] 16 50 [ =3, ] 32 50 [ =1, ] 64 50 [ =0,所以 ,所求的最高次幂是 2(50!)=25+12+6+3+1=47. 由定理 2.1,我们很容易得到下面的推论: 推论 2.2 n!=∏≤ ∑ ∞ = np p n r r p 1 ][ ,其中 表示取遍不超过 n 的一切素因数上的乘积式. ≤np Π 推论 2.3 组合数 =k Cn )!(! ! knk n − 是整数, 0 < k n < . 证明 由 Gauss 函数的性质 4,有 ][][][ r r r p k p kn p n + − ≥ , ][][][1 1 1 r r r r r r p k p kn p n ∞ = ∞ = ∞ = Σ+ − Σ≥Σ . 所以, ][][ ][ 1 1 1 r r r r r r p n np p k p kn np p p ∞ = ∞ = ∞ = Σ ≤ Σ+ − Σ ≤ Π Π .于是由推论 2.2,我们得到 − nknk !)!(! ,即组合数 =k Cn )!(! ! knk n − 是 整数. 在下一节我们就会知道组合数 =k Cn )!(! ! knk n − 恰好是二项式的系数.这种数的发现应归属于我国古代 数学家贾宪,宋朝数学家杨辉在他的详解九章算术里指出贾宪用过下面的数字图形: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 "" " " 因此,我们可以看出二项式的系数早在杨辉之前就已经知道了,这比欧洲至少早两百多年. 3、二项式定理及其应用 - 22 -