练习-排列组合竞赛真题

1~5:CBADA

1. 甲、乙、丙三位同学选修课程，从 4 门课程中，甲选修 2 门，乙、丙各选修3门，则不同的选修方案共有（ ）种。

A. 36 B. 48 C. 96 D. 192

C(4,2)*C(4,3)*C(4,3)
  6     4    4 = 96

2. 从一个 4 × 4 的棋盘中选取不在同一行也不在同一列上的两个方格，共有（ ）种方法。

A. 60 B. 72 C. 86 D. 64

16 * 9 / 2 = 72

3. 5 个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（ ）种不同排列方法?

A. 48 B. 36 C. 24 D. 72

C(4,4) * 2 = 24 * 2 = 48

4. 将 7 个名额分给 4 个不同的班级，允许有的班级没有名额，有（ ）种不 同的分配方案。

A. 60 B. 84 C. 96 D. 120

11 分配给４个班， 每个班至少１个。
 ＊｜＊｜＊｜＊｜＊｜＊｜＊｜＊｜＊｜＊｜＊
C(10, 3) = 120

5. 10 个三好学生名额分配到 7 个班级，每个班级至少有一个名额，一共有（ ）种不同的分配方案。

A. 84 B. 72 C. 56 D. 504

*|*|*|*|*|*|*|*|*|*
C(9,6) = 84

6~10: BADBC

---

6. 有 7 个一模一样的苹果，放到 3 个一样的盘子中，一共有（ ）种放法。

A. 7 B. 8 C. 21 D. 3^7

相同的苹果，放相同的盘子，重复的不能计算在内。
（7，0，0），
（6，1，0），
（5，2，0），（5，1，1），
（4，3，0），（4，2，1），
（3，3，1），（3，2，2），共8种；
答：共有8种不同的放法．

7. 有五副不同颜色的手套（共 10 只手套，每副手套左右手各 1 只），一次性从中取 6 只手套，请问恰好能配成两副手套的不同取法有（ ）种。

A. 120 B. 180 C. 150 D. 30

先从5副手套中任取二副，有C(5,2)=10种取法，再从剩下的三副手套中，任选二副手套，并各取一只（左左，左右，右左，右右共4种）
C(3,2)*4 = 12种.
由分步计数乘法原理，合计10*12=120种

8. A班有5名风纪委员，B班有4名风纪委员，C班有3名风纪委员。现在需要这些同学中选取6名风纪委员巡逻，如果只关注各班派出的风纪委员人数，有几种不同的方案？

A. 9 B. 12 C. 15 D. 18 *

