B牌完美覆盖


对于m*n棋盘被多米诺覆盖的问题，还存在另外一种一般化 的方法。设b是一个1*1的方格并排连接成1*b的方格条来代 替多米诺牌。我们称这些方格条为b-牌。因此，一张b牌可 以盖住一行上或者一列上的b个连续的方格。 那么，何时m*n的棋盘具有一个b牌的完美覆盖？ 结论： 一张m行n列棋盘有一个b牌的完美覆盖，当且仅当b是m 的一个因子或b是n的一个因子。 怎样证明？
实例
1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数 解答: 1)小于10000的不含1的正整数可看做4位数, 但0000除外. 故有9×9×9×9－1＝6560个. 含1的有：9999－6560=3439个 另: 全部4位数有104 个,不含1的四位数有9 4 个, 含1的4位数为两个的差: 104 －9 4 = 3439个
组合数学
长沙市雅礼中学 朱全民
什么是组合数学



生活中常见的组合问题 计算赛制下的总的比赛次数 幻方 笔画网络图 扑克牌游戏 组合数学问题常呈现的形式 能否排列…… 存在一个……..吗 能用多少种方法 计算……的数目 研究一个已知的排列 构造一个最优的排列 组合数学是研究离散结构的存在、计数、分析和优化等问题的一门科学
棋盘的完美覆盖



考虑一张普通的国际象棋棋盘，他被分成8*8的64个正方形。 设有形状一样的多米诺骨牌，每张牌恰好覆盖棋盘上相邻的 两个方格。那么，是否能够把32张多米诺牌放到棋盘上，使 得任何两张多米诺牌均不重叠，每张多米诺牌覆盖两个方格， 并且所有的方格都被覆盖住？ 我们把这样一种排列称为棋盘被多米诺牌完美覆盖。 Fischer在1961年发现，它有12988816=24*(901)2种 如果将棋盘换成m*n的呢，还存在完美覆盖吗？ 不难看出，m*n为偶数时，存在完美匹配。 如果用一把剪刀剪去8*8的棋盘一幅对角上的两个方格，剩 下62方格，能否用31个多米诺牌进行完美覆盖吗？ 一块被切割过的棋盘具有完美匹配的必要和充分条件是什么？
切割立方体


考虑一个边长3英尺的立方体木块。我们希望把它切割成27 个边长1英尺的小立方体。完成这项工作所需最小切割次数 是多少？ 一种方法是依序切割6次，每个方向上切割2次并在切割时保 持该立方体不变 如果在每次切割后重新排放所切得的各块，则是否能用更少 的切割次数完成这项工作呢？ 考察一个4*4棋盘，它有一个8张多米诺牌的完美覆盖。 证明总能把棋盘横向或者纵向切成两块且不使这些多米 诺牌被切断。 切割的水平或竖直的直线叫做完美覆盖断层线。
组合



定义 n个不同元素中取r个不重复的元素组成一个子集， 而不考虑其元素的顺序，称为从n个中取r个的无重组合。组 合的全体组成的集合用C(n,r)表示，对应于可重组合C(n,r) 实例 n个不同的球中,取出r个,放入r个相同的盒子里，每盒1个 若放入盒子后再将盒子标号区别，则又回到排列模型。每一 个组合可有r!个标号方案。 C(n,r)=P(n,r)/r! 显然有 C(n,0)=1, C(n,n)=1, C(n,1)=n, C(n,r)=0 当 r>n,
y (m,n) . . .
0
. . .
x



在上例的基础上若设m<n，求(0,1)点到(m,n)点不接触对角线x=y的格路 的数目 (“接触”包括“穿过”),从(0,1)点到(m,n)点的格路，有的接触 x=y，有的不接触。对每一条接触x=y的格路，做(0,1)点到第一个接触点 部分关于x=y的对称格路，这样得到一条从(1,0)到(m,n)的格路。 容易看出从(0,1)到(m,n)接触x=y的格路与 (1,0)到(m,n)的格路(必穿过 x=y)一一对应 故所求格路数为C(n+m-1,m) - (n+m-1,m-1) 若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得x y=1，(0,0)关于x－y=1的对称点为(1,-1). 故所求格路数为C(n+m,m) - (n+m,m-1)
组合的物理意义


“一一对应”概念是一个在计数中极为 基本的概念。一一对应既是单射又是 满射。如我们说A集合有n个元素 |A|=n，无非是建立了将A中元与[1,n] 元一一对应的关系。在组合计数时往 往借助于一一对应实现模型转换。比 如要对A集合计数，但直接计数有困 难，于是可设法构造一易于计数的B， 使得A与B一一对应。 简单格路问题 : |(0,0)→(m,n)|=Ｃ (n+m,m),从 (0,0)点出发沿x轴或y轴的 正方向每步走一个单位，最终走到 (m,n)点，有多少条路径？
A 人 B C D
钥 匙 １２３４５６ √√√ √√√ √ √√ √ √ √
最短路经问题


考虑一个由道路和路口组成的子系统。一人想从一个路口A 行进到另一路口B。现在问题是要确定一条通路，沿此通路 从A到B的距离最小——一条最短路径。 这是一个关于图的问题，图是组合数学中已经研究而且还将 广泛研究的离散结构的一个例子。 怎样求最短路径？
Nim取子游戏



