排列组合
2024-11-27 21:50:55
发布于：广东
排列组合
一、计数
按照统计要求，将符合所有条件的结果筛选出来，统计所有结果的数量叫做计数！
二、分类加法
完成一件事的方法，有n类方案，第一类方案中有m1种方法，第二类方案中有m2种方法，第n类方案中有mn种方法，则完成这件事的总方法数：m1+m2+···mn。分类加法又叫做：完成一件事不同方案的枚举法，一一列举时要求：有顺序地、不重复、不遗漏。
例：完成报考志愿填写，依据分数得知可以填报的学校共有100所，则完成报考志愿填写，有100种不同的方案，填写这100所内的每所学校，都能完成报考志愿填写这件事。
三、分步乘法
完成一件事的方法，需要有顺序地完成n个步骤，完成第一个步骤有m1种不同方法，完成第二个步骤有m2种不同的方法，完成第n个步骤有mn种不同的方法，则完成这件事的方法种数：m1×m2···×mn。
例：完成报考志愿填写，填写时要求：第1志愿填1所，第2志愿填1所，要求第1志愿和第2志愿学校不相同。分数符合录取要求的学校共有10所，即第1志愿填写时有10所学校可选，即10种选择，填完第1志愿后，第2志愿填写时剩9所。则完成第1、2志愿愿填写这件事，共有10×9=90种不同的方案。
四、排列
从n个不同元素中取出m个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列。这样的全部的排列个数，叫做排列数，写做：Amn
。
例：A32
，人分步完成选座位的角度：2个人选3个座位的方法总数，第1个人选时有3个座位，第2个人选时剩2个座位，则2个人分步完成选成选座位这件事，共有3×2=6种不同的方案。
例：A32
，座位分步完成选人的角度：2个座位选3个人的方法总数，第1个座位选人时有3人可选，第2个座位选人时剩2人可选，则2个座位分步完成选人这件事，共有3×2=6种不同的方案。
例：A32
，先选人后排列的角度：3个人里不重复地选出2个人为一组，得到3组，每组对2个座位进行分步选择，即每组内第一个人选座时有2种选择，第二个人选座时剩1种选择。则3个人里不重复地选出2个人为一组，再分步选择2个座位的方法总数：3×2=6种不同的方案。
五、组合
从n个不同元素中，不重复地选出m个元素的一个组合，这样的组合的总数叫做组合数，写做：
。
例：
，从3个不同的元素中，不重复地选出2个元素成为一组，这样元素不同的小组共有3种。以ABC为例，从中不重复地选出2个元素成为一组，这样元素不重复的小组，枚举得出：(A,B)，(A,C)，(B,C)共3种。
例：
，从3个不同的元素中，不重复地选出2个元素成为一组，剩余的元素自动成为一组，则这样剩余的不同元素的小组共有3种。以ABC为例，[选出的元素组(A,B)，剩余的元素小组(C)]，[选出的元素组(A,C)，剩余的元素小组(B)]，[选出的元素组(B,C)，剩余的元素小组(D)]，所以
。
例：
，从3个不同的元素中，分步选出第一个元素、第二个元素，因为一个组合内的位置是无序的（都是相同的座位，谁坐第1个，谁坐第2个，没有区别），所以需要剔除掉，元素相同仅元素顺序不同的组合（即重复出现的组合），所以
六、排列组合的区别
从n个不同元素中，每次取出m个元素为一组，如果该组内对每个元素的位置是有要求的（位置不同代表意义不同的）即排列，无要求（位置不同代表意义相同）的即组合。所以，如果以选出的元素与对应的位置关系来看：
① 排列，n个不同元素中选出m个元素的一个排列，每个元素所在的位置是不同的。如ABC选出2个元素AB，则AB和BA是两种方案。所以排列的性质为：一个排列的内部，每个元素的地位都是不等的，也就是内部要讲秩序。
② 组合，n个不同元素中选出m个元素的一个组合，每个元素所在的位置是相同的。如ABC选出2个元素AB，则AB和BA是一种方案。所以组合的性质为：一个组合的内部，每个元素的地位都是相等的，也就是内部不讲秩序。
七、分组分配
7.1 分组：将n个不同元素分成m组，每种分组的方案不相同。
例：3个人(ABC)，分成2个小组，第一个小组1人，第二个小组2人，不同的分组方案有多少个？
列举法：共有3种不同的分组方案。
第一步：ABC中选1个 第二步：从剩余中选2个 分组方案
A BC 一种，且不重复
B AC 一种，且不重复
C BD 一种，且不重复
公式计算：
C31*A22=3
7.2 平均分组：将n个不同元素平均分成m组，每种分组的方案不相同。
例：4个人(ABCD)分成2个小组每组2人（平均分成2组），不同的分组方案有多少个？
列举法：共有3种不同分组方案。
第一步：4选2 第二步：2选2 判定 分组方案
AB CD 合法 一种分组
AC BD 合法 一种分组
AD BC 合法 一种分组
BC AD 与(AD,BC)分组方案相同 一种重复分组
BD AC 与(AC,BD)分组方案相同 一种重复分组
CD AB 与(AB,CD)分组方案相同 一种重复分组
公式计算：
C42*C22/A22=3
7.3 分配
例：4个人(ABCD)，其中去上海1人，去北京3人，不同的分配方案有多少个？
第1种解题思路：分步乘法
第一步：第一个位置上海在4人中选1个人，4种选法
第二步：第二个位置北京在剩余3人中选3人，剩1种选法
分步相乘：4×1=4种不同的分配方案
第2种解题思路：先分组+再分配
第一步分组有4种不同的方案：[(A),(BCD)]，[(B),(ACD)]，[(C),(BCD)]，[(D),(ABC)]
第二步分配去北京和上海：每个小组都只有1种选择
所以答案是：4种不同的分配方案
公式计算：
C41C331=4
7.4 平均分配：先分组+再分配
例：4个人(ABCD)，平均分给北京和上海，不同的分配方案有多少个？
4个人平均分配给2个城市，即每个城市分到2人
第一步先分组，分成2组2人，则分成3种不同的分组方案：
第1组 [(AB),(CD)]，第2组[(AC),(BD)]，第3组[(AD),(BC)]
第二步再分配：每组方案都有2个城市可以选择
如：第1组的(AB)去上海，则(CD)去北京；或(CD)去上海，则(AB)去北京，有2种方案。第2-3组同理。
所以答案是：3×2=6种不同的分配方案
公式计算：
C42*C22/A22/A22=6
7.5 分组分配：先分组+再分配
例：4个人(ABCD)分成2组，分别去北京和上海，不同的分配方案有多少个？
4人分成2组，分类讨论：有2种不同的分组方案(1+3)、(2+2)
第一种方案：第1步分组有4种不同的方案：[(A),(BCD)]，[(B),(ACD)]，[(C),(ABD)]，[(D),(ABC)]
第一种方案：第2步分配去北京和上海：每个小组都有2种选择
第一种答案：4×2=8种不同的分配方案，
第二种方案：第1步分组有3种不同的方案：[(AB),(CD)]，[(AC),(BD)]，[(AD),(BC)]
第二种方案：第2步分配去北京和上海：每个小组都有2种选择
第二种答案：3×2=6种不同的分配方案，
分类相加：8+6=14，即共有14种不同的分配方案。
八、排列组合处理技巧类型
8.1 特殊元素和位置优先安排：特殊要求，优先安排！
例：ABCD分别去苏州、扬州、杭州、上海4个城市，其中A不能去上海，B必须去扬州
策略：AB有特殊要求，先安排A或B
第一步：B必须去扬州，则B只有1种选择
第二步：A不能去上海，只能在苏州、杭州中2选1，则有2种选择
第三步：C在剩余2个城市中2选1，则有2种选择
第四步：D在剩余1个城市中选，则只有1种选择
分步乘法：1×2×2×1=4种不同的方案
公式计算：
c11c21c21*c11=4
8.2 相邻元素之捆绑法：元素相邻，捆绑为一！
例：ABCDE站成一排，要求AB站在一起，且A要站首位，有多少种不同的排法？
第一步：A站首位，则B只能站第二位，所以AB捆在一起只有1种排法
第二步：CED在剩余3个位置里排
答案：分步相乘
1*A33=6
8.3 不相邻元素之插空法：元素间隔，分位插入！
例：ABCDE站在一排，要求AB不相邻，且E不在最后一位，有多少种不同的排法？
第一步：把AB丢一边，先排E，要求不在最后一位，则E在CDE的3个位置中有2个位置可选
第二步：ED在剩余2个位置选，即
第三步：数一数空隙，得到（C_E_D），共有4个_（空隙）
第三步：将A和B在4个空隙位置里依次选2个，即
答案：分步乘法 C21A22A42=48
8.4 定序元素之只选不排：定序元素=相同元素，只选不排！
不同元素的定序问题，和相同元素排列是一样的，概括：元素选好座位后不排排列（只选不排），逻辑是：选好座位后，要求是规定的顺序，所以不用再彼此调换顺序
例：AABDC，5个人站一排，要求A在B的前面，且B不在最后一位，有多少种排法？
第一步：AAB先选座，选完就定序了不用再排列，AAB在前面4个位置里选3个即
第二步：CD选座和排列
答案：分步相乘4×2=8种
8.5 相同元素分配之挡板法：同元进盒，挡板分隔！
例：AAAA放到2个不同的盒子里，每个盒子至少一个球
分类枚举法：AAAA代表相同的元素，两个不同的盒子代表两个不同的位置，每个盒子至少一个球表示可以有如下几种分配方案：(1,3)(3,1)(2,2)，所以共有3种不同的分配方案。
挡板法：A_A_A_A，共有3个空隙，要分成2份，所以从3个缝隙里任取1个缝隙即可，即
例：
，
，有多少组不同的解？
分类枚举法：0+0+5=5，0+1+4=5，0+2+3=5....
挡板法思路：
看做是3个不同的盒子，把5等分成5个1这样相同的元素
第一步：
，两边各借3，等式依然成立
第二步：把8分成8个1，即11111111，这样8个相同的元素
第三步：数一数8个1之间的空隙，共有7个：1_1_1_1_1_1_1_1
第四步：3个盒子，即要插2个板，将8个1分成3份，每份进一个盒子
答案： C72=21
8.6 不同元素分配之分步乘法：异元进盒，分步相乘！
条件：不同元素、不同盒子(位置)下使用
例：有3封不同的信要从3个邮箱里发出，有多少种不同的发法？
第一步：第1封信有3种不同的选择
第二步：第2封信有3种不同的选择
第三步：第3封信有3种不同的选择
答案：3×3×3=27种
备注：另外一种思路是：先分组，再分配，不再开展
8.7 正难则反之求补集法：正面难攻，则回手掏！
正难则反策略，假设问题有2个条件（AB），概括：先求出满足A条件的结果，然后再该结果里剔除掉不满足B条件的结果，得到的就是既满足A又满足B的结果。换成集合的思想来说，就是指求AB的交集。
例：A有3本不同的书，B有2本不同的书，要从这5本书里取3本出来，其中B的书至少有1本
回手掏：(从5本中任取3本的方案)-(3本书中B的书一本都没有方案)=任取3本中且B的书至少有一本的方案
第一步：从AB共5本中任取3本，即
第二步：B的书至少有1本的反面就是B的书一本都没有，也就是从A那里取3本即
答案：
C53-C33=9
有帮助，赞一个