第20讲自主招生数学试题中的组合数学

1、 第二十讲:组合数学 1 第二十讲:自主招生数学试题中的组合数学杨老师专论（电话号码：2078159；手机号码 组合数学是自主招生考试中较难的问题,组合问题的解决往往不需要高深的数学知识,但常常包含高超的解题技巧.自主招生的考试中出现的组合问题主要有:计数问题;组合恒等式;存在性问题;组合最值等. .知识拓展 1.计数问题: .容斥原理:有限集合x的元素个数记为|x|,则:|ab|=|a|+|b|-|ab|;|cu(ab)|=|u|-|ab|=|u|-|a|-|b|+|ab|;|abc|=|a|+|b|+|c|-|ab|-|bc|-|ca|+|abc|;|cu(abc

2、)|=|u|-|abc|=|u|-|a|-|b|-|c|+|ab|+|bc|+|ca|-|abc|. .不定方程整数解:不定方程x1+x2+xn=m(n,mn+,mn2)正整数解的个数=,它与计数问题有紧密联系,利用该结论可解决一类计数问题; .映射方法:当直接计算集合a的元素个数|a|较困难时,着意于寻找,或构造容易计算其个数的集合b,并设法建立一个a到b的一一映射f,由映射定理知|a|=|b|,这种思想方法就称为映射方法; .递归方法:利用递推思想解决计数问题的程序是:一是求初始值:a1,a2等;二是建立an与an-1,an-2等的关系式;三是求an. 2.组合等式: 基本性质:cnn-k

3、=cnk;kcnk=ncn-1k-1;cn-1k-1+cn-1k=cnk;cn0+cn1+cnn=2n;cn0+cn2+cn4+=cn1+cn3+cn5+=2n-1;cnkckm=cn-mk-m; 常用等式:cnn+cn+1n+cn+2n+cn+kn=cn+k+1n+1;范德蒙等式:=cn+mk; 证明方法:性质法:利用组合数的上述基本性质;二项式定理法:通过对二项式展开式进行变形(求导,或积分),然后赋值(含复数);模型法:构造组合模型,并对某同一个计数问题利用两种方法计算. 3.存在性问题: 极端原理:包括:(i)自然数集的任意非空子集中必有最小数;(ii)实数集的非空有限子集中必有最小数

4、,也必有最大数; 抽屉原理:包括:(i)(第一抽屉原理)将m个物件放入n个抽屉内,则必有一个抽屉内有至少+1个物件;(ii)(第二抽屉原理)将m个物件放入n个抽屉内,则必有一个抽屉内有至多个物件. 平均值原理:包括:(i)设a是实数a1,a2,an的算术平均数,则a1,a2,an中必有一个不小于a,也必有一个不大于a;(ii)设a是正实数a1,a2,an的几何平均数,则a1,a2,an中必有一个不小于a,也必有一个不大于a. 4.组合最值:求解组合最值问题的方法:估值法、计数法、调整法等. .归类分析 1.计数方法之容斥原理:例1:(2008年复旦大学保送生考试试题)5个不同元素ai(i=1,

5、2,3,4,5)排成一列,规定a1不许排第一,a2不许排第二,不同的排法有( )(a)64种 (b)72种 (c)78种 (d)84种解析:设集合u=5个不同元素ai(i=1,2,3,4,5)排列,a=5个不同元素ai(i=1,2,3,4,5)排列,且a1排第一,b=5个不同元素ai(i=1,2,3,4,5)排列,且a2排第二,则|u|=5！,|a|=|b|=4！,|ab|=3！不同的排法=|cu(ab)|=|u|-|a|-|b|+|ab|=5！-2×4！+3！=78.选(c). 2 第二十讲:组合数学 练习1:1.(2009年全国高中数学联赛江西初赛试题)从集合m=1,2,3,20

6、09中,去掉所有3的倍数以及5的倍数后,则m中剩下的元素个数为 . (2012年全国高中数学联赛安徽初赛试题)不超过2012且与210的最大公约数是1的正整数共有 个. (1995年第6届“希望杯”全国数学邀请赛试题)与105有大于1的公约数的两位自然数的和是( )(a)2078 (b)2295 (c)2708 (d)3338 (2009年全国高中数学联赛浙江初赛试题)设1x,y,z6,则自然数x,y,z的乘积能被10整除的情形有 种.2.(2007年全国高中数学联赛安徽预赛试题)在正整数构成的等差数列1,3,5,7, 中删去所有和55互质的项之后,把余下的各项按从小到大的顺序排成一个新数列a

