《组合数学》Brualdi著 第二章 排列与组合 阅读笔记

这一章主要讨论4个一般的原理及它们蕴含的某些计数公式。

1. 四个基本计数原理

1.1 加法原理

  • 首先给出划分的概念,如下

    是集合。集合的一个划分是满足下面条件的的子集的集合,即使得的每一个元素恰好只属于这些子集中的一个子集:

    子集称为该划分的部分。集合的对象数目记做,有时也称作为的大小。

  • 加法原理:设集合被划分成两两不相交的部分,则的对象数目可以通过确定它的每一个部分的对象数目并如此相加而得到:

  • 运用加法原理的技巧是把集合划分成少量的易于处理的部分。

加法原理的实用形式:如果有种方法能够从一堆中选出一个物品,又有种方法从另一堆中选出一个物品,那么从两堆中选出一个物品有种方法。

1.2 乘法原理

  • 乘法原理:令是对象的有序对的集合,其中第一个对象来自大小为的一个集合,而对于对象的每个选择,对象种选择。于是,的大小为

  • 在乘法原理中,对象种选择可以随着的选择而变化。唯一的要求是,选择的个数应是相同的,而不必是相同的选择。

乘法原理的实用形式:如果第一项任务有个结果,而不论第一项任务的结果如何,第二项任务都有个结果,那么,这两项任务连续执行就有个结果。

1.3 减法原理

  • 减法原理:令是一个集合,而是包含的更大集合。设中的。那么中的对象数目由下面的法则给出:

在应用减法原理时,集合通常是包含讨论中所有对象的某个自然集合。只有在与计数中对象数目相比更容易计数的对象数目时,使用减法原理才会更有效。

1.4 除法原理

  • 除法原理

    是一个有限的集合,把它划分为个部分使得每一个部分包含的对象的对象数目相同。于是,此划分中的部分的数目为;

1.5 几个经验法则

  • 只要对一个任务的选择个数的答案要用到“依赖于”(或类似的词语),那么就不能用乘法原理。
  • 如果一个任务的执行没有一个固定的顺序,那么可以通过改变任务的执行顺序来更容易的解决。
  • 优先选择约束性最强的选择

2. 集合的排列

2.1 线性排列

  • 是正整数,一个元素集合排列就是个元素中的个元素的有序放置。我们用表示元素集合的排列的数目。如果,则。显然,对每个正整数

  • 对于正整数,有

    证明:在构建元素集合的排列时,我们可以用种方法选择第一项,不论第一项如何选出,都可以用种方法选择第二项,,不论前项如何选出,都可以用种方法选择第项。根据乘法原理,这项可以用种方法选出。

  • 对于非负整数,我们定义如下:

    并约定。所以我们有

2.2 循环排列或圆排列

  • 2.1节的线性排列考虑的是把对象排成一条线,现在考虑把它们排成一个圆,因此重要的是元素间的相对位置而不是自身的位置。怎么样的两个循环排列是相同的呢?明显的,如果其中一个可以通过旋转与另一个重合,即通过一个圆周位移而得倒另一个,那它们就是相同的。
  • 一个元素的循环排列会有个元素间隔,如果在任意一个间隔处把圆剪开,那么可以得到一个线性排列。因此一个元素的循环排列对应于个线性排序。

  • 圆排列数个不同元素集合的循环排列的数目是

    特别的,个元素的循环排列的数目是

    证明:我们使用除法原理完成证明,把线性排列的集合划分成若干部分,当且仅当两个线性排列对应于同一个循环排列时它们同属于一个部分。因此,循环排列的数目就等于划分的部分的数目。由于每一个部分都含有个线性排列,因此,循环排列的数目是

