数量关系
数学模型
排列组合

排列组合

(一)排列和排列数

1. 排列 A(array)

Anm=n(n1)(n2)(nm+1)A_n^m = n(n-1)(n-2)\cdots(n-m+1)

nn 个不同元素中,任取 m(mn)m (m \leq n) 个元素,按照一定的顺序排成一列,叫做从 nn 个不同元素中取出 mm 个元素的一个排列。

2. 排列数公式:

Anm=n(n1)(n2)(nm+1)A_n^m = n(n-1)(n-2)\cdots(n-m+1)

nn 个不同元素中取出 m(mn)m (m \leq n) 个元素的所有排列数为:

Anm=n(n1)(n2)(nm+1)A_n^m = n(n-1)(n-2)\dots(n-m+1)

n=mn = m 时,为全排列

Ann=n(n1)(n2)321=n!A_n^n = n(n-1)(n-2)\dots3 \cdot 2 \cdot 1 = n! Anm=Cnm×AmmA_n^m = C_n^m \times A_m^m

排列其实相当于一步步的组合。大学寝室选 6 人去打饭,在窗口排队共有

A66A_6^6

种,第一位有 6 种,排第二有 5 种⋯⋯第六有 1 种,所以一共有 6×5×4×3×2×16 \times 5 \times 4 \times 3 \times 2 \times 1 种,相当于 C66×C55×C44×C33×C22×C11C_6^6 \times C_5^5 \times C_4^4 \times C_3^3 \times C_2^2 \times C_1^1 种。

假如只是从 6 人中选 3 人打饭,不用排队,则是 C63C_6^3 种,如果算上排队,则 C63×A33C_6^3 \times A_3^3 种,即相当于一开始就选出排队的 A63A_6^3 种。


注意: 先组合再排列,注意排列的是 CnmC_n^m 中的 nn,一定是 nn 分不同情况下有顺序,如果不区分,则不用乘 AnmA_n^m

(二)组合和组合数

1. 组合 C(combination)

nn 个不同元素中,任取 m(mn)m(m \leq n) 个元素并成一组,叫做从 nn 个不同元素中取出 mm 个元素的一个组合。

2. 组合数公式:

nn 个不同元素中取出 m(mn)m(m \leq n) 个元素的所有组合的个数

  1. Cnm=AnmAmm=m(m1)(m2)(mn+1)m!C_n^m = \frac{A_n^m}{A_m^m} = \frac{m(m-1)(m-2)\cdots(m-n+1)}{m!}

  2. Cnm=CnnmC_n^m = C_n^{n-m}

从寝室 6 人中选 2 人去打饭,剩下 4 人在寝室,选 2 人打饭和留 4 人在寝室是一样的,2 人打饭即剩的 4 人肯定在寝室,所以

C62=C64C_6^2 = C_6^4


区别: 排列——与顺序有关,组合——与顺序无关。


(三)加法原理和乘法原理

1. 加法原理

完成一件事,有 nn 类办法,在第 1 类办法中有 m1m_1 种不同的方法,在第 2 类办法中有 m2m_2 种不同的方法⋯⋯在第 nn 类办法中有 mnm_n 种不同的方法,那么完成这件事共有 N=m1+m2++mnN = m_1 + m_2 + \cdots + m_n 种不同的方法。

例如: 从甲地到乙地,一天中,火车有 3 趟,汽车有 2 趟,那么一天中从甲地到乙地有几种方式? 解析 从甲地到乙地的方式可以是乘坐火车或者汽车。既然有 3 趟火车和 2 趟汽车,那么总的出行选择方式就是火车和汽车的选择方式之和。

  • 选择火车的方式有 3 种。
  • 选择汽车的方式有 2 种。

因此,总的方式数是 3 + 2 = 5 种。所以,一天中从甲地到乙地总共有 5 种不同的方式。

2. 乘法原理