7、n,易见a1=1,a2=3,a3=7,a4=9,a5=13,.那么a2007=( )(a)9597 (b)5519 (c)2831 (d)2759 (2010年全国高中数学联赛天津初赛试题)a1,a2,a3,a4,a5是1,2,3,4,5的一个排列,且满足|ai-ai+1|1(i=1,2,3,4),则满足条件的排列a1,a2,a3,a4,a5的数目为 . (2004年全国高中数学联赛试题)对于整数n4,求出最小的整数f(n),使得对于任何正整数m,集合m,m+1,m+n-1的任一个f(n)元子集,均有至少3个两两互素的元素. 2.计数方法之不定方程整数解:例2:(2011年“卓越联盟”自主招生

8、考试试题)数列an共有11项,a1=0,a11=4,且|ak+1-ak|=1,k=1,2,10.满足这种条件的不同数列的个数为( )(a)100 (b)120 (c)140 (d)160解析:令xk=ak+1-ak,k=1,2,10.由|ak+1-ak|=1|xk|=1xk=1,或-1;又由a11=a1+(a2-a1)+(a3-a2)+(a11-a10)x1+x2+xn=4xn中有7个1,3个-1.又因数列an与数列xn成一一对应,而数列xn的个数=7个1与3个-1的不同排列数=c103=120.选(b).练习2:1.(2003年全国高中数学联赛安徽初赛试题)已知x、y、z均为正整数.则方程x

9、+y+z=15有 组解. (1999年全国高中数学联赛河北初赛试题)x+y+z=1999的正整数解的个数是 . (2007年全国高中数学联赛四川初赛试题)已知“不定方程x1+x2+xm=n(nm)的正整数解(x1,x2,xm)的组数(其中m,nz+)”,则x1+x2+x3+x413的正整数解的组数为 (用具体数字作答). (1985年全国高中数学联赛试题)方程2x1+x2+x3+x4+x5+x6+x7+x8+x9+x10=3的非负整数解共有_组. (2009年全国高中数学联赛湖北初赛试题)求不定方程x1+x2+x3+3x4+3x5+5x6=21的正整数解的组数.2.(2011年全国高中数学联赛

10、天津初赛试题)将(a+b+c+d)9展开之后再合并同类项,所得的多项式的项数是 . (1988年全国高中数学联赛试题)甲、乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛,双方先由1号队员比赛,负者被淘汰,胜者再与负方2号队员比赛,直到有一方队员全被淘汰为止,另一方获胜,形成一种比赛过程,那么所有可能出现的比赛过程的种数为_. (2008年全国高中数学联赛试题)将24个志愿者名额分配给3个学校,则每校至少有一个名额且各校名额互不相同的分配方法共有 种.解:设分配给3个学校的名额数分别为x,y,z,则每校至少有一个名额的分法数为不定方程x+y+z=24的正整数解的个数=253.x,y,z均相

11、等的正整数解的个数是1;x,y,z中有且仅有两个相等,不妨设y=z,则x+2y=24x=2kk+y=12,其正整数解的个数是11,除去解(8,8,8),正整数解的个数是=11-1“至少有两个学校的名额数相同”的分配方法有3×10+1=31种.综上知,满足条件的分配方法共有25331222种. (1990年全国高中数学联赛试题)8个女孩和25个男孩围成一圈,任意两个女孩之间至少站两个男孩,那么,共有_种不同的排列方法(只要把圈旋转一下就重合的排法认为是相同的). (2005年全国高中数学联赛试题)如果自然数a的各位数字之和等于7,那么称a为“吉祥数”.将所有“吉祥数”从小到大排成一列a

