【两个基本计数原理及应用】
(1)加法原理和分类计数法
1．加法原理
2．加法原理的集合形式
3．分类的要求
每一类中的每一种方法都可以独立地完成此任务；两类不同办法中的具体方法，互不相同(即分类不重)；完成此任务的任何一种方法，都属于某一类(即分类不漏)。
(2)乘法原理和分步计数法
1．乘法原理
2．合理分步的要求
任何一步的一种方法都不能完成此任务，必须且只须连续完成这n步才能完成此任务；各步计数相互独立；只要有一步中所采取的方法不同，则对应的完成此事的方法也不同。
1．首先明确任务的意义
例1. 从1、2、3、……、20这二十个数中任取三个不同的数组成等差数列，这样的不同等差数列有________个。
妹纸批注：这个例子妹纸觉得还是很有用的！！大家可以先做做再看后面的解答！！！
分析：首先要把复杂的生活背景或其它数学背景转化为一个明确的排列组合问题。
设a,b,c成等差，∴ 2b=a+c, 可知b由a,c决定，
又∵ 2b是偶数，∴ a,c同奇或同偶，即：从1，3，5，……，19或2，4，6，8，……，20这十个数中选出两个数进行排列，由此就可确定等差数列，因而本题为180。童鞋们要注意啊。。。为什么答案不是直接等于C（10,2）*2 = 90呢？？？请回想我刚才的例子“1、2、3挑两个组成一个数字和1、2、3挑两个数字是完全不一样的！例如我选1和2，排列里面12和21是两个数字！但是组合的话挑1和2就和挑2和1没有分别！！！”然后题目这里要求的是能组成多少个等差数列。。如果我从奇数组里面选出1和3然后确定一个等差数列例如{1,2,3}，那么呢{3,2,1}其实是不同的等差数列吧？？所以我们要再在90的基础上乘以2，因为第一个数能和第三个数对调变变成两个不同的等差数列！！！！
例2. 某城市有4条东西街道和6条南北的街道互相垂直且街道之间的间距相同。M在城市最南街道与最西街道的交点；N在城市最北街道与最东街道的交点。若规定只能向东或向北两个方向沿街道前进，则从M到N有多少种不同的走法?
分析：对实际背景的分析可以逐层深入
（一）从M到N必须向上走三步，向右走五步，共走八步。
（二）每一步是向上还是向右，决定了不同的走法。
（三）事实上，当把向上的步骤决定后，剩下的步骤只能向右。
从而，任务可叙述为：从八个步骤中选出哪三步是向上走，就可以确定走法数，
∴ 本题答案为：56
妹纸批注：这题由于妹纸不会弄图片的关系所以全部改成文字了，但是意思一点没有变！！！读完发现这题简直就是jj里面的原题啊！！！PO出来大家对比一下
264. 【确定】八条街道互相垂直，四条南北街道四条东西街道， A在最南和最西的交点，B在最北和最东的交点。从A到B，只向上或者向右行走，也就是只向被或者向东走，有几种走法？（图片妹纸弄不来所以偷懒改成文字啦，原题可以去找JJ里面的哦！！！）
20ß看这里
2．注意加法原理与乘法原理的特点，分析是分类还是分步，是排列还是组合
例3. 在一块并排的10垄田地中，选择二垄分别种植A，B两种作物，每种种植一垄，为有利于作物生长，要求A，B两种作物的间隔不少于6垄，不同的选法共有______种。
分析：条件中“要求A、B两种作物的间隔不少于6垄”这个条件不容易用一个包含排列数，组合数的式子表示，因而采取分类的方法。
第一类：A在第一垄，B有3种选择；
第二类：A在第二垄，B有2种选择；
第三类：A在第三垄，B有1种选择，
同理A、B位置互换 ，共12种。
例4. 从6双不同颜色的手套中任取4只，其中恰好有一双同色的取法有________。
(A)240 (B)180 (C)120 (D)60
分析：显然本题应分步解决。
（一）从6双中选出一双同色的手套，有6种方法；
（二）从剩下的十只手套中任选一只，有10种方法。
（三）从除前所涉及的两双手套之外的八只手套中任选一只，有8种方法；
（四）由于选取与顺序无关，因而（二）（三）中的选法重复一次，因而共240种。
或分步
（一）从6双中选出一双同色的手套，有C（6,1）=6种方法
（二）从剩下的5双手套中任选两双，有C（5,2）=10种方法
（三）从两双中手套中分别拿两只手套，有C（2,1）×C（2,1）=4种方法。
同样得出共**×**×**=240种。
妹纸说：个人觉得第一种更好理解！让我深深体会到“顺序”是神马！以前觉得没有顺序的话岂不是数字应该更多更大？然后现在仔细想想真是too young too simple啊！！就比如我前面举的例子：1、2、3挑两个组成一个数字和1、2、3挑两个数字是完全不一样的！1、2、3挑两个组成一个数字那是排列；1、2、3挑两个数字那是组合。例如我选1和2，排列里面12和21是两个数字！但是组合的话挑1和2就和挑2和1没有分别！！！
例5. 身高互不相同的6个人排成2横行3纵列，在第一行的每一个人都比他同列的身后的人个子矮，则所有不同的排法种数为_______。
分析：每一纵列中的两人只要选定，则他们只有一种站位方法，因而每一纵列的排队方法只与人的选法有关系，共有三纵列，从而有C（6,2）×C（4,2）×C（2,2）=90种。童鞋补充解释（Thanks to 伤心的小鹅肝）~~~~两行三纵列，然后因为只要第一行的人比第二行的人矮，那么每一列，如果第一行的人选定，那么第二行的人也一定选定，所以第一列是C(6,2), 第二列是C（4，2），第三列是C（2，2）。欢迎更多童鞋补充完善O(∩_∩)O~~
例6. 在11名工人中，有5人只能当钳工，4人只能当车工，另外2人能当钳工也能当车工。现从11人中选出4人当钳工，4人当车工，问共有多少种不同的选法?
妹纸说：看到这题以后妹纸就明白Gmac为神马那么喜欢出排列组合的题了。。。思维逻辑啊思维逻辑。。。
分析：采用加法原理首先要做到分类不重不漏，如何做到这一点？分类的标准必须前后统一。
以两个全能的工人为分类的对象，考虑以他们当中有几个去当钳工为分类标准。
第一类：这两个人都去当钳工，有C（2,2）×C（5,2）×C（4,4）=10种；
第二类：这两人人都去当车工，有C（5,4）×C（2,2）×C（4,2）=30种；
第三类：这两人都不去当钳工，有C（5,4）×C（4,4）=5种；
第四类：这两个人一个去当钳工、一个去当车工，C（2,1）×C（5,3）×C（4,3）=80种；
第五类：这两个人一个去当钳工、另一个不去当车工，C（2,1）×C（5,3）×C（4,4）=20种；
第六类：这两个人一个去当车工、另一个不去当钳工，C（5,4）×C（2,1）×C（4,3）=40种；
因而共有185种。
例7. 强烈推荐看现有印着0，l，3，5，7，9的六张卡片，如果允许9可以作6用，那么从中任意抽出三张可以组成多少个不同的三位数?
妹纸说：这题花了妹纸巨多心思！！！这题原本的分析有点残缺。而且好难啊！！！！经过妹纸的搜索和上下求证。把脑子都想烂了终于通了！！！！妹纸把分析仔细的重新梳理了一遍。如果有童鞋发现问题欢迎指出讨论！！！
分析：有同学认为只要把0，l，3，5，7，9的排法数乘以2即为所求，但实际上抽出的三个数中有9的话才可能用6替换，因而必须分类。
(蓝条里面都是妹纸自己的补充，希望各位自己求证)首先，两个重要的因素是“三位数的千位数不能是0”和“抽到9可以用6替换”。
所以：
抽出的三数含0，含9的情况: 0不能为千位数，所以X09，X90，9X0，90X。剩下一位数有四种情况1，3，5，7。即4*4。9能够由6替代，所以4*4*2=32，有32种方法；
抽出的三数含0不含9的情况：0不能为千位数，所以必须是XX0，X0X。又因为不含9.所以剩下两位数有四种情况1，3，5，7。即4*3（一个位数用掉一个数字以后，下一个位数就只有3个数可以用啦）。所以一起有4*3*2=24，有24种方法；
抽出的三数含9不含0的情况：木有0所以不用担心千位数是啥。但是必须抽中9哦，所以9XX，X9X，XX9。剩下两位数有四种情况1，3，5，7。即4*3。所以含9的一起有4*3*3=36种。然而！！！大家不要忘记了！！！6他能替代9啊！！！所以还要乘以2，一起36*2=72，有72种方法；
抽出的三数不含9也不含0的情况：题目做到这里难的部分已经结束了。。。木有0也木有9嘛那就很容易啦。1，3，5，7这四个数字随便组成个3位数就行了。所以4*3*2=24，有24种方法。
因此共有32+24+72+24=152种方法。
另外一种方法：9可以做6用，相当于有7张牌，所以算得为6*6*5=180。（注意：这里一开始就去掉了0在千位数的情况哦，所以后面就不用worry啦）但是实际只有6张牌。所以要除去同一次中抽出9和6的，包含9和6的三位数中有6种排列，96X，69X，9X6，6X9，X69，X96。其中包括开头不是0的四种排列和开头或许是0的两种排列。开头不是0的四种排列中，剩下的一位有5种情况，0、1、3、5、7。即5*4。开头可能为0的两种数列中，因为开始我们已经排除了0开头的情况，所以我们不用另外worry 0开头的情况啦。所以剩下的一位的只有4种情况，1、3、5、7。即4*2。总共减去(5*4+4*2)28种，结果为152。
例8. 停车场划一排12个停车位置，今有8辆车需要停放，要求空车位连在一起，不同的停车方法是________种。
分析：把空车位看成一个元素，和8辆车共九个元素排列，因而共有A（9,8）=362880种停车方法。
PS把4个空车位绑起来变成一个~~~后面有具体捆绑法的讲解~~~
3．特殊元素，优先处理；特殊位置，优先考虑
例9. 六人站成一排，求（1）甲、乙既不在排头也不在排尾的排法数；（2）甲不在排头，乙不在排尾，且甲乙不相邻的排法数。
妹纸说：第一小题是个小热身~~~请把大脑用在第二小题。
分析：（1）按照先排出首位和末尾再排中间四位分步计数
第一类：排出首位和末尾、因为甲乙不在首位和末尾，那么首位和末尾实在其它四位数选出两位进行排列，一共有A（4,2）=12种；
第二类：由于六个元素中已经有两位排在首位和末尾，因此中间四位是把剩下的四位元素进行顺序排列，共A（4,4）=24种；
根据乘法原理得即不再排头也不在排尾数共12×24=288种。
（2）第一类：甲在排尾，乙在排头，有A（4,4）种方法。
为什么呢：因为甲乙他们已经不能再相邻了啊！！！！所以情况是：乙，X，X，X，X，甲。中间四个随便你怎么排啊。。。但切记这个是排列！不是组合！（12、21与1和2、2和1的问题）。所以他们只能4*3*2*1啦。
第二类：甲在排尾，乙不在排头，有3×A（4,4）种方法。
如果捏是甲在排尾乙不在排头，那么就是：X，X，X，X，X，甲。但寺！甲乙不能相邻，而且乙呢不在排头，所以乙就只有3个位置可以选啦~~~然后剩下四个位置被另外四个瓜分。所以就是3*4*3*2*1咯。
第三类：乙在排头，甲不在排尾，有3×A（4,4）种方法。
这个推理和上面一样。乙，X，X，X，X，X。第二位和最后一位不是甲，所以甲有3种选择~~~然后剩下爱站哪站哪~~~~3*4*3*2*1
第四类：甲不在排尾也不再排头，乙不在排头也不再排尾，有6×A（4,4）种方法（排除相邻）。
甲不在排尾也不再排头，乙不在排头也不再排尾。那么他们就只能是：（X，甲，X，乙，X，X）、（X，乙，X，甲，X，X）、（X，X，甲，X，乙，X）、（X，X，乙，X，甲，X）、（X，甲，X，X，乙，X）、（X，乙，X，X，甲，X）。一起六种情况。剩下四个位子他们爱咋咋滴~~~所以是6*4*3*2*1
共A（4,4）+3×A（4,4）+3×A（4,4）+6×A（4,4）=312种。
例10. 对某件产品的6件不同正品和4件不同次品进行一一测试，至区分出所有次品为止。若所有次品恰好在第五次测试时被全部发现，则这样的测试方法有多少种可能?
妹纸补充：相似JJ（这题不是解题思路相同）
116. 【确定】一个运货的船，有好几个boxes，每个box有10个碗，要从每个箱子里一次抽三个出来验货，如果次品数atleast是1就不能shipped，问有个箱子里次品数是3，最后能shipped的概率是多大？
7/24ß嘿嘿
分析：本题意指第五次测试的产品一定是次品，并且是最后一个次品，因而第五次测试应算是特殊位置了，分步完成。
第一步：第五次测试的有C（4,1）种可能；（意思就是四个次品里面任何一个都有可能是第五次测试到的）
第二步：前四次有一件正品有C（6,1）种可能。（一起有四个次品~要保证第五次测出全部次品切第五次测出次品，那么前四次里面就有一次会抽到正品。正品有6个，任何一个都有可能抽到~~）
第三步：前四次有A（4,4）种可能。（除了最后一次必须是次品以外，前面四位数是什么顺序是随便的，所以他们有4*3*2*1种方法排）
∴ 共有4*6*4*3*2*1=576种可能。
正题思路就是把第五次确定咯~先组合他们再排列他们~~~~但是注意这里是相乘因为他们要一起做才能完成~~~也就是他们只是任务的一个步骤~~~
4．捆绑与插空
例11. 8人排成一队：（1）甲乙必须相邻；（2）甲乙不相邻；（3）甲乙必须相邻且与丙不相邻；（4）甲乙必须相邻，丙丁必须相邻；（5）甲乙不相邻，丙丁不相邻
妹纸飘过：这题看起来类似于例9嗯~~~但是比例9简单而且是用捆绑插空的方法呢~~~
分析：（1）甲乙必须相邻，就是把甲乙捆绑；把他们看成一个人，然后就变成了7个人排队咯~~所以是A（7,7）。因为甲乙他们俩直接自己又可以交换位置，所以就是A（7,7）*2 = 10080种。
（2）甲乙不相邻，有了上一步的基础者一步就好做啦~~~把全部的可能排列减去甲乙相邻的排列就可以了~~~~如果考试直接碰到也不要慌~~~就按这个思路也不会错哇~~~A（8,8）-A（7,7）*2= 30240。
（3）甲乙必须相邻且与丙不相邻，先求甲乙必须相邻且与丙相邻A（6,6）*2*2。理由和上面一样哈~~~把三个人绑一起排列，就是A（6,6）。其中在把甲乙绑一起和乙互相对换位置*2，然后在把帮在一起的甲乙对换位置*2。
甲乙必须相邻且与丙不相邻 = 甲乙必须相邻—甲乙必须相邻且与丙相邻，即A（7,7）*2-A（6,6）*2*2 = 7200。
（4）甲乙必须相邻，丙丁必须相邻。把甲乙绑一起，把丙丁绑一起。然后呢就变成6个人排6个位子了~~~~所以是A（6,6）。可是甲乙可以换位置，丙丁也可以换位置，于是*2*2。
答案A（6,6）*2*2=2880。
（5）甲乙不相邻，丙丁不相邻。
甲乙不相邻，丙丁不相邻 = 所有的可能排列—{[甲乙必须相邻（第一小题算的）+ 丙丁必须相邻（与第一小题算法一样）]—[甲乙必须相邻，丙丁必须相邻（第四小题算的）]}
剪掉甲乙必须相邻和丙丁必须相邻这部分比较好理解，但是由于（甲乙必须相邻+丙丁必须相邻）包括了（甲乙必须相邻，丙丁必须相邻）。所以要剪掉~~~~~~
A（8,8）- [A（7,7）*2*2—A（6,6）*2*2] = 17280。
5．间接计数法.
(1)排除法
例12. 三行三列共九个点，以这些点为顶点可组成多少个三角形?
分析：有些问题正面求解有一定困难，可以采用间接法。
所求问题的方法数= 任意三个点的组合数—共线三点的方法数
即C(9,3)— 8
∴ 共76种。
例13. 正方体8个顶点中取出4个，可组成多少个四面体?
分析：所求问题的方法数=任意选四点的组合数-共面四点的方法数，
∴ 共=70-12=58个。
这题俺自己也木有懂共四面方法数怎么算出来的。。求指导~~~俺就直接以为是6个表面乘以2了。。。
例14. l，2，3，……，9中取出两个分别作为对数的底数和真数，可组成多少个不同数值的对数?
哈哈。。。有木有跟我一样完全忘记对数是什么的童鞋。。。
补充知识：如果 a^x=N（a>0，且a≠1），那么数x叫做以a为底N的对数（logarithm），记作x=log(a) N .其中，a叫做对数的底数，N叫做真数。且a>o，a≠1，N>0。
分析：由于底数不能为1。
首先，当1选上时，1必为真数，∴ 有1种情况。
其次，当不选1时，从2至9中任取两个分别作为底数，真数，共A（8,2）=56，其中log（2）4=log（3）9 ，log（4）2=log（9）3 ,log（2）3=log（4）9 ,log（3）2=log（9）4.
因而一共有53个。
6．挡板的使用
例15. 10个名额分配到八个班，每班至少一个名额，问有多少种不同的分配方法?
下面JJ是不是有一点像。。。八过JJ这题难多了！！！具体解释请看JJ~~~
44. 【确定】将140个东西均分给N个人，N≧2，且每个人至少得到两个，问N有多少种可能？
10ßs刷立现
分析：把10个名额看成十个元素，在这十个元素之间形成的九个空。（大家发挥想象，电影院十个并排椅子中间有9个间隔）九个空中选出七个位置放置档板（在电影院椅子间放块板把两个椅子隔开），则每一种放置方式就相当于一种分配方式。因而共C(9，7)=36种。
7．注意排列组合的区别与联系：所有的排列都可以看作是先取组合，再做全排列；同样，组合如补充一个阶段(排序)可转化为排列问题。
例16. 用数字0，1，2，3，4，5组成没有重复数字的四位数，（1）可组成多少个不同的四位数? （2）可组成多少个不同的四位偶数？ （3）可组成多少个能被3整除的四位数?
分析：（1）有A（6,4）-A（5,3）=300个。
A（6,4）为一起可以组成的四位数字总数~~~但寺！！！不要忘记0不能在第一位啊！！！！所以要把0XXX的情况剪掉，即A（5,3）。所以一起就是A（6,4）-A（5,3）啦~~~~
（2）分为两类：0在末位的情况：有A（5,3）=60种；
0不在末位的情况：有C（2,1）×A（5,3）-C（2,1）×A（4,2）=96种。
C（2,1）×A（5,3）表示的是：如果是偶数呢，末尾必须是2或者4啦，所以两个选一个啦，即C（2,1）。然后剩下三位呢就随便选啦A（5,3）。然后他们是两个步骤。所以相乘~~~
但寺！！！请不要忘记0在第一位的情况~~~~0XXX，最后一位还是两个选一个，即C（2,1）。然后剩下两位呢就随便选啦，即A（4,2）。这两个也是步骤~所以相乘~~~~~
∴ 共60+96=156种。
（3）先把四个相加能被3整除的四个数从小到大列举出来，即先选
0，1，2，3
0，1，3，5
0，2，3，4
0，3，4，5
1，2，4，5
它们排列出来的数一定可以被3整除，再排列，有：4×[A（4,4）-A（3,3）]+A（4,4）=96种。
妹纸这里一开始没有弄清楚为什么四个相加能被3整除组成的数就能被3整除。。。然后又继续挖啊挖~~~~解释是：假设这是两位数ab，把它写成10a+b，它的各位数字之和是a+b，两式相减，得9a，因为9a能被3整除，所以如果a+b能被3整除，那么ab也能被3整除。
假设这是三位数abc，把它写成100a+10b+c，它的各位数字之和是a+b+c，两式相减，得99a+9b，因为99a+9b能被3整除，所以如果a+b+c能被3整除，那么abc也能被3整除。
四位数，五位数，六位数……推导方法类似。
然后再要求排列就很好求啦~~前四列数字排列方法都是[A（4,4）（全部可能的四位数）—A（3,3）（0开头的四位数）]，所以乘以4。然后最后一组木有0，所以不存在0开头的情况就能随便排啦~~~就是A（4,4）。
8．分组问题
例17. 5名学生分配到4个不同的科技小组参加活动，每个科技小组至少有一名学生参加，则分配方法共有多少种？
分析：（一）先把5个学生分成二人，一人，一人，一人各一组。
其中涉及到平均分成四组，有C（5,3）=10种分组方法。可以看成4个板三个板不空的隔板法。
（二）再考虑分配到四个不同的科技小组，有A（4,4）=24种。
由（一）（二）可知，共10×24=240种。1和2就和挑2和1没有分别！！！
