第一章 什么是组合数学

第一章什么是组合数学

组合学问题在生活中随处可见。例如，计算下列赛制下总的比赛次数：n个球队参赛，每队只和其他队比赛一次。创建幻方。在纸上画一个网络。用铅笔沿着网络的线路走，在笔不离开纸面且不重复线路的条件下，笔画出网络因。在玩扑克牌游戏中，计算满堂红牌的手数，以确定出现一手满堂红牌的几率。所有这些都是组合学问题。正如人们想到的．组合数学的历史渊源扎根于数学娱乐和游戏之中。过去研究过的许多问题，不论出于消遣还是出于对其美学的考虑，如今在纯科学和应用科学中都具有高度的重要性。今天，组合数学是数学的一门重要分支，而且它的影响还在继续扩大。组合数学自60年代以来急速发展的部分原因就在于计算机在我们的社会中所发挥的重要影响，而且这种影响还在继续发挥。由于运算速度的持续增加，计算机已经能够解决大型问题，这在以前是不可能做到的。然而计算机不能独立运行，它需要编程来控制。这些程序的基础往往是求解问题的组合学算法，对于这些算法，运行时间效率和存储需求分析需要更多的组合学思想。

组合数学近期发展的另一个原因是它对于那些过去很少与数学正式接触的学科的适用性。由此我们发现，组合数学的思想和技巧不仅正在用于数学应用的传统自然科学领城，而且也用于社会科学、生物科学、信息论等领域。此外，组合数学和组合学思想在许多数学分支中已经变得越来越重要。

组合数学涉及到将一个集合的物体排列成满足一些指定规则的格式。如下两类一般性问题反复出现：

排列的存在性如果有人想要排列—个集合的成员使得某些条件得以满

足，那么这样一种排列是否可行根本就不是显而易见的。这是最根本的问题。如果这种排列不总是可能的，那么我们要问，这种排列在什么样的(必要和充分)条件下能够实现？

排列的计数和分类如果一个指定的排列是可能的，那么就会存在多种

方法去实现它。此时，人们就可以计数并将它们分类。

虽然对任何组合问题都可以考虑其存在性和计数问题，但在实践中常常发生的却是：如果存在性问题需要广泛地研究，那么计数问题则是非常困难的。然而，如果指定的排列问题的存在性容易解决，那么计算实现该排列的方法的数目则是可能的。在例外的情形下(即当它们的数目较小时)，这些排列可以被列出来，理解列出所有的排列与确定它们的数目之间的区别很重要。一旦这些排列被列出，它们就可通过与整数集{1，2，3，…，n}之间建立一一对应而被数出，其中n 是某个整数。我们计数的方法就是：1，2，3…，n。但是，我们主要关心的是事先不列出指定类型的排列而确定它们的数目的方法。当然，这些排列的总数也许很大以至于不可能把它们部列出来，概括地说，许多组合学问题常呈现下列形式：“能否排列…?”

“存在一个……吗?”

“能用多少方法—…?”

“计算……的数目。”

与上述问题同时出现的另外两种组合学问题是：

研究一个巳知的排列 当人们建立起满足某些指定条件的一个排列(可能不容易)以后，可能要考察这个排列的性质和结构，这样的结构可能会涉及到分类问题，也许还涉及到一些潜在的应用，它还可能牵扯到下面的问题。

构造一个最优的排列 如果有可能存在多于一个的排列，人们也许想要确定满足某些优化准则的一个排列，即找出某种规定意义下的“最好的”或“最优的”的排列。

因此，组合数学可以一般地描述为：组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科。

组合数学中解决问题的主要工具之一为数学归纳法。归纳是一个强有力的过程，在组合数学中尤其是如此。用数学归纳法证明一个强结果常常比证明一个弱结果更容易。虽然在归纳阶段验证多一些是必要的，但归纳假设却是更强的一步。数学归纳法的部分技巧就是找到假设的正确的平衡来进行归纳。

然而．一般说来，许多组合数学问题的解决需要某些特别的论证。人们不能总是退到已知的结果或公理那里。人们必须研究情况，挖掘洞察力，并运用他们灵活的谋略来解决问题，这里并不是说不存在可以使用的一般原则和方法；比如：容斥原理、所谓的钨巢原理、递归关系和生成函数的方法等就是一般的原则和方法，我们将在后面各章讨论这些原则和方法。但是，洞察到这些原则和方法能够使用以及如何使用常常需要智慧。这样的经验在解决组合问题时是非常重要的。也就是说，用组合数学解决问题一般说来和用数学解决问题一样，你解决的问题越多，那么能够解决下一个问题的可能性就越大。

为了使前面的讨论更加具体，现在让我们转到组合问题的几个实例。这些例子从相对简单(但需要解题的灵感)的问题直到其解曾是组合数学中主要成就的那样一些问题。有些问题在后面的章节中还要更详细地讨论。

例1：棋盘的完美覆盖

考虑一张普通的国际象棋棋盘，它被分成88?(8行8列)的64个正方形。设有形状一样的多米诺牌，每张牌恰好覆盖棋盘上相邻的两个方格。那么，是否能够把32张多米诺牌摆放到棋盘上，使得任何两张多米诺牌均不重叠，每张多米诺牌覆盖两个方格，并且棋盘上所有的方格都被覆盖住？

我们把这样一种排列称为棋盘被多米诺牌的完美覆盖。