12、1,a2,a3,若an=2005,则a5n= . 3.计数方法之映射方法:例3:(2006年武汉大学保送生考试试题)设an是等差数列,从a1,a2,a3,a20中任取3个不同的数,使这三个数仍成 第二十讲:组合数学 3 等差数列,则这样不同的等差数列最多有( )(a)90个 (b)120个 (c)180个 (d)200个解析:三个数an,am,ak成等差数列an+ak=2amn+k=2mn与k同奇,或同偶,且当n与k确定后,m惟一确定.令a=a1,a3,a19,b=a2,a4,a20.则所取三数x,y,z成等差数列与x,za,或x,zb成一一对应,故不同等差数列的个数=a102+a102=18

13、0.选(c).练习3:1.(2002年全国高中数学联赛山东初赛试题)设集合m=-1,0,1,n=2,3,4,5,6.映射f:mn,则对任意的xm,x+f(x)+xf(x)恒为奇数的映射f的个数为( )(a)122 (b)15 (c)50 (d)27 (2005年全国高中数学联赛安徽初赛试题)设集合m=-2,0,1,n=1,2,3,4,5,映射f:mn使对任意的xm,都有x+f(x)+xf(x)是奇数,则这样的映射f的个数是( )(a)45 (b)27 (c)15 (d)11 (2007年全国高中数学联赛甘肃初赛试题)设a=0,1,2,3,b=2,3,4,5,6,映射f:ab满足对任意的xa,x

14、+f(x)+xf2(x)为奇数.则这样的映射的个数为( ).(a)80 (b)100 (c)250 (d)625 (2002年全国高中数学联赛试题)己知两个实数集合a=a1,a2,a100与b=b1,b2,b50,若从a到b的映射f使得b中每个元素都有原象,且f(a1)f(a2)f(a100),则这样的映射共有( )(a) (b) (c) (d) (2006年全国高中数学联赛辽宁初赛试题)设a=1,2,n(n>1,nn),映射f:aa.则满足f(1)f(2)f(n),且像恰好取k(1<kn)个不同值的f的个数为 .2.(2011年全国高中数学联赛北京初赛试题)二次三项式x2+ax+

15、b(a、bn)的根是实数,且ab=22011,则这样的二次三项式共有 个. (1983年全国高中数学联赛试题)三边均为整数,且最大边长为11的三角形,共有 个. (1985年全国高中数学联赛试题)在已知数列1,4,8,10,16,19,21,25,30,43中,相领若干数之各能被11整除的数组共有_. (1983年上海市高中数学竞赛(新知杯)试题)在集合1,2,n中,任意取出一个子集,计算它的元素之和,则所有各个子集元素之和的总和是_. (2011年全国高中数学联赛山西初赛试题)如果四位数的四个数码满足a+b=c+d,就称其为“好数”;例如2011就是一个“好数”.那么,“好数”的个数是 .

16、4.计数方法之递归方法:例4:(2007年复旦大学保送生考试试题)将一个四棱锥的每个顶点染上一种颜色,并使同一条棱的两端点异色,如果只有5种颜色可使用,那么不同的染色方法的总数是( )(a)120 (b)260 (c)340 (d)420解析:本题是1995年全国高中数学联赛试题的原题.为给出一般性的解法,我们首先证明一个著名的问题: 环着色问题:用m+1(m2)种颜色给平面n(n3)边形的顶点染色,每一个顶点染上一种颜色,且相邻的两顶点异色,则共有a(n,m+1)=mn+(-1)nm种不同的染色方法.证明:设n边形的顶点分别为a1,a2,an,不同的染色方法为an; 当n=3时,给顶点a1染