(5,4,3 = 12
C(12,6) /  6! 
A         B        C
*****   &&&&     %%%
501  1
510  2
420  3
411
402
312
321
330
303
240
231
213
222
141
132
123
042
033

9. 由数字1, 1, 2, 4, 8, 8所组成的不同的4位数的个数是（）。

A. 104 B. 102 C. 98 D. 100

穷举法。
1.当取出1，1，2，4时，共有C(4,2)*2=12种;
2.当取出1，1，2，8，也是12种;
3当取出1，1，4，8,也是12种;
4当取出1，1，8，8，为C(4，2)是6种;
5当取出为1，2，4，8时候，为A(4,4)=24种;
6当取出1，2,8，8，为12种;
7当取出1，4，8，8为12种，
8当取出2，4，8，8为12种。
一共102种情况。

10. —些数字可以颠倒过来看，例如0、1、8颠倒过来还是本身，6颠倒过来是9, 9颠倒过来看还是6,其他数字颠倒过来都不构成数字。 类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901。假设某个城市的车牌只由5位数字组成，每一位都可以取0到9。 请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌？（）

A. 60 B. 125 C. 75 D. 100

ＡＢＣＤＥ
５５３ ＝ ７５

11~15: BCBAA

11. 一些数字可以颠倒过来看，例如0、1、8颠倒过来还是本身，6颠倒过来是 9,9颠倒过来看还是6,其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901 。假设某个城市的车牌只有5位数字，每一位都可以取0到9。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的5位数能被3整除？（）

A. 40 B. 25 C. 30 D. 20

在前一题基础上。
想被3整数，就是各位加起来的和可以被3整数。
可以对每一位的数对3取模：
      0 1 8 6 9
-----------
第1位：0 2 1 0 0  （第1位决定第5位）
第2位：0 2 1 0 0  （第2位决定第4位）
中间位：0 1 2
 中间， 第1位，第2位：
    （0 0 0）：1 * 3 * 3 = 9
    （0 2 1）：1 * 1 * 1 = 1
    （0 1 2）：1 * 1 * 1 = 1

    （1 0 2）：1 * 3 * 1 = 3
    （1 2 0）：1 * 1 * 3 = 3；
    （1 1 1）：1 * 1 * 1 = 1

    （2 0 1）：1 * 3 * 1 = 3
    （2 1 0）：1 * 1 * 3 = 3
    （2 2 2）：1 * 1 * 1 = 1
合计11+7+7=25

12. 把8个同样的球放在5个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的分法？（） 提示：如果8个球都放在一个袋子里，无论是哪个袋子，都只算同一种分法。

A. 22 B. 24 C. 18 D. 20

合计１８种
8 0 0 0 0 

7 1 0 0 0 
6 2 0 0 0 
5 3 0 0 0 
4 4 0 0 0 

6 1 1 0 0
5 2 1 0 0
4 3 1 0 0 
4 2 2 0 0 
3 3 2 0 0 

5 1 1 1 0
4 2 1 1 0
3 3 1 1 0
3 2 2 1 0
2 2 2 2 0

4 1 1 1 1 
3 2 1 1 1
2 2 2 1 1  

13. 设含有10 个元素的集合的全部子集数为 S，其中由 7 个元素组成的子集数为 T，则 T / S 的值为（ ）。

A. 5 / 32 B. 15 / 128 C. 1 / 8 D. 21 / 128

计算子集数：
集合A中有n个元素，则A的子集个数为2^n个（2的n次方个），真子集个数为2^n-1个（减去集合A本身），非空真子集个数为2^n-2个（减去集合A本身和空集）
0 7, 6 5 4 3 2 1, 
2^7 = 120
2^10 = 1024

14. 由四个没有区别的点构成的简单无向连通图的个数是（ ）。

A. 6 B. 7 C. 8 D. 9

3条边的两种，4条边的2种，5条边的1种，6条边的1种

15. 二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，24 个顶点的二分图至多有（ ）条边。

A. 144 B. 100 C. 48 D. 122

二分图中顶点可以分成两个集合， 顶点在集合内没有边相连。 要想使二分图边最多。 一个集合的一个点， 必须与另一个集合每个点都有边相连，就是将24分成两个数， 使其乘积最大。 12*12 = 144

下面是二分图的定义，特性及应用。
二分图，也称为二部图或偶图，是一种特殊的无向图结构。在这种图中，顶点集V可以被分割成两个不相交的子集A和B，使得图中的每一条边（i, j）所连接的两个顶点i和j分别属于这两个不同的子集（i属于A，j属于B）。这意味着，在二分图中，两个子集内的顶点不相邻，即它们之间没有共同的边。这种特性使得二分图在图论中具有特殊的意义和用途。

二分图的一个重要性质是它们不含有奇数环，可能包含长度为偶数的环，并且不一定是连通图。这种定义不仅适用于无向图，也适用于有向图，其中顶点集被分割成两个不相交的集合，且每条有向边都从一个集合指向另一个集合。

二分图的应用非常广泛，包括在计算机科学、网络设计、社交网络分析等领域。例如，在社交网络中，可以将用户分为两组（如男性和女性），然后分析哪些用户之间存在关系（即边），从而研究社交网络的模式和结构。此外，二分图的最大匹配问题也是其重要的应用之一。

tags: 排列组合，数学