这是一个简单的排列问题，人们能够很快构造许多不同的完美覆盖。但是，计算不同的完美覆盖的总数就不足一件容易的事情，不过，这还是有可能做到的。这个数由Fischer 在1961年发现，它是12988816＝2)901(2?。这种普通的国际象棋棋盘可以用排成m 行n 列的mn 个方格的一般棋盘代替。此时，这种棋盘的完美覆盖就未必存在了。比如33?的棋盘就确实不存企完美覆盖，那么，对于什么样的m 和n 存在完美覆盖呢? 不难看出，当且仅当m 和n 中至少有一个是偶数时。n m ?棋盘存在完美覆盖。或者说，当且仅当棋盘的方格数为偶数时．n m ?棋盘存在完美覆盖。Fischer 已经得出涉及到三角函数的用来计算n m ?棋盘的不同完美覆盖数的更一般公式。

再来考查8x 8的国际象棋棋盘并用一把剪刀剪掉棋盘一副对角上的两个方格，总共剩下62个方格。那么，是否能够排列31张多米诺牌来得出对这副被剪过的棋盘的完美覆盖?

虽然这副被剪过的棋盘与8x 8棋盘非常接近，且后者有一干二百多万个完美覆盖，但是，这副被剪过的棋盘却没有完美覆盖。其证明是简单而巧妙的组合推型的一个实例。

在一副普通的8x 8棋盘上交替地将方格涂成黑色和白色，则其中32个方格是白色的。而另外32个方格是黑色的。如果我们剪掉棋盘一副对角上的两个方格，那么我们就剪除了同样颜色的两个方格，比如两个白色方格。这就变成了32个黑方格和30个白方格、但是每张多米诺牌需要覆盖一个黑方格和一个白方格，于是，31张不重叠的多米诺牌则盖住31个白方格和31个黑方格。因此，这副被剪过的棋盘没有完美覆盖，上述推理可总结为：

313230

m?棋盘上的方格交替徐成黑色和自色，切除一些方格，更一般地．可以将n

得到一块切过的棋盘什么时候能有一个完美覆盖？

为使完美覆盖存在，这块被切过的棋盘必须又有相等的黑方格数和白方格数但是，这个条件却不是充分的，图l-1中的例子指出了这一点。

图l-1具有相等的黑方格数和白方格数

因此，我们要问：一块被切过的棋盘县有完美覆盖的必要和充分条件是什么?这个问题可以应用二分图中的匹配理论得到完全的解决力案。这个问题存在一个实际的公式表示。但它是以指派申请人去做他们有资格胜的上作的术语给出的。（可参看布鲁迪 Brualdi著，冯舜玺，罗平等译，《组合数学》，机械工业出版社，第九章）。

m?棋盘被多米诺牌完美覆盖的问题，还存在另外一种一般化的方法，对于n

设b是一个正整数。我们用由b个1Xl的方格并排连接成的1xb的方格条来代替多米诺牌，我们称这些方格条为b-牌(bomino)，因此，一张b牌可以盖住一行上或是一列上b个连续的方格。图1-2画出了和一张5-牌。一张2-牌就是上面提到的普通的多米诺牌，1-牌叫做单牌。

m x n棋盘被b-脾的一个完美覆盖是b-牌在棋盘上的这样一个排列、使得盘上没有两张牌重叠，每一条b-牌盖住盘上的b个方格，并且盘上的所有方格都被盖住。那么．何时m x n棋盘将具有一个b-牌的完美覆盖?

既然盘上的每个方格恰被一条5-牌覆盖，于是，要想使覆盖成为完全覆盖，

b就必须是mn的一个因子。的确，完美覆盖存在的一个充分条件就是：b是m 的一个因子或b是n的一个因子。因为，如果b是m的一个因子，我们就可对n 列的每一列用n/b个b-牌铺盖并进而完成对m x n棋盘的完美覆盖，而如果b 是n的一个因子，我们就可对m行的每一行用m/b个b-牌铺盖并进而完成对m x n棋盘的完美覆盖。这样的充分条件是否也是完美覆盖存在的必要条件呢?

现在设b是素数且存在m x n棋盘被b-牌的完美覆盖。于是，b是mn的因子。且由素数其本性质可知b或者是m的因子，或者是n的因子。我们断言，至少在b是素数的情况下，一块m x n棋盘被-牌完美覆盖当且仅当b是m的因子，或者b是n的因子。

当b不是素数时，我们要用不同的方式讨论。设我们有对m x n棋盘的b-牌完美覆盖。

此时我们证明，m和n分别被b除所得余数至少有一个是零。设用b除m和n分别得到商p和q，以及余数r和s。

bq

s

n<

s

+

,

=0

≤

+

r

r

b

bp

m<

=0

≤

,；b

如果r＝o，则b是m的因子。如果s＝o，则b是n的因子。我们不妨设s

r≤，因为如果必要，我们可将棋盘的行列互换。下面我们要证r＝o。现在我们把在讨论用多米诺牌(b＝2)覆盖国际象棋盘时将棋盘方格交替涂成黑白色的情况推广成涂成b种颜色。把b种颜色标成1，2，…,b。我们用图1-3所示的方式将bxb棋盘涂色，并用这种方法对m＝10,n＝11，b＝4的情况以图1-4所示的

方式延伸到m x n棋盘的涂色。

完美覆盖中的每张b牌盖住b个方块且每个方块各占一种颜色。因些，盘上每

种颜色的方块数目必然是相同的。我们把棋盘分为三部分：上面pb行n列部分，左下方r行qb列部分。以及右下方r行s列部分。上面部分的每一列中各种颜色均出现p次，故各种颜色在盘上总共出现np次。盘的左下部分每行各种颜色均出现q次，故各种颜色在盘上总共出现rq次。既然每种颜色在整个棋盘上出现的次数都是相同的，那么，棋盘的右下方r行s列部分每种颜色出现的次数也必然是相同的。

右下方r xs部分中的颜色1(从而每种颜色)究竟出现多少次?由于已经假设r≤，我们的涂色特点使得颜色1在石下方r xs部分的每一行出现一次从而在s

这个r xs部分出现r次。现在让我们计算这r x s部分中方块的数日。一方面，它有rs个方块；另一方面，b种颜色中的每一种颜色有r个方块从而共有rb个方块。于是，rs＝rb。如果0

r，则两边消去r得到s＝b，这与s

≠

此，正如所料，r＝o。我们总结如下：

一张m行n列棋盘有一个b-牌的完美覆盖，当互仅当b是m的一个因子或者b是n的一个因子。

上述结论的一个惊人的改述如下：

如果完美覆盖中所有的b-牌都是水平摆放或者所有的b-牌都是垂直摆放，则称其为平凡的。于是，一张m行n列棋盘有一个b-牌完美覆盖，当且仅当它是一个平凡的完美覆盖。应当指出，这并不意味着只有完美覆盖才是平凡覆盖。但它确实意味着，如果一个完美覆盖是可能的，那么一个平凡的完美覆盖也是可能的。

例2：切割立方体

考虑一个边长3英尺的立方体木块。我们希望把它切割成27个边长1英尺的小立方体。完成这项工作所需切割的最小次数是多少?

一种方法是依序切割6次，每个方向上切割2次，并在切割时保持该立方体形状不变。如图1-5所示。可是，如果在每次切割后重新排放所切得的各块，则是否能用更少的切割次数完成这项工作呢，在图1-5中也给出了这样一个例子，其中的第二刀比在第一刀后不重新排放所切得的切块要多。因此要切的木头块数以及木头块的排放方式数随着切割的进行而增加，这似乎是一个分析起来困难的问题。

让我们换一种方式来看一看这个问题。这27个小立方体除去中间的一块以外其余各块都至少有一面是原来的大立方体表面的一部分。中间的这个立方体的每个侧面都是通过切割形成的。既然它有6个侧面，那就必须切割6次才能形成。因此，至少需要6次切割，而每次重新排放再切不会再少于6次。有精力的学生可以尝试一些不同的切割方式，看一看哪些方式只用6次能够切成27个小立方体。

例3：幻方

幻方是最古老和最流行的数学游戏之一。一个n 阶幻方是由整数1，2，3，…,n 2按下述方式组成的n x n 方阵；该方阵每行上的整数的和、每列上的整数的和以及两每条对角线上的整数的和都等于向一个数s ，这个整数s 就叫做该幻方的幻和。如何确定那些能够组成n 阶幻方的n 的值，同时找出一般的构造方法？

下面是3阶和4阶幻方的两个例子：

这两个幻方的幻和分别是15和34。在中世纪时期曾存在与幻方相关的玄想；人们将幻方佩带身上用来辟邪，本杰明〃富兰亮林就是一个幻方迷，他的论文中包含有很多有趣的例子。

一个n 阶幻方中的所有整数的和为

2)1(321222

+=++++n n n 这里用到了算术级数的求和公式(见5.1节)。由于一个n 阶幻方共有n 行，

每一行都有一个幻和s ，因此我们得到关系=ns 2

)1(22+n n 。于是，任意两个n 阶幻方都有相同的幻和，即2

)1(2+=n n s 。 其组合问题就是确定那些能够组成n 阶幻方的n 的值，同时找出一般的构造方法。不难验证，不可能存在2阶幻方(其幻和应该是5)。但是，对于所有其他的n ，n 阶幻方能够构造出来，存在着许多构造幻方的特殊方法。这里，我们介绍De la loubere 在17世纪发现的一种构造n 阶幻方的方法，其中n 是奇数，首先将1放在最上一行的中间。其后的整数沿着自左下至右上的这条对角线按照自然顺序放置，但同时须作如下修正：

1)在到达顶行时，下一个整数要放在底行，所放位置就是把底行当作顶行上边一行时该数应该放置的位置。

2)当到达最右边的一列时，下一个整数要放在最左边的一列上，所放位置就

是把最左边的一列当作最右边那列的右边的列时该数应该放置的位置。

3)当要放的位置上已经填好了整数，或上一个整数已经放在了幻方的右上角时，则当前要摆放的整数将放在紧挨上述位置的下方。

下面给出一个根据该方法所构造的5阶幻方:

幻方在3维情形下的推广也已经被研究。n 阶幻方体是以下述方式由整数3,2,1n 构造成的一个n n n ??的立方体阵列，其在下述每一条直线上的n 个元素和s 都是相同的：

1)平行于立方体一条边的直线。

2)每个截面上的两条对角线。

3)四条空间对角线。