完成一件事需要 nn 个步骤,做第 1 步有 m1m_1 种不同的方法,做第 2 步有 m2m_2 种不同的方法,⋯⋯做第 nn 步有 mnm_n 种不同的方法,那么完成这件事共有

N=m1×m2××mnN = m_1 \times m_2 \times \cdots \times m_n

种不同的方法。

例如: 从甲地到乙地,必须先经过丙地,一天中,从甲地到丙地火车有 3 趟,从丙地到乙地汽车有 2 趟,那么一天中从甲地到乙地有几种方式? 解析 要从甲地到达乙地,因为必经丙地,所以需要考虑从甲地到丙地,再从丙地到乙地的组合方式。 从甲地到丙地有 3 趟火车可选,从丙地到乙地有 2 趟汽车可选。每趟火车都可以搭配 2 趟汽车中的任一趟,因此,总的组合方式为: 3 趟火车 * 2 趟汽车 = 6 种方式 所以,一天中从甲地到乙地总共有 6 种不同的方式。

解题策略

1. 内部组合,外部排列

例1: 某次专业技能大赛有来自A科室的4名职工和来自B科室 的2名职工参加,结果有3人获奖且每人的成绩均不相同。如果获奖者中最 多只有1人来自B科室,那么获奖者的名单和名次顺序有多少种不同的可能 性?

  • A. 48
  • B. 72
  • C. 96
  • D. 120

解析: 分类。

  • 情况 1: 获奖 B 科 1 人,A 科 2 人,B 选 1,有 2 种,A 选 2,有 C42=6C_4^2 = 6 种,获奖 3 人排序有 A33=6A_3^3 = 6 种,总情况 2 ×6×6=72\times 6 \times 6 = 72 种(错误点: 情况 1,A 选 2 时不能直接先排 A2A^2易错)。

  • 情况 2: 获奖三人都是 A:A 选 3,有 A33=24A_3^3 = 24 种。两种情况相加 72+24=9672 + 24 = 96 种。C

分步组合时,已经排列,不需再排列。一次性组合出来可以再 A 排列,如果本身是分步操作组合选取,则不需要再排列。

易错点: 两个一样的东西组合,不分顺序的情况下,一定有一次重复,总情况数一定要减掉重复的。

2. 错位排列

主体完全错位,欧拉错装信封问题:

D1=0, D2=1, D3=2, D4=9, D5=44, D6=265D_1 = 0, \ D_2 = 1, \ D_3 = 2, \ D_4 = 9, \ D_5 = 44, \ D_6 = 265

【递推公式】:

