数学奥赛辅导组合计数

组合组合计数组合4星题课程目标知识提要组合•定义组合：从n个不同元素中取出m个〔m≦n〕元素作为一组〔不计顺序〕，可选择的方法数叫做从n个不同元素中取出m个不同的组合数，记作：C n m•公式C n m = A n m÷A m m•重要结论C n0 = C n n = 1C n m = C n n−mC n0 + C n1 + C n2 + ⋯ + C n n = 2n精选例题组合1. 从10名男生，8名女生中选出5人参加游泳比赛．在以下条件下，分别有种选法．〔1〕恰有3名女生入选；〔2〕至少有3名女生入选；〔3〕某两名女生，某两名男生必须入选．【答案】〔1〕2520；〔2〕3276；〔3〕14【分析】〔1〕C83×C102=56×45=2520(种)；〔2〕2520+C84×C101+C85=2520+700+56=3276(种);〔3〕选了4人，还差1人，从剩下的18−4=14(人)中任意选择一个即可，有14种选择．2. 在以下图中，“构建和谐社会，创美好崇义〞，从上往下读，上下、左右都不能跳读，共有种不同的读法．【答案】252【分析】根据题意，分析可得，原问题可转化为从10行中，选出5次向左，剩下的5次向右的组合问题．根据题意，从上往下读，上下、左右都不能跳读，那么从上一行到下一行必须向左或向右，分析可得，从上到下，从“构〞到“义〞之间共10个间隙，必须是5次向左，5次向右；即可转化为从10行中，选出5次向左，剩下的5次向右，那么有C105=252(种)．3. 各位数字之和为4的四位数有个，其中能被11整除的有个．【答案】20；6【分析】详解：设abcd的各位数字之和为4，那么a、b+1、c+1、d+1这四个正整数的和是7．由于x+y+z+w=7的正整数解个数是C63=20个，故各位数字之和4的四位数有20个．其中能被11整除的数，必有a+c=b+d=2，(a,c)的取值有(1,1)、(2,0)两种，(b,d)的取值有(0,2)、(1,1)、(2,0)三种，故有2×3=6个．4. 甲、乙、丙三户人家打算订阅报纸，共有7种不同的报纸可供选择，每户人家都订三份不同的报纸，并且知道这三户人家每两户所订的报纸恰好有一份相同，那么三户人家共有种不同的订阅方式．【答案】5670【分析】甲户有C73=35种选择；乙户要选甲户订的报纸订一种，另两种从甲没订过的选，所以有C31×C42=18种丙户要么选择甲乙都订的报纸，再选甲乙都没订的〔就剩两种了〕，或者从甲乙订的互相不同的那两份报纸中各挑一份，再挑个甲乙都没订的，所以有C21×C21×C21+1=9种35×18×9=5670种.5. —个由某些正整数所组成的数组具有以下的性质：〔1〕这个数组中的每个数，除了1以外，都至少可被2,3或5中的一个数整除．〔2〕对于任意整数n，如果此数组中包含有2n,3n或5n中的一个，那么此数组中必同时包含有n及2n,3n,5n．此数组中数的个数在300和400之间．那么此数组有个数．【答案】364【分析】假设该数中某一数为m，且m能被2整除，那么m2也在数组中，以此类推，m能被2k整除，那么m2k 也在数组中．同理m能被3k整除，那么m3k也在数组中，而将m中所有含2,3,5的因数都除去后，剩下的m2a×3b×5c也在数组中，并且没有质因数2,3,5了，而除了1以外，数组中任意数都可被2,3或5中一个数整除，因此该数m2a×3b×5c 只能为1．结论：数组中所有数含的质因数只有2,3,5．如果数组中含2k，那么就知道2k−1,2k−1×3,2k−1×5都在其中，以此类推，2k−2,2k−2×3,2k−2×32,2k−2×3×5,2k−2×5,2k−2×52都在其中，再以此类推，2a×3b×5c(a+b+ c⩽k)都在数组中，同理，假设数组中含3k或5k，那么都有同样的结论，即2a×3b×5c(a+b+c⩽k)都在数组中；我们只需将k分类：当k=0时，a=b=c=0，数组中只有1一个这样的数；当 k =1 时，a +b +c =1，有 3 组解，数组中就会对应含有 2,3,5 这三个数；…… 当 k =n 时，a +b +c =n ，共有 C n+22 组解，所以共有 A =C 22+C 32+C 42+⋯+C n+22 个数，而只有当 n =11 时，有 A =1+3+6+10+⋯+78=364，在 300～400 中，所以答案为 364．6. 如图，正方形 ACEG 的边界上共有 7 个点 A 、B 、C 、D 、E 、F 、G 、其中 B 、D 、F 分别在边 AC 、CE 、EG 上．以这 7 个点中的 4 个点为顶点组成的不同的四边形的个数是 个．【答案】 23【分析】 从 7 个点中选出 4 个点有 C 74=7×6×5×44×3×2×1=35〔种〕方法．但其中有三个点在同一条直线上的情况，此时所选择的四个点不能组成四边形．这在同一条直线上的三个点可能是 A 、B 、C ，可能是 C 、D 、E ，也可能是 E 、F 、G ，而对于其中的每一种情况，第四个点都可以从其余的 4 个点中选取．因此应排除的情况有 3×4=12〔种〕，所以组成的不同的四边形的个数是 35−12=23〔个〕．7. 在一次射击比赛中，8 个泥制的靶子挂成三列〔如图〕，其中有两列各挂 3 个，一列挂 2 个，一位射手按照以下规那么去击碎靶子：先挑选一列，然后必须击碎这列中尚未击碎的靶子中最低一个，假设每次射击都严格执行这一规那么，击碎全部 8 个靶子的不同方法有 种．【答案】560【分析】8个泥制的靶子，看做8个位置，从中选出3个放左侧一列，再选一列放右侧一列，余下放中间列，并且下边先破最上边最后破，故有C83×C53×C22=560(种).8. 有红、黄、蓝、白、黑五种形状大小完全一样的小球假设干，每人必须从中选3只小球．要使有两人得到球的颜色完全一样，至少有人参加选球．【答案】36【分析】分所选3个球同色、两种颜色、三种颜色三种情况，共有C51+2C52+C53=35〔种〕情况，35+1=36．9. 从6双不同的鞋中取出2只，其中没有成双的鞋．共有种不同取法．【答案】60【分析】第一只鞋可以从12只鞋中任选，而第二只鞋只能从剩下的10只鞋中任选，且选第一只鞋与第二只鞋无顺序之分，所以C122×C101÷2=60．10. 将5枚棋子放入下面编号为4×4表格的格子中，每个格子最多放一枚，如果耍求每行，每列都有棋子．那么共有种不同放法．【答案】432【分析】5枚棋子放4行，每行都有，一定是1行2枚，另3行各1枚；同理，有1列2枚，另3列各1枚；〔1〕如图a〕，1行2枚和1列2枚有1枚重复．按①，②，③，④，⑤的顺序选格，有：16×3×3×2×1=288(种)〔2〕如图b〕，1行2枚和1列2枚无重复．此时，这4枚棋子占据了三行三列，那么最后一枚棋子的位置是确定的．首先，选择三行三列的方法数为C43×C43=9种，所以这种情况下总的方法数是16×9=144种．综上所述，共288+144=432(种)．11. 9枚棋子放入5×5的方格网内，每个方格至多只放一枚棋子，且每行每列的棋子个数均为奇数个，那么共有种不同的放法．【答案】600【分析】反过来考虑6个空格，那么肯定是某3行和某3列中每行每列各有2个，如下：▫ ▫ ○▫ ○ ▫○ ▫ ▫▫表示空格，○表示有棋子的方格，其他方格全部有棋子．选择有空格的3行3列有C53×C53=100种选法，在这3行3列中选择6个空格有3×2×1=6种选法，所以总共有600种．12. 中国大陆的车牌号一般包括一个汉字与6个由字母或数字组成的编码构成，比方“京 QFR 067〞，汉字后面紧跟一个字母〔从A到Z〕，之后的位置上可以是数字〔从0到9〕，也可以是字母〔从A到Z，但不包括O和I〕，但最多只允许有2个字母．那么，按照这个规那么，以“京Q〞开头的不同车牌号一共可以有个．【答案】7060000【分析】京Q的车牌，根据题意可以分为没有字母的，只有一个字母的，含有两个字母的，下面分类计算：〔1〕没有字母的，即有5个数字组成，共有10×10×10×10×10=100000〔2〕只有一个字母，除掉O和I后，还有24个字母可以选择，即：24×5×10×10×10×10=1200000〔3〕含有两个字母的，先从5个位置中选俩位置，有C52种选法，然后每个位置上都可能有24种不同的字母，再把数字放好即可C52×24×24×10×10×10=5760000综上，共有100000+1200000+5760000=706000013. 如果一个大于9的整数，其每个数位上的数字都比它右边数位上的数字小，那么我们称它为“迎春数〞．那么，小于2008的“迎春数〞共有个．【答案】176【分析】方法一：枚举法——按位数分类计算．两位数中，“迎春数〞个数〔1〕十位数字是1，这样的“迎春数〞有12,13,⋯,19，共8个；〔2〕十位数字是2，这样的“迎春数〞有23,⋯,29，共7个；〔3〕十位数字是3，这样的“迎春数〞有34,⋯,39，共6个；〔4〕十位数字是4，这样的“迎春数〞有45,⋯,49，共5个；〔5〕十位数字是5，这样的“迎春数〞有56,⋯,59，共4个；〔6〕十位数字是6，这样的“迎春数〞有67,68,69，共3个；〔7〕十位数字是7，这样的“迎春数〞有78,79，共2个；〔8〕十位数字是8，这样的“迎春数〞只有89这1个；〔9〕没有十位数字是9的两位的“迎春数〞；所以两位数中，“迎春数〞共有8+7+6+⋯+1=36〔个〕．三位数中，“迎春数〞个数〔1〕百位数字是1，这样的“迎春数〞有123～129,134～139,⋯,189，共28个；〔2〕百位数字是2，这样的“迎春数〞有234～239,⋯,289，共21个；〔3〕百位数字是3，这样的“迎春数〞有345～349,⋯,389，共15个；〔4〕百位数字是4，这样的“迎春数〞有456～459,⋯,489，共10个；〔5〕百位数字是5，这样的“迎春数〞有567～569,⋯,589，共6个；〔6〕百位数字是6，这样的“迎春数〞有678,679,689，共3个；〔7〕百位数字是7，这样的“迎春数〞只有789，这1个；〔8〕没有百位数字是8,9的三位的“迎春数〞；所以三位数中，“迎春数〞共有28+21+15+10+6+3+1=84〔个〕．1000～1999的自然数中，“迎春数〞个数〔1〕前两位数字是12，这样的“迎春数〞有1234～1239,⋯,1289，共21个；〔2〕前两位数字是13，这样的“迎春数〞有1345～1349,⋯,1389，共15个；〔3〕前两位数字是14，这样的“迎春数〞有1456～1459,⋯,1489，共10个；〔4〕前两位数字是15，这样的“迎春数〞有1567～1569,⋯,1589，共6个；〔5〕前两位数字是16，这样的“迎春数〞有1678,1679,1689，共3个；〔6〕前两位数字是17，这样的“迎春数〞只有1789这1个；〔7〕没有前两位数字是18,19的四位的“迎春数〞；所以四位数中，“迎春数〞共有56个．2000～2008的自然数中，没有“迎春数〞所以小于2008的自然数中，“迎春数〞共有36+84+56=176〔个〕．方法二：利用组合原理小于2008的自然数中，只可能是两位数、三位数和1000多的数．计算两位“迎春数〞的个数，它就等于从1～9这9个数字中任意取出2个不同的数字，每一种取法对应于一个“迎春数〞，即有多少种取法就有多少个“迎春数〞．显然不同的取法有C92=9×8÷2=36〔种〕，所以两位的“迎春数〞共有36个．同样计算三位数和1000多的数中“迎春数〞的个数，它们分别有C93=9×8×7÷(3×2×1)=84〔个〕和C83=8×7×6÷(3×2×1)=56〔个〕．所以小于2008的自然数中，“迎春数〞共有36+84+56=176〔个〕．14. 用2颗红色的珠子，2颗蓝色，2颗紫色，2颗绿色的珠子串成如以下图所示的手链，要求两颗红色珠子相邻，两颗紫色珠子相邻，那么，可以串成种不同的手链．【答案】16【分析】因为是手链，所以，旋转、翻转相同的只能算同一种按红色和紫色珠子的分布有如下三种〔如图〕：第一种：与红色相邻的两颗珠子有：蓝蓝、绿绿、蓝绿三种，其中蓝绿的有两种可能，共4种；第二种：单独的一颗有2种可能，另3颗有3种可能，共：2×3=6(种)；第三种：此时是有序排列，四个位置两个放蓝珠子即可，有C42=6(种)；共4+6+6=16(种)不同的手链。