Nim取子游戏是由两个面对若干堆硬币（或石子,豆粒,…） 进行的游戏。设有k>=1堆硬币，各堆含有n1,n2,…,nk枚硬 币。游戏的目的就是选择最后剩下的硬币。 规则如下： 1. 游戏人交替进行游戏 2. 当轮到每个游戏人取子时，选择这些硬币堆中的一堆， 并从所选堆中取走至少1枚硬币。 3. 所有的堆都变为空时，游戏结束，最后取子的人赢得所 有的硬币。 如何取子？有何依据？
实例


如果每个单词包含３、4或5个元音，那么字母表中的26个字 母可以构造多少个8字母词？可以理解为，在一个词中字母 的使用次数没有限制。 我们按所含的元音个数来对单词进行计数，然后运用加法原 理。 3元音词: C(8,3)53215 4元音词: C(8,4)54214 5元音词: C(8,5)55213 因此词的总数为 C(8,3)53215 ＋ C(8,4)54214＋ C(8,5)55213
2)“含0”和“含1”不可直接套用。0019
含1但不含0。 在组合的习题中有许多类似的隐含的 规定，要特别留神。 不含0的1位数有9个，2位数有92个， 3位数有93个，4位数有94个 不含0小于10000的正整数有 9+92+93+94 =(95-1)/(9-1)=7380个 含0小于10000的正整数有 9999－7380=2619个
排列



定义 从n个不同的元素中，取r个不重复的元素，按次序 排列，称为从n个中取r个的无重排列。排列的全体组成的集 合用 P(n,r)表示。当r=n时称为全排列。一般不说可重即无 重。可重排列的相应记号为 P(n,r)。 实例 n个不同的球中,取出r个,放入r个不同的盒子里，每盒1个 第1个盒子有n种选择，第2个有n-1种选择，··· ··· ，第r个有nr+1种选择。 P(n,r)=n*(n-1)*…*(n-r+1) 有时也用[n]r表示


某保密装置须同时使用若干把不同的钥匙才能打开。现有７人，每人持 若干钥匙。须４人到场，所备钥匙才能开锁。问①至少有多少把不同的 钥匙？②每人至少持几把钥匙？ 解 ①每３人至少缺１把钥匙，且每３人所缺钥匙不同。故至少共有 C(7,3)=35把不同的钥匙。 ② 任一人对于其他６人中的每３人，都至少有１把钥匙与之相配才能 开锁。故每人至少持C(6,3)＝20把不同的钥匙。 举例，４人中３人到场，共有C(4,2)=6把不同的钥匙。每人有C(3,2)=3 把钥匙。
考虑一张平面图或在一个球面上的地图，地图上的国家都是 连通区域，为了能够很快分出国家，需要对这些国家着色， 以使得具有共同边界的国家被涂成不同颜色(角点处不算着 共同的边界)，能够保证如此着色每一张地图所需的最少的 颜色是多少？ 答案：4种颜色即可 证明？
36军官问题




设有分别来自6各军团共有6种不同军衔的36名军官，他们能 否排成6*6(6行6列的编队使得每行每列都有各种军衔的军官 1名)，并且每行每列上的不同军衔的6名军官分别来自不同 的军团？ 问题是，使36个序偶(i,j)，能否排成6*6的阵列，使得每行每 列，这6个整数都能以某种顺序出现在序偶第一个元素的位 置上。 看n=3的情况 123 1 2 3 (1,1) (2,2) (3,3) 312 2 3 1 (3,2) (1,3) (2,1) 231 3 1 2 (2,3) (3,1) (1,2) 是否存在6阶正交拉丁方？如何构造？
幻方
一个n阶幻方是由整数 1,2,…,n2,组成，其每行、每 列和两条对角线的和都等于 同一个数s。 这个整数s叫幻方的幻和。 一个n阶幻方的所有整数和 s=1+2+…+n2= n2(n2+1)/2 怎样构造幻方？ 幻方在3为情况下的情况呢？

4 3
9 5
2 7
8
1
6
四色问题


可重复的排列



如果Ｓ是一个多重集，那么Ｓ的一个ｒ排列是Ｓ的ｒ个元素 的一个有序排放．如果Ｓ的元素总个数是ｎ（包含计算重 复），那么Ｓ的ｎ排列也将称为Ｓ的全排列．例如，如果Ｓ ＝｛2•a,1•b,3•c｝那么acbc,cbcc都是4排列. 如果S是一个多重集,它有K个不同的类型元素，每一个元素 都有无穷重复个数，那么，Ｓ的ｒ排列个数为kr 如果S是一个多重集,它有K个不同的类型元素，各元素分别 为n1,n2,…,nk个，那么，Ｓ的ｒ排列个数为 n! / (n1!*n2!*…*nr!) 在8*8的棋盘上对于８个非攻击型的车共有多少种可能的放 法？(车的颜色相同，不同，第ｉ种颜色的车有ni个,分别讨 论)yyFra biblioteky=x