Dn=(n1)(Dn2+Dn1)=(项数1×(前两项的和)D_n = (n-1) \left( D_{n-2} + D_{n-1} \right) = (项数-1)\times(前两项的和)

3. 圆周排列

nn 个元素,共有 (n1)!(n-1)!

关键词: 环形/围成一圈/圆桌: nn 个元素,共有 (n1)!(n-1)!

主体环形而坐,圆周排列,nn 个元素/人的环形排列数:

Annn=Ann1=N1!\frac{A_n^n}{n} = A_n^{n-1} = (N-1)!

: 3 人直线排列有 A33=6A_3^3 = 6 种,环形排列有

A333=A22=2\frac{A_3^3}{3} = A_2^2 = 2种。

Here is the extracted content in Markdown and LaTeX format:


4. 平均分组

全部平均分组

  1. nn 个组,元素个数相同,只需要分组不用排列。

  2. 排列总情况数 ÷ AnnA_n^n

分成 nn 组,先排列,再 ÷ AnnA_n^n,即: 排列总情况数Ann\frac{\text{排列总情况数}}{A_n^n} 分成 3 组,÷ A33A_3^3,分成 4 组,÷ A44A_4^4,分成 5 组,÷ A55A_5^5,分成 mm 组,÷ AmmA_m^m

5. 比赛问题

循环赛:

NN 支队伍进行循环赛

  1. 单循环: 比赛场次 = C(n,2)C(n, 2)

一般意义上的循环赛,

任意两支队伍打一场比赛: 比赛场次 = Cn2C_n^2

  1. 双循环:

任意两支队伍打两场比赛 = 单循环 ×2\times 2,分主客场:

比赛场次 = An2A_n^2 【基本不考】

淘汰赛:

每场比赛淘汰一支队伍,每轮比赛淘汰一半的队伍。

  1. 按轮淘汰:

nn 个人,每次分 2 组比赛,每次淘汰一半人,决出胜负需比赛 n1n-1 次。

  • ① 16 人,分成两组每组 8 人,比赛 8 场淘汰一半剩 8 人。
  • ② 8 人,再分成两组各 4 人比赛第 4 场,淘汰一半剩 4 人。
  • ③ 4 人,分成两组各 2 人比赛第 2 场,淘汰一半剩 2 人。
  • ④ 2 人,最后 1 场决出胜负。

一共比赛 8+4+2+1=158+4+2+1=15 场。比赛场次 = N1N-1

  1. 按场淘汰

  2. NN 个人比赛,决出冠亚军,比赛场次 = N1N - 1

  3. NN 个人比赛,决出 1, 2, 3, 4 名,比赛场次 = NN

即决出冠亚军后,还有两个人要比赛决出第三名和第四名,在原来基础上多一场比赛,N1+1=NN - 1 + 1 = N

: 100 人比赛,每场淘汰一个,最后剩 1 个冠军,则一共进行 99 场比赛,淘汰了 99 人。

6. 递推方法

本质是递推过程,即斐波那契数列

1,1,2,3,5,8,13,21,34,55,891, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

本质是一个递推和数列,从第三项开始为前两项之和。

f(n)=f(n1)+f(n2)+...f(n) = f(n-1) + f(n-2) + ...

f(n)=f(n1)f(n2)...f(n) = f(n-1) * f(n-2) * ...

等递推公式

7. 多人传球

MM 个人传 NN 次球,有多少种传球方式: X=(M1)NMX = \frac{(M-1)^N}{M}

  1. XX 最接近的整数:最终传给“非自己”的某人。
  2. XX 第二接近的整数:最终传给自己

解题方法

(一)特殊优先

  1. 题目: 某一个或几个元素在指定位置或不在指定位置。
  2. 原则: 谁特殊,优先谁!

位置优先元素优先

(二)捆绑法

  1. 主体相邻捆绑法
  2. 内部排列 + 外部打包排列

先捆绑,整体排列完再内部排。

(三)插空法

  1. 主体不相邻,不能连着/连续不能挨着。
  2. 技巧: 先排其他,再插“不相邻”。

(1) NN 个物体 N+1N+1 个空(包括两端),物体之间 N1N-1 个空不相邻对象去插另一对象的空(不是反过来),NN 个物体 N+1N+1 个空(包括两端),物体之间 N1N-1 个空。

(2) 先单独将被插空对象排列,再插空。

(3) 两种主体都不能连续,多数量主体插少数量主体的空(包括两端)。

(四)插板法

  1. 相同元素分配问题,每组至少分到多少个

(1) 相同元素分配(说明不需排列,无顺序);

(2) 每组至少分一个;

(3) 所分组不同。

  1. MM 个元素分成 NN 组,每组至少 1 个:C(M1,N1)C(M-1, N-1) 种方法

(1) MM 个元素分成 NN 组,每组至少 1 个:CM1N1C_{M-1}^{N-1} 种方法。

(2) MM 个元素分成 XX 个:转化成每组至少 1 个

先每组分 X1X-1 个,剩 M(X1)NM-(X-1)N 个,再按每组至少 1 个分,共 CN1[M(X1)N]1C_{N-1}^{[M-(X-1)N]-1}种。

例 1. 3 个人分 5 个苹果,每人至少一个,有多少种分法?

解析: 等价于“x+y+z=5x + y + z = 5 有多少组正整数解?”用隔板法,答案为 C(4,2)C(4, 2)

(五)逆向计数法

  1. 正难则反,逆向计数
  2. 正面情况多,反面情况少。

例 1. 某班有 50 名学生,其中 20 名男生,30 名女生。从中选出 3 名学生,至少有 1 名男生,有多少种选法?

解析: 正面情况多,反面情况少。 解法一: 我们需要从 50 名学生中选出 3 名学生,且至少有 1 名男生。我们可以通过以下步骤来解决这个问题:

  1. 计算总的选法数: 从 50 名学生中选出 3 名学生的总选法数是: (503)=50×49×483×2×1=19600\binom{50}{3} = \frac{50 \times 49 \times 48}{3 \times 2 \times 1} = 19600

  2. 计算没有男生的选法数: 没有男生的情况意味着选出的 3 名学生全是女生。班上有 30 名女生,从中选出 3 名女生的选法数是: (303)=30×29×283×2×1=4060\binom{30}{3} = \frac{30 \times 29 \times 28}{3 \times 2 \times 1} = 4060

  3. 计算至少有 1 名男生的选法数: 至少有 1 名男生的选法数等于总选法数减去没有男生的选法数: (503)(303)=196004060=15540\binom{50}{3} - \binom{30}{3} = 19600 - 4060 = 15540

因此,至少有 1 名男生的选法数是: 15540\boxed{15540}

解法二: 要解这个问题,我们可以通过计算总的选择方法,然后减去全是女生的选择方法。

  1. 计算总的选择方法:从 50 名学生中选择 3 名,不考虑性别。使用组合数的计算方法,这可以表示为 C(50, 3)。 C(50,3)=50!3!(503)!=50×49×483×2×1=19600C(50, 3) = \frac{50!}{3!(50-3)!} = \frac{50 \times 49 \times 48}{3 \times 2 \times 1} = 19600
  2. 计算全是女生的选法:从 30 名女生中选择 3 名。这可以表示为 C(30, 3)。 C(30,3)=30!3!(303)!=30×29×283×2×1=4060C(30, 3) = \frac{30!}{3!(30-3)!} = \frac{30 \times 29 \times 28}{3 \times 2 \times 1} = 4060
  3. 计算至少有 1 名男生的选法:总的选择方法减去全是女生的选法,即 19600 - 4060 = 15540。 因此,从这 50 名学生中选出 3 名学生,且其中至少有 1 名男生的选择方法共有 15540 种。

例题讲解

例1: 四对情侣排成一队买演唱会门票,已知每对情侣必须排在 一起,问共有多少种不同的排队顺序?

  • A.24 种
  • B.96 种
  • C.384 种
  • D.40320 种

解析: 捆绑法。

  • 每对情侣捆绑在一起,相当于 4 对情侣排成一排,有 A44=24A_4^4 = 24 种排法。
  • 每对情侣内部有 A22=2A_2^2 = 2 种排法,所以总共有 24×2×2×2×2=38424 \times 2 \times 2 \times 2 \times 2 = 384 种排法。
  • C

例2: 某市举办经济建设成就展,计划在六月上旬组织5个 单位参观,其中1个单位由于人数较多,需要连续参观2天,其他4个单位 只需参观1天,若每天最多只能安排一个单位参观,则参观的时间安排共有 ()种。

  • A.650
  • B.700
  • C.15120
  • D.16800

捆绑法。连续参观2天看作一个整体,6月上旬一共10天,将整 体的2天和其他8天看作9个时段,安排5个单位参观,有A9 5=15120种。C。 捆绑的两天不用排列

例3: 将7个大小相同的桔子分给4个小朋友,要求每个小朋友 至少得到1个桔子,一共有几种分配方法?

  • A.14
  • B.18
  • C.20
  • D.22

解析: 插板法,7 个桔子分 4 人,每人至少一个,相当于在中间 6 个空插 3 个板,则共有 C63=20C_6^3 = 20种。C

例4: 某企业选拔170多名优秀人才平均分配为7组 参加培训。在选拔出的人才中,党员人数比非党员多3倍。接受培训的党员 中的10%在培训结束后被随机派往甲单位等12个基层单位进一步锻炼。已知 每个基层单位至少分配1人,问甲单位分配人数多于1的概率在以下哪个范 围内?

  • A.不到14%
  • B.14%-17%之间
  • C.17%-20%之间
  • D.超过20%

解析:(1)170多人且是7的倍数,则总人数应为175,党员和非党员 比例4:1,分别为140和35,所以14个党员分配给12个单位C14 12。 (2)甲分配多于1只有两种情况, 第一种情况:甲 3 人,其他单位全是 1 人,只有 1 种情况。

第二种情况:甲 2 人,其他单位一个 2,其他全是 1,相当于 12 个人分到 11 个单位每个单位至少 1 人,插空 C1110=11C_{11}^{10} = 11 种情况,共 11 + 1 = 12 种情况。

概率为 12÷C1412=12/7812 \div C_{14}^{12} = 12 / 78B

方法 2:反面即甲分配 1 个,剩下 13 分配给 11 个人,插板 C1210=66C_{12}^{10} = 66,概率为 (7866)÷78=12/78 (78 - 66) \div 78 = 12 / 78。正面分两种,反面只有一种情况。B

例5: 某论坛邀请了六位嘉宾,安排其中三人进行单独演 讲,另三人参加圆桌对话节目。如每位嘉宾都可以参加演讲或圆桌对话,演 讲顺序分先后且圆桌对话必须安排在任意两场演讲之间,问一共有多少种不 同的安排方式?

  • A. 120
  • B. 240
  • C. 480
  • D. 1440

解析:插空法。 圆桌对话须在任意两场演讲之间,则: (1)圆桌对话相邻; (2)圆桌不能在演讲两端。 六人中选三人按先后演讲,有A63=120A_6^3 = 120种,三场演讲之间两个空,圆桌对话有C21=2C_2^1 = 2 种,共120×2=240120 \times 2 = 240B

例6: 把12棵同样的松树和6棵同样的柏树种植在道路两 侧,每侧种植9棵,要求每侧的柏树数量相等且不相邻,且道路起点和终点 处两侧种植的都必须是松树。问有多少种不同的种植方法?

  • A.36
  • B.50
  • C.100
  • D.400

解析:

  1. 每侧 3 棵柏树,9 - 3 = 6 棵松树。

  2. “不相邻”插空,柏树不相邻,两端是松树,则柏树只能插在松树中间,6 棵松树中间有 5 个空,故柏树有C53=10C_5^3 = 10种。

  3. “两侧”则有 C53C53=100C_5^3 C_5^3 = 100种。C。【树都一样,而且两边各 9 固定,不需再排列】。

例7: 四位厨师聚餐时各做一道拿手菜。现在要求每人去品尝一 道菜,但不能尝自己的那道。问共有几种不同尝法?

  • A.6 种
  • B.9 种
  • C.12 种
  • D.15 种

解析: 错位排列:D4=9D_4 = 9B

例8: 5个瓶子都贴了标签,其中恰好贴错了三个,则错 的可能情况有几种?

  • A.6
  • B.10
  • C.12
  • D.20

解析: 先贴错的3个找出来,再3个错位排列,D3×C53=20 D_3 \times C_5^3 = 20D

例9: 某部门从8名员工中选派4人参加培训,其中2人参 加计算机培训,1人参加英语培训,1人参加财务培训,问不同的选法有多少 种?

  • A.256
  • B.840
  • C.1680
  • D.5040

解析: 整体分步讨论,8 选 2 参加计算机, C82=28C_8^2 = 28 剩余 6 选 1 参加英语,C61=6C_6^1 = 6,剩余 5 选 1 参加财务,C51=5C_5^1 = 5,总情况为 C82C61C51=840C_8^2 C_6^1 C_5^1 = 840,或C84C42A21=840C_8^4 C_4^2 A_2^1 = 840C84C42C21C11=840C_8^4 C_4^2 C_2^1 C_1^1 = 840 B

例10: 有5对夫妇参加一场婚宴,他们被安排在一张10个 座位的圆桌就餐,但是婚礼操办者并不知道他们彼此之间的关系,只是随机 安排座位。问5对夫妇恰好都被安排在一起相邻而坐的概率是多少?

  • A. 在1‰到5‰之间
  • B. 在5‰到1%之间
  • C. 超过1%
  • D. 不超过1‰

解析: 圆周排列,5 对夫妻先打包环形排列有 A44A_4^4 种,每对夫妻之间有 2 种,则

A44×25/A99=4/(210×9)2/1000A_4^4 \times 2^5 / A_9^9 = 4 / (210 \times 9) \approx 2 / 1000 A

例11: 某单位组织的羽毛球男单比赛共有48名选手报名参 加,比赛采用淘汰赛制,在比赛中负一场的选手即被淘汰,直至决出最后的 冠军,如每名选手每天最多参加一场比赛,则比赛至少需要举行几天?

  • A.4
  • B.5
  • C.6
  • D.7

解析:按轮淘汰。要使比赛天数最少,则每天比赛选手尽可能多,加之 每名选手每天最多参加一场比赛, 第一天总共比赛48÷2=24场,还剩24名;第二天24÷2=12场,剩12 名;第三天12÷2=6场,剩6名;第四天6÷2=3场,剩3名;第五天选2人 比赛,淘汰1人;第六天,剩下的2人决出冠军。至少6天。C

例12: 16支球队分两组,每组打单循环赛,共需打多少场比 赛?

  • A.16
  • B.56
  • C.64
  • D.120

解析: 单循环赛,则每组比赛有C82=28C_8^2 = 28场,两组共需打28×2=5628 \times 2 = 56场。B

例13: 四人进行篮球接球练习,要求每人接球后再传给别人。 开始由甲发球,并作为第一次传球,若第五次传球后,球又回到甲手中,则 共有传球方式( )种。

  • A.60 种
  • B.65 种
  • C.70 种
  • D.75 种

根据传球公式,MM个人传 NN次球,4 个人传 5 次球,则

X=(M1)NM=(41)54=60.75X = \frac{(M-1)^N}{M} = \frac{(4-1)^5}{4} = 60.75

XX第二接近的整数是最终传回自己手中的方法数,最接近整数是 61,第二接近整数是 60。A

例14: 某县通过发展旅游业来实现乡村振 兴,引进了甲、乙、丙、丁、戊和己6名专家。其中甲、乙、丙是环境保护 专家,丁、戊、己是旅游行业专家,甲、丁、戊熟悉社交媒体宣传。现要将6 名专家平均分成2个小组,每个小组都要有环境保护专家、旅游行业专家和 熟悉社交媒体宣传的人,问有多少种不同的分组方式?

  • A.12
  • B.24
  • C.4
  • D.8

解析: 随机选三个分到一组,剩余为另一组,方法数为 C63C_6^3,涉及均匀分组问题,故为: C63A22=10\frac{C_6^3}{A_2^2} = 10种,剔除 2 种不符合的情况(甲乙丙、丁戊己)(甲丁戊、乙丙丁), 还剩 102=810 - 2 = 8种。D

例15: 某班同学要订 A、B、C、D 四种学习报,每人至少 订一种,最多订四种,那么每个同学有多少种不同的订报方式?

  • A.7 种
  • B.12 种
  • C.15 种
  • D.21 种

解析: 方法 1: C41+C42+C43+C44=15C_4^1 + C_4^2 + C_4^3 + C_4^4 = 15C
方法 2: 每份报纸分两种情况:订和不订,所有可能 = 不订 = 2 × 2 × 2 × 2 - 1 = 15。