小学奥数趣味学习《计数问题》典型例题及解答计数问题是指数学中排列组合应用中的计数问题。

数学计数原理中排列组合问题简单的解决方法，是解决计数问题的基本原则与一般策略。

解题思路和方法：特殊元素优先安排；相邻问题捆绑处理（先整体后局部）；不相邻问题插空处理；顺序一定问题除法处理。

例题1：用2、0、1、8四个数字组成四位数，一共可以组成多少个不同的四位数？解：1、本题考查的是一般计数问题，0是特殊元素，需要特殊安排。

2、组成的四位数最高位上不能是0，那么1、2、8可作最高位。

1作最高位时有1028，1082，1208，1280，1802,1820；2作最高位时有2018，2081，2108，2180，2801，2810；8作最高位时有8012，8021，8102，8120，8201，8210。

3、所以，最高位有3种排法，后三位有6种排法，一共18种。

例题2：欢欢有5顶帽子，上衣11件，裤子18条。

如果一顶帽子、一件上衣和一条裤子作为一套服饰，欢欢希望每天都穿不一样的服饰，那么欢欢的愿望能实现多少天？解：1、本题考查衣服的搭配，只要计算出欢欢能组成多少套不同的服饰，即可确定天数。

2、在解决计数问题时关键要搞清楚用加法原理还是乘法原理来计算。