数s 叫做幻方体的幻和且其值为2/)(4n n +。不难证明，不存在2阶幻方体，我们把它留作练习。可以证明，也不存在3阶幻方体。

设存在3阶幻方体，该幻方体的幻和就应42。考虑其任一个3x3横截面

其上元素已如所示。由于该正方体是幻方，故

42

424242

42

=++=++=++=++=++f e d c b a d y c e y b f y a

将前三个方程相加并减去后两个方程，我们得到3y ＝42，从而y ＝14。但是，y 是位于横截面的中心的，于是，就有7个横截面，它们的中心位置不同但又都必须是y 值14。可是，y 值14只能占据一个位置。因此我们断言；不存在3阶幻方体。证明不存在4阶幻方体要困难得多？一个8阶的幻方体在Gardner 的一篇文章中给出。

本书将不对幻方作近一步研究。

例4：四色问题

考虑一张平面地图或在一个球面上的地图，地图上的国家都是连通的区域。为了能够很快地区分出国家来，需要对这些国家着色，以使得具有共同边界的国家被涂成不同的颜色（角点处不算作共同边界）。能够保证如此着色每一张地图

所需的最少的颜色数是多少?

直到不久前，这还曾是数学中著名的尚未解决的问题之一。由于该问题叙述起来简单，理解起来又容易，因此它吸引着众多的非专业人员。除去著名的三等分已知角问题外，四色问题可能比任何其他问题都会激发更多的业余数学爱好者的兴趣。它大约在1850年由Franci5 Guthrie首先提出，那时他还仅是名研究生。四色问题也刺激了大量的数学研究。一些地图需要4种颜色。图1-7中的地图就是一个例子。既然这个地图的四个国家中每两国部有一条共同的边界，那么很清楚，对该地图着色必须用4种颜色。

1890年HeawMdu证明了用5种颜色对任何地图着色都是足够的。证明下面的问题也不是非常困难的，即：不可能有这样的平面地图，图上有5个国家，其中的每两个国家都有一条共同的边界。这样的地图假如存在。那就需要5种颜色。但是，没有5个国家其中每两国都有一条共同边界并不意味着四种颜色就足够了。也许某张平面地图因为其他一些更加微妙的原因而需要5种颜色。

在1976年．AppeI与Haken宣称他们已经证明了任意平面地图都能够用4种颜色着色。他们的证明需要计算机计算1200小时，100亿个分离的逻辑判定！1989年， N．Robertson、D．P．5anders等简化了该证明，不过简化了的证明仍然需要大量的计算机检验。

例5：36军官问题

设有分别来自6个军团共有6种不问军衔的36名军官，他们能否排成6x 6(6行6列)的编队使得每行每列都有各种军衔的军官1名，并且每行和每列上的不同军衔的6名军官还分别来自不同的军团？

这个问题于18世纪由瑞士数学家欧拉(L．Euler)作为一个数学游戏提出，它对统计学产生重要的影响，特别是在实验设计方面。一个军官可由一个序偶(i，j)来表示，其中i表示该军官的军衔(i＝1，2，…，6)，而j表示他所在的军团(j＝1，2，…，6)。于是，这个问题是问：

36个序偶(i，j) (i＝1，2,…，6；j＝1，2，…，6)能否排成6x 6阵列，使得在每行和每列，这6个整数1，2，…，6都能以某种顺序出现在序偶第一个元素的位置上，并以某种顺序出现在序偶第二个元素的位置上？

这样得序列可以分裂成两个6×6的阵列，一个对应序偶的第一个位置(军衔

阵列)，而另一个则对应序偶的第二个位置(军团阵列)。因此，该问题又可以叙述成：

是否存在这祥的两个6x 6矩阵，其元素取自1，2，…，6，使得

1)整数1，2，…，6以某种顺序出现在矩阵的每一行和每一列，并且

2) 当这两个矩阵并置时，所有的36个序偶(i，j) （I＝1，2，…，6，j＝1，2，…，6）全部出现?

为把上述问题具体化，我们设有来自3个军团共有3种军衔的9名军官。此时问题的一个解为

上述的军衔矩阵和军团矩阵是所谓的3阶拉丁方的例子；在矩阵每行上和每列上，整数1，2和3中的每一个都出现一次。下述两个矩阵是2阶和4阶拉丁方：

式(1-3)中的两个3阶拉丁方叫做是正交的, 因为此时存在由i＝1，2,3及j＝1，2，3生成的全部9个可能的序偶(i，j)。于是，我们又可将欧拉问题改述为：

是否存在两个正交的6阶拉丁方?

欧拉考察了更一般的n阶正交拉丁方的问题。容易看出，由于除了上述的2阶拉丁方外，就只有拉丁方

了，而且这两个拉丁方不是正交的，因此也就不存在2阶正交拉丁方。欧拉指出如何构造一对n阶正交拉丁方，而无论n是奇数还是4的倍数。注意，这并不包括n＝6。在经过多次尝试的基础上，他断言不存在6阶正交拉丁方对，但没有证明。他猜想，不存在像6，10，14，18，…，4k+2，…这样阶数的拉丁方对。通过穷举法，Tarry在1910年证明了欧拉猜想，对于n＝6是成立的。大约在1960年前后，三位数理统计学家Bose、Parker和shrikhande成功地证明了欧拉猜想对于所有的n＞6都是不成立的。就是说，他们指出了对于每一个n＝4k+2，k＝2，3，4,…，如何构造一对n阶正交拉丁方.这是一个重要的成就，它使得欧拉

猜想可以休矣。后面，我们将探讨如何使用叫做域的由有限个数组成的数系来构造正交拉丁方，以及它们是怎样被应用到实验设计中去的。

例6：最短路径问题

考虑一个由道路和路口组成的系统。一人想从一个路口4行进到另一个路口B 。一般说来，从路口A 到B 存在许多通路。现在的问题是要确定一条通路，使沿此通路从A 到B 的距离尽可能小-一条最短路径，这是组合优化问题的一个例子。解决这个问题的一种可能的方法是以某种系统的方式列出从A 到B 所有可能的路径(当然，沿着任何一条道路行进都没有必要多于一次，因此，从A 到B 的路径只存在有限多条)，计算沿每条路径的距离，然后选择一条最短的路径。但是，这并不是一条非常有效的计算程式。对于大的系统，工作量可能太大，以至在合理的时间范围内得不到问题的解。因此，现在需要的是这样一种确定最短路径的算法，它所需要的工作量随着系统规模的增加而不会增加得太快。更精确地说，算法的工作量应该不超出问题规模的一个多项式函数(相反的情况，比如指数函数)。我们将在后面描述这样的算法。这种算法实际上将找出从A 到系统的每一个其他路口的最短路径。

找出两个路口间的最短路径问题可以抽象地叙述如下。令X 为称做项点的对象的有限集(顶点对应交叉路口以及道路的终点)，而今E 为顶点的无序对并称之为边(边对应道路)的集合。于是，某些顶点对被边连结起来，而其他的顶点之间没有边连结。有序二元组(X ．E)叫做图。图中联结顶点x 和y 的途径(walk)即顶点的这样的序列，其中的第一个顶点是x ，最后一个顶点是y ，而其中的任意两个相邻顶点由一条边联结。每条边对应一个非负实数（该边的长）。联结途径的相邻顶点的边的长的和称做该途径的长。给定两个顶点x 和y ，最短路径问题就是找出从x 到y 的一条具有最小长的途径。图1-8所描述的图中有6个顶点和10条边。标在边上的数表示相应的边的长。联接x 和y 的一条途径是x ，a ，b ，d ，y ，其长为4。另一条途径是x 、b ，d ，y ，其长为3。不难看出，后者给出了联结x 和y 的最短路径。 x

a d c y

b 1221

2

1

11

1

1

图1-8 图是组合学中已经研究而且还将继续广泛研究的离散结构的一个例子。图的概念的普遍性使得它在下述不同的领域取得广泛的应用，如心理学、社会学、化学、遗传学以及通信科学。因此，可以让一个图的顶点对应人，如果两人互不信任那么就用一条边将它们联结起来；也可让顶点代表原子，边则表示原子间的化学键。你也许能够设想其他的方法使图模拟一些现象。图的某些重要的概念和性质可以查看图论相关书籍。

例7：Nim 取子游戏

我们通过追溯娱乐数学中的组合数学起源来结束本章，考查古代的Nim 取子游戏，游戏的解依赖于奇偶性,它是解决组合数学概念的一个重要问题：当我们考察棋盘的完美覆盖时指出，为使一张棋盘能有一个用多米诺牌产生的完美覆盖，这张棋盘就必须要有偶数个方格,此时我们用到了一个简单的奇偶性结论。

Nim 取子游戏是由两个人面对若干堆硬币(或石子，或豆粒，或…)迚行的游戏。设有1≥k 堆硬币，各堆分别含有k n n n ,,,21 枚硬币。游戏的目的就是选择最后剩下的硬币。游戏法则如下：

1)游戏人交替迚行游戏(我们称第一个取子者为游戏人Ⅰ，称第二个为游戏人Ⅱ)。

2)当轮到每个游戏人取子时，选择这些硬币堆中的一堆，并从所选的堆中取走至少一枚硬币(游戏人可以取走他所选择的堆中的全部硬币，于是留下一个空堆)。当所有的堆都变成空堆时，游戏结束。最后取子(即能够取走最后一堆中剩下的所有硬币)的游戏人，视为游戏的得胜者。

这个游戏中的变量是堆数k 和各推的硬币数k n n n ,,,21 。对应的组合问题是，确定游戏人Ⅰ获胜还是游戏人Ⅱ获胜以及游戏人应该如何取子才能保证获胜(获胜策略)。