17、色有m+1种方法,给点a2染色有m种方法,给点a3染色有m-1种方法,所以a(3,m+1)=(m+1)m(m-1); 考虑一般地,给顶点a1染色有m+1种方法,给顶点a2,a3,an染色均有m种方法,所以共有(m+1)mn-1种染法,这些染法可分为两类:a1与an不同色,有a(n,m+1)种方法;a1与an同色,此时a1与an-1必不同色,将a1与an视为一个点,n边形变n-1为边形,有a(n-1,m+1)种方法;所以a(n,m+1)+a(n-1,m+1)=(m+1)mn-1(-1)na(n,m+1)-(-1)n-1a(n-1,m+1)=(-1)n(m+1)mn-1,令bn=(-1)na(n,

18、m+1)b3=-(m+1)m(m-1),bn-bn-1=(-1)n(m+1)mn-1=-(m+1)(-m)n-1bn=b3+(b4-b3)+(b5-b4)+(bn-bn-1)=-(m+1)m(m-1)-(m+1)(-m)3+(-m)4+(-m)n-1=-(m+1)m(m-1)-(m+1)=-(m+1)m(m-1)-(-m)3+(-m)n=m-(-m)nan=mn+(-1)nm. 4 第二十讲:组合数学 现解本题:先染顶点,有5种;再用余下的4(m=3)种颜色染底面4(n=4)点,有a(4,4)=84种,所以共有5×84=420种.选(d).练习4:1.(2005年全国高中数学联赛河南

19、初赛试题)甲、乙、丙三人练习传球,设传球n次,球从甲手中传出,第n次仍传给甲,共有an种不同的传球方法,则数列an的通项公式为( )(a)an=2n+ (b)an=2n- (c)an=2n+(-1)n (d)不能确定 (2009年全国高中数学联赛河南初赛试题)5个人互相传球,要求接球后马上传给别人,由甲开始作为第一次传球,则经过4次传球后又传回到甲手中的不同传球方法种数为 . (2011年全国高中数学联赛广东初赛试题)10名学生站成一排,要给每名学生发一顶红色、黄色或者蓝色的帽子,要求每种颜色的帽子都要有,且相邻的两名学生帽子的颜色不同.则满足要求的发帽子的方法共有 种. (2009年美国数学

20、邀请赛试题)设集合s=20,21,210,记n为s中任意两个元素之差(大数减小数)的和.求n除以1000的余数.2.(2008年第四届北方数学奥林匹克邀请赛试题)给定 1 2 3 4 97 98 99 100三角形数表如图: 3 5 7 195 197 199其中第一行各数依次是1,2,100,从第二行起每个数 8 12 392 396分别等于它上一行左、右两数的和.求m的值. 20 788 m (2005年第一届北方数学奥林匹克邀请赛试题)已知n位数的各位数字只能取集合1,2,3,4,5中的元素,设含有数字5且在5的前面不含3的n位数的个数为f(n).求f(n). (2008年第四届北方数学

21、奥林匹克邀请赛试题)给定 .由n(n+1)个点组成的正三角形点陈,如图: . .记以点陈中三个点为顶点的所有正三角形的个数为 . . .f(n).求f(n)的表达式. . . . . . . . . . (1991年全国高中数学联赛试题)设an为下述自然数n的个数:n的各位数字之和为n且每位数字只能取1,3或4,求证:a2n是完全平方数,这里n=1,2,. 第二十讲:组合数学 5 6 第二十讲:组合数学 第二十讲:组合数学 7 第二十讲:组合数学 1 第二十讲:组合数学杨老师专论（电话号码：2078159；手机号码 组合数学是自主招生考试中较难的问题,组合问题的解决往

22、往不需要高深的数学知识,但常常包含高超的解题技巧.自主招生的考试中出现的组合问题主要有:计数问题;组合恒等式;存在性问题;组合最值等. .知识拓展 1.计数问题: .容斥原理:有限集合x的元素个数记为|x|,则:|ab|=|a|+|b|-|ab|;|cu(ab)|=|u|-|ab|=|u|-|a|-|b|+|ab|;|abc|=|a|+|b|+|c|-|ab|-|bc|-|ca|+|abc|;|cu(abc)|=|u|-|abc|=|u|-|a|-|b|-|c|+|ab|+|bc|+|ca|-|abc|. .不定方程整数解:不定方程x1+x2+xn=m(n,mn+,mn2)正整数解的个数=,它

23、与计数问题有紧密联系,利用该结论可解决一类计数问题; .映射方法:当直接计算集合a的元素个数|a|较困难时,着意于寻找,或构造容易计算其个数的集合b,并设法建立一个a到b的一一映射f,由映射定理知|a|=|b|,这种思想方法就称为映射方法; .递归方法:利用递推思想解决计数问题的程序是:一是求初始值:a1,a2等;二是建立an与an-1,an-2等的关系式;三是求an. 2.组合等式: 基本性质:cnn-k=cnk;kcnk=ncn-1k-1;cn-1k-1+cn-1k=cnk;cn0+cn1+cnn=2n;cn0+cn2+cn4+=cn1+cn3+cn5+=2n-1;cnkckm=cn-mk

