Richard A.Brualdi 组合数学5th 课后习题答案
其实这篇文章只是用来记录我解题思路的笔记。
第一章 什么是组合数学
1.证明 mxn 棋盘被多米诺骨牌完美覆盖当且仅当 m 和 n 中至少有一个是偶数。
step1：已知多米诺骨牌是1x2的矩形，设m与n同时为奇数且不妨设m<n,
step2: 因为n为奇数，所以为了填满一行，至少需要把一张多米诺骨牌竖着摆，这里不妨用纵向摆放的多米诺骨牌填充第1、2行。易知，若想填充满一行，则必定填充满满两行。
step3：因为有m行（m为奇数），所以最终必定剩下一行，当仅剩下一行时，棋盘无法完美覆盖。
2.考虑m和n都是奇数的mxn棋盘，为了固定表记方式，假设棋盘左上方的方格被涂成白色，证明如果切掉棋盘上任意一个白色方格，那么这个被切过的棋盘存在完美覆盖。
step1：假设被切掉的白色方格的位置为（j,k）由于假设，其中j,k为奇数。因为我们可以用竖向摆放的方式一次性填充完两行，所以可以先将除第 j 行以外所有行填充完毕。
step2：在剩下的第 j 行里，因为被切掉的是出于奇数位置k的方格，所以剩下的空间必定能被横向摆放的1x2多米诺骨牌完美覆盖。
3.想象一座由64个牢房组成的监狱，这些牢房被排列成8x8棋盘，所有相邻的牢房都有门，某角落处的一间牢房里的囚犯被告知，如果他能经过其他每一间牢房正好一次，达到对角线上相对的另外一间牢房，他就能被释放，他能获得自由吗？
step1：先简化问题，设想2x2的牢房，答案显然是不能。
step2：将牢房简化为黑白棋盘，问题就转换为 从白色(不妨设)出发，经过所有房间一次，最终到达对角线上对应的白色格子的走法是否存在。
step3：因为棋盘是黑白相间的结构，所以每次移动必定是从一种白色移动到黑色或者黑色移动到白色，所以要想从白色移动到白色，必须经过奇数个房间，但是房间的总数是64，是偶数，所以不可能存在一种走法，可以同时满足“只经过所有房间一次”和“最终到达对角线上相对应的房间”。
4.题目略 解答未必正确，只是我的想法
(a)
step1：只考虑最右边的多米诺骨牌的摆法是横向还是竖向，若是竖向，剩余的2x（n-1）的摆法数为f(n-1)，若是横向，剩余的2x（n-1）的摆法为f(n-2)。
step2：所有当n>2时，f(n) = f(n-1)+f(n-2) 且 f(1)=1,f(2)=2。
| f(n) | f(n-1)+f(n-2) |
|---|---|
| f(1) | 1 |
| f(2) | 2 |
| f(3) | 3 |
| f(4) | 5 |
| f(5) | 8 |
| f(6) | 13 |
| f(7) | 21 |
| f(8) | 34 |
| f(9) | 55 |
| f(10) | 89 |
| f(11) | 144 |
| f(12) | 233 |
(b)
step1：易知，当n为奇数时不存在完美覆盖，所以g(1),g(3),g(5)都为0.
step2：根据（a）知，g(2)=3,
step3: 在不考虑棋盘旋转的情况下，即不认为中心对称的两种摆法是同一种摆法，g(4)可以分解为2个g(2)，则由g2(2)种摆法,除此之外还要再考虑不能从中间切开的那种摆法，即中间两列的上面两行是横着摆放的，其实空间填充满(仅由一种填充方法)这种摆法，和这种摆法的镜像。所以，g(4)=3*g(2) + 2
step4: 我们现在考虑不能从中间切开的组合为一个整体，g(2)的3种摆法都不能从中间切开，g(4)里存在2种不能从中间切开的摆法，并且在任意的3xn且n>4，n为偶数 的棋盘里，都存着将g(n-2)种不能从中间切开的那两种摆法居中摆放，其余空间简单填充的两种新的不能中切的摆法。
step5：根据4中的分析，可以将n>4的且n为偶数的一般情况归纳成以下几种情况:
1)棋盘最右边的3x2的空间里由g(2)种摆放，剩余的空间里有g(n-2)种摆放
2)棋盘最右边的3x4的空间里有2种不能中切的3x4的摆放，剩余的空间里有g(n-4)种摆法
3)棋盘最右边的3x6的空间里有2种不能中切的3x6的摆放，剩余的空间里有g(n-6)种摆法
…)
(n-2) /2 )棋盘最右边的3x (n-2) 的空间里有2种不能中切的3x (n-2)的摆放，剩余的空间里有g(2)种摆法
n/2 ) 将g(n-2)里不能中切的两种摆法居中，剩余的空间简单填充，形成最后两种不能中切的摆法。
step6：以上分析能不遗漏的将所有摆法考虑到，考虑是否能从中间切开是问题的关键。
当n为奇数,g(n)=0,当为偶数时
g(0)=1,g(2)=3,if(n>2):g(n)=3×g(n?2)+2∑i=2n2g(n?2i)g(0)=1,g(2)=3,if(n>2):g(n) = 3\times g(n-2) + 2 \sum_{i=2}^{\frac{n}{2}} g(n-2i) g(0)=1,g(2)=3,if(n>2):g(n)=3×g(n?2)+2i=2∑2n??g(n?2i)
5.求3x4多米诺骨牌完美覆盖数。
step1：套用4(b)的结论，g(4)=3g(2)+2g(0)=11
6.题目略
step1：当n为偶数，易知多米诺骨牌可以填充完一行，进而可以填充完整个正方体
step2：若n为奇数，且存在一个1x1的空洞位于(i,j,k)处，不妨将(, ,k)那一层单独拿出来，可以得到两个长方体，并且这两个长方体的高为偶数，可以用竖着摆的多米诺骨牌进行填充。
step3：剩下的第k层 nxn正方体的情形就如同第2题描述的情景，必定可以找到一种摆法使得除(i,j)除的空洞以外的空间进行完美填充，换言之，无论如何填充，都必定留下一个1x1x1空洞。