为了进一步理解Nim 取子游戏，我们考查某些特殊情况。如果游戏开始时只有一堆硬币，游戏人Ⅰ则通过取走所有的硬币而获胜。现在设有2堆且它们分别含有21,n n 枚硬币。游戏人Ⅰ能否获胜并不在于21,n n 的具体值是多少，而是取决于它们是不是相等。设21n n ≠，游戏人Ⅰ从大堆中取走足够的硬币使得两堆含有相问数目的硬币留给游戏人Ⅱ去取，以后当轮到游戏人Ⅰ取子时就模仿游戏人Ⅱ来取子。于是，如果游戏人Ⅱ从一堆取走c 枚硬币，那么游戏人Ⅰ就从另一堆也取走c 枚硬币，这样的策略将保证游戏人Ⅰ获胜。如果21n n =，游戏人Ⅱ则可通过模仿游戏人Ⅰ来取子而获胜。这样，我们就完全解决了2堆Nim 取子游戏问题。一堆有8枚硬币而另一堆有5枚硬币的2堆Nim 取子游戏的例子叙述如下： 8,5I Ⅱ2,25,25,5I Ⅱ0,2I 0,0 上述求解2-堆Nim 取子游戏的思想，即取子后使得留下2堆子数相等的方法，可以推广到任意k 堆的情形。游戏人所需要的洞察力来自以2为基的正整数的概念。回忆一下，每个正整数n 都可以通过反复减去不超过该数的2的最大幂而被表示出来。例如，为了将十进制数57表示成基为2的数，我们观察到

212121292929225225225257257201034

345

456

5=-<≤=-<≤=-<≤=-<≤

因此 0345222257+++=

而57表示成基为2的数是 111001

在基为2的数中的每位数字不是0就是1。第i 个位置上的数字对应i 2，叫做第i 位(i ≥0)。我们可以认为每一堆硬币数由2的幂数的子堆组成，而2则是该数的基。于是，57枚硬币组成的堆则由大小为03452,2,2,2的各子堆组成。在2-堆Nim 取子游戏中，各种大小的子堆的总数只能是0，1或2：具有特定大小的子堆恰好存在一个当且仅当游戏中的两堆具有不同的大小，换句话说，各种大小的子堆的总堆数是偶数当且仅当游戏中的2堆具有相同的大小，也就是说，游戏人Ⅱ可以取胜。

现在考虑各堆大小分别为k n n n ,,,21 的一般的Nim 取子游戏。将每一个数i n 表示成基为2的数：

1

2122121e e e n b b b n a a a n s s s s === (我们通过在前面补0的方法可以假设，所有各堆的大小都是具有相同位数的以2为基的数)。如果每一种大小的子堆的个数都是偶数，我们就称Nim 取子游戏是平衡的。因此，Nim 取子游戏是平衡的，当且仅当

是偶数

＋是偶数是偶数

000e e b a b a e b a i i i s s s ++++++++ 一个Nim 取子游戏如果不是平衡的，就称为非平衡的。如果和数i i i e b a ++是偶数，我们就说第i 位是平街的，否则就称为非平衡的。因此，一个平衡的取子游戏就是其中的所有的位都是平衡的游戏，而非平衡取子游戏则是至少存在一个非平衡位的游戏。

于是，我们有

游戏人Ⅰ能够在非平衡Nim 取子游戏中取胜，而游戏人Ⅱ能够在平衡Nim 取子游戏中取胜。

为了理解上述结论，我们推广在2-堆Nim 取子游戏中所用的策赂。设Nim 取子游戏是非平衡的。令最大非平衡位为第i 位。于是，游戏人Ⅰ用这样一种方法取子，使得留给游戏人Ⅱ的游戏是平衡的取子游戏。具体地说，游戏人Ⅰ选择第j 位是1的一个堆，然后从所选的堆中取走一些硬币使得游戏成为平衡的游戏。此后，无论游戏人Ⅱ怎么做，他留给游戏人Ⅰ的都将是非平衡的游戏，而游戏人Ⅰ再次将游戏变成平衡状态。如此继续进行下去，则游戏人Ⅰ必然取胜。如果取子游戏从平衡状态开始，那么游戏人Ⅰ第一次取子后必将形成非平衡游戏，这时，只要游戏人Ⅱ取子，她就采取使游戏平衡的策略。

例如，考虑4-堆Nim 取子游戏，其中各堆大小分别为7，9，12和15枚硬

币。这些堆的大小写成基为2的数分别是0111，1001，ll00和1111。用2的幂的子堆表示。

我们有这局游戏是非平面的，其中第3号位、第2号为和第0号位都是非平衡的。游戏人Ⅰ可以选择大小为12的堆并取走11枚硬币，只剩下个1。由于基为2的数1是0001，取子游戏变为平衡状态。同样的道理，游戏人Ⅰ也可以选择大小为9的堆并取走5枚硬币而剩下4，或者，游戏人Ⅰ还能选择大小为15的堆并取走13枚硬币而留下了2。

排列组合问题的解法第三计

每周一计第三计——排列组合问题的解法 解决排列组合问题要讲究策略，用顺口溜概括为：审明题意，排（组）分清；合理分类，用准加乘；周密思考，防漏防重；直接间接，思路可循；元素位置，特殊先行；一题多解，检验真伪。 （一）.特殊元素、特殊位置的“优先安排法” 对于特殊元素的排列组合问题，一般先考虑特殊元素，再考虑其他元素的安排。在操作时，针对实际问题，有时“元素优先”，有时“位置优先”。 例1 ： 0、2、3、4、5这五个数字，组成没有重复数字的三位数，其中偶数共有几个？ 解法一：(元素优先)分两类：第一类，含0：0在个位有 种，0在十位有 种； 第二类，不含0：有1 223A A 种。 故共有（ 24A ＋1123A A ）＋1223A A ＝３０种。 注：在考虑每一类时，又要优先考虑个位。 解法二：(位置优先)分两类：第一类，0在个位有 种；第二类，0不在个位，先从两个偶数中选一个 放个位，再选一个放百位，最后考虑十位，有 种。 故共有 练习：甲、乙、丙、丁、戊、己六位同学选四人组队参加4*100m 接力赛，其中甲、乙不跑最后一棒，共有多少种不同的安排方法？（此题可有元素优先和位置优先两个角度两种解法，但位置优先则更简单） （二）．排除法 对于含有否定词语的问题，还可以从总体中把不符合要求的除去. 例２：５个人从左到右站成一排，甲不站排头，乙不站第二个位置，不同的站法有543543 2A A A -+=78种． （三）.相邻问题“捆绑法” 对于某些元素要求相邻．． 排列的问题，可先将相邻元素捆绑成整体并看作一个元素再与其它元素进行排列，同时对相邻元素内部进行自排。 例3： 5个男生3个女生排成一列，要求女生排一起，共有几种排法？ 解：先把3个女生捆绑为一个整体再与其他5个男生全排列。同时，3个女生自身也应 全排列。由乘法原理共有6365A A 种。 （四）。不相邻问题“插空法” 对于某几个元素不相邻的排列问题，可先将其他可相邻元素排好，再将不相邻的元素在已排好的元素之间及两端的空隙之间插入即可（注意有时候两端的空隙的插法是不符合题意的） 例4： 5个男生3个女生排成一列，要求女生不相邻且不可排两头，共有几种排法？ 解：先排无限制条件的男生，女生插在5个男生间的4个空隙，由乘法原理共有 种。 注意：①分清“谁插入谁”的问题。要先排可相邻的元素，再插入不相邻的元素； ②数清可插的位置数；③插入时是以组合形式插入还是以排列形式插入要把握准。 例5： 马路上有编号为1、2、3、…、9的9盏路灯，现要关掉其中的三盏，但不能同时关掉相邻的两盏或三盏，也不能关两端的路灯，则满足要求的关灯方法有几种？ 解：由于问题中有6盏亮3盏暗，又两端不可暗，故可在6盏亮的5个间隙中插入3个暗的即可，有3 5 C 种。 （五）。定序问题选位不排 对于某几个元素顺序一定的排列问题，可先在总位置中选出顺序一定元素的位置而不参加排列，然后对其它元素进行排列。 例6： 5人参加百米跑，若无同时到达终点的情况，则甲比乙先到有几种情况？ 解：先在5个位置中选2个位置放定序元素(甲、乙)有 种，再排列其它3人有 ，由乘法原理得共有 =60种。 1345240A A =5354A A 25C 3 3 A 25C 3 3A 24 A 1123A A 111233 A A A 2111423330 A A A A +=24A

【智博教育原创专题】排列组合的常见题型及其解法大全(包含高中所有的题型)

★绝密 备战2014专题 主编：冷世平