24、-m; 常用等式:cnn+cn+1n+cn+2n+cn+kn=cn+k+1n+1;范德蒙等式:=cn+mk; 证明方法:性质法:利用组合数的上述基本性质;二项式定理法:通过对二项式展开式进行变形(求导,或积分),然后赋值(含复数);模型法:构造组合模型,并对某同一个计数问题利用两种方法计算. 3.存在性问题: 极端原理:包括:(i)自然数集的任意非空子集中必有最小数;(ii)实数集的非空有限子集中必有最小数,也必有最大数; 抽屉原理:包括:(i)(第一抽屉原理)将m个物件放入n个抽屉内,则必有一个抽屉内有至少+1个物件;(ii)(第二抽屉原理)将m个物件放入n个抽屉内,则必有一个抽屉内有至多个

25、物件. 平均值原理:包括:(i)设a是实数a1,a2,an的算术平均数,则a1,a2,an中必有一个不小于a,也必有一个不大于a;(ii)设a是正实数a1,a2,an的几何平均数,则a1,a2,an中必有一个不小于a,也必有一个不大于a. 4.组合最值:求解组合最值问题的方法:估值法、计数法、调整法等. .归类分析 1.计数方法之容斥原理:例1:(2008年复旦大学保送生考试试题)5个不同元素ai(i=1,2,3,4,5)排成一列,规定a1不许排第一,a2不许排第二,不同的排法有( )(a)64种 (b)72种 (c)78种 (d)84种解析:设集合u=5个不同元素ai(i=1,2,3,4,5

26、)排列,a=5个不同元素ai(i=1,2,3,4,5)排列,且a1排第一,b=5个不同元素ai(i=1,2,3,4,5)排列,且a2排第二,则|u|=5！,|a|=|b|=4！,|ab|=3！不同的排法=|cu(ab)|=|u|-|a|-|b|+|ab|=5！-2×4！+3！=78.选(c). 2 第二十讲:组合数学 练习1:1.(2009年全国高中数学联赛江西初赛试题)从集合m=1,2,3,2009中,去掉所有3的倍数以及5的倍数后,则m中剩下的元素个数为 .解:集合m中,3的倍数有=669个,5的倍数有=401个,15的倍数有=133个,则剩下的元素个数为2009-(669+40

27、1)+133=1072个. (2012年全国高中数学联赛安徽初赛试题)不超过2012且与210的最大公约数是1的正整数共有 个.解:设全集u=x|0<x2012,xn,则|u|=2012,因210=2×3×5×7.设a=x|2|x,xu,b=x|3|x,xu,c=x|5|x,xu,d=x|7|x,xu,则|a|=1006,|b|=670,|c|=402,|d|=287,|ab|=335,|ac|=201,|ad|=143,|bc|=134,|bd|=95,|cd|=57,|abc|=67,|abd|=47,|acd|=28,|bcd|=19,|abcd|=9

28、|cu(abcd)|=|u|-|a|-|b|-|c|-|d|+|ab|+|ac|+|ad|+|bd|+|cd|-|abc|-|abd|-|acd|-|bcd|+|abcd|=2012-1006-670-402-287+335+201+143+134+95+57-67-47-28-19+9=460. (1995年第6届“希望杯”全国数学邀请赛试题)与105有大于1的公约数的两位自然数的和是( )(a)2078 (b)2295 (c)2708 (d)3338解:由105=3×5×7.两位自然数中,3的倍数的和=3(4+5+33)=1665;5的倍数的和=5(2+3+19)=94

