研究生组合数学复习要点..教学文稿.ppt

解 设所求数为N，以S表示(biǎoshì)由 的全排列(páiliè)之集， 作成(zuòchéng) 以A，B分别表示S中 由容斥原理， * 第五十一页，共71页。 22、由a，b，c，d四个字符组成所有n位(n≥4)字符串中，a，b，c，三个字母(zìmǔ)同时出现在一个串中至少一次的这种n位字符串的个数有多少？ 解 设S表示(biǎoshì)由a，b，c，d构成的所有n位字符串之集。 则 * 第五十二页，共71页。 于是(yúshì)所求数为 * 第五十三页，共71页。 * 第五十四页，共71页。 * 第五十五页，共71页。 24、随意把一个3×9棋盘的每个方格涂成红色或蓝色,证明必有两列方格,它们(tā men)的涂色方法是一样的. 证 用红、蓝两色去涂3×1棋盘共有 种涂色方法. 表示第i种涂色方法. 以 设K是任一个已用红色(hóngsè)或蓝色涂了色的3×9棋盘, 表示(biǎoshì)K的第i列的涂色方法, 以 并令 由抽屉原理,必有某 与第l列的涂色方法是一样的. 则K的第k列 * 第五十六页，共71页。 第五十七页，共71页。 证 (1)将这个(zhè ge)等边三角形分成4个边长为 的等边三角形. 而每个小等边三角形内任意两点之间的距离(jùlí)不超过 由抽屉原理(yuánlǐ)，5个点必有2个点在一个小三角形中， 这2个点的距离不超过 * 第五十八页，共71页。 (2)将这个(zhè ge)等边三角形分成9个边长为 的等边三角形. 而每个小等边三角形内任意两点之间的距离(jùlí)不超过 * 第五十九页，共71页。 (3)将这个(zhè ge)等边三角形分成 个边长为 的等边三角形. 由抽屉(chōu ti)原理，10个点必有2个点在一个小三角形中， 这2个点的距离(jùlí)不超过 * 第六十页，共71页。 26、某个宴会共有2n个人出席，每个人均至少认识其中的n个人. 求证(qiúzhèng): 可安排这2n个人中的某4个人围圆桌而坐, 使得每个人的旁边都是他所认识的人. 证 用平面上的点表示个人, 并以V表示这个点所成之集. 对V中的任意两个点, 如果它们表示的两个人互相认识(不认识), 则用红边(蓝边)把这两个点连结起来, 这样得到一个2着色的 如果 的边全是红色, 则结论显然成立; 否则它至少有一条蓝边， 设 是一条蓝边, 令 第六十一页，共71页。 如果(rúguǒ) 则 第六十二页，共71页。 第六十三页，共71页。 第六十四页，共71页。 8、由字母a，b，c，d，e组成(zǔ chénɡ)的总字母数为n的单词中，要求a与b的个数之和为偶数，问这样的单词有多少个？ 解 设满足条件的单词(dāncí)个数为an ，这样的单词(dāncí)只有两类：一类包括偶数个a与偶数个b；另一类包括奇数个a与奇数个b. 因此{an }对应(duìyìng)的母函数为 * 第十九页，共71页。 故 * 第二十页，共71页。 9、把2n件相异物品放到m个不同的盒中，使得每个盒子(hé zi)中的物品件数均为偶数(零也是偶数)，求不同的放法种数. 解 相应(xiāngyīng)的指母函数是 * 第二十一页，共71页。 故所求放法数为 * 第二十二页，共71页。 10、由数字(shùzì)1至9组成的每种数字(shùzì)至少出现1次的 位数有多少(duōshǎo)个？ 解 设所求的数为 则 的指母函数(hánshù)为 * 第二十三页，共71页。 所以(suǒyǐ) (此题也可用容斥原理(yuánlǐ)做) * 第二十四页，共71页。 11、求由0、1、2组成的长为n的三进制串的个数,但其中的0和1不相邻(即01和10从不(cónɡ bù)出现) 解 设所求三进制串的个数为 则 (1)若首位(shǒu wèi)是2,则此类三进制串有 (2)若首位(shǒu wèi)是1,则第二位必是1或2. 若第二位是2,则此类串有 若前二位是1,则第三位必是1或2. 若第三位是2,则此类串有 * 第二十五页，共71页。 ……；若前n-2位是1,则第n-1位必是1或2. 若第n-1位必是2，则此类串有 若前n-1位是1,则第n位必是1或2，则此类串有2个. 所以(suǒyǐ)首位是1的三进制串有 个. (3)若首位(shǒu wèi)是0,同理可得三进制串有 个. 因此(yīncǐ), 得 * 第二十六页，