排列组合的常见题型及其解法排列组合问题，通常都是出现在选择题或填空题中，问题千变万化，解法灵活，条件隐晦，思维抽象，难以找到解题的突破口,实践证明，解决问题的有效方法是：题型与解法归类、识别模式、熟练运用。 ◆处理排列组合应用题的一般步骤为： ①明确要完成的是一件什么事（审题）；②有序还是无序；③分步还是分类。 ◆处理排列组合应用题的规律 ⑴两种思路：直接法，间接法；⑵两种途径：元素分析法，位置分析法。 排列组合知识，广泛应用于实际，掌握好排列组合知识，能帮助我们在生产生活中，解决许多实际应用问题。同时排列组合问题历来就是一个老大难的问题。因此有必要对排列组合问题的解题规律和解题方法作一点归纳和总结，以期充分掌握排列组合知识。首先，谈谈排列组合综合问题的一般解题规律: ⑴使用“分类计数原理”还是“分步计数原理”要根据我们完成某件事时采取的方式而定，可以分类来完成这件事时用“分类计数原理”，需要分步来完成这件事时就用“分步计数原理”；那么，怎样确定是分类，还是分步骤？“分类”表现为其中任何一类均可独立完成所给的事件，而“分步”必须把各步骤均完成才能完成所给事件，所以准确理解两个原理强调完成一件事情的几类办法互不干扰，相互独立，彼此间交集为空集，并集为全集，不论哪类办法都能将事情单独完成，分步计数原理强调各步骤缺一不可，需要依次完成所有步骤才能完成这件事，步与步之间互不影响，即前步用什么方法不影响后面的步骤采用的方法。 ⑵排列与组合定义相近，它们的区别在于是否与顺序有关。 ⑶复杂的排列问题常常通过试验、画“树图”、“框图”等手段使问题直观化，从而寻求解题途径，由于结果的正确性难于检验，因此常常需要用不同的方法求解来获得检验。 ⑷按元素的性质进行分类，按事件发生的连续性进行分步是处理排列组合问题的基本思想方法，要注意“至少、至多”等限制词的意义。 ⑸处理排列、组合综合问题，一般思想是先选元素（组合），后排列，按元素的性质进行“分类”和按事件的过程“分步”，始终是处理排列、组合问题的基本原理和方法，通过解题训练要注意积累和掌握分类和分步的基本技能，保证每步独立，达到分类标准明确，分步层次清楚，不重不漏。 ⑹在解决排列组合综合问题时，必须深刻理解排列组合的概念，能熟练地对问题进行分类，牢记排列数与组合数公式与组合数性质，容易产生的错误是重复和遗漏计数。 总之，解决排列组合问题的基本规律，即：分类相加，分步相乘，排组分清，加乘明确；有序排列，无序组合；正难则反，间接排除等；其次，我们在抓住问题的本质特征和规律，灵活运用基本原理和公式进行分析解答的同时，还要注意讲究一些解题策略和方法技巧，使一些看似复杂的问题迎刃而解。下面介绍几种常用的解题方法和策略。 【策略1】特殊元素（位置）用优先考虑 把有限制条件的元素（位置）称为特殊元素（位置），对于这类问题一般采取特殊元素（位置）优先安排的方法。 【例1】6人站成一横排，其中甲不站左端也不站右端，有种不同站法。 【分析】解有限制条件的元素（位置）这类问题常采取特殊元素（位置）优先安排的方法。 【法一】（优先考虑特殊元素）因为甲不能站左右两端，故第一步先让甲排在左右两端之间的任一位置上，有4种站法；第二步再让其余的5人站在其他5个位置上，有120种站法，故站法共有480种； A种方法；剩下四【法二】（优先考虑特殊位置）先从除甲外的五个元素中任取两个站在两端，有2 5 A种方法，共计有480种。 个人作全排列有4 4 用0,2,3,4,5五个数字，组成没有重复数字的三位数，其中偶数共有个。30 【策略2】相邻问题用捆绑法 将相邻的元素内部进行全排列，绑成一捆，看作一个整体，视为一个元素，与其他元素进行排列。

组合数学 第五章

