[关闭]
@ArrowLLL 2017-04-06T10:56:45.000000Z 字数 2680 阅读 1782

“排列与组合”笔记

数学 组合数学


主页地址 :月光森林


1. 基本计数原理

设集合S的 一个划分 即为S的子集的集合 ,使得S的每一个元素恰好是这些子集之一的元素:

子集称为该划分的部分。

集合的元素个数表示为, 又是称之为的大小。

加法原理

设集合S划分为部分 。则S的元素个数可以通过找出它的每一个划分的个数来确定,我们把这些数相加,得到:

如果集合可以重叠,那么要使用一个更深刻的原理(容斥原理)来计数S中的元素个数。

用选择的术语叙述加法原理的形式为 :

如果有p种方法能够从一堆中选择一个物体,而有q种方法能从另一堆中选择一个物体,那么从这两堆中选择一个物体的方法共有p+q种。

这种形式的加法原理可以很容易推广到多堆。

乘法原理

令S是元素的序偶(a, b)的集合,其中一个元素a来自大小为p的一个集合,而对a的每个选择,元素b存在着q种选择。于是,S的大小为p × q :

乘法原理的第二种形式:

如果一项任务有p项结果,而不论第一项任务的结果如何,第二项任务都有q个结果,那么,这两个任务连续执行就有p×q个结果。*

减法原理

令A是一个集合,而U是包含A的更大的集合。设

是A在U中的补。那么A中的元素个数|A|由下列法则给出:

在应用减法原理中,集合U通常是某个自然的集合,包括讨论中所有元素的(即所谓的泛集)。使用减法原理只有当对U中的元素计数和对中元素计数比对A中元素计数容易时才有意义。

除法原理

令S是一个有限集,它以下述方式被划分成k部分,每一部分包含相同数目的元素。此时,划分中的部分的数目由下述公式给出:

于是,如果我们知道S中元素个数以及各部分所含元素的相同的个数,则可以确定部分的数目。

集合的排列

令r是正整数。我们把n个元素的集合S的一个r-排列理解为n个元素中的r个元素的有序摆放。

我们用 表示n个元素集合的r-排列的数目。如果 ,则 。显然,对每一个正整数 , 有 。一个n-元素集合S的一个n-排列被更简单地称为S的一个排列或n个元素的一个排列。于是,集合S的一个排列就是以某种顺序列出S的所有元素。

定理 : 对于正整数 ,有

定义(读作n的阶乘)为 。并约定 。于是我们可以写成:

对于,定义为 1,正好与时的公式一致。n个元素的排列数为

我们把元素的排列看成一条线,称之为线性排列,或线排列。如果两个排列的元素相同而且排列次序也相同,那么就是两个相同的排列,只能算作一种排列。

从集合的n个不同元素中,取出r个元素按照某种次序(如逆时针)排成一个圆圈,称这样的排列为圆排列,或循环排列。

定理 : n个元素的集合的循环r-排列的个数由


给出。特别的,n个元素的循环排列的个数是

集合的组合

令r为非负整数。我们把n个元素的集合S的r-组合理解为从S的n个元素中对r个元素的无序选择。换句话说,S的一个r-组合是S的一个子集,该子集由S的n个元素中的r个组成,即S的一个r-元素子集。

如果用表示n-元素集的r-组合的个数。特别地,

定理 : 对于 , 有
因此

多重集的排列

如果S是一个多重集,那么S的一个r-排列是S的r个元素的一个有序排放。如果S的元素个数是n个(包括重复元素),那么S的n-排列也将称为S的排列。

定理 : 令S是一个多重集,它有K个不同类型的元素,每一个元素都有无限重复次数。那么,S的r-排列的个数为

如果S的k个不同种类是元素的重复数均至少为r,那么定理还是成立的。

定理 : 令S是一个多重集,有K个不同类型的元素。各元素的重数分别是。设S的大小为。 则S的排列数等于

定理 : 令n是一个正整数,并令是正整数且 。将n个元素的集合划分成k个被做标签的盒子的方式数为

其中盒1含有个元素,盒2含有个元素,... , 盒k含有个元素。

如果这些盒子不被做标签,那么划分的个数是:

多重集的组合

如果S是一个多重集,那么S的r-组合是S中的r个元素的一个无序选择。因此,S的一个r-组合本身就是就是一个多重集 —— S的一个子多重集

定理 : 令S为具有k种类型元素的一个多重集,每种元素具有无限的重复数。则S的r-组合的个数等于

可以证明,S的r-组合的个数等于方程 的解的个数,其中这些解都是非负整数。而这些解的个数等于两种不同类型元素的多重集 的排列的个数形同。

如果S中的K种元素的重复数都不小于r,定理仍然成立。

假设在r-组合中,


以上です~

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注