29、5;7的倍数的和=7(2+3+14)=728;15的倍数的和=15(1+2+6)=315;21的倍数的和=21(1+2+3+4)=210;35的倍数的和=35(1+2)=105.故1665+945+784-315-210-105=2708,选(c). (2009年全国高中数学联赛浙江初赛试题)设1x,y,z6,则自然数x,y,z的乘积能被10整除的情形有 种.解:x,y,z的取法有63种;x,y,z不取2,4,6的取法有33种;x,y,z不取5的取法有53种;x,y,z不取2,4,5,6的取法有23种.由容斥原理得:x,y,z的乘积能被10整除的情形有63-33-53+2372.2.(2007

30、年全国高中数学联赛安徽预赛试题)在正整数构成的等差数列1,3,5,7, 中删去所有和55互质的项之后,把余下的各项按从小到大的顺序排成一个新数列an,易见a1=1,a2=3,a3=7,a4=9,a5=13,.那么a2007=( )(a)9597 (b)5519 (c)2831 (d)2759解:an可看成是在正整数数列1,2,3,4,5,6,7,中删去所有能被2,5或11整除的项之后,把余下的各项按从小至大顺序排成的数列.由三阶容斥原理,1,2,3,4,m中不能被2,5或11整除的项的个数为xm=m-+-,其中a不表示不大于a的最大整数,即的整数部分.估值:设2007=xm=m-+-=m(1-

31、)(1-)(1-)=mm2007××5519.又因为x5519=5519-+-=2007.并且5519不是2,5,11的倍数,从而知a2007=5519.选(b). (2010年全国高中数学联赛天津初赛试题)a1,a2,a3,a4,a5是1,2,3,4,5的一个排列,且满足|ai-ai+1|1(i=1,2,3,4),则满足条件的排列a1,a2,a3,a4,a5的数目为 .解:设全集u=1,2,3,4,5的所有排列,a=1,2,3,4,5的满足1,2相邻排列,b=1,2,3,4,5的满足2,3相邻排列,c=1,2,3,4,5的满足3,4相邻排列,d=1,2,3,4,5的满足4

32、,5相邻排列,则|u|=5！=120,|a|=|b|=|c|=|d|=2！×4！=48,|ab|=|bc|=|cd|=2！×3！=12,|ac|=|ad|=|bd|=2！×2！×3！=24,|abc|=|bcd|=2！×2！=4,|abd|=|acd|=2！×2！×2！=8,|abcd|=2|cu(abcd)|=|u|-|a|-|b|-|c|-|d|+|ab|+|ac|+|ad|+|bd|+|cd|-|abc|-|abd|-|acd|-|bcd|+|abcd|=120-5×48+3×12+3×2

33、4-2×4-2×8+2= (2004年全国高中数学联赛试题)对于整数n4,求出最小的整数f(n),使得对于任何正整数m,集合m,m+1,m+n-1的任一个f(n)元子集,均有至少3个两两互素的元素.解:当n4时,对集合m=m,m+1,m+n-1;若2|m,则m+1,m+2,m+3两两互素;若2m,则m,m+1,m+2两两互素;于是m的 第二十讲:组合数学 3 所有n元子集(m本身)中均至少有3个两两互素的元素f(n)存在,且f(n)n; 设tn=t|tn+1|且2|t,或3|t=2,3,4,6,8,9,则tn中任意3个元素均不两两互素f(n)|tn|+1,由容斥原理知|tn

34、|=+-f(n)+-+1f(4)4,f(5)5,f(6)5,f(7)6,f(8)7,f(9)8;以下证明f(6)=5; 设x1,x2,x3,x4,x5为m,m+1,m+2,m+3,m+4,m+5中的5个数;若这5个数中有3个是奇数,则这个奇数两两互素;若这5个数中有2个是奇数,则必有3个偶数,不妨设x1,x2,x3为偶数,x4,x5为奇数,则x1,x2,x3中至多有1个被3整,除至多有1个被5整除x1,x2,x3中至少有1个不被3整除,也不被5整除,不妨设为x3,则x3,x4,x5两两互素.综上,f(6)=5; 又由m,m+1,m+n=m,m+1,m+n-1m+nf(n+1)f(n)+1;由f

35、(6)=5f(4)=4,f(5)=5,f(7)=6,f(8)=7,f(9)=8;即当4n9时,f(n)=+-+1;以下用数学归纳法证明f(n)=+-+1(n4);假设当nk时命题成立,则当n=k+1时,由m,m+1,m+n=m,m+1,m+n-6m+n-5,m+n-4,m+n-3.m+n-2.m+n-1,m+nf(k+1)f(k-5)+f(6)-1=+-+1;又由f(n)+-+1f(k+1)+-+1f(k+1)=+-+1. 2.计数方法之不定方程整数解:例2:(2011年“卓越联盟”自主招生考试试题)数列an共有11项,a1=0,a11=4,且|ak+1-ak|=1,k=1,2,10.满足这种