第五章 区组设计与编码 1.拉丁方与正交拉丁方 拉丁方：由1，2，…，n 构成n ×n 方阵n n ij a ?)(，如果每行每列中1，2，…，n 各出现一次，则称此方阵为拉丁方。 如： ??? ? ? ?=12212 n ???? ? ? ?????? ? ?=12 3312231 21 3132321 3 n 正交换丁方：设()() n n ij n n ij a A a A ??==) 2(2) 1(1是两个n ×n 的拉丁方，如果矩阵 ()() n n ij ij a a ?) 2()1(,中2n 个数偶()) 2()1(,ij ij a a 互不相同，n j i ,,2, 1, =， 则称1A 和2A 正交，或称1A 和2A 是互相正交的拉丁方。 如：???? ? ? ?=???? ? ??=12 3312 231 ,213132 32121A A 由于??? ? ? ? ?)1,2() 2,1()3,3()3,1()1,3() 2,2()2,3()3,2()1,1(中元素两两不同，故21A A ⊥ 36名军官问题：ij a 表示军官的军衔为i ，军官所在的团为j ，()66),(?j i 要求第一个数字构成拉丁方，第二个数字也构成拉丁方，并且正交。 定理：两两相互正交的n 阶拉丁方的个数不超过n-1个 pf ：设k A A A ,,,21 是两两相互正交的n 阶拉丁方，往证1-≤n k 。设n a a a 21是1， 2，…，n 的一个全排列，() ,,,2,1,) (k l a A n n l ij l ==?对1A 作如下置换

??? ? ??n a a a n 2 1 21，得一方阵() n n ij a A ?=) 1(1，则1A 与k A A ,2正交。 事实上，如果1A 不与2A 正交，则 ()() n n ij ij a a ?) 2() 1(,中至少有一对数偶出现次数超过1次，设该对数偶为),(m l a a ，则 ),(m a l 在( )) 2() 1(,ij ij a a 中至少出现2次，与2 1 ,A A 正交矛盾，由此不妨设k A A A ,,,21 的 第一行均为),,2,1(n ，任取,1k m l ≤<≤则方阵 ()() n n m ij ij a a ?) ()1(,的第一行均是),,(),2,1(),1,1((r n 从而1不能出现在k A A A ,,,21 的 第2行第1列元素，故这些元素只能取2，3，…, n 中一个，而且取法不能相同，故n k ≤。 2.域与有限域 域：),(,:) 1(,+→?+≠V V V V V φ Abel 群 b a b a +→),( （2） ),(:* * *?→??V V V V Abel 群 ab b a →),( }0/{* V V = （3）分配律成立 ac ab c b a +=+)( ca ba a c b +=+)( 则称),,(?+V 为域 例： Q ，R ，C ， {}Q b a bi a i Q ∈+=,|)( 二元域}1,0{2=F ， p 元域}1,,2,1,0{-=p F p 有限域：元素个数有限的域叫做有限域 比如： },,2,1,0{p F p =模p 的剩余类域， 取)(x f 是][x F p 中n 次不可约多项式，则

组合数学习题4(共5章)

第四章 生成函数 1. 求下列数列的生成函数： （1）{0,1,16,81,…,n 4,…} 解：G{k 4 }= 235 (11111) 1x x x x x +++-（） （2）343,,,333n +?????????? ? ? ????? ???? 解：3n G n +?????? ?????=4 1(1)x - （3）{1,0,2,0,3,0,4,0,……} 解：A(x)=1+2x 2+3x 4+4x 6+…=2 1 1x -. （4）{1,k ,k 2,k 3,…} 解：A(x)=1+kx+k 2x 2+k 3x 3+…= 1 1kx -. 2. 求下列和式： （1）14+24+…+n 4 解：由上面第一题可知，{n 4}生成函数为 A(x)=235 (11111)1x x x x x +++-（）=0 k k k a x ∞=∑， 此处a k =k 4 .令b n =14 +24 +…+n 4 ，则b n =0n k k a =∑，由性质3即得数列{b n }的生 成函数为 B(x)= 0n n n b x ∞ =∑=() 1A x x -=34 125(1111)i i i x x x x x i ∞ =++++?? ??? ∑. 比较等式两边x n 的系数，便得 14+24+…+n 4 =b n =1525354511111234n n n n n n n n -+-+-+-++++----???????? ? ? ? ? ???????? 321 (1)(691)30 n n n n n =+++- （2）1·2+2·3+…+n (n +1) 解：{ n (n +1)}的生成函数为A(x)= 3 2(1)x x -=0 k k k a x ∞ =∑，此处a k = n (n +1). 令b n =1·2+2·3+…+n (n +1)，则b n =0 n k k a =∑.由性质3即得数列{b n }的生成 函数为B(x)= n n n b x ∞ =∑= () 1A x x -= 4 2(1)x x -=032n k k k x x k =+?? ?? ?∑. 比较等式两边x n 的系数，便得

高中数学-排列组合解法大全

排列组合解法大全 复习巩固 1.分类计数原理(加法原理) 完成一件事，有n 类办法，在第1类办法中有1m 种不同的方法，在第2类办法中有2m 种不同的方法，…，在第n 类办法中有n m 种不同的方法，那么完成这件事共有： 12n N m m m =+++ 种不同的方法． 2.分步计数原理（乘法原理） 完成一件事，需要分成n 个步骤，做第1步有1m 种不同的方法，做第2步有2m 种不同的方法，…，做第n 步有n m 种不同的方法，那么完成这件事共有： 12n N m m m =??? 种不同的方法． 3.分类计数原理分步计数原理区别 分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。 分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件． 解决排列组合综合性问题的一般过程如下: 1.认真审题弄清要做什么事 2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。 3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素. 4.解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略 一.特殊元素和特殊位置优先策略 例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置. 先排末位共有1 3C 然后排首位共有1 4C 最后排其它位置共有3 4A 由分步计数原理得1 1 3434288C C A = 练习题:7种不同的花种在排成一列的花盆里,若两种葵花不种在中间，也不种在两端的花盆里，问有 多少不同的种法？ 二.相邻元素捆绑策略 例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法. 解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元 素进行排列，同时对相邻元素内部进行自排。由分步计数原理可得共有5 2 2 522480A A A =种不同的排法 C 1 4 A 3 4 C 1 3 位置分析法和元素分析法是解决排列组合问题最常用也是最基本的方法,若以元素分析为主,需先安排特殊元素,再处理其它元素.若以位置分析为主,需先满足特殊位置的要求,再处理其它位置。若有多个约束条件，往往是考虑一个约束条件的同时还要兼顾其它条件

第一章 什么是组合数学

第一章什么是组合数学 组合学问题在生活中随处可见。例如，计算下列赛制下总的比赛次数：n个球队参赛，每队只和其他队比赛一次。创建幻方。在纸上画一个网络。用铅笔沿着网络的线路走，在笔不离开纸面且不重复线路的条件下，笔画出网络因。在玩扑克牌游戏中，计算满堂红牌的手数，以确定出现一手满堂红牌的几率。所有这些都是组合学问题。正如人们想到的．组合数学的历史渊源扎根于数学娱乐和游戏之中。过去研究过的许多问题，不论出于消遣还是出于对其美学的考虑，如今在纯科学和应用科学中都具有高度的重要性。今天，组合数学是数学的一门重要分支，而且它的影响还在继续扩大。组合数学自60年代以来急速发展的部分原因就在于计算机在我们的社会中所发挥的重要影响，而且这种影响还在继续发挥。由于运算速度的持续增加，计算机已经能够解决大型问题，这在以前是不可能做到的。然而计算机不能独立运行，它需要编程来控制。这些程序的基础往往是求解问题的组合学算法，对于这些算法，运行时间效率和存储需求分析需要更多的组合学思想。 组合数学近期发展的另一个原因是它对于那些过去很少与数学正式接触的学科的适用性。由此我们发现，组合数学的思想和技巧不仅正在用于数学应用的传统自然科学领城，而且也用于社会科学、生物科学、信息论等领域。此外，组合数学和组合学思想在许多数学分支中已经变得越来越重要。 组合数学涉及到将一个集合的物体排列成满足一些指定规则的格式。如下两类一般性问题反复出现： 排列的存在性如果有人想要排列—个集合的成员使得某些条件得以满 足，那么这样一种排列是否可行根本就不是显而易见的。这是最根本的问题。如果这种排列不总是可能的，那么我们要问，这种排列在什么样的(必要和充分)条件下能够实现？ 排列的计数和分类如果一个指定的排列是可能的，那么就会存在多种 方法去实现它。此时，人们就可以计数并将它们分类。 虽然对任何组合问题都可以考虑其存在性和计数问题，但在实践中常常发生的却是：如果存在性问题需要广泛地研究，那么计数问题则是非常困难的。然而，如果指定的排列问题的存在性容易解决，那么计算实现该排列的方法的数目则是可能的。在例外的情形下(即当它们的数目较小时)，这些排列可以被列出来，理解列出所有的排列与确定它们的数目之间的区别很重要。一旦这些排列被列出，它们就可通过与整数集{1，2，3，…，n}之间建立一一对应而被数出，其中n 是某个整数。我们计数的方法就是：1，2，3…，n。但是，我们主要关心的是事先不列出指定类型的排列而确定它们的数目的方法。当然，这些排列的总数也许很大以至于不可能把它们部列出来，概括地说，许多组合学问题常呈现下列形式：“能否排列…?” “存在一个……吗?” “能用多少方法—…?” “计算……的数目。”

排列组合测试题(含答案)

排例组合专题训练 1． 将3个不同的小球放入4个盒子中，则不同放法种数有A ．81 B ．64 C ．12 D ．14 2．5个人排成一排,其中甲、乙两人至少有一人在两端的排法种数有 A ．33A B ．334A C ．523533A A A - D ．23113 23233A A A A A + 3．,,,,a b c d e 共5个人，从中选1名组长1名副组长，但a 不能当副组长，不同的选法总数是 A.20 B ．16 C ．10 D ．6 4．现有男、女学生共8人，从男生中选2人，从女生中选1人分别参加数学、物理、化学三科竞赛，共有90种不同方案，那么男、女生人数分别是 A ．男生2人女生6人 B ．男生3人女生5人 C ．男生5人女生3人 D ．男生6人女生2人. 5．在8 2 x ? ?的展开式中的常数项是A.7 B ．7- C ．28 D ．28- 6．5 (12)(2)x x -+的展开式中3 x 的项的系数是A.120 B ．120- C ．100 D ．100- 7．22n x ???展开式中只有第六项二项式系数最大,则展开式中的常数项是 A ．180 B ．90 C ．45 D ．360 8．由数字1、2、3、4、5组成没有重复数字的五位数，其中小于50000的偶数共有 A ．60个 B ．48个 C ．36个 D ． 24个 9．3张不同的电影票全部分给10个人,每人至多一张,则有不同分法的种数是 A ．1260 B ．120 C ．240 D ．720 10．n N ∈且55n <,则乘积(55)(56) (69)n n n ---等于 A ．5569n n A -- B ．15 69n A - C ．15 55n A - D ．14 69n A - 11．从不同号码的5双鞋中任取4只，其中恰好有1双的取法种数为 A ．120 B ．240 C ．280 D ．60 12．把10 )x -把二项式定理展开，展开式的第8项的系数是 A ．135 B ．135- C ．- D ． 13．2122n x x ??+ ?? ?的展开式中，2 x 的系数是224，则2 1x 的系数是A.14 B ．28C ．56 D ．112 14．不共面的四个定点到面α的距离都相等，这样的面α共有几个A ．3 B ．4 C ．6 D ．7

排列组合解法大全

排列组合解法大全 一.特殊元素和特殊位置优先策略 例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置. 先排末位共有1 3C 然后排首位共有14C 最后排其它位置共有34A 由分步计数原理得113434288C C A = 练习题:7种不同的花种在排成一列的花盆里,若两种葵花不种在中间，也不种在两端的花 盆里，问有多少不同的种法？ 二.相邻元素捆绑策略 例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法. 解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素， 再与其它元素进行排列，同时对相邻元素内部进行自排。由分步计数原理可得共有522522480A A A =种不同的排法 练习题:某人射击8枪，命中4枪， 4枪命中恰好有3枪连在一起的情形的不同种数为 20 三.不相邻问题插空策略 例3.一个晚会的节目有4个舞蹈,2个相声,3个独唱,舞蹈节目不能连续出场,则节目的出 场顺序有多少种？ 解:分两步进行第一步排2个相声和3个独唱共有55A 种，第二步将4舞蹈插入第一步排 好的6个元素中间包含首尾两个空位共有种4 6A 不同的方法,由分步计数原理,节目的不同顺序共有5456A A 种 练习题：某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个新节目插入原节目单中，且两个新节目不相邻，那么不同插法的种数为 30 四.定序问题倍缩空位插入策略 例4.7人排队,其中甲乙丙3人顺序一定共有多少不同的排法 解:(倍缩法)对于某几个元素顺序一定的排列问题,可先把这几个元素与其他元素一起进 行排列,然后用总排列数除以这几个元素之间的全排列数,则共有不同排法 种数是：73 73/A A (空位法)设想有7把椅子让除甲乙丙以外的四人就坐共有4 7A 种方法，其余的三个位

李凡长版 组合数学课后习题答案 习题1

1 第一章 排列组合 1、 在小于2000的数中，有多少个正整数含有数字2？ 解：千位数为1或0，百位数为2的正整数个数为：2*1*10*10； 千位数为1或0，百位数不为2，十位数为2的正整数个数为：2*9*1*10； 千位数为1或0，百位数和十位数皆不为2，个位数为2的正整数个数为：2*9*9*1； 故满足题意的整数个数为：2*1*10*10+2*9*1*10+2*9*9*1＝542。 2、 在所有7位01串中，同时含有“101”串和“11”串的有多少个？ 解：（1） 串中有6个1：1个0有5个位置可以插入：5种。 （2） 串中有5个1，除去0111110，个数为()6 2 -1＝14。 （或： ()()41 42 *2+＝14） （3）串中有4个1：分两种情况：①3个0单独插入，出去1010101，共()53 -1 种；②其中两个0一组，另外一个单独，则有 ()()2*)2,2(41 52 -P 种。 （4）串中有3个1：串只能为**1101**或**1011**，故共4*2种。 所以满足条件的串共48个。 3、一学生在搜索2004年1月份某领域的论文时，共找到中文的10篇，英文的12篇，德文的5篇，法文的6篇，且所有的都不相同。如果他只需要2篇，但必须是不同语言的，那么他共有多少种选择？ 解：10*12+10*5+10*6+12*5+12*6+5*6 4、设由1，2，3，4，5，6组成的各位数字互异的4位偶数共有n 个，其和为m 。求n 和m 。 解：由1，2，3，4，5，6组成的各位数字互异，且个位数字为2，4，6的偶数均有P(5,3)=60个，于是：n = 60*3 = 180。 以a 1,a 2,a 3,a 4分别表示这180个偶数的个位、十位、百位、千位数字之和，则 m = a 1+10a 2+100a 3+1000a 4。 因为个位数字为2，4，6的偶数各有60个，故 a 1 = (2+4+6)*60=720。 因为千（百，十）位数字为1，3，5的偶数各有3*P(4,2) = 36个，为2，4，6的偶数各有2*P(4,2) = 24个，故 a 2 = a 3 = a 4 = (1+3+5)*36 + (2+4+6)*24 = 612。 因此， m = 720 + 612*(10 + 100 + 1000) = 680040。 5、 从{1，2，…，7}中选出不同的5个数字组成的5位数中，1与2不相邻的数 字有多少个？ 解：1与2相邻：())4,4(253P ??。故有1和 2 但它们不相邻的方案数： ()())4,4(2)5,5(53 5 3 P P ??-? 只有1或2：())5,5(254P ?? 没有1和2：P(5,5)

李凡长版-组合数学课后习题答案-习题3

李凡长版-组合数学课后习题答案-习题3

第三章递推关系 1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限 区域数记为f(n),求f(n)满足的递推关系. 解： f(n)=f(n-1)+2 f(1)=2,f(2)=4 解得f(n)=2n. 2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求 f(n)满足的递推关系. 解：设a n-1a n-2 …a 1 是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1) 表示。 a n 可以有两种情况： 1）不管上述序列中是否有2，因为a n 的位置在最左边，因此0 和1均可选； 2）当上述序列中没有1时，2可选； 故满足条件的序列数为 f(n)=2f(n-1)+2n-1 n 1, f(1)=3 解得f(n)=2n-1(2+n). 3.n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足 的递推关系. 解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。 则有 h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1） f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2） 将（1）得到的h(n)=(2n+4n)/2代入（2），可得 n+4n)/2-2f(n), 4.求满足相邻位不同为0的n位二进制序列中0的个数f(n). 解：这种序列有两种情况： 1)最后一位为0，这种情况有f(n-3)个； 2)最后一位为1，这种情况有2f(n-2)个； 所以 f(1)=2,f(2)=3,f(3)=5. 5.求n位0,1序列中“00”只在最后两位才出现的序列数f(n). 解：最后两位是“00”的序列共有2n-2个。 f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能； f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能； 依此类推，有 17

