下载文档原格式
组合组合计数组合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. 直接计数法这个方法最简单和直接，也是最常见的方法。
直接计数法指的是通过简单的数学运算，如加减乘除等，来计算所需要的组合方案数。
举个例子，如果我们需要从1,2,3,4,5这五个数中选取3个数组成排列，那么我们可以用直接计数法得到：$5*4*3=60$。
2. 阶乘计数法阶乘计数法是指通过对组合元素进行阶乘计算来得到组合情况的方法。
因为阶乘的数值是很大的，所以这种方法一般用于较小规模的组合计数。
比如说，有10个人排队来参加比赛，如果要按照顺序进行比赛，那么第一名有10种选择，第二名有9种选择，第三名有8种选择，依次类推，那么总的组合情况就是$10!=3.628.800$种。
3. 组合计数法组合计数法是指通过对组合元素的选择进行计算得到组合情况数的方法。
组合计数法可以分为有放回组合和无放回组合。
有放回组合通常使用二项式定理进行计算，无放回组合通常使用错排公式进行计算。
比如说，如果我们要从5个人中选取3个人，得到的组合数可以根据二项式定理进行计算：$comb(5,3)=C_5^3=\frac{5!}{3!*(5-3)!}=10$。
4. 排列计数法排列计数法是指通过对元素的排列来计算组合情况数的方法。
排列计数法可以分为有放回排列和无放回排列。
比如说，如果我们将4个人任意排列，那么排列情况可以通过乘法原理进行计算：$4*3*2*1=24$。
总之，组合计数方法的选择要根据实际问题来判断，我们可以根据问题的特点合理选择计数方法，进而解决问题。
组合组合计数组合3星题课程目标知识提要组合•定义组合：从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. 甲、乙、丙三户人家打算订阅报纸，共有7种不同的报纸可供选择，每户人家都订三份不同的报纸，并且知道这三户人家每两户所订的报纸恰好有一份相同，那么三户人家共有种不同的订阅方式．【答案】5670【分析】甲户有C73=35种选择；乙户要选甲户订的报纸订一种，另两种从甲没订过的选，所以有C31×C42=18种丙户要么选择甲乙都订的报纸，再选甲乙都没订的〔就剩两种了〕，或者从甲乙订的互相不同的那两份报纸中各挑一份，再挑个甲乙都没订的，所以有C21×C21×C21+1=9种35×18×9=5670种.2. 在以下图中，“构建和谐社会，创美好崇义〞，从上往下读，上下、左右都不能跳读，共有种不同的读法．【答案】252【分析】根据题意，分析可得，原问题可转化为从10行中，选出5次向左，剩下的5次向右的组合问题．根据题意，从上往下读，上下、左右都不能跳读，那么从上一行到下一行必须向左或向右，分析可得，从上到下，从“构〞到“义〞之间共10个间隙，必须是5次向左，5次向右；即可转化为从10行中，选出5次向左，剩下的5次向右，那么有C105=252(种)．3. 从6双不同的鞋中取出2只，其中没有成双的鞋．共有种不同取法．【答案】60【分析】第一只鞋可以从12只鞋中任选，而第二只鞋只能从剩下的10只鞋中任选，且选第一只鞋与第二只鞋无顺序之分，所以C122×C101÷2=60．4. 5家企业中的每两家都签订了一份合同，那么他们共签订了份合同．【答案】10【分析】根据题意，从5个元素中任意取2个有多少种取法便有多少份合同，C52=10种．5. 〔1〕平面上7个点，任意三点不共线，那么可以连出个三角形．〔2〕如下图，两条平行线上各有4个点，从这些点中任取3个作为顶点，可以连出个三角形【答案】〔1〕35；〔2〕48【分析】详解：〔1〕任取三个点就确定了一个三角形，共有C73=35个．〔2〕一条直线上任取两个点，另一条上取一个点，就确定了一个三角形，共有C42×C41=48个．6. 如图，正方形ACEG的边界上共有7个点A、B、C、D、E、F、G、其中B、D、F分别在边AC、CE、EG上．以这7个点中的4个点为顶点组成的不同的四边形的个数是个．【答案】23【分析】从7个点中选出4个点有C74=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. 如果一个自然数中任一数位上的数字都大于其左边的每个数字，那么称这个是“上升数〞．由1，2，3，4，5这5个数字组成的4位数中“上升数〞共有个．【答案】5【分析】根据题意，其实就从5个数中选出4个，C54=5．8. 如以下图所示，在纸上画有A、B、C三点，经过其中任意两点画一条直线，可以画3条直线．如果在纸上画有5个点，其中任意三个点都不在一条直线上，经过每两点画一条直线，可以画条直线．【答案】10【分析】每个点和其余四个点可以组成一条直线，最后每条直线算了两次，再除以2．=10．5×4÷2，或直接利用组合知识得C52=5×429. 从15名同学选出5人，上场参加篮球比赛．请问：〔1〕如果甲、乙两人必须入选，共有种选法．〔2〕如果甲、乙两人中至少有一人入选，共有种选法．【答案】〔1〕286；〔2〕1716【分析】〔1〕甲乙必须入选，还需要从除去他们后剩下的13人中选3人参赛，C133=13×12×11÷6=286(种);〔2〕方法一：甲、乙两人任选一人有C21种，再从剩下15−2=13(人)中任选4人有C134种，因此有C21×C134=2×715=1430(种);甲、乙两人都入选有C132=286(种);所以甲、乙两人中至少有一人入选一共1430+286=1716(种).方法二：排除法．问题的反面是甲乙两人都没有入选，即C155−C135=1716(种).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. 用2颗红色的珠子，2颗蓝色，2颗紫色，2颗绿色的珠子串成如以下图所示的手链，要求两颗红色珠子相邻，两颗紫色珠子相邻，那么，可以串成种不同的手链．【答案】16【分析】因为是手链，所以，旋转、翻转相同的只能算同一种按红色和紫色珠子的分布有如下三种〔如图〕：第一种：与红色相邻的两颗珠子有：蓝蓝、绿绿、蓝绿三种，其中蓝绿的有两种可能，共4种；第二种：单独的一颗有2种可能，另3颗有3种可能，共：2×3=6(种)；第三种：此时是有序排列，四个位置两个放蓝珠子即可，有C42=6(种)；共4+6+6=16(种)不同的手链。
如何高效解决复杂的排列组合计数在数学和计算机科学领域，排列组合计数是一个常见而又复杂的问题。
无论是在组合数学、概率论、算法设计还是实际应用中，排列组合计数问题都扮演着重要角色。
然而，面对复杂的排列组合计数，我们往往需要高效的解决方法。
本文将介绍一些方法和技巧，旨在帮助读者更高效地解决这类问题。
1. 利用公式或定理对于一些简单的排列组合计数问题，我们可以直接利用已知的公式或定理来求解。
比如，计算从n个数中选取r个数的组合数，可以使用二项式系数公式：C(n, r) = n! / (r!(n-r)!)这个公式可以很方便地计算出组合数，同时也可以通过计算阶乘的方式进行优化。
类似的，对于排列数的计算，我们也可以利用相应的公式或定理，如全排列公式：P(n, r) = n! / (n-r)!2. 使用递推关系在一些复杂的排列组合计数问题中，我们可以利用递推关系进行求解。
这种方法非常高效，避免了重复计算，并且在实际应用中经常被使用。
例如，计算杨辉三角形中的数值，可以使用递推关系：C(i, j) = C(i-1, j-1) + C(i-1, j)通过不断更新C(i, j)的值，我们可以得到杨辉三角形中任意位置的数字。
同样地，对于其他复杂的排列组合计数问题，可以尝试寻找递推关系并利用之。
3. 利用动态规划动态规划是解决排列组合计数问题的一种常见方法。
其基本思想是将原问题划分为若干子问题，并存储子问题的解，以便在需要时进行查找。
通过逐步求解子问题，最终得到原问题的解。
动态规划方法适用于多阶段决策问题，并且可以大大提高计算效率。
例如，考虑一个背包问题，给定一组物品和一个容量为V的背包，每个物品都有自己的重量和价值。
我们希望选择一些物品放入背包中，使得放入背包的物品价值总和最大。
利用动态规划方法，我们可以定义状态变量、转移方程和初始条件来解决这个问题。
4. 使用计算工具或编程语言对于极其复杂的排列组合计数问题，手动计算往往是低效且容易出错的。
四年级名校第二讲组合计数——最短路线教学目标：1.让学生了解如何用标数法来解题。
2.让学生学会如何走最短路线。
3.让学生在学习中，学会数学的逻辑思维能力。
教学重点：如何用标数法解题。
教学难点：标数时我们应用什么样的方法去标数。
教学过程：导入：我们平时在出去玩的时候是不是有很多不同的路线可以选择，但是我们往往会选择一条最短的线路来走，但是事实上我们有的时候最短的路不止有一条。
这样就涉及到了我们数学当中一个非常有名的专题就是组合计数。
（出示课题）新授：例1下图是一个街道平面图，某人从A里走到B处（只能从南到北及从西到东）共有多少种不同的走法？分析：首先我们要看清楚题目，题目当中说的是只能从南到北及从西到东，那么我们只能怎么走呢？我们只能从下往上或者从左往右走。
我们可以这样想，从A点出发可以去2个地方，如果是这样我们是不是可以反过来想呢？到达那2个点只能从哪里来则我们可以这样标数。
那么从哪里来有几条路？（强调学生要注意标数的时候一定要一排一排的标，这样才能做到不重复不遗漏。
）那么我就可以这样标数，如图。
练习：演练一例2苏珊从A步行道Z，行走方向都是向东或向南，路线如图所示。
那么苏珊从A到Z有多少条不同的行走路线？分析：我们从A出发要到Z，可以随便走么？方向只能是向东或者向南，那么我们就可以用标数的方法将其标出来，这样就可以做出来了。
注意一定要一排一排的标，不能乱标。
要引导学生一个一个来。
练习：演练二例3 一直密封从A处出发，A回到家里B处，每次只能从一个蜂房爬向右侧邻近的蜂房而不准逆行，共有多少种回家的方法？分析：如果我们从蜂房的A出发回到B处，同学们可不可以将我们小蜜蜂的回家的路线试着画出来呢？将小蜜蜂的路线图画出来之后我们就可以用标数法将其做出来了。
例4如图所示科学家“爱因斯坦”的英文名拼写为“Einstein”，按见图所示方向有多少种不同的方法拼出英文单词“Einstein”?分析：我们在拼出英文单词的时候是不是可以随便拼写呢？我们一定要按照这个引文单词拼写的顺序来标数。
组合计数计数的方法大致有以下几种：1．基本方法.其中包括分情况讨论——加法原理；在每种情况中，逐步递进，先做一件事，再做第二件事，……这就需要乘法原理. 还有，从反而考虑问题：在总数中减去A不出现的个数得到A出现的个数.2. 应用公式. 包括排列、组合、允许重复的组合、圆周排列等. 这些公式在通常的课本中可以找到.3. 利用对应.4. 建立递推关系.5. 利用容斥原理.6.算两次7. 利用母函数8.其它问题讨论：1.从1，2，…，49中取出6个不同的数，使得其中至少有两个相邻，问共有多少种取法？解：首先,集合{}1,2,,49M = 的所有不同的6元子集的个数为649C ,但是,其中6个数不相邻的子集{}1261,,,,1,1,2,3,4,i i a a a a a i ++<= 不满足题中要求.记满足①的所有6元子集的集合为A ,并令{}{}126126,,,,,,a a a b b b → , 其中1,1,2,3,4,5,6.i i b a i i =-+=显然,126,,,b b b 互不相同且有126144.b b b ≤<<<≤ 容易验证②定义的映射是由集合A 到集合{}1,2,,44 的所有不同的6元子集的一一映射.所以644||||.A B C ==故满足条件的取法共有649C －644C 种.2．求方程123420x x x x +++=且满足123416,07,48,26x x x x ≤≤≤≤≤≤≤≤的（有序）整数解的个数.解：作替换11223344,1,3,1y x y x y x y y ==+=-=-，则问题化为求123417y y y y +++= ①满足123416,18,15,15y y y y ≤≤≤≤≤≤≤≤的整数解的个数.记S 为方程①的正整数解的集合；1234,,,S S S S 分别是S 有满足12347,9,6,6y y y y ≥≥≥≥的子集，则所求的解的个数为1234||S S S S I I I I .第3讲例1知163||()560S ==.为求出1||S ，再令'116y y =-，则1||S 等于'123411y y y y +++=的正整数解的个数4713()120+-=.同样可算出45148123343||()56,||||()165S S S +-+-=====；以及513143||||()10S S S S ===I I ，2324||||1S S S S ==I I ， 634322||()20,||0S S S S ===I I ；而1234||||i j k S S S S S S S I I I I I 和都是0.最后由容斥原理求得问题中的解的个数是56012016556165102122096----+⨯+⨯+=. 3．设{}1,2,,1000S =L ，A 是S 的一个201元子集，若A 中各元素之和能被5整除，则称A 为S 的好子集，求S 的所有好子集的个数.解：将S 的所有201元子集分为5类：01234,,,,S S S S S ，其中{|,||201A k S A A S A =⊆=且中5}k 各元素之和被除的余数为 (0,1,2,3,4)k =.作映射0:(14)k f S S k →≤≤如下：若122010{,,,}A a a a S =∈…，则12201(){,,,}f A a ka k a k =+++…，其中当1000i a k +>时，用1000i a k +-代替i k a +，则不难得到20120111()201(mod5)i i i i a k a k k ==+=+≡∑∑，即()k f A S ∈，容易验证f 是双射，所以0||||(14)k S S k =≤≤，记这个数为a ，则2010123410005||||||||||a S S S S S C =++++=. 所以，S 的好子集个数为201010001||5S a C ==.4．圆周上有n 个点(6)n ≥，每两点间连一线段，假设其中任意三条线段在圆内不共点，于是任三条线段相交构成一个三角形.试求这些线段确定的三角形的个数.解：我们称圆周上的点为外点，任意两条对角线在圆内的交点为内点，则所确定的三角形按其顶点可分为4类：(1)第一类三角形的3个顶点均为外点，其个数设为I 1;(2)第二类三角形的顶点中有2个外点和l 个内点，其个数设为I 2； (3)第三类三角形的顶点中有1个外点和2个内点，其个数设为I 3; (4)第四类三角形的三个顶点均为内点，其个数记为I 4．显然，第一类三角形与圆周上的3点组集合成一一对应，所以31n I C =．其次，如图1-4(1)，圆周上任取4点A 1，A 2，A 3，A 4，两两相连的线段，确定了4个第二类三角形：12233441,,,AOA A OA A OA A OA ∆∆∆∆．反之，每4个这样有公共内顶点的第二类三角形对应了圆周上的一个4点组，于是，414n I C =．类似的，如图l-4(2)，圆周上任取5点A 1，A 2，A 3，A 4，A 5，两两连一线段，确定了5个第三类三角形：112223334445551,,,,A B B A B B A B B A B B A B B ∆∆∆∆∆，于是可得515n I C =．最后，如图1-4(3)，圆周上任取6点A 1，A 2，A 3，A 4，A 5，A 6，对应于1个第四类三角形，所以64n I C =．综上所述，得所确定的三角形共有345645n n n nC C C C +++个． 当我们要建立组合计数问题中的不等关系时，常常要构造单射或满射来实现．关于这方面的例题，我们将在后面的章节中叙述．5. 设M 是平面上所有整点的集合, M 中的点{P 0, P 1, …, P n }构成的一条折线满足P i －1P i =1, i =1, 2, …, n , 则称这条折线长度为n , 又设F (n )表示起点P 0在原点, 而终点P n 在x 轴上的长度为n 的不同折线的条数. 求证: F (n )=C n n 2.解1：将折线中上转化为上上，下转化为右右，左转化为右上，右转化为上右，则将每条折线唯一对应到一条(0，0)至(n ，n )的折线，显见2()n n F n C =.解2：考察有m 步向y 轴正向走的折线.因为折线从原点出发，最后回到x 轴，所以必有m 步是向y 轴负向走.因此，这种折线的条数为22m m n m n n m C C --⋅.从而知长度为n 的所有不同折线的条数为[]220()2nm mn m n n m m F n C C --==⋅∑①下面用等函数法来计算①右端的和数.考察恒等式2(1)(12)n n x x x 2+=++上式左端n x 的系数为2nn C ，右端n x 的系数为[][]22220!22!(2)!!nnn mm mn m n n m m m n C C m n m m ---==⋅=⋅-∑∑ ②由①和②即得2()nn F n C =.6.有人民币1元3张，2元2张，5元1张，10元1张，50元1张，能组成多少种币值？各有多少种组合方案？ 解：1元币3张，可以组合成0元或1元或2元或3元各一种，用231x x x +++来表示，其中k x 代表k 元币值，其系数为组成这一币值的方案.于是2元币2张可用241x x ++来表示，5元币1张可用51x +来表示，依此类推.于是有母函数2324510502345678910111213141516171819202122505152535455565758596061(1)(1)(1)(1)(1)1222323223232232322222232322323x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ++++++++=+++++++++++++++++++++++++++++++++++626364656667686970717222323222x x x x x x x x x x ++++++++++ 各币值及方案数见各项幂值及系数.7．将圆分为(2)n n ≥个扇形，每个扇形用r 种不同颜色之一染色，要求相邻扇形所染的颜色不同，问有多少种染色方法.解：设圆分成的扇形为12,,,n S S S …，且一共有n a 种染色方法，则120,(1)a a r r ==-.当n ≥2时，1S 有r 种染法，2S 有r －1种染法，…，n S 有r －1种染法，共有1(1)n r r -⋅－种方法．但这种方法只保证1,(1,2,,1)i i S S i n +=-…的颜色不同，不保证n S 与11n S S +=的颜色不同，所以1(1)n r r -⋅-种方法可分为两类：第一类：n S 与1S 颜色不同，有n a 种方法； 第二类：n S 与1S 颜色相同，有1n a -种方法， 故 11(1)(2)n n n r r a a n --=+≥- 可求得*(1)(1)(1),()n nn a r r n N =--+-∈ 8．将周长为24的圆周等分成24段从24个分点中选取8个点，使得其中任何两点间所走的弧长都不等于3和8．问满足要求的8点组的不同取法共有多少种?说明理由． 解1：将24个分点依次编号为l ，2，…，24，并将它们按“坏的关系”排成如下的3×8数表：易见，表中每行中相邻两数所代表的两个分点间所夹的弧长为3，每列相邻两数所代表的两个分点间所夹的弧长都是8(首尾两数也算作相邻)．这样一来，题中对所取8点的要求化为要求所取8点的号码在数表中互不相邻．所以，每列恰取l 个数，每行至多取4个互不相邻的数．从而3行数中分别取数的个数只有4种不同情形：{4，4，0}，{4，3，1}，{4，2，2}，{3，3，2}．(1){4，4，0}．3行中任取一行不取数，有3种不同取法．另两行中第一行取4个互不相邻的数，有两种不同取法．余下4列为另一行所取4个数所在的列惟一确定．由乘法原理知这种情形共有6种不同取法．(2){4，3，1}．在3行中取数的个数分别为4，3，1，共有3！= 6种不同安排．在一行中取4个互不相邻的数，有两种不同取法．在另一行和余下4列中选1个数，有4种不同选法．最后第3行从余下3列中各选l 个数，选法惟一确定．由乘法原理知，这时共有6×2×4=48(种)不同选法．(3){4，2，2}．从3行中选定一行取4个互不相邻的数，选行有3种不同，取数有两种不同，共有6种不同取法，余下4列互不相邻．第2行从4列中任取2列，共有246C = (种)不同取法．由乘法原理知，这种情形共有6×6=36(种)不同取法．(4){3，3，2}．从3行数中选定一行取2个不相邻的数，选行有3种不同，选数有27120C -=(种)不同(其中减1是去掉两个数分别在第l 列与第8列的一种)．选定两数之后，余下6列被分成两部分，有3种不同分段情形：{1，5}，{2，4}和{3，3}．3种分段的种数分别为8，8，4．容易看出：(1)对于{1，5}分段，取3列互不相邻，有两种不同取法； (2)对于{2，4}分段，取3列互不相邻，有4种不同取法； (3)对于{3，3}分段，取3列互不相邻，有两种不同取法． 所以，这种情形的不同取法种数为3×(8×2+8×4+4×2)=168．综上可知，满足题中要求的不同取法种数为6+48+36+168=258． 解2：像在解法一中一样地将24个数写成3×8数表，于是选取8个数时每列恰取一个数，这时，从第1列取l 个数，共有3种不同取法．第1列取定后，第2列所取的数不能与第1列所取的数同行，故只有两种不同取法．以后每列都有两种不同取法，共有3×27种不同取法．但其中第l 列所取的数与第8列所取的数同行的所有取法都不满足要求．若记从3 × n 数表中每列恰取一个数且任何相邻两列(包括第n 列与第1列)所取的数都不同行的不同取法种数为x n ，则上段论述的结论恰为x 8+x 7=3×27．类似地可以得到x n +x n －1=3⨯2n －1由此递推即得7768767667654323232(32)3(22)3(2222222)386258x x x x =⨯-=⨯=⨯-=⨯-+⋅⋅⋅⋅⋅⋅=⨯-+-+-+=⨯=即满足题中要求的不同取法种数为258.9.一种密码锁的密码设置是在正n 边形12n A A A 的每个顶点处赋值0和1两个数中的一个，同时在每个顶点涂然红、蓝两种颜色之一，使得任意相邻的两个顶点的数字或颜色中至少有一个相同。