5顶帽子每顶都可以配11件上衣，每组帽子和上衣组合又可以单独配18条裤子，所以5×11×18=990套。

例题3：如图，小红从家到学校，只能向东或向南，一共多少种不同的路线？解：1、解决这个问题时，如果一条一条的去找，容易重复或者漏掉，我们可以采用标数字的方法。

2、小红从家到A有1条路，在A点标上1，从家到B有1条路，在B点标上1。

所以，从小红家到C就有2条路（从家到A的1与从家到B的1相加所得的和），以此类推，可以得到其它交点上的数字，如下图所示：所以一共有10种不同的路线。

组合(插板、定序) 之技巧方法篇(★★★)马路上有编号为1，2，3，…，10的十只路灯，为节约用电又能看清路面，可以把其中的三只灯关掉，但又不能同时关掉相邻的两只，在两端的灯也不能关掉的情况下，求满足条件的关灯方法有多少种？(★★★)一个小组共10名学生，其中4名女生，6名男生。

现从中选出3名代表，其中至少有一名女生的选法？例1例2例3(★★★★)由数字1，2，3组成的五位数，要求这五位数中1，2，3至少各出现一次，那么这样的五位数共有个。

例4(★★★★)(迎春杯初赛试题)⑴如果一个大于9的整数，其每个数位上的数字都比它右边数位上的数字小，那么我们称它为“迎春数”。

那么，小于2008的“迎春数”共有个。

例4(★★★★)⑵某种奖券的号码有9位，如果奖券至少有两个非零数字并且从左边第一个非零数字起，每个数字小于它右边的数字，就称这样的号码为“中奖号码”，如000000015，000001257。

“中奖号码”有多少个？例5(★★★★)有11名外语翻译人员，其中5名是英语翻译员，4名是日语翻译员，另外两名英语、日语都精通。

从中找出8人，使他们组成两个翻译小组，其中4人翻译英文，另4人翻译日文，这两个小组能同时工作。

问这样的分配名单共可以开出多少张?例6(★★★★)⑴把10个相同的球放入3个不同的盒子里，要求每个盒子里至少有一个球，有多少种放法？例6(★★★★)⑵小红有10块糖，每天至少吃1块，7天吃完，她共有多少种不同的吃法？(★★★★)把10个相同的球放入3个不同的盒子里，要求每个盒子里都至少有2个球，有多少种放法？一、本讲知识⑴一般地，从n 个不同元素中任意取出m 个(m ≤n )元素组成一组，不计较组内各元素的顺序，叫做从n 个不同元素中取出m 个元素的一个组合。