组合数学作业答案

第二章作业答案 7. 证明，对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。 证明 用100分别除这52个整数，得到的余数必为0, 1,…, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，…，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a 和b 。若a 和b 被100除余数相同，则b a -能被100整除。若a 和b 被100除余数之和是100，则b a +能被100整除。 11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。 证明 设从第一天到第i 天她共学习了i a 小时。因为她每天至少学习1小时，所以 3721,,,a a a 和13,,13,133721+++a a a 都是严格单调递增序列。因为总的学习时间 不超过 60 小时，所以6037≤a ，731337≤+a 。3721,,,a a a , 13,,13,133721+++a a a 是1和73之间的74个整数，由鸽巢原理知道，它们中存在相 同的整数，有i a 和13+j a 使得13+=j i a a ，13=-j i a a ，从第1+j 天到第i 天她恰好学习了13小时。 14. 一只袋子装了100个苹果、100个香蕉、100个桔子和100个梨。如果我每分钟从袋子里取出一个水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？ 解 由加强形式的鸽巢原理知道，如果从袋子中取出451)112(4=+-?个水果，则能肯定至少已拿出12个相同种类的水果。因此，需要45分钟。 17. 证明：在一群1>n 个人中，存在两个人，他们在这群人中有相同数目的熟人（假设没有人与他/她自己是熟人）。 证明 因为每个人都不是自己的熟人，所以每个人的熟人的数目是从0到1-n 的整数。若有两个人的熟人的数目分别是0和1-n ，则有人谁都不认识，有人认识所有的人，这是不可能的。因此，这n 个人的熟人的数目是1-n 个整数之一，必有两个人有相同数目的熟人。 第三章作业答案 6. 有多少使下列性质同时成立的大于5400的整数？ (a) 各位数字互异。 (b) 数字2和7不出现。 解 因为只能出现数字0, 1, 3, 4, 5, 6, 8, 9，所以整数的位数至多为8。 ① 考虑8位整数。最高位不能为0，因此8位整数有)7,7(7P ?个。 ② 考虑7位整数。最高位不能为0，因此8位整数有)6,7(7P ?个。

组合数学与图论复习题及参考答案

组合数学与图论复习题及答案 1．Show that if n+1 integers are chosen form the set {1,2, …,2n},then there are always two which differ by at most 2. 从{1,2, …,2n}中选出n+1个数，在这n+1个数中，一定存在两个数，其中一个整数能整除另外一个整数。 任何一个数都可以写成2k*L，其中k是非负数，L是正奇数。现在从1到 2n之间只有n个奇数。由于有n+1个数都能表示成2k*L，而L的取值只有n中，所以有鸽子洞原理知道，至少有两个数的L是一样的，于是对应k小的那个就可以整除k大的另一个数。 2．Show that for any given 52 integers there are exist two of them whose sum, or else difference, is divisible 100. 设52个整数a1，a2，…，a52被100除的余数分别是r1,r2,…,r52，而任意一个数被100除余数为0，1，2，…，99，一共100个。他们可以分为51个类{0},{1,99},{2,98},…,{49,51},{50}。将这51个集合视为鸽笼，则将r1,r2,…,r52放入51个笼子中，至少有两个属于同一个笼子，所以要么有ri＝rj，要么有ri＋rj ＝100，也就是说ai－aj|100或者ai＋aj|100。 3．从1，2，3，…，2n中任选n+1个数，证明在这n+1个数中至少有一对数互质。 鸽子洞原理，必有两个数相邻，相邻的两个数互质 4．Prove that Ramsey number R(p,q)≤R(p,q-1)+R(p-1,q). 令N＝R(p,q-1)+R(p-1,q)，从N个人中中随意选取一个a，F表示与a相识的人，S表示与a不相识的人。 在剩下的R(p,q-1)+R(p-1,q)－2＋1个人中，由鸽子洞原理有，或者F中有 R(p,q-1)人，或者S中有R(p-1,q)人。如果F中有R(p,q-1)人，则与a相识的人为p个；如果S中有R(p-1,q)人，则与a不相识的人有p个。所以有R(p,q)≤ R(p,q-1)+R(p-1,q) 5．There are 10 people, either there are 3 each pair of whom are acquainted, or there are 4 each pair of whom are unacquainted。 从10人中随意选一个人p，F表示与p相识的人，S表示与p不相识的人若F中至少有4人，如果至少有4人不相识，则满足题设；如果有2人相识，则加上p有3人相识，也满足题设。 若F中至多有3人，则S中至少有6人，6人中至少有3人相识，或者不相识。如果相识则满足题设，如果不相识加上p不相识的人就有4个，也满足题设。6．In how many ways can six men and six ladies be seated at round table if the men and ladies to sit in alternate seats? 6个男的先进行圆排列，然后6个女的插入空位。 7．In how many ways can 15 people be seated at round table if B refuses to sit next to A? What if B only refuses to sit on A right?

超全超全的排列组合的二十种解法

排列有两种定义，但计算方法只有一种，凡是符合这两种定义的都用这种方法计算。定义的前提条件是m≦n，m与n均为自然数。①从n个不同元素中，任取m个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。②从n个不同元素中，取出m个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数。 ③用具体的例子来理解上面的定义：4种颜色按不同颜色，进行排列，有多少种排列方法，如果是6种颜色呢。从6种颜色中取出4种进行排列呢。 解：A(4,4)=4x(4-1)x(4-2)x(4-3)x(4-4+1)=4x1x2x3x1=24。 A(6,6)=6x5x4x3x2x1=720。 A(6,4)=6!/(6-4)!=(6x5x4x3x2x1)/2=360。 [计算公式] 排列用符号A(n,m)表示，m≦n。 计算公式是：A(n,m)＝n(n-1)(n-2)……(n-m+1)＝n!/(n-m)! 此外规定0!=1，n!表示n(n-1)(n-2) (1) 例如：6!=6x5x4x3x2x1=720，4!=4x3x2x1=24。 组合的定义及其计算公式 1 组合的定义有两种。定义的前提条件是m≦n。 ①从n个不同元素中，任取m个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合。 ②从n个不同元素中，取出m个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。 ③用例子来理解定义：从4种颜色中，取出2种颜色，能形成多少种组合。 解：C(4,2)=A(4,2)/2!={[4x(4-1)x(4-2)x(4-3)x(4-4+1)]/[2x(2-1)x(2-2+1)]}/[2x(2-1)x(2-2+1)]=[( 4x3x2x1)/2]/2=6。 [计算公式] 组合用符号C(n,m)表示，m≦n。 公式是：C(n,m)=A(n,m)/m! 或C(n,m)=C(n,n-m)。

李凡长版 组合数学课后习题答案 习题5

第五章 P ólya 计数理论 1. 计算（123）（234）（5）（14）（23）,并指出它的共轭类. 解：题中出现了5个不同的元素：分别是：1，2，3，4，5。即|S n |＝5。 ??? ? ?????? ?????? ??=512345432152431543215413254321) 23)(14)(5)(234)(123( ??? ? ?????? ??=51234543215214354321 ??? ? ??=5341254321 )5)(34)(12(= （5）（12）（34）的置换的型为1122而S n 中属于1122型的元素个数为15 21!1!2! 52 1=个其共轭类为 （5）（14）（23），（5）（13）（24），（1）（23）（45），（1）（24）（35）， （1）（25）（34），（2）（13）（45），（2）（14）（35），（2）（15）（34）， （3）（12）（45），（3）（14）（25），（3）（15）（24），（4）（12）（35）， （4）（13）（25），（4）（15）（24） 2. 设D 是n 元集合,G 是D 上的置换群.对于D 的子集A 和B ,如果存在G ∈σ, 使得}|)({A a a B ∈=σ,则称A 与B 是等价的.求G 的等价类的个数. 解：根据Burnside 引理∑= =n i i a c G l 1 1)(1，其中c 1(a i )表示在置换a i 作用下保持不变的元素个数，则有 c 1(σI )=n; 设在σ的作用下，A 的元素在B 中的个数为i ，则 c 2(σ)=n －2i ； 若没有其他置换，则G 诱出来的等价类个数为l=i n i n n -=-+)]2([2 1 3. 由0,1,6,8,9组成的n 位数,如果把一个数调转过来读得到另一个数,则称这两 个数是相等的.例如,0168和8910,0890与0680是相等的.问不相等的n 位数有多少个？ 解：该题可理解为相当于n 位数，0，1，6，8，9这5个数存在一定的置换关系

完整版排列组合的二十种解法最全的排列组合方法总结

教学目标 1. 进一步理解和应用分步计数原理和分类计数原理。 2. 掌握解决排列组合问题的常用策略 ；能运用解题策略解决简单的综合应用题。提高学生解决问题分 析问题的能力 3. 学会应用数学思想和方法解决排列组合问题 复习巩固 1. 分类计数原理（加法原理） 完成一件事，有n 类办法，在第1类办法中有 m i 种不同的方法，在第 2类办法中有m 2种不同的方 法，…，在第n 类办法中有m n 种不同的方法，那么完成这件事共有： N m i m 2 L m n 种不同的方法. 2. 分步计数原理（乘法原理） 完成一件事，需要分成n 个步骤，做第1步有叶种不同的方法，做第2步有m 2种不同的方法，… 做第n 步有m n 种不同的方法，那么完成这件事共有: N mi m 2 L m n 种不同的方法. 3. 分类计数原理分步计数原理区别 分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。 分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件. 解决排列组合综合性问题的一般过程如下 ： 1. 认真审题弄清要做什么事 2. 怎样做才能完成所要做的事 ，即采取分步还是分类，或是分步与分类同时进行，确定分多少步及多少 类。 3. 确定每一步或每一类是排列问题 （有序）还是组合（无序）问题，元素总数是多少及取出多少个元素 . 4. 解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略 一.特殊元素和特殊位置优先策略 例1.由0,1,2,3,4,5 可以组成多少个没有重复数字五位奇数 . 解：由于末位和首位有特殊要求，应该优先安排，以免不合要求的元素占了这两个位置 . 先排末位共有C ； 然后排首位共有C 1 最后排其它位置共有 A 3 由分步计数原理得C 4C ；A ； 288 位置分析法和元素分析法是解决排列组合问题最常用也是最基本的方法 ，若以元素分析为主，需 先安排特殊元素，再处理其它元素.若以位置分析为主，需先满足特殊位置的要求，再处理其它位 置。若 有多个约束条件，往往是考虑一个约束条件的同时还要兼顾其它条件 练习题:7种不同的花种在排成一列的花盆里 多少不同的种法？ 二. 相邻元素捆绑策略 例2. 7人站成一排，其中甲乙相邻且丙丁相邻，共有多少种不同的排法. 解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元 素进行排 A 3 ,若两种葵花不种在中间，也不种在两端的花盆里，冋有 A 5 A 2 A 2 480种不同的

Richard组合数学第5版-第5章课后习题答案(英文版)

Math475Text:Brualdi,Introductory Combinatorics5th Ed. Prof:Paul Terwilliger Selected solutions for Chapter5 1.For an integer k and a real number n,we show n k = n?1 k?1 + n?1 k . First assume k≤?1.Then each side equals0.Next assume k=0.Then each side equals 1.Next assume k≥1.Recall P(n,k)=n(n?1)(n?2)···(n?k+1). We have n k = P(n,k) k! = nP(n?1,k?1) k! . n?1 k?1 = P(n?1,k?1) (k?1)! = kP(n?1,k?1) k! . n?1 k = P(n?1,k) k! = (n?k)P(n?1,k?1) k! . The result follows. 2.Pascal’s triangle begins 1 11 121 1331 14641 15101051 1615201561 172135352171 18285670562881 193684126126843691 1104512021025221012045101 ··· 1

3.Let Z denote the set of integers.For nonnegative n∈Z de?ne F(n)= k∈Z n?k k . The sum is well de?ned since?nitely many summands are nonzero.We have F(0)=1and F(1)=1.We show F(n)=F(n?1)+F(n?2)for n≥2.Let n be https://www.doczj.com/doc/3f13916285.html,ing Pascal’s formula and a change of variables k=h+1, F(n)= k∈Z n?k k = k∈Z n?k?1 k + k∈Z n?k?1 k?1 = k∈Z n?k?1 k + h∈Z n?h?2 h =F(n?1)+F(n?2). Thus F(n)is the n th Fibonacci number. 4.We have (x+y)5=x5+5x4y+10x3y2+10x2y3+5xy4+y5 and (x+y)6=x6+6x5y+15x4y2+20x3y3+15x2y4+6xy5+y6. 5.We have (2x?y)7= 7 k=0 7 k 27?k(?1)k x7?k y k. 6.The coe?cient of x5y13is35(?2)13 18 5 .The coe?cient of x8y9is0since8+9=18. https://www.doczj.com/doc/3f13916285.html,ing the binomial theorem, 3n=(1+2)n= n k=0 n k 2k. Similarly,for any real number r, (1+r)n= n k=0 n k r k. https://www.doczj.com/doc/3f13916285.html,ing the binomial theorem, 2n=(3?1)n= n k=0 (?1)k n k 3n?k. 2