CSP初赛知识精讲--排列组合

本文主要是介绍CSP初赛知识精讲--排列组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第十一节 排列组合

基础知识

 排列是指从给定个数的元素中取出指定个数的元素进行排序。
 组合是指从给定个数的元素中仅仅取出指定元素个数的元素，不考虑排序。
 排列组合问题的关键就是研究给定要求的排列和组合可能出现的情况的总数。

定义与公式
 排列：从n个不同元素中，任取m(m≤n，均为自然数)个不同的元素按照一定的顺序排成一列，所有排列的个数，称作从n个元素中取出m个元素的排列数。用符号$A(n,m)$或 $A_n^m$表示。计算公式如下：
$$A_n^m=\frac{n!}{(n-m)!}$$
 组合：从n个不同元素中，任取m(m≤n)个元素并成一组，所有组合的个数，称作从n个元素中取出m个元素的组合数。用符号$C(n,m)$或$C_n^m$表示。计算公式如下：
$$C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}$$
 基本计数原理
 加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m₁种不同的犯法，在第二类办法中有m₂种不同的方法…在第n类办法中有m_n种不同的方法，那么完成这件事共有$$N=m_1+m_2+...+m_n$$种不同的方法。
 乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m₁种不同的方法，做第二步有m₂种不同的方法…做第n步有m_n种不同的方法，那么完成这件事共有$$N=m_1\times m_2\times ...\times m_n$$种不同的方法。

范例精讲

 例1 从一个$4\times 4$的棋盘中选取不在同一行也不在同一列上的两个方格，共有( )种方法。
  A.60  B.72  C.86  D.64
 【正确答案：B】
 解析：对每个方格来说，与其不在同一行同一列的方格有$3\times 3=9$个，总共有$4\times 4=16$个方格，也就是会有$16\times 9$种，但是会有重复的情况(A格和B格，B格和A格，是一种情况)，所以有$16\times 9÷2=72$种。

 例2 5个小朋友排成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有( )种不同的排列方法。
  A.48  B.36  C.24  D.72
 【正确答案：A】
 解析：我们可以把双胞胎先看成一个整体，则问题变成了4个人的排列问题，共有$A(4,4)=24$种，然后两个双胞胎内部的排列有$A(2,2)=2$种，所以共有$24\times 2=48$种。

 例3 有5副不同颜色的手套(共10只手套，每副手套左右手各一只)，一次性从中取6只手套，请问恰好能配成两副手套的不同取法有( )种。
  A.120  B.180  C.150  D.30
 【正确答案：A】
 解析：首先确定两副凑成一对的手套颜色组合用$C(5,2)=10$种。然后是不成一副手套的两个手套的选择，先确定颜色组合有$C(3,2)=3$种取法，再分左右手，每种颜色下又有$C(2,1)=2$种取法，总共$10\times 3\times 2\times 2=120$种。

 例4 由数字$1、1、2、4、8、8$所组成的不同的$4$位数的个数是( )。
  A.104  B.102  C.98  D.100
 【正确答案：B】
 解析：因为存在相同的值，不能一次性考虑完，需要分情况讨论。

• $1、2、4、8$组成的$4$位数：$A(4,4)=24$种。
• $1、1、2、4、8$组成的$4$位数(一定有两个$1$)：先从$2、4、8$三个数种选两个，再除去两个$1$内部的重复排列：$C(3,2)\times A(4,4)/A(2,2)=36$种。
• $1、2、4、8、8$组成的$4$位数(一定有两个$8$)：同上，也有$36$种。
• $1、1、8、8$组成的$4$位数：考虑两个$1$和两个$8$各自内部重复排列，共有$A(4,4)/(A(2,2)\times A(2,2))=6$种。
  总共：$24+36+36+6=102$种。

 例5 设含有$10$个元素的集合的全部子集数位$S$，其中由$7$个元素组成的子集数位$T$，则$T/S$的值为（ ）。
  A.$5/32$  B.$15/128$  C.$1/8$  D.$21/128$
 【正确答案：B】
 解析：每个元素选入子集和不选入子集两种选择，$10$个元素就有2¹⁰=1024种选择，即$S=1024$。$T=C(10,7)=C(10,3)=120$。$T/S=120/1024=15/128$。

 相同与不同、空与不空问题
 盒子不空：

• 5个不同的小球放入3个不同的盒子(每盒不空)，一共有多少种放法？
  $$\frac{C_5^2{C}_3^2}{A_2^2}{A}_3^3+\frac{C_5^1{C}_4^1}{A_2^2}{A}_3^3=150$$
• 5个不同的小球放入3个相同的盒子(每盒不空)，一共有多少种放法？
  $$\frac{C_5^2{C}_3^2}{A_2^2}+\frac{C_5^1{C}_4^1}{A_2^2}A=25$$
• 5个相同的小球放入3个不同的盒子(每盒不空)，一共有多少种放法？
  $$C_4^2=6$$
• 5个相同的小球放入3个相同的盒子(每盒不空)，一共有多少种放法？
  $$1+1=2$$

 盒子可空：

• 5个不同的小球放入3个不同的盒子(可有空盒)，一共有多少种放法？
  $$3^5=243$$
• 5个不同的小球放入3个相同的盒子(可有空盒)，一共有多少种放法？
  $$1+C_5^1+C_5^2+\frac{C_5^2{C}_3^2}{A_2^2}+\frac{C_5^1{C}_4^1}{A_2^2}=41$$
• 5个相同的小球放入3个不同的盒子(可有空盒)，一共有多少种放法？
  $$C_7^2=21$$
• 5个相同的小球放入3个相同的盒子(可有空盒)，一共有多少种放法？
  $$1+2+2=5$$

赛题训练

1. 10个三好学生名额分配到7个班级，每个班级至少有一个名额，一共有( )种不同的分配方案。
    A.84 B.72 C.56 D.504
2. 把8个同样的球放在5个同样的袋子里，允许有的袋子空着，共有( )种不同的分法。(提示：如果8个球都放在一个袋子里，无论是哪个袋子，都只算一种分法。)
    A.22 B.24 C.18 D.20
3. 将7个名额分给4个不同的班级，允许有的班级没有名额，有( )种不同的分配方案。
    A.60 B.84 C.96 D.120
4. 甲、乙、丙三位同学选修课程，从4门课程中，甲选修2门，乙、丙各选修3门，则不同的选修方案共有( )种。
    A.36 B.48 C.96 D.192
5. 有7各一模一样的苹果，放到3个一模一样的盘子中，一共有( )种放法。
    A.7 B.8 C.21 D.3⁷

这篇关于CSP初赛知识精讲--排列组合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---