所有组合的个数，叫做从n 个不同元素中取出m 个元素的组合数，记作m n C⑵(1)(2)(1)!mnC n n n n m m =---+÷ ⑶重要结论：①01n nn C C ＝＝ ②m n m n n C C -＝二、本讲方法隔板法——相同物品放在不同位置(或分给不同的人) 特征——⑴相同物品⑵放在不同位置(或分给不同人) ⑶至少一个例7。

数学竞赛讲义第一讲 组合计数本讲概述组合数学是竞赛中最重要的一个板块，也是变化最多，最灵活，难以掌握，至今还没有一个系统体系的学科.解决竞赛中的组合数学问题，往往不需要太多专门的知识，而是要求深刻的洞察能力和强大的化归、转化能力.所谓“得组合者得天下”，在联赛一二试乃至冬令营、集训队、IMO 中，最后的胜者往往是成功完成组合问题的同学.因此，学习组合数学对于竞赛获奖以及数学能力的培养都有着十分重要的意义.从本讲开始，我们将用七讲来对组合数学做一个大致的勾勒.通过这七讲的学习，达到以下目的：1、掌握联赛一二试组合问题的特点与解法；2、对组合数学这门学科有一个初步的认识，为进一步学习打下基础；3、了解部分冬令营级别组合问题的难度与解题模式.七讲内容分别为：一、组合计数（1） 比高考略难的基本计数问题 二、组合计数（2） 需要较多技巧的专门计数问题 三、组合恒等式 较为重要和有趣味的组合恒等式 四、抽屉原理与存在性问题 五、容斥原理与极端性原理六、染色问题与操作问题 七、组合数学综合问题本讲中，假定各位同学已经大致学完了高考难度的排列组合模块内容，对加法原理、乘法原理等有一定的理解并能完成相关的问题.教师备注：本讲可与下一讲打通讲述，也可本讲专门讲常规的枚举、基本的组合问题，下一讲专门讲述一些较为高级的技巧.首先给出一些相关的基本知识： 1、 加法原理与乘法原理加法原理：完成一件事的方法可分成n 个互不相交的类，在第1类到第n 类分别有12,,...,n m m m 种方法，则总共完成这件事有121...nin i mm m m ==+++∑种方法.应用加法原理的关键在于通过适当的分类，使得每一类都相对易于计数.乘法原理：完成一件事的方法有n 个步骤，，在第1步到第n 步分别有12,,...,n m m m 种方法，则总共完成这件事有121...nin i m mm m ==∏种方法. 应用乘法原理的关键在于通过适当的分步，使得每一步都相对易于计数.由上可见，加法原理与乘法原理也是化归思想的应用，通过这两个原理以及它们的组合，可以将一个复杂的组合计数问题分解成若干个便于计数的小问题.2、 无重排列与组合阶乘：定义 !(1)(2)...21n n n n =⋅-⋅-⋅⋅⋅，读作n 的阶乘无重排列：从n 个不同元素中任取m 个不同元素排成一列，不同的排列种数称为排列数，记为mnA （部分书中记为m n P ），由乘法原理得到!(1)...(1)()!m n n A n n n m n m ==⋅-⋅⋅⋅-+-无重组合：从n 个不同元素中任取m 个元素并为一组，不同的组合种数称为组合数，记为mn C ，其公式为(1)...(1)!!!()!!mmn nA n n n m n C m m n m m ⋅-⋅⋅⋅-+===- 3、 可重排列与组合（仅给出结论，请自证之）可重排列：从n 个不同元素中可重复地任取m 个元素排成一列，不同的排列种数有mn 种； 有限个重复元素的全排列：设n 个元素由k 个不同元素12,,...,k a a a 组成，分别有12,,...,k n n n 个（12...k n n n n +++=），那么这n 个元素的全排列数为12!!!...!k n n n n ⋅⋅⋅可重组合：从n 个不同元素中，任意可重复地选取m 个元素，称为n 个不同元素中取m 个元素的可重组合，其种数为1mn m C +-4、 圆排列（仅给出结论，请自证之）在n 个不同元素中，每次取出m 个元素排在一个圆环上，叫做一个圆排列（或叫环状排列）．圆排列有三个特点：（i ）无头无尾；（ii ）按照同一方向转换后仍是同一排列；（iii ）两个圆排列只有在元素不同或者元素虽然相同，但元素之间的顺序不同，才是不同的圆排列．在},,,,{321n a a a a A =的n 个元素中，每次取出m 个不同的元素进行圆排列，圆排列数为mn A m．例题精讲板块一 利用加法、乘法原理以及枚举方法计数联赛一试的填空题中出现的计数问题有接近一半的问题不需要用到很高深的技巧，而是直接利用最基本的加法、乘法原理，以及枚举方法来计数.这主要是考虑到有一部分参加联赛的同学并未经过专业的竞赛训练.虽然如此，这部分计数问题枚举起来往往分类复杂，需要小心仔细.从往年的联赛试题来看，枚举法解决计数问题是最主要的题型之一，其难点在于做到“不重不漏”，这是加法原理的一个简单的应用.枚举过程中，采用恰当的分类、分步形式，往往会收到化难为易的效果.【例1】 (高考难度的热身问题)（1）等腰三角形的三边均为正整数．它们周长不大于10．这样不同的三角形的种数为A ．8B ．9C ．10D ．1l（2）有两排座位，前排11个座位，后排12个座位，现安排2人就座，规定前排中间的3个座位不能坐，并且这2人不左右相邻，那么不同排法的种数是 A.234 B ．346 C. 350 D ．363 【解析】 （1）设三边为x,y ，z ，则x+y+z ≤10，由三边关系共有(1，1，1)，(1，2，2)，(1，3，3)，(1，4，4)，(2，2，2)，(2，2，3)，(2，3，3)，(2，4，4)，(3，3，3)，(3，3，4)共10种．（2）B 前排中间的3个座位不能坐，有排法220A ，其中相邻的分三类，在前排的其中的4个座位有322A ；则符合条件的排法种数中2222222201133A A A A ---=346，故选B （这是正难则反的思想，从总体中除去不符合要求的）另解：分三类：①两人坐在前排，按要求有4·6+4·5=44种坐法．②两人坐在后排，按要求有：211A =110种坐法．③两人分别坐在前后排，有8×12×2=192种∴共有346种排法．【例2】 （1）有多少个能被3整除而又含有数字6的五位数？（2）集合{1,2,...,100}的子集中共有多少个至少包含一个奇数？【解析】 （1）按照上题正难则反的思想，可以先找出所有的五位数，共有90000个，其中可被3整除的有30000个，下面研究这30000个数中不含数字6的数，最高位有8种选择，千、百、十位各有9种选择，个位数除不能为6外，还应满足恰各位数之和可被3整除，这恰有3种选择，例如当前四位除以3余2时，个位应为1,4,7之一；故能被3整除且不含数字6的有8999317496⨯⨯⨯⨯=个，故所求五位数有30000-17496=12504个（2）显然全部子集数为1002个，不包含任何奇数的子集即{2,4,6,...,98,100}的子集共有502个，故所求子集个数为1005022-个.(思考：请用最简洁的方法确定为何n 元集合子集数为2n个)【例3】 设ABCDEF 为正六边形，一只青蛙开始在顶点A 处，它每次可随意地跳到相邻两顶点之一．若在5次之内跳到D 点，则停止跳动；若5次之内不能到达D 点，则跳完5次也停止跳动，那么这只青蛙从开始到停止，可能出现的不同跳法共 种【解析】 这是标准的联赛风格的枚举问题，所谓杀鸡焉用牛刀，用递归方法来解这类问题就太麻烦了.显然青蛙不能跳1，2,4次到达D 点，于是青蛙的跳法只有以下两种： （1）青蛙跳3次后到达D 点，有2种跳法； （2）青蛙跳5次后停止，跳3次有322-种，后两次有22种，共计24种； 所以，合计有26种跳法注 本题为1997年联赛试题【例4】 从给定的六种不同颜色中选用若干种颜色，将一个正方体的六个面染色，每面恰染一种颜色，每两个具有公共棱的面染成不同的颜色。

数学奥赛辅导 组合计数知识、方法、技能组合计数就是计算集合的元素个数。

它是组合数学的重要组成部分.在具体问题中给出的集合各式各样，都具有实际意义，而且集体中的元素是由某些条件所确定的，要判定一个元素是否属于某集合A ，已非易事，要确定A 的元素个数就更难了.这正是研究计算问题的原因。

解决组合计算问题虽然不需要高深理论知识，却需要重要的计算原理与思想方法. Ⅰ．几种特殊的排列、组合 1．圆排列定义1：从几个元素中任取r 个不同元素仅按元素之间的相对位置而不分首尾排成一个圆圈，这种排列称为n 个不同元素的r ——圆排列。

r ——圆排列数记为rn K .定理1：.rP K rn r n证：对n 个不同元素取r 个的任一圆排列，均有r 种不同的方式展开成r 个不同的直线排列，且不同的圆排列展开的直线排列也彼此不同，故有r ·rn K =P r n ，得正.2．重复排列定义2：从n 个不同元素中允许重复的任取r 个元素排成一列，称为n 个不同元素的r ——可重复排列.定理2：n 个不同元素的r ——可重排列数为n r .证：在按顺序选取的r 个元素中，每个元素都有n 种不同的选法，故由乘法原理有，其排列数为n r .3．不全相异元素的全排列定义3：设n 个元素可分为k 组，每一组中的元素是相同的，不同组间的元素是不同的，其中第i 组的元素个数为n i (i =1, 2, …, k ), n 1+n 2+…+n k =n . 则这n 个元素的全排列称为不全相异元素的全排列.定理3：n 个元素的不全相异元素的全排列个数为.!!!!.21k n n n n证：先把每组中的元素看做是不相同的，则n 个不同元素的全排列数为n!，然后分别将每个组的元素还其本来面目看成是相同的，则在这n!个全排列中，每个排列都重复出现了n 1！n 2!……n k ！次，所以不全相异元素的全排列数.!!!!.21k n n n n4．多组组合定义4：将n 个不同的元素分成k 组的组合称为n 个不同元素的k ——组合.定理4：对于一个n 个不同元素的k ——组合，若第i 组有n i 个元素（i =1, 2, …，k ），则不同的分组方法数为.!!!!.21k n n n n证：我们把分组的过程安排成相继的k 个步骤.第一步，从n 个不同元素中选n 1个，有1nn C 种方法；第二步，从n －n 1个元素中选n 2个有21nn n C 种方法；…；第k 步，从n －（n 1+n 2+…+n k －1）个元素中选n k 个元素，有k nn C －（n 1+n 2+…+n k －1）种方法，再由乘法原理得证.5．重重组合定义5：从n 个不同元素中任取r 个允许元素重复出现的组合称为n 个不同元素的r ——可重组合.定理5：n 个不同元素的r ——可重组合的个数为C r n+r －1 .证：设（a 1 , a 2 ,…，a r ）是取自{1，2，…，n}中的任一r 可重复组合，并设a 1≤a 2≤…≤a r .令 b i =a i +i －1(1≤i ≤r).从而b 1=a 1 , b 2=a 2+1 , b 3=a 3+2,…, b r =a+r －1r . 显然下面两组数是一对一的：a 1≤a 2≤a 3≤…≤a r , 1≤a 1<a 2+1<a 3+2<…<a r +r －1≤n+r －1.设 A={（a 1 , a 2 ,…，a r ）|a i ∈{1，2，…，n}，a 1≤a 2≤…≤a r }， B={（b 1, b 2,…，b r ）|b i ∈{1，2，…，n+r －1}，b 1< b 2<…<b r }. 则由A 、B 之间存在一一对应，故|A|=|B|=C r n+r －1 .Ⅱ．枚举法所谓枚举法就是把集合A 中的元素一一列举出来，从而计算出集体A 的元素个数。

组合计数问题和概率组合计数问题是教学竞赛中常见的一类问题，也是数学竞赛中与实际生活联系最为直接的内容。

计数问题的顺利解决会给其他排列组合问题的解决打下竖实的基础。

概率作为新增内容，拓展了排列组合的研究和应用的领域。

实则是以排列组合为基础的内容，所以概率的考查通常与计数问题联系在一起，既要用到排列组合的知识来解答，也要用到排列、组合的解题思路。

解组合计数问题的基本方法有枚举法和利用基本计数原理及基本公式、映射方法、算二次方法、递推方法、容斥原理等，其中蕴含的数学思想有分类讨论的思想、化纳和转化的思想、函数与方程的思想等重要的数学思想。

例1． （2004年全国高中联赛题）设三位数为abc n =，若以a ，b ，c 为三条边的长可以构成一个等腰(含等边)三角形，则这样的三位数n 有A ．45个B ．81个C ．165个D ．216个解：选C 。

理由：a , b , c 要构成三角形边长，显然不为零，即a , b , c ∈{1, 2, 3, …, 9}。

（1）若构成等边三角形，则c b a ==可取{1, 2, …, 9}中任何一个值，所以这样的三位数的个数为9191==C n 。

（2）若构成等腰（非等边）三角形，设这样的三角形个数为n 2，且等腰三角形的三边长为a 1, b 1=c 1。

当111c b a =<时，即腰大于底边时，等腰（非等边）三角形由数组(a 1, b 1)惟一确定，有29C 个；当111c b a =>时，即腰小于底边时，这时数组(a 1, b 1)有29C 个，但必须1112b a b <<才能构成三角形。

而不能构成三角形的组数(a 1, b 1)是共20种情况，故这时等腰（非等边）三角形只有2039-C 个。

同时，每个数组(a 1, b 1)可形成23C 个三位abc ，故156)20(2929232=-+=C C C n 。

综上，16521=+=n n n ，故选C 。

组合计数（一）一、基础知识（一）、两条基本原理1、（加法原理）如果完成某件事有n 类互相排斥的办法，在第1类办法中有1m 种方法，在第2类办法中有2m 种方法，……，在第n 类办法中有n m 种方法，那么完成这件事共有n m m m N +++= 21种不同的方法.2、（乘法原理）如果完成某件事需要分n 个互相独立的步骤，做第1步有1m 种方法，做第2步有2m 种方法，……，做第n 步有n m 种方法，只有依次完成每个步骤，才能完成这件事，那么完成这件事共有n m m m N ⋅⋅⋅= 21种不同的方法.（二）、排列及排列数公式1、定义1：（排列）从n 个不同的元素中任取)(n m m ≤个元素（各不相同），按照一定的顺序排列成一列，叫做从n 个不同元素中取出m 个元素的一个排列．2、定义2：（排列数）从n 个不同的元素中任取)(n m m ≤个元素的所有排列的个数，叫做从n 个不同元素中取出m 个元素的排列数，记做mn A ． 3、排列数公式：!)(!)1()2)(1(m n n m n n n n A mn -=+---= ，N n m ∈,,且n m ≤．4、全排列公式：!12)2)(1(n n n n A nn =⋅--= ．(三)、组合及组合数公式1、定义3：（组合）从n 个不同的元素中任取)(n m m ≤个元素（各不相同）并成一组，叫做从n 个不同元素中取出m 个元素的一个组合．2、定义4：(组合数) 从n 个不同的元素中任取)(n m m ≤个元素的所有组合的个数，叫做从n 个不同元素中取出m 个元素的组合数，记做mn C ．3、组合数公式：!)(!!!)1()2)(1(m n m n m m n n n n A A C m mmn mn-=+---== ． 4、组合数的两个性质：（1）m n n m n C C -=； （2）11-++=m n m n m n C C C ．(四)、几种特殊排列与组合1、圆排列：将从n 个不同的元素首尾排成一圈，称为n 个相异元素的圆排列，这种排列的个数为!)1(-n ．2、可重复的排列：从n 个不同的元素中取m 个元素（同一元素允许重复取出），按照一定的顺序排列成一列，叫做从n 个不同元素中取m 个元素的可重复排列．这种排列的个数为mn ．3、可重复的组合：从n 个不同的元素中取m 个元素（同一元素允许重复取出）并成一组，叫做从n 个不同元素中取m 个元素的可重复组合．这种组合的个数为mm n C 1-+．4、不全相异元素的全排列：如果n 个元素中，分别有k n n n ,,,21 个元素相同，且n n n n k =+++ 21，则这n 个元素的全排列称为不全相异元素的全排列．这种排列的个数为!!!!21k n n n n ⋅⋅⋅ ．5、多重组合：把n 个相异元素分为)(n k k ≤个不同的组，其中第i 组有i n 个元素（,,,2,1k i =n n n n k =+++ 21），则不同的分组方法的种数为!!!!21k n n n n ⋅⋅⋅ ．（五）两个重要结论（1）、不定方程)(21m n n x x x m ≥=+++ 的正整数解的组数为11--m n C ；（2）、不定方程n x x x m =+++ 21的非负整数解的组数为nm n m m n C C 111-+--+=.二、典型问题选讲问题1、12名同学合影，站成前排4人后排8人，现摄影师要从后排8人中抽2人调整到前排，若其他人的相对顺序不变，求不同调整方法的总数．问题2、7个人并排站成一排，（1） 如果甲必须站在正中间，有多少种排法？ （2） 如果甲乙两人必须站在两端，有多少种排法？ （3） 如果甲乙两人必须相邻，有多少种排法？ （4） 如果甲乙两人必须不相邻，有多少种排法？（5） 如果甲乙两人中间必须恰有2人，有多少种排法？（6） 如果甲乙丙三人之间都恰好有1个其他人，有多少种排法？ （7） 如果甲乙丙三人两两不相邻，有多少种排法？问题3、4男4女交替坐在圆桌旁，有多少种坐法？问题4、10个男生和5个女生聚餐，围坐在圆桌旁，任意两个女生不相邻的坐法有多少种？问题5、将3面红旗、4面蓝旗、2面黄旗依次挂在旗杆上，求组成不同的标志的种数．问题6、求不定方程15210321=++++x x x x 的正整数解的组数．问题7、求不定方程233332254321=++++x x x x x 的正整数解的组数．问题8、在世界杯足球赛前，F 国教练为了考察721,,,A A A 这七名队员，准备让他们在三场训练比赛（每场90分钟）都上场．假设在比赛的任何时刻，这些队员中有且仅有一人在场上，并且4321,,,A A A A 每人上场的总时间（以分钟为单位）均能被7整除，765,.,A A A 每人上场的总时间（以分钟为单位）均能被13整除．如果每场换人次数不限，那么按每名队员上场的总时间计算，共有多少种不同的情况．问题9、求各位数字之和等于11的3位数的个数．问题10、如果自然数a 的各位数字之和等于7，那么就称a 为“吉祥数”．将所有“吉祥数”从小到大排成一列 ,,,321a a a ，若2005=n a ，则=n a 5 ．问题11、将24个志愿者名额分配给3个学校，问每校至少有1名额且各校名额互不相同的分配方法有多少种？问题12、甲、乙两队各出7名队员按事先安排好的顺序出场参加围棋擂台赛，双方先由号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，依次类推，直到有一方队员全被淘汰为止，另一方获得胜利，形成一种比赛过程，求所有可能出现的比赛过程的种数.问题13、如果从数14,,2,1 中，按由小到大的顺序取出321,,a a a ，使同时满足3,32312≥-≥-a a a a ，那么，所有符合上述要求的不同取法有多少种？问题14、设10021,,,a a a 是100,,3,2,1 的任意排列，部分和11a S =，212a a S +=，,3213a a a S ++=，10021100a a a S +++= .若数列)1001}({≤≤j S j 中的每一项都不被3整除，问这样的排列有多少个？。

奥林匹克数学中的组合问题奥林匹克数学中的组合问题是指在给定的一组对象中选择其中几个对象，形成一个由这些对象组成的集合。

组合问题是数学中的一个重要分支，也是奥林匹克数学竞赛的难点之一。

在奥林匹克数学竞赛中，组合问题要求考生具备逻辑思维和抽象思维能力，有时还需要一定的想象力和创造力。

以下是奥林匹克数学中组合问题的基本步骤：第一步：明确问题组合问题的第一步是要明确问题，即明确给定的对象和要求选择的集合的性质。

例如，问题可能要求在5个仪器中选择3个仪器，并且这3个仪器能够组成一组能够实现某种功能的仪器组合。

第二步：计算对象总数组合问题中需要计算对象的总数，这是问题的基本数据。

例如，如果给定了5个仪器，则对象总数为5。

第三步：确定选择的对象数组合问题需要确定要从给定的对象中选择多少个对象。

例如，如果要从给定的5个仪器中选择3个仪器，则选择的对象数为3。

第四步：计算组合数组合问题需要计算可以选择的方案数，即选择若干对象形成的集合的总数。

组合数可以用下列公式计算：$$C_n^m=\frac{n!}{m! (n-m)!}$$其中，$C_n^m$表示从n个不同对象中选择m个对象的方案数，称为“从n个不同的对象中选出m个对象的组合数”。

例如，选择3个对象的组合数可以计算如下：$$C_5^3=\frac{5!}{3! (5-3)!}=\frac{5\times4\times3}{3\times2\times1}=10$$即从5个对象中选出3个对象的方案数为10。

第五步：求解问题组合问题需要根据题目要求，结合计算出的组合数，得出具体的方案。

例如，如果要求从5个仪器中选择3个仪器，并且这3个仪器能够组成一组能够实现某种功能的仪器组合，则需要在10个可能的方案中找到满足条件的方案。

总之，奥林匹克数学中的组合问题是一个需要逻辑思维和抽象思维能力的问题，需要根据题目要求明确问题，计算对象总数和选择的对象数，计算组合数，然后结合题目要求求解问题。

奥林匹克数学题型高级组合计数问题在奥林匹克数学竞赛中，高级组合计数问题是一类常见的题型，它要求学生利用组合数学的知识，解决复杂的计数问题。

本文将介绍高级组合计数问题的定义、基本性质以及解题思路，并通过实例进行详细说明。

一、高级组合计数问题的定义和基本性质1. 定义：高级组合计数问题是指在给定条件下，求解满足特定要求的组合的个数。

2. 基本性质：在解决高级组合计数问题时，需要了解以下几个基本性质：a. 排列组合公式：排列是指从n个元素中取出m个元素进行全排列，记作A(n,m)；组合是指从n个元素中取出m个元素进行组合，记作C(n,m)。

排列和组合的计算公式如下：A(n,m) = n! / (n-m)!C(n,m) = n! / (m!(n-m)!)b. 加法原理：如果一个事物可以通过某种方式分成若干部分，而每一部分又可以有若干种不同的选择方式，则总的选择方式数等于各部分选择方式数的乘积。

c. 乘法原理：如果一个事物可以通过若干个步骤完成，且每个步骤的选择方式数相互独立，则总的选择方式数等于各步骤选择方式数的乘积。

d. 容斥原理：当计算两个集合的并集时，求其元素个数的一种方法就是将两个集合的元素个数相加，然后减去它们的交集元素个数。

二、高级组合计数问题的解题思路在解决高级组合计数问题时，我们可以采用如下的解题思路：1. 理解问题：首先要仔细阅读题目，理解题目中所给出的要求，并明确所需计算的数量是排列还是组合。

2. 确定组合对象：根据题目的要求，确定组合对象的数量和特性，例如考虑选择的人数、事件的种类等。

3. 划定条件：根据题目的限制条件，确定每个组合对象的选择方式和约束条件，如是否可以重复选择、是否需要特定的顺序等。

4. 计算数量：根据以上信息，利用排列组合公式、加法原理、乘法原理和容斥原理等基本性质，计算满足要求的组合的数量。

5. 检查结果：最后，对计算结果进行检查，确保计算过程准确无误。

可以通过简单的验证或更复杂的例子来检验答案的正确性。

组合数学选讲组合数学是中学数学竞赛的“重头戏”，具有形式多样，内容广泛的特点.本讲主要围绕组合计数，组合恒等式及组合最值展开例题讲解1．圆周上有800个点，依顺时针方向标号为1,2,…,800它们将圆周分成800个间隙.今选定某一点染成红色，然后按如下规则，逐次染红其余的一些点：若第k号点染成了红色，则可依顺时针方向转过k个间隙，将所到达的点染成红色，试求圆周上最多可以得到多少个红点？2．集合X的覆盖是指X的一族互不相同的非空子集A1、A2、…、A k，它们的并集A1∪A2∪…∪A k=X，现有集合X={1,2,…,n}，若不考虑A1, A2,…, A k的顺序，试求X的覆盖有多少个？3．已知集合X={1,2,…,n}，映射f ：X →X ，满足对所有的x ∈X ，均有f(f(x))=x ，求这样的映射f 的个数.4．S 为{1,2,…,n}的一些子集族，且S 中任意两个集合互不包含，求证：S 的元素个数的最大值为(Sperner 定理)5．设M={ 1,2,3,…,2m n} (m,n ∈N *)是连续2m n 个正整数组成的集合，求最小的正整数k ，使得M 的任何k 元子集中都存在m+1个数，a 1,a 2,…a m+1，满足a i |a i+1 (i=1,2,…,m).n n 2⎛⎫⎪⎡⎤ ⎪ ⎪⎢⎥⎣⎦⎝⎭6．计算.7．证明： (范德蒙公式)8．在平面上有n(≥3)个点，设其中任意两点的距离的最大值为d ，我们称距离为d 的两点间的线段为该点集的直径，证明：直径的数目至多有n 条.9．已知：两个非负整数组成的不同集合和.求证：集合与集合相同的充要条件是n 是2的幂次，这里允许集合内，相同的n2k 1n k k =⎛⎫⎪⎝⎭∑qk 0n m m n k q k q =+⎛⎫⎛⎫⎛⎫= ⎪⎪ ⎪-⎝⎭⎝⎭⎝⎭∑},,,{1n a a a a },,,{21n b b b }1{n j i a a j i ≤<≤+}1{n j i b b j i ≤<≤+元素重复出现.课后练习1. 空间n 条直线，最多能把空间分成多少块空间区域？2. 证明：.3. 证明：.2nk 0n 2n k n =⎛⎫⎛⎫⎛⎫= ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭∑n k k 0n 111(1)1k 2k n=⎛⎫⎛⎫-+++=-⎪⎪⎝⎭⎝⎭∑4. 证明：在边长为1的等边三角形内有五个点，则这五个点中一定有距离小于的两点.例题答案：1．解：易见，第k 号点能被染红的充要条件是∃j ∈N *⋃{0}，使得a 02j ≡k (mod800)，1≤k ≤800 ①12⨯这里a 0是最初染的点的号码，为求最大值，不妨令a 0=1.即2j ≡k (mod25×52).当j=0,1,2,3,4时，k 分别为1,2,4,8,16，又由于2模25的阶，因此，当j ≥5时2j+20-2j =2j (220-1)≡0(mod 800),而对∀k<20,k ∈N *，及j ≥5,j ∈N *，由于25+(2k -1)，所以2j+k -2j =2j (2k -1)不为800的倍数. 所以，共存在5+20=25个k ，满足①式。