36、条件的不同数列的个数为( )(a)100 (b)120 (c)140 (d)160解析:令xk=ak+1-ak,k=1,2,10.由|ak+1-ak|=1|xk|=1xk=1,或-1;又由a11=a1+(a2-a1)+(a3-a2)+(a11-a10)x1+x2+xn=4xn中有7个1,3个-1.又因数列an与数列xn成一一对应,而数列xn的个数=7个1与3个-1的不同排列数=c103=120.选(b).练习2:1.(2003年全国高中数学联赛安徽初赛试题)已知x、y、z均为正整数.则方程x+y+z=15有 组解.解:c15-13-1=c142=91. (1999年全国高中数学联赛河北初赛试题

37、)x+y+z=1999的正整数解的个数是 .解:c1999-13-1=c19982=999×1997. (2007年全国高中数学联赛四川初赛试题)已知“不定方程x1+x2+xm=n(nm)的正整数解(x1,x2,xm)的组数(其中m,nz+)”,则x1+x2+x3+x413的正整数解的组数为 (用具体数字作答).解:x1+x2+x3+x44.x1+x2+x3+x4=4,5,13的正整数解的组数分别为,所以,x1+x2+x3+x413的正整数解的组数为+=715. (1985年全国高中数学联赛试题)方程2x1+x2+x3+x4+x5+x6+x7+x8+x9+x10=3的非负整数解共有_

38、组.解:由2x1+x2+x3+x4+x5+x6+x7+x8+x9+x10=32x13x1=0,1.当x1=0时,x2+x3+x4+x5+x6+x7+x8+x9+x10=3的非负整数解共有=165;当x1=1时,x2+x3+x4+x5+x6+x7+x8+x9+x10=1的非负整数解共有=9,所以共有165+9=174. (2009年全国高中数学联赛湖北初赛试题)求不定方程x1+x2+x3+3x4+3x5+5x6=21的正整数解的组数.解:设x1+x2+x3=x,x4+x5=y,x6=z,则x3,y2,z1,且x1+x2+x3+3x4+3x5+5x6=21x+3y+5z=21.先研究不定方程x+3

39、y+5z=21的正整数解.5z=21-(x+3y)21-(3+3×2)z2z=1,2.当z=1时,x+3y=16,其解为(x,y)=(4,4),(7,3),(10,2);当z=2时,x+3y=11,其解为(x,y)=(5,2).综上,不定方程x+3y+5z=21满足x3,y2,z1的正整数解为(x,y,z)=(4,4,1),(7,3,1),(10,2,1),(5,2,2).又因不定方程x1+x2+x3=x的正整数解的组数=,不定方程x4+x5=y的正整数解的组数= 4 第二十讲:组合数学 .根据乘法原理:当(x,y,z)=(4,4,1)时,正整数解的组数=;当(x,y,z)=(7,3

40、,1)时,正整数解的组数=;当(x,y,z)=(10,2,1)时,正整数解的组数=;当(x,y,z)=(5,2,1)时,正整数解的组数=.根据加法原理:不定方程x1+x2+x3+3x4+3x5+5x6=21的正整数解的组数=+=81.2.(2011年全国高中数学联赛天津初赛试题)将(a+b+c+d)9展开之后再合并同类项,所得的多项式的项数是 .解:展开式的一般式为xambnckdt,其中非负整数m,n,k,t,满足:m+n+k+t=9,展开式的项与不定方程m+n+k+t=9的非负整数解构成一一对应,不定方程m+n+k+t=9解个数为=220有220项. (1988年全国高中数学联赛试题)甲、