2.3 环排列

  • 循环排列是将元素排列在平面上,现在考虑将元素排列在空间中,串成一个环,我们称之为环排列。这些元素组成的所有不同环排列的数目叫做环排列数

  • 环排列除了做圆周位移,还可以做空间上的翻转。存在这样一些特殊的循环排列,它们在空间上进行翻转后依然保持不变,我们称之为对称循环排列。

  • 因此,一个循环排列对应于一个环排列,一个环排列对应于一个对称循环或者两个非对称循环排列。设集合(不考虑元素是否重复)的所有循环排列数为,其中,对称循环排列的数目为,则的环排列数为

3. 集合的组合

3.1组合数

  • 元素集合,集合的一个组合通常表示的元素的一个无序选择。我们用表示元素集合的组合的数目,显然

    还有

    对于每一个非负整数,下述事实成立:

    特别的,

  • 对于,有

    因此

    证明:令是一个元素集合。的每个排列都恰由下面两个任务的执行结果而产生:

    ​ (1)从中选出个元素。

    ​ (2)以某种顺序摆放选出的个元素。

    根据定义,执行第一个任务的方法数目是,执行第二个任务的方法数则是。根据乘法原理,我们有,因此

  • 推论:对于,有

3.2 帕斯卡公式

  • 对于所有满足的整数,有证明(组合推理证明):设元素集合。指定中的一个元素并把它记作。设是从中除去后得到的集合。把子集的集合划分成两部分。在中放入不包含的所有子集,在中放入包含的所有子集。的大小是,根据加法原理,有

因为中的子集正好是集合个元素的子集,有

中的子集可以通过把元素加到子集中而得到,因此

因此,最后得到

3.3 连加恒等式

  • 对于,有

    且这个共同值等于元素的子集数量。

    证明(双计数法):首先,我们发现的每一个子集是相对于某个子集。因为等于子集数量,所以根据加法原理得

    等于的子集数量。

    我们还可以这样计数:把一个子集的选择分解成项任务:设的元素是,对于每一个元素要做出两种选择:或者进入当前子集;或者不进入当前子集。因此,根据乘法原理,我们有种方法得到的一个子集。

    至此,我们证明了这两个计数相等,从而完成了证明。

4. 多重集合的排列

4.1 无限重复数集合的排列数

  • 我们称含有重复元素的集合为多重集和,对于有种类型元素的多重集,用表示元素出现的次数。这个多重集合可以表示为

  • 是有种不同类型对象的多重集合,每一个元素都有无限重复数。那么排列的数目是

    证明:在构造排列过程中,对于任意的第项都可以选择为个类型中的一个对象。因此,根据乘法原理,项可以有种选择方法。

4.2 有限重复数集合的组合数

  • 是有种不同类型对象的多重集合,且每一种类型的有限重复数分别是。设的大小为。则的排列数目等于证明:给定多重集合,它有种类型对象,比如说,且重复数分别是,对象总数。考虑一共有个位置,我们需要在每个位置上放置的一个对象。首先,我们确定放置的位置,所以必须从个位置的集合中取出个位置的子集,这样做的方法是。下一步,要确定放置的位置。现在还剩下个位置,我们必须从中选出个位置来,这样做的方法数是。以此类推,利用乘法原理,我们发现的排列个数为化简得到

4.3 书上的两个定理

  • 是正整数,并设是正整数且。把对象集合划分到个标有标签的盒子,且第1个盒子含有个对象,第2个对象含有个对象,,第个盒子含有个对象,这样的划分方法数等于

    如果这些盒子没有标签,且,那么划分数等于

    证明:第一个公式的证明同4.2节的证明一样,这里不做说明。考虑第二个公式,对于把这些对象分配到个没有标签的盒子里的每一种方法,都有种方法给这些标签标上标签。因此,根据除法原理,我们可以得到划分数为

  • 种颜色共个车,第一种颜色有个,第二种颜色有个,,第种颜色有个。把这些车放置在一个的棋盘上使得车之间不能相互攻击(不同行且不同列)的方法数等于

    证明:我们给棋盘上每个方格赋予一个坐标对,整数分别表明方格所处的行和列,并且都是1和之间的整数。因为车之间不能相互攻击,所以每一列一定只存在一个车。因此,它们的坐标可表示为

    但是,每一列上也必须存在一个车。因此必须是的一个排列。因此,在一个的棋盘上放置个非攻击性车的集合与的排列之间存在一一对应关系,方法数为

    对于每一个排列,需要确定放置在上面的车子的颜色。因为颜色的排列数为

    所以,根据乘法原理,得到最终的方法数为

