排列组合 · 概率论、数理统计与信息论 05

关键字排列组合

摘要 —— 本文给出了排列组合的定义与相关方法的实践。

本文首先介绍排列和组合的定义,然后通过各种案例介绍了常用的方法,如隔板法、插空法等。

1 定义

1.1 排列数

从 $n$ 个不同元素中取出 $k$ 个元素的排列数:

$$ A_n^k := n \times (n - 1) \times ... \times (n -k + 1) = \frac{n!}{ (n - k)! }, \quad k \leq n $$

1.2 组合数

从 n 个不同元素中取出 k 个元素的组合数:在排列数的基础上除去同一组数重复出现的排列数。

$$ C_n^k := \frac{A_n^k}{k!} = \frac{n!}{k! (n-k)!}, \quad k \leq n $$

2 实战

2.1 分步乘法原理

由 0、1、2、3、4、5 可以组成多少个没有重复数字的五位奇数?

解答:个位数只能选 1、3、5,即 $C_3^1$,万位数不能为 0,因此由 $C_4^1$ 中选择,中间三位数在剩余的四个数中任选三个进行排列即可,有 $A_4^3$ 种选择,根据分步乘法原理可得答案 $C_3^1 \times C_4^1 \times A_4^3=288$。

2.2 分类加法原理

旅行社有豪华游 5 种,普通游 4 种,某单位欲从中选择 4 种,且豪华游和普通游至少各一种的选择有多少种?

解答:根据要求,允许的情况有 “1 豪华 3 普通”、“2 豪华 2 普通”、“3 豪华 1 普通”,三种分别有 $C_5^1 \times C_4^3$、$C_5^2 \times C_4^2$、$C_5^3 \times C_4^1$ 种选择,根据分类加法原理,三种选择数相加可得 120。另解:$C_9^4 - C_5^4 - C_4^4$。

2.3 相邻问题与捆绑法

问题 1:有三个女生四个男生站在一排,要求女生必须相邻,男生必须相邻(即一个人左右两边至少有一个是他的同性),一共有多少种排法?

解答:显然,女生和男生需要分别抱团(各自捆绑成为一个整体),一共有两个整体,因此整体而言有 $A_2^2$ 种排列。在每个整体内部,各有 $A_3^3$ 和 $A_4^4$ 中排列(松绑),因此一共有 $A_2^2 \times A_3^3 \times A_4^4$ 种。

问题 2:A、B、C、D、E 五人站一排,AB 必须相邻且 B 必须在 A 的右边,则一共有多少种排法?

解答:$A_4^4$。不用松绑。

问题 3:A、B、C、D、E 五人站一排, B 必须在 A 的右边,则一共有多少种排法?

解答:

2.4 相离问题与插空法

5 名母亲带领 5 个孩子拍照,孩子不相邻的站法有多少种?

解答:5 名母亲一共有 $A_5^5$ 种排列,留下了 6 个空位,一个空位中不能有超过 1 个孩子,因此是 $A_6^5$ 种排法,因此答案为 $A_5^5 \times A_6^5$。

2.5 相离与相邻综合

问题 1:3 名男生和 4 名女生排队站一排,求排队方法种数。

  1. 男女各站一起(男生必须相邻、女生必须相邻):$A_2^2 \times A_3^3 \times A_4^4$。
  2. 男生必须站一起:男生捆绑,$A_3^3 \times A_5^5$。
  3. 男生不能相邻:插空,$A_4^4 \times A_5^3$。
  4. 男女各不相邻:男女生各自以对方为桩插空,$A_3^3 \times A_4^4$。

问题 2:8 个节目种有 2 个唱歌、3 个舞蹈、3 个曲艺,求编排方法数。

  1. 一个唱歌开头,一个唱歌结尾:$A_2^2 \times A_6^6$。
  2. 两个唱歌不相邻:$A_6^6 \times A_7^2$。
  3. 两个唱歌相邻且三个舞蹈不相邻:$A_4^4 \times A_5^3 \times A_2^2$。

2.6 相同元素分组与隔板法

问题 1:10 各运动员分给 7 个班,每班至少一个,有多少种分配方案?

解答:首先,这是一个分配问题,不关心每个班分到的谁,只关心每个班分到几个人。因此使用组合数。10 个班一共有 9 个可以插入 6 个板子的空档(最外面两个非法),因此答案为 $C_9^6$。可总结,$n$ 个元素分成 $m$ 份,分配方案一共有 $C_{n-1}^{m-1}$ 种。

问题 2:将 6 个相同的小球放入 4 个盒子,求分配方案种数。

  1. 每个盒子都不为空:直接 $C_5^3$。
  2. 恰有一个空盒子:首先随意插入两个板子 $C_5^2$,最后一个板子的插入要产生一个空盒,因此只能选最左外侧、最右外侧或者前两个板子所在的位置,即 $C_4^1$,所以答案为 $C_5^2 \times C_4^1$。
  3. 恰有两个空盒子:

    • 思路 1:首先随意插入一个板子 $C_5^1$,然后在三个可选的位置中选择两个($C_3^2$)或一个($C_3^1$)插入剩下的两个板子,因此答案为 $C_5^1 \times (C_3^2 + C_3^1)$。

    • 思路 2:首先选择两个不为空的盒子 $C_4^2$,然后问题变成了将 6 个小球放入 2 个盒子,直接 $C_5^1$,因此答案为 $C_4^2 \times C_5^1$。

2.7 平均分组问题 / 不同元素分组与除量法

问题 1:6 本不同的书平均分成 3 堆,每堆 2 本共有多少种分法?

解答:如果直接 $C_6^2 \times C_4^2 \times C_2^2$ 的话,会造成重复计算。例如,(AB, CD, EF)和 (AB, EF, CD) 其实是一样的,因为堆没有编号,当我们使用 $C_6^2 \times C_4^2 \times C_2^2$ 时,不自觉地给三个堆排了序。因此需要除以相同量的策略种数,答案为 $C_6^2 \times C_4^2 \times C_2^2 / A_3^3$。

问题 2:将 13 个球队分成 3 组,一组 5 个队,其他两组 4 个队,有多少种分法?

解答:队数相同的两组需要去掉排序,因此答案为 $C_{13}^5 \times C_8^4 \times C_4^4 / A_2^2$。

问题 3:高三年级一共有 6 个班,现从外地转入 4 名学生,要安排到该年级的两个班级且每个班级安排 2 名,一共有几种安排方法?

解答:首先相当于四个不同元素分成两组,使用除量法可得 $C_4^2 \times C_2^2 / A_2^2$ 种,然后将这两个组作为两个整体安排到 6 个班中,即 $A_6^2$,所以答案为 $A_6^2 \times C_4^2 \times C_2^2 / A_2^2$。

问题 4:6 本不同的书,分为 3 组,求分配方法个数。

  1. 每组 2 本:这是平均分组,因此得 $C_6^2 \times C_4^2 \times C_2^2 / A_3^3$。
  2. 一组 1 本,一组 2 本,一组 3 本:没有重复数量的分组,直接 $C_6^1 \times C_5^2 \times C_3^3$。
  3. 一组 4 本,两外两组各 1 本:这是部分平均分组,因此得 $C_6^4 \times C_2^1 \times C_2^1 / A_2^2$。

2.8 选排问题与先取后排法

问题 1:四个不同的球放入编号为 1、2、3、4 的四个盒子中,恰有一个空盒的放法有多少种?

解答:因为球不同,所以不能使用隔板法。分析可知满足条件的放法必须有某个盒子放两个球,某两个盒子放一个球,最后一个盒子没有球。先从 4 个球里面选择两个 $C_4^2$ 放入某个盒子中,然后通过 “三个被选中的盒子的全排列” 确定 (2, 1, 1, 0) 对应的盒子编号,即 $A_4^3$,因此答案为 $C_4^2 \times A_4^3$,这里用到了 “先选择后排序” 的思路。

问题 2:9 名运动员,其中男 5 名,女 4 名,有多少种混合双打的分组方法?

解答:首先需要各选择两人,即 $C_5^2 \times C_4^2$,然后男 1 有两种选择(女 1 或女 2,$A_2^2$),男 1 的选择确定后男 2 的选择自动确定,因此答案为 $C_5^2 \times C_4^2 \times A_2^2$。

问题 3:电视台有 8 个节目准备分两天播出,每天播出 4 个,其中某电视剧和某专题报道必须在第一天播出,某谈话节目必须在第二天播出,供有多少种播出方案?

解答:不妨将 8 个节目分别记为 ABCDEFGH,必须在第一天播出的是 AB,必须在第二天播出的是 C,则第一天还需要在剩下的 5 个节目中选择 2 个($C_5^2$),然后第一天的节目全排列 $A_4^4$;第二天在剩余的 3 个节目中选 3 个,然后全排列,即 $C_3^3 \times A_4^4$,因此答案为 $C_5^2 \times A_4^4 \times C_3^3 \times A_4^4$。

问题 4:用数字 1、2、3、4、5、6 组成没有重复数字的四位数,其中个位、十位和百位上的数字之和位偶数的四位数共有多少个?

解答:对于 “个十百” 这三个位置,要么是那个全是偶数,要么一个偶数两个奇数,即 $C_3^3 + C_3^1 C_3^2$ 种组合,然后对这三个数排序($A_3^3$),最后,千位数从剩余的 3 个里面选择一个,即 $C_3^1$,所以答案为 $(C_3^3 + C_3^1 \times C_3^2 ) \times A_3^3 \times C_3^1$。

转载申请

本作品采用 知识共享署名 4.0 国际许可协议 进行许可, 转载时请注明原文链接。您必须给出适当的署名,并标明是否对本文作了修改。

您也可以通过下方按钮直接分享本页面:


发表评论

登录以发表评论

最新评论


Designed & written by Hailiang Zhao.
hliangzhao.cn. Copyright © 2021 - 2022 | 浙ICP备2021026965号-1
Manage