排列与组合分析和总结.docx

排列与组合

排列与组合的知识是组合计数的基础，今天开始，我们将系统地介绍组合计数理论。

组合计数所要解决的中心问题是求满足某些条件的方案总数。

比如:

(l)在全系100 名学生中选出3 名学生去参加

ACM比赛，有多少种方案?

一棵有n个结点的二叉树共有多少种不同构的形式?

将8个皇后放在一张棋盘上使得没有两个处于互相攻击的位置，共有多少种放置方法?

排列与组合的知识就是解答诸如这类问题的。组合计数理论最初的应用是概率的计算。Laplace(1749-1827)首先定义了概率的概念。他

说，如果一个确定的集合中总共有T个对象，并且

有一个具有F个对象的有利子集。那么，随机地从这个全集中选取出有利对象的概率是F/T。

为了从这个定义计算概率，我们必须能够计算出有利对象的数目与可能情况的总数。这就涉及到组合计数问题。

基本概念

在学习排列与组合时我们首先引入两个非常直

观的原理。

加法原理若事件X能以x种方式发生，另一个不同的事件Y能以y种不同的方式发生，则事件X或事件Y能以(x+y)种方式发生。

例1全系共三个班级，这三个班级准备参加

ACM竞赛的学生人数分别为3、4、5，则全系准备参加ACM竟赛的人数为3+4+5=12。

乘法原理若事件X能以x种方式发生，另一个不同的事件Y能以y种不同的方式发生，则事件X和事件Y能以xy种方式发生。

例2求小于10亿且包含数字l的正整数的个

数。

解首先计算不包含数字1的数的个数，从0，2，

3，4，5，6，7，8，9中寻找9个符号的字符串。第一个数字有9种选择，第二个数字有9种选择，等等。

然后，根据乘法原理共有 个这

样的数，其中包括000000000。如果我们从1000000000中减去这样的数，得到答案为

612579511。

定义1从n个不同的元素中，有次序地选取r

个元素，称为从n中取r个的排列，其排列数记为

到P(n,r)。当r=n时，称此排列为全排列。

比如从A,B,C,D四个英文字母中有次序地选取出两个字母，则可以得到如下的12种情况:

AB AC AD BA BC BD CACB CD DA DB DC

我们记为P(4,2)=12。这就是从4个元素中取出

个元素的例子。

定理3.1

证明：在n个不同的元素中，有次序地选取出r个元素，可以采取以下方式：首先取一个元素，有n种选择；然后取第二个元素，有n-1个种选择；??；最后取第r 个元素，有(n-r+1)种选择。由乘法原理得

例3从n个不同元素中选取出r个元素围成一个圆，求选取的方案总数。

解:从n个不同元素中选取出r个元素的排列数为

。设自 为一个排列。将其加以变

换

一共有r个排列。但是这r个排列对应同一个圆排列，也就是说每一个圆排列对应着r个线排列，所以从n个不同元素中选取出r个元素组成的圆排列总数为

定义2从n个不同元素中，选取r个元素而不考虑其次序时，称为从n个中取出r个的组合，其组合数记为C(n,r)，或

比如从{A,B,C,D}中选取出2个元素的组合，则有如下情况:

{A,B}{A,C}{A，D}{B,C}{B,D}{C,D}

我们记作C(4,2)=6或

对于一个从n个元素中选取出r个元素的每一个组合，我们都对这r个元素进行全排列，便得到了一个从n个元素中选取r个元素的排列。

所以可以得到下面的定理:

定理2

例4在如图1所示的棋盘中，若从左下角走到右上角，并且规定只能向右走或者向上走，问共有多少种方案?

图1 一个4x3的棋盘

解：我们看到图1是一个4x3的棋盘。如果从左下角向右走4步，然后再向上走3步就可以到达右上角。并且发现:如果从左下角开始，无论怎么走，只要向右走4步和向上走3步都可以到达右上角。所以我们用0代表向右走一步，用1代表向上走一步。那么从左下角到右上角的一种可能的走法就唯一地对应了一个由4个0和3个1组成的7位01

字符串。反之，给定一个由4个0和3个1组成的

7位01字符串。我们规定0代表向右走，1代表向上走，则这个01字符串又惟一地对应着一种可能的走法。这样便建立了一种一一对应关系。所以我们所求的方案数就是由4个0和3个1组成的7位

01字符串的个数，即

有一些数学问题可以使用不同的方法来得到答案。在组合数学中这些问题是大量存在的。不同的人