5. 多重集合的组合数

5.1 无限重复数集合的组合数

  • 是有种类型对象的多重集合,每种元素均具有无限的重复数。那么组合的个数等于证明1:设种类型的对象是,使得的任意组合均呈的形式,其中皆为非负整数,并且。反过来,每个满足的非负整数序列对应于的一个组合。因此,组合的个数等于方程的解的个数,其中皆为非负整数。下面我们证明,这些解的个数等于有两种不同类型对象且有个对象的多重集合的排列的个数。给定的一个排列,分成了组。设第一个的左边有,在第一个和第二个之间有个,在最后一个的右边有。于是,是满足的非负整数解。反之,给定非负整数满足,我们可以按上述步骤反推并构造的一个排列。于是,多重集合组合的个数等于多重集合的排列的个数,即证明2:考虑把种类型对象分别与整数形成一一对应,则组合可表示为,其中,并且因为考虑的是组合数,我们规定按升序排序。现在做映射,则一一对应。并且既使有重复,也不会重复。因为,于是,组合数等于组合数

6. 课后习题

第29题

是重复数为的多重集,其中。令。证明的循环排列数等于

证明:因为确定为1,不妨总将它对应的对象的位置视为起点位置。现在问题转换为求剩余其他元素的线性排列数,明显的,剩余其他元素的线性排列数为

题目得证。

第39题

有20根完全相同的棍列成一行,占据20个不同的位置:

要从中选出6根。

一个一般性的转换:把选出的棍子按原来的顺序排成,设为非负整数,设的左边有个棍子 ,在之间有个个 棍子 ,,在最后的的右边有个棍子。于是,是满足的非负整数解。棍子在不同条件下的选择方法数就等于对方程变量限定范围时的解的个数。

第48题

证明和至多的排列的数目等于

证明:假设一共有个位置。从中选出个位置,规定前个位置上,而最后一个位置不做处理,并且这个位置之前所有空余位置(至多为个)都用来放置,每一次的位置选择对应于一个题目要求的排列。反之,给定一个排列,可以依次把各个元素从左至右放好,所有的位置和末尾的后一个位置就是我们需要选择的位置。因此,每一个排列与一个元素的组合是一一对应的,而元素的组合数为

题目证明完毕。

  • 如果将所有的排列按出现的个数来做划分,那么我们可以得到个部分。一个含有的部分的大小为或者,根据加法原理,我们可以得到下面的组合恒等式

第49题

证明最多和 最多的排列数等于

证明:将所有的排列按出现的次数进行划分,得到个部分。则第个部分是和最多的排列的集合,大小为。根据加法原理,可以得到最多和 最多的排列数等于

第53题

在集合的排列和塔状集间建立一一对应,其中

:给定集合的一个排列。设表示,由此可以得到一个塔状集,其中

反之给定一个塔状集,其中。从开始依次取出当前集合比前一个集合多的一个数,并排成一列。这样形成的序列恰好是集合的一个排列。

第54题

确定形如的塔数。

:考虑为中的每个数设立一个2位2进制串,规定表示这个数既不在中,也不在中;表示这个数不在中,在中;表示这个数既在中,也在中。每个数的状态码只能是3个中的一个。因此,塔数为个。

------------- 本文结束 感谢您的阅读 -------------

本文标题:《组合数学》Brualdi著 第二章 排列与组合 阅读笔记

文章作者:Perry

发布时间:2019年09月06日 - 02:01

最后更新:2019年10月05日 - 23:13

原始链接:https://perry96.com/archives/d2014c21.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%