问题集8的解 到期：星期一下午9点，4月11日 问题1一个电子玩具显示4×4彩色方块的格。在所有的时间内，四个是红色的，四个是绿 色的，四个是蓝色的，四个是黄色的。例如这里是一个可能的配置： R B R Y B G G B R R B 这个配置有多少种可能？ 解：这个等价于包括4个R,4个G,4个B和4个Y的序列的个数，也就是： 16! (4!)4 (b)在这个显示下，有5个按钮，序号为1,2,3,4,5。玩家可能按一个序列的按钮：然 而，同样的按钮不能在同一行按两次。有多少个按钮按的序列是可能的。 解：对于第一个按钮按下有5种选择，对于每个后续的按钮有4种选择。因此，按钮按下 的不同的序列是5·4。 (©)每个按钮按下以一种负责并不是随机的方式搅乱着色的方块。证明，存在不同的序列32 次按钮的按下使得产生同样的配置，如果题目初始是在以上显示的状态。 解：我们使用鸽巢原理。令A是所有32按钮按下的序列，令B是所有的配置，令fA→B 映射每个按钮按下的序列到其产生的配置。现在： |A>42>16!>B 因此，通过鸽巢原理，f不是单射的：也就是存在不同的元素al,a2∈A以便fa1)=fa2)。 用其他话说，存在两个不同的按钮按下序列产生同样的配置。 问题2假设你有五个6面的骰子，其被着色为红色，蓝色，绿色，白色和黑色。一次滚动 指定每次投掷的值。例如，一次滚动是： PDF文件使用"pdfFactory Pro"试用版本创建ww,fineprint.cn
问题集 8 的解 到期：星期一下午 9 点，4 月 11 日 问题 1 一个电子玩具显示 4×4 彩色方块的格。在所有的时间内，四个是红色的，四个是绿 色的，四个是蓝色的，四个是黄色的。例如这里是一个可能的配置： 这个配置有多少种可能？ 解：这个等价于包括 4 个 R，4 个 G，4 个 B 和 4 个 Y 的序列的个数，也就是： (b) 在这个显示下，有 5 个按钮，序号为 1，2，3，4，5。玩家可能按一个序列的按钮；然 而，同样的按钮不能在同一行按两次。有多少个 n 按钮按的序列是可能的。 解：对于第一个按钮按下有 5 种选择，对于每个后续的按钮有 4 种选择。因此，n 按钮按下 的不同的序列是 5· 4n-1。 (c) 每个按钮按下以一种负责并不是随机的方式搅乱着色的方块。证明，存在不同的序列 32 次按钮的按下使得产生同样的配置，如果题目初始是在以上显示的状态。 解：我们使用鸽巢原理。令 A 是所有 32 按钮按下的序列，令 B 是所有的配置，令 f: AàB 映射每个按钮按下的序列到其产生的配置。现在： 因此，通过鸽巢原理， f 不是单射的；也就是存在不同的元素 a1, a2 ∈ A 以便 f(a1) = f(a2)。 用其他话说，存在两个不同的按钮按下序列产生同样的配置。 问题 2 假设你有五个 6 面的骰子，其被着色为红色，蓝色，绿色，白色和黑色。一次滚动 指定每次投掷的值。例如，一次滚动是： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
31415 red green blue white black 对以下问题，你不需要化简你的回答，但是要简短解释你的原因。 (a)有多少滚动每次投掷的值都不一样？ 例如：(1,2,3,4,5)是这种类型的投掷，但是(1,1,2,3,4)不是。 解：这样的投掷是6·5·4·3·2 (b)有多少个滚动两个骰子有同样的值，且剩余的三个骰子有不同的值？ 例如：(6,1,6,2,3)是这种类型的，但是(1,1,2,2,3)和(4,4,4,5,6)不是。 解：存在 （2)个可能对的滚动，其也许有同样的值且6种对这个值的可能。对于剩下的三 次滚动存在5·4·3可能不同的值。因此这类型的滚动的个数是： 5 6.5.4.3 2 (©)有多少次滚动中两个骰子有同样的值，两个不同的骰子有一个第二个值，剩余的投掷 一个第三个值？ 例子：(6,1,2,1,2)是这中类型的滚动，但是(4,4,4,4,5)和(5,5,5,6,6) 不是。 5 3 解：存在（2)两个值也许重复的值。存在2)滚动，这里大的重复的值也许出现且2)剩 余的滚动这里更小的重复值也许出现。仅存在一个剩余的工动，这里没有出现重复的值，其 有4个剩余的值来取。因此，这种类型的滚动的数目是： 问题3这个问题关心从52张牌中处理七张牌把。 (a)多少种不同的牌把是可能的？ 解：从52张牌中取7张牌就产生了一把牌。因此通过子集规则(Subset Rule)得到可能的把数 是： PDF文件使用"pdfFactory Pro”试用版本创建ww.fineprint.cn
对以下问题，你不需要化简你的回答，但是要简短解释你的原因。 (a) 有多少滚动每次投掷的值都不一样？ 例如：（1，2，3，4，5）是这种类型的投掷，但是（1，1，2，3，4）不是。 解：这样的投掷是 6 ·5 ·4 ·3 ·2 (b) 有多少个滚动两个骰子有同样的值，且剩余的三个骰子有不同的值？ 例如：（6，1，6，2，3）是这种类型的，但是（1，1，2，2，3）和（4，4，4，5，6）不是。 解：存在 个可能对的滚动，其也许有同样的值且 6 种对这个值的可能。对于剩下的三 次滚动存在 5·4·3 可能不同的值。 因此这类型的滚动的个数是： (c) 有多少次滚动中两个骰子有同样的值，两个不同的骰子有一个第二个值，剩余的投掷 一个第三个值？ 例子：（6，1，2，1，2）是这中类型的滚动，但是（4，4，4，4，5）和（5，5，5，6，6） 不是。 解：存在 两个值也许重复的值。存在 滚动，这里大的重复的值也许出现且 剩 余的滚动这里更小的重复值也许出现。仅存在一个剩余的工动，这里没有出现重复的值，其 有 4 个剩余的值来取。因此，这种类型的滚动的数目是： 问题 3 这个问题关心从 52 张牌中处理七张牌把。 (a) 多少种不同的牌把是可能的？ 解：从 52 张牌中取 7 张牌就产生了一把牌。因此通过子集规则(Subset Rule)得到可能的把数 是： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
52 7 (b)有多少把牌中包括3对和没有3张或4张一样的？ 解：对指定的序列存在一个双射： 13 ●对的值，这个可能在 、3 中方式中选择。 4 最低值对的花色，能在2 方式中选择。 /4 ● 中间值的对的花色，能在 2 方式中选择。 4 ● 最高值对的花色，可能漴2) 方式中选择。 。剩余卡片的值，能在10种方式种选择。 。剩余卡片的花色，能在4种方式种选择。 因此，7张牌扑克把的个数包括三对且没有三个或者四个是一样的。 .10.4 3 2 通过一般乘法准则得到。 (©)有多少手牌所有的牌都有同样的花色？ 解：和指定的序列存在双射： ●所有牌的花色，能以4种方式选择。 /13 ● 牌的值，能有 7 种方式。 3 因此7张牌能以4· 、7 方式选择。 (d)有多少手有5或者更多脸的牌？(Jack,王后以及国王是脸牌) 解：在有恰好k个脸牌和对的把之间存在双射： PDF文件使用"pdfFactory Pro”试用版本创建ww,fineprint..cn
(b) 有多少把牌中包括 3 对和没有 3 张或 4 张一样的？ 解：对指定的序列存在一个双射： l 对的值，这个可能在 中方式中选择。 l 最低值对的花色，能在 方式中选择。 l 中间值的对的花色，能在 方式中选择。 l 最高值对的花色，可能漴 方式中选择。 l 剩余卡片的值，能在 10 种方式种选择。 l 剩余卡片的花色，能在 4 种方式种选择。 因此，7 张牌扑克把的个数包括三对且没有三个或者四个是一样的。 通过一般乘法准则得到。 (c) 有多少手牌所有的牌都有同样的花色？ 解：和指定的序列存在双射： l 所有牌的花色，能以 4 种方式选择。 l 牌的值，能有 种方式。 因此 7 张牌能以 4 · 方式选择。 (d) 有多少手有 5 或者更多脸的牌？（Jack，王后以及国王是脸牌） 解：在有恰好 k 个脸牌和对的把之间存在双射： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
12 一个k脸牌的集合，能被在 种方式选择。 40 ● 一个7-k标号的牌，能被以 7-k 方式选择。 因此，存在 ()(0) 把牌恰好有k张脸牌。由加法规则，存在 ()()+()()+()(0 把有5,6，和7的脸牌。 问题4讲义描述了一个生气的技巧，在其中，观众从一副牌种选择5张牌，助手在同样的 顺序揭开4张牌，魔术师判定最后一张牌。 现在假设存在两副牌，一个有蓝背，令一个有黑背。正如以前，观众选择5张牌。助理 以同样的次序翻开其中的4张牌。（魔术师允许看这些牌的两边。）魔术师必须判定花色，值， 和剩余牌的后背颜色。 (a)证明这是可能的。 解：构建一个二部图，对每个5张牌的可能集合和对每个在右边的可能的4张牌的序列的顶 点。在有5张牌的集合和4张牌的序列放一条连线，如果在序列中的每张牌也在集合中。换 句话说，存在一个5张牌的集合和4张牌的序列的边，如果助理能翻出观众提供的4的序列 选择那个5的集合。 现在魔术技巧是可能的，如果存在在左边的顶点的匹配。特别的，观众挑出5张牌的集合。 那么助手翻出4张牌匹配的序列。最后，魔术师在一个匹配的集合中命名剩余的卡片。 我们能使用Hl定理直接证明要求的匹配的存在（正如在笔记中）或者使用一个定理（正如在 演讲中)： 推论如果每个在二部图左边的顶点有度c和每个在右边的顶点有度d,那么对左边的顶点 存在一个匹配，如果c≥d心0. 这里我们将使用推论。在这种情况中，每个在左边的顶点有度c=5·4·3·2=120, 因为助理能揭露任何5张牌中的一张，然后4张牌，3张牌，最后2张牌。每个在右边的顶 点的度是d=104-4=100,因为第五张牌能是在两副牌中的除在序列中的四张牌外的任 何一张牌。因此，通过推论的在左边的顶点的匹配是存在的，且技巧被完成。 (6)附加题：描述一种可行的方法来进行这个技巧。（我们没有这个问题的解！） PDF文件使用"pdfFactory Pro”试用版本创建w.fineprint.cn
l 一个 k 脸牌的集合，能被在 种方式选择。 l 一个 7-k 标号的牌，能被以 方式选择。 因此， 存 在 把牌恰好 有 k 张脸牌 。 由 加法规则 ， 存 在 把有 5，6，和 7 的脸牌。 问题 4 讲义描述了一个生气的技巧，在其中，观众从一副牌种选择 5 张牌，助手在同样的 顺序揭开 4 张牌，魔术师判定最后一张牌。 现在假设存在两副牌，一个有蓝背，令一个有黑背。正如以前，观众选择 5 张牌。助理 以同样的次序翻开其中的 4 张牌。（魔术师允许看这些牌的两边。）魔术师必须判定花色，值， 和剩余牌的后背颜色。 (a) 证明这是可能的。 解：构建一个二部图，对每个 5 张牌的可能集合和对每个在右边的可能的 4 张牌的序列的顶 点。在有 5 张牌的集合和 4 张牌的序列放一条连线，如果在序列中的每张牌也在集合中。换 句话说，存在一个 5 张牌的集合和 4 张牌的序列的边，如果助理能翻出观众提供的 4 的序列 选择那个 5 的集合。 现在魔术技巧是可能的，如果存在在左边的顶点的匹配。特别的，观众挑出 5 张牌的集合。 那么助手翻出 4 张牌匹配的序列。最后，魔术师在一个匹配的集合中命名剩余的卡片。 我们能使用 Hall 定理直接证明要求的匹配的存在(正如在笔记中)或者使用一个定理(正如在 演讲中)： 推论 如果每个在二部图左边的顶点有度 c 和每个在右边的顶点有度 d，那么对左边的顶点 存在一个匹配，如果 c ≥ d> 0. 这里我们将使用推论。在这种情况中，每个在左边的顶点有度 c = 5· 4 ·3 ·2 = 120， 因为助理能揭露任何 5 张牌中的一张，然后 4 张牌，3 张牌，最后 2 张牌。每个在右边的顶 点的度是 d = 104 -4 = 100，因为第五张牌能是在两副牌中的除在序列中的四张牌外的任 何一张牌。因此，通过推论的在左边的顶点的匹配是存在的，且技巧被完成。 (b) 附加题：描述一种可行的方法来进行这个技巧。（我们没有这个问题的解！） PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
问题5McGi11 icuddy女士没有宠物的集合从来不出外面。特别： ●她带3,4,5只狗。 ●她带正整数个鸣鸟，这些总是成对出现。 ●她也许或者也许不带她的鳄鱼Freddy。 令T表示个能陪伴她的宠物的不同集合的个数。例如，T6=2因为在6个宠物中存在2 个可能的集合。 ●3只狗，2个鸣鸟，1个鳄鱼 ●4只狗，2只鸣鸟，0个鳄鱼 (a)给出一个对序列(To,T,T2,T,…,)的生成函数的闭形。 解 T(x)=(x3+x4+x5)·(x2+z4+x6+x8+.): + collections of dogs collections of songbirds collections of gators 、22 =3++)11+四 x5+x6+x7 1-x 第二个方程从几何级数的和的公式得到。最后一步是化简。 (b)从这个生成函数，对T寻找一个闭形表达式。（你的回答涉及到几种情况.） 解 x5+x6+x7 =(5+x6+x)(1+x+x3+x3+.) 1-E =x5+2x6+3x7+3x8+3x9+. 因此，我们有： 0 0≤n≤4 1 n=5 Tn= 2 n=6 3 n≥7 PDF文件使用"pdfFactory Pro”试用版本创建ww.fineprint.cn
问题 5 McGillicuddy 女士没有宠物的集合从来不出外面。特别： l 她带 3，4，5 只狗。 l 她带正整数个鸣鸟，这些总是成对出现。 l 她也许或者也许不带她的鳄鱼 Freddy。 令 Tn表示 n 个能陪伴她的宠物的不同集合的个数。例如，T6 = 2 因为在 6 个宠物中存在 2 个可能的集合。 l 3 只狗，2 个鸣鸟，1 个鳄鱼 l 4 只狗，2 只鸣鸟，0 个鳄鱼 (a) 给出一个对序列(T0,T1,T2,T3,…,)的生成函数的闭形。 解 。 第二个方程从几何级数的和的公式得到。最后一步是化简。 (b) 从这个生成函数，对 Tn寻找一个闭形表达式。(你的回答涉及到几种情况.) 解 。 因此，我们有： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
问题6在这个问题种，我们将使用生成函数来求解递推： to =0 t1=1 tn =5tn-1-6tn-2 (forn≥2) (a)寻找生成函数F(x)的闭形，对于序列： (to,t1,t2,. 解：从递推等式得到，这是精确的序列： (0,1,5t1-6to,5t2-6t1,5t3-6t2,. 我们能根据生成函数F(x)表达这个序列： 0, 3ta, 501, 52. 53 0,0. -6fo, -6t1: -6t2, 一-6x2F(x) -(0,1. 0. D. 0. 。。 ）一x -0,5t011,51-6t05t26t1,5tg-6t2:)>1x) 第二项是正确的，5to+1=1,因为to=0。因此我们有方程： F(x)=5xF(x)-6x2F(x)+x 对F(x)求解这个方程给出： F(x)= c 1-5x+6x2 (b)重写这个生成函数为分数形式的和： C 1-rx 这里c和r是常数。 解：分解分母给出1-5x+6x2=(1-2x)(1-3x)。因此我们能重写分数为形式： T c d 1-5t+6x2=1-2元 1-3x PDF文件使用"pdfFactory Pro"试用版本创建www,fineprint..cn
问题 6 在这个问题种，我们将使用生成函数来求解递推： (a) 寻找生成函数 F(x)的闭形，对于序列： 解：从递推等式得到，这是精确的序列： 我们能根据生成函数 F(x) 表达这个序列: 第二项是正确的，5t0 + 1 = 1，因为 t0 = 0。因此我们有方程： 对 F(x)求解这个方程给出： (b) 重写这个生成函数为分数形式的和： 这里 c 和 r 是常数。 解：分解分母给出 1-5x +6x2 = (1-2x)(1-3x)。因此我们能重写分数为形式： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
替换x=0给出方程c+d=0。替换X=1给出1/2=一c-d/2或者等价的，2c+d=-1。 求解这个线性方程系统给出c=-1且d=1。因此，我们有： -1 1 F(x)= 1-2x +1-3元 (c)使用事实扩展每个分数： 1 =1+rx+r2x2+r3x3+. 1-rx 组合这些表达式获得对t的闭形表达式。 解： F(x)=-20-21x-22x2-23x3-. +30+31x+32x2+33x3+.. =(30-2)+(31-21)x+(32-22)x2-(33-23)x3-.. 因此，t=3”-2 问题7以下是一个等式的组合证明。什么是等式？ 证明：Stiky Peterson拥有n个蝾螈，t个蟾蜍，s个鼻涕虫。方便地，他和其他ntt+s学 生生活在一个宿舍中。（这些学生是不同的，但是同样种类的动物是没有区别的。）Stinky 想要把一个动物放到他的邻居的床上。令W是他能做的所有方式的集合。 在一方面，他能首先判断谁得到了鼻涕虫。然后，他能判断在他的剩下的邻居中谁能得 到一个蟾蜍。因此W|等于在左边的表达式。 在另一方面，Stinky能首先判定那个人应该得到蝾螈和鼻涕虫，然后，从这些中判定 谁真正的应该得到一个蝾螈。这个说明|W|是等于在右边的表达式。 既然两个表达式等于W,它们必须互相相等。 (组合证明是真正的证明。它们不仅严谨，而且传达一种直觉上的理解，一个纯粹的算 术证明也许不能发现。然而，组合证明通常比这一个有更少的颜色。) 解： (++)()=(t）( 问题8考虑以下等式： PDF文件使用"pdfFactory Pro”试用版本创建ww,fineprint.cn
替换 x = 0 给出方程 c + d = 0。替换 x = 1 给出 1/2＝ －c-d/2 或者等价的，2c+d = -1。 求解这个线性方程系统给出 c=-1 且 d=1。因此，我们有： (c) 使用事实扩展每个分数： 组合这些表达式获得对 tn的闭形表达式。 解： 因此，tn = 3n -2n 问题 7 以下是一个等式的组合证明。什么是等式？ 证明：Stiky Peterson 拥有 n 个 蝾螈，t 个蟾蜍, s 个鼻涕虫。方便地，他和其他 n+t+s 学 生生活在一个宿舍中。（这些学生是不同的，但是同样种类的动物是没有区别的。）Stinky 想要把一个动物放到他的邻居的床上。令 W 是他能做的所有方式的集合。 在一方面，他能首先判断谁得到了鼻涕虫。然后，他能判断在他的剩下的邻居中谁能得 到一个蟾蜍。因此|W|等于在左边的表达式。 在另一方面，Stinky 能首先判定那个人应该得到蝾螈和鼻涕虫，然后，从这些中判定 谁真正的应该得到一个蝾螈。这个说明|W| 是等于在右边的表达式。 既然两个表达式等于|W|，它们必须互相相等。 (组合证明是真正的证明。它们不仅严谨，而且传达一种直觉上的理解，一个纯粹的算 术证明也许不能发现。然而，组合证明通常比这一个有更少的颜色。) 解： 问题 8 考虑以下等式： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
(4)-三)(4) () (a)描述一个二进制序列的集合S它的大小是左边给出的表达式的值。 解：令S是所有的恰有n+1个1的2n比特序列。 (b)描述一个分解S到不相交子集T,…,T的方法，以便： 特别的，清晰说明那个在S中的元素是在集合Tk中，并解释为什么|T满足等式。 解：令T包括在前面的n个位置恰好有k个零的2比特序列。每个这样的序列有nk个1 在前面的n个位置，因此k+1个1在最后的n个位置。存在 (k)方式选择前面的n个比 n 特以及k+1 方式末运择最后的个比特，且在所有中在在风)(k十1） 个元素。 (b)解释为什么等式(*)逻辑上满足。 解，既然S等于T0U.UTn-1的交集的集合，根据求和规则涵。 S=ToU...U Tn-1 从两个前面的部分换结果给出等式(*)， PDF文件使用"pdfFactory Pro”试用版本创建ww,fineprint.cn
(a) 描述一个二进制序列的集合 S 它的大小是左边给出的表达式的值。 解：令 S 是所有的恰有 n+1 个 1 的 2n 比特序列。 (b) 描述一个分解 S 到不相交子集 T0,…,Tn-1的方法，以便： 特别的，清晰说明那个在 S 中的元素是在集合 Tk中，并解释为什么|Tk|满足等式。 解：令 Tk包括在前面的 n 个位置恰好有 k 个零的 2n 比特序列。每个这样的序列有 n-k 个 1 在前面的 n 个位置，因此 k+1 个 1 在最后的 n 个位置。存在 方式选择前面的 n 个比 特以及 方式来选择最后的 n 个比特，且在所有中存在 个元素。 (b) 解释为什么等式(*)逻辑上满足。 解：既然 S 等于 的交集的集合，根据求和规则蕴涵， 从两个前面的部分换结果给出等式（*）. PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn