第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！-24！+3！=78.选(c). 2 第二十讲:组合数学 练习1:1.(2009年全国高中数学联赛江西初赛试题)从集合m=1,2,3,2009中,去掉

6、所有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互质的项之后,把余下的各项按从小到大的顺序排成一个新数列an,易见a1

7、=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+y+z=1

9、5有 组解. (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“至少有两个学校的名额数相同”的分配方法有310+1=31种.综上知,满足条件的分配方法共有25331222种. (1990年全国高中数学联赛试题)8个女孩和25个男孩围成一圈,任意两个女孩之间至少站两个男孩,那么,共有_种不同的排列方法(只要把圈旋转一下就重合的排法认为是相同的). (2005年全国高中数学联赛试题)如果自然数a的各位数字之和等于7,那么称a为“吉祥数”.将所有“吉祥数”从小到大排成一列a1,a2,a3,若an=

12、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=180.选(c).练习3:1

13、.(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+f(x)+xf2(x)

14、为奇数.则这样的映射的个数为( ).(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(n1,nn),映射f:aa.则满足f(1)f(2)f(n),且像恰好取k(1kn)个不同值的f的个数为 .2.(2011年全国高中数学联赛北京初赛试题)二次三项式x2+ax+b(a、bn)的根是实数,且ab=220

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

16、年复旦大学保送生考试试题)将一个四棱锥的每个顶点染上一种颜色,并使同一条棱的两端点异色,如果只有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染色有m+1种方法,给点a2染色有m种方法

17、,给点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,m+1)b3=-(m+1)m(m-1),

18、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种,所以共有584=420种.选(d).练习4:1.(2005年全国高中数学联赛河南初赛试题)甲、乙、丙三人练习传球,设传球n次,球从甲

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

20、任意两个元素之差(大数减小数)的和.求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年第四届北方数学奥林匹克邀请赛试题)给定 .由n(n+1)个点组成的

21、正三角形点陈,如图: . .记以点陈中三个点为顶点的所有正三角形的个数为 . . .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-m; 常用等式:cnn+cn+1n+cn+2n+c

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

25、,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)排列,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！-24！+3！=78