41、乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛,双方先由1号队员比赛,负者被淘汰,胜者再与负方2号队员比赛,直到有一方队员全被淘汰为止,另一方获胜,形成一种比赛过程,那么所有可能出现的比赛过程的种数为_.解:当甲队获胜时,甲队淘汰乙队7名队员.设甲队中第i号队员淘汰乙队xi名队员,则x1+x2+x7=7,一种比赛过程与不定方程x1+x2+x7=7的非负整数解构成一一对应,非负整数解=.同理,当乙队获胜时,比赛过程种数=,所以,所有可能出现的比赛过程的种数为=2=3432. (2008年全国高中数学联赛试题)将24个志愿者名额分配给3个学校,则每校至少有一个名额且各校名额互不相同的分配方法

42、共有 种.解:设分配给3个学校的名额数分别为x,y,z,则每校至少有一个名额的分法数为不定方程x+y+z=24的正整数解的个数=253.x,y,z均相等的正整数解的个数是1;x,y,z中有且仅有两个相等,不妨设y=z,则x+2y=24x=2kk+y=12,其正整数解的个数是11,除去解(8,8,8),正整数解的个数是=11-1“至少有两个学校的名额数相同”的分配方法有3×10+1=31种.综上知,满足条件的分配方法共有25331222种. (1990年全国高中数学联赛试题)8个女孩和25个男孩围成一圈,任意两个女孩之间至少站两个男孩,那么,共有_种不同的排列方法(只要把圈旋转一下就重

43、合的排法认为是相同的).解:分别以8个女孩为组长,将25个男孩分入该8个组,各组内男孩的个数分别记为x1,x2,x8,则:x1+x2+xn=25(xi2,i=1,2,8),令yi=xi-1,则:y1+y2+y8=17(yi1,i=1,2,8),其正整数解的个数为c17-18-1=c167,即25个男孩分成8个组,每组至少2人的分组数为c167;8个组(每组均排成以女孩为头)圆排列数为(8-1)！=7！;又25个男孩站入的方法数为25！.所以,共有c67×7！×25！种不同的排列方法. (2005年全国高中数学联赛试题)如果自然数a的各位数字之和等于7,那么称a为“吉祥数”.

44、将所有“吉祥数”从小到大排成一列a1,a2,a3,若an=2005,则a5n= .解:方程x1+x2+xk=m的非负整数解的个数为.而使x11,xi0(i2)的整数解个数为.现取m=7,可知,k位“吉祥数”的个数为p(k)=.2005是形如的数中最小的一个“吉祥数”,且p(1)=1,p(2)=7,p(3)=28,对于四位“吉祥数”,其个数为满足a+b+c=6的非负整数解个数,即=28个2005是第1+7+28+28+165个“吉祥数”,即a65=2005.从而n=65,5n=325.又p(4)=84,p(5)=210p(1)+p(2)+p(3)+p(4)+p(5)=330.从大到小最后六个五位

45、“吉祥数”依次是:70000,61000,60100,60010,60001,52000第325个“吉祥数”是52000,即a5n=5200. 3.计数方法之映射方法:例3:(2006年武汉大学保送生考试试题)设an是等差数列,从a1,a2,a3,a20中任取3个不同的数,使这三个数仍成 第二十讲:组合数学 5 等差数列,则这样不同的等差数列最多有( )(a)90个 (b)120个 (c)180个 (d)200个解析:三个数an,am,ak成等差数列an+ak=2amn+k=2mn与k同奇,或同偶,且当n与k确定后,m惟一确定.令a=a1,a3,a19,b=a2,a4,a20.则所取三数x,y

46、,z成等差数列与x,za,或x,zb成一一对应,故不同等差数列的个数=a102+a102=180.选(c).练习3:1.(2002年全国高中数学联赛山东初赛试题)设集合m=-1,0,1,n=2,3,4,5,6.映射f:mn,则对任意的xm,x+f(x)+xf(x)恒为奇数的映射f的个数为( )(a)122 (b)15 (c)50 (d)27解:x+f(x)+xf(x)是奇数1+x+f(x)+xf(x)=(1+x)1+f(x)是偶数当x是偶数时,f(x)是奇数.当x=0时,f(x)3,5;当x=-1,1时,f(x)n.所以,这样的映射f的个数=2×5×5=50.选(c). (2005年全国高中数学联赛安徽初赛试题)设集合m=-2,0,1,n=1,2,3,4,5,映射f:mn使对任意的xm,都有x+f(x)+xf(x)是奇数,则这样的映射f的个数是( )(a)45 (