研究生组合数学复习要点

研究生组合数学复习要点二、母函数1.母函数与数列的关系2.母函数与排列数、组合数的关系3.用普通型母函数解决多重集的组合问题4.用指数型母函数解决多重集的排列问题5.用母函数解递推关系式6.不定方程的整数解的个数与多重集的组合数之2三、递推关系1.常系数线性递推关系的解法（特征根法）2.用待定系数法求常系数线性非齐次递推关系的特解(前两种类型)3.列递推关系解应用题4.一般递推关系的线性化5.Fibonacci数列及其模型6.第二类Stirling数的组合意义7.Catalan数列及其解法3四、容斥原理1.容斥原理的基本形式(容斥原理、逐步淘汰原理)2.容斥原理的应用(比如解决多重集排列组合问题)3.有限制条件的排列(比如错排问题、相邻禁位排列问题、保位问题)4五、抽屉原理1.抽屉原理的几种基本形式2.抽屉原理的简单应用5六、波利亚(Pólya)定理1.置换在研究等价类计数中的作用2.将置换表为轮换之积3.Burnside引理计数公式4.Pólya定理计数公式5.Pólya定理的应用61、一位学者要在一周内安排50个小时的工作时间，而且每天至少工作5小时，问共有多少种安排方案？练习题72、n个男n个女排成一男女相间的队伍，试问有多少种不同的方案.若围成一圆桌坐下，又有多少种不同的方案？8910解用表示所求方法数.易知使得相邻格子异色的涂色方法数有其中使得首末两格同色的涂色方法有所以用m种颜色去涂棋盘,每格涂一种颜色,种,种,从而11另一解法参见教材P87例12解(1)先任意选定一个女人入座，有种方法；(2)再安排其他女人入座，使得任何两个女人之间至少有k个空座位：13此不定方程的解的个数为于是完成此步骤的方法有种.14(3)最后安排m个男人入座，有m!种方法.由乘法原理，所求的安排座位方法数为15

6、某学者每周工作6天,共42小时,每天工作的小时数是整数,且每天工作时间不少于6小时也不多于8小时,如果编排一周的工作时间表,问有多少种不同的方案？16177、将充分多的苹果、香蕉、橘子和梨进行装袋，要求每袋中苹果数是偶数，香蕉数是5的倍数，橘子最多4个，而梨的个数为0或1。如果每袋装n个水果，求装袋的种类数。18198、由字母a，b，c，d，e组成的总字母数为n的单词中，要求a与b的个数之和为偶数，问这样的单词有多少个？解设满足条件的单词个数为an

，这样的单词只有两类：一类包括偶数个a与偶数个b；另一类包括奇数个a与奇数个b.

因此{an

}对应的母函数为

20故219、把2n件相异物品放到m个不同的盒中，使得每个盒子中的物品件数均为偶数(零也是偶数)，求不同的放法种数.解相应的指母函数是22故所求放法数为2310、由数字1至9组成的每种数字至少出现1次的位数有多少个？解设所求的数为则的指母函数为24所以(此题也可用容斥原理做)2511、求由0、1、2组成的长为n的三进制串的个数,但其中的0和1不相邻(即01和10从不出现)解

设所求三进制串的个数为则(1)若首位是2,则此类三进制串有(2)若首位是1,则第二位必是1或2.若第二位是2,则此类串有若前二位是1,则第三位必是1或2.若第三位是2,则此类串有26……；若前n-2位是1,则第n-1位必是1或2.若第n-1位必是2，则此类串有若前n-1位是1,则第n位必是1或2，则此类串有2个.所以首位是1的三进制串有个.(3)若首位是0,同理可得三进制串有个.因此,得27两式相减，得定解问题求得通解代入初值得2812、有多少个长度为n的0与1串,在这些串中,既不包含子串010，也不包含子串101？解设这种数串的个数为将满足条件的数串分为两类：(1)最后两位数字相同.这种长度为n的数串可由长度为n-1的串最后一位数字重复一次而得，故这类数串的个数

(2)最后两位数字不同.这种长度为n的数串可由长度为n-2的串最后一位(设为a)重复一次，再加上与a不同的数字而得,故这类数串的个数为29于是得递推关系由Fibonacci数列,得通解代入初值,得3013、平面上有两两相交，无3线共点的n条直线,求这n条直线把平面分成多少个区域？解设这n条直线把平面分成个区域，易知条直线把平面分成去掉所给n条直线中的一条直线,则剩下的n-1个区域.线放回原处后,于是得定解问题再把去掉的那条直则在的基础上增加了n个区域,31解得显然，当n=1时，上式仍成立.故n条直线把平面分成个区域.3214、有2n个人排成一队购票，票价5元。2n个人中有n个人有5元的钱币，另外n个人有10元的钱币。开始售票时售票处没有准备找零的钱。问有多少种列队方式，使得只要有10元的人买票，售票处就有5元的钱币找零？解将有5元钱币的人赋值1，有10元钱币的人赋值-1，则该问题为：包括n个1和n个-1的2n个数构成序列，使33这2n个数的排列是多重集的排列，排列总数为的排列是：“从左向右扫描，出现-1的累计数超过1的累计数”，所以存在最小的k，使而这些排列中，不符合要求34前k个变号后，可得到一个有n+1个1和n-1个-1的序列，反之，n+1个1和n-1个-1的序列，必存在k，使得该序列的前k个数中1的个数恰比-1的个数多1.将这k个数变号，就得到一个有n个1和n个-1的序列，于是不合要求的排列与多重集的排列一一对应.这种排列有35个.故所求列队方式数为36另解把有5角钱的人用1标识,有1元钱的人用0标识,问题就转化为“由n个1和n个0组成的2n位排列中，从左向右扫描，1的累计数不小于0的累计数”.故所求序列数为3715、十个数字(0到9)和四个运算符(+,-,*,/)组成14个元素,求由其中的n个元素的排列构成一形式算术表达式的个数.解令表示n个元素排列成算术表达式的数目，则特征方程解得特征根得通解38代入初始条件得故3916、设有地址从1到n的单元，用以记录一组信息，这个信息的每个元素都占用两个单元，而且存放的地址是完全随机的，因而可能出现两个存放信息单元之间留一个空单元无法存放其它信息.求这n个单元留下空单元的平均数.解设这个平均数为并设某一个信息占用了第两个单元，第一部分有i个单元，这i个单元留下空单元把这组单元剩余的单元分成两个部分，的平均数为

第二部分有个单元，这些单元留下空单元的平均数为

于是某一个信40则留下空单元息若占用了第

两个单元，的平均数为

由于用相邻两个单元的几率相等，故

即又由41得解得（解法见教材P69例）4217、一个计算机系统把一个十进制数字串作为一个编码字，如果它包含偶数个0，就是有效的.求有效的n位编码字的个数an.解显然若末位数是1到9中某个数，则前面n-1位组成的有效数有an-1个，因此，末位数不是0的n位有效数字有

9

an-1个.若末位数是0，则这样的n位十进制数有10n-1个，

而不是有效数的有an-1个(因n-1位的有效数后面添一个0就不是有效数了),所以末位数是0的有效数有

43个.于是得递推关系即解得通解代入初始条件得故所求有效数字有个.4418、把件彼此相异的物品分给甲、乙、丙三人，使得甲至少分得两件物品，乙和丙至少分得一件物品，有多少种不同的分法？解设有N种不同的分法.因为把n件彼此相异的物品分给3个人，使得每人至少分得一件物品的方法共有种，其中使得甲恰分得一件物品的分法有45种，故4647484920、n个单位各派2名代表出席一个会议，2n名代表围一圆桌坐下.试问：(1)各单位代表入座的方案有多少种?(2)各单位的2位代表不相邻的方案有多少种?解(1)这是2n个元的圆排列,故各单位代表入座方式有(2)设这2n个人入座方式的全体为S，则{S中第i个单位的两个人相邻的入座方式}则50由容斥原理，所求方案数为51解设所求数为N，以S表示由的全排列之集，作成以A，B分别表示S中由容斥原理，5222、由a，b，c，d四个字符组成所有n位(n≥4)字符串中，a，b，c，三个字母同时出现在一个串中至少一次的这种n位字符串的个数有多少？解

设S表示由a，b，c，d构成的所有n位字符串之集。则53于是所求数为54555624、随意把一个3×9棋盘的每个方格涂成红色或蓝色,证明必有两列方格,它们的涂色方法是一样的.证用红、蓝两色去涂3×1棋盘共有种涂色方法.表示第i种涂色方法.以设K是任一个已用红色或蓝色涂了色的3×9棋盘,表示K的第i列的涂色方法,以并令由抽屉原理,必有某与第l列的涂色方法是一样的.则K的第k列57证(1)将这个等边三角形分成4个边长为的等边三角形.而每个小等边三角形内任意两点之间的距离不超过由抽屉原理，5个点必有2个点在一个小三角形中，这2个点的距离不超过58

(2)将这个等边三角形分成9个边长为的等边三角形.而每个小等边三角形内任意两点之间的距离不超过59

(3)将这个等边三角形分成个边长为的等边三角形.由抽屉原理，10个点必有2个点在一个小三角形中，这2个点的距离不超过6026、某个宴会共有2n个人出席，每个人均至少认识其中的n个人.求证:可安排这2n个人中的某4个人围圆桌而坐,使得每个人的旁边都是他所认识的人.证用平面上的点表示个人,并以V表示这个点所成之集.对V中的任意两个点,如果它们表示的两个人互相认识(不认识),则用红边(蓝边)把这两个点连结起来,这样得到一个2着色的如果的边全是红色,则结论显然成立;否则它至少有一条蓝边，设是一条蓝边,令如果则28、有n个人(n为大于等于4的偶数)举行一次聚会，参加的每个人都有偶数个(有可能是0个)熟人.证明：在这次聚会上有3人有相同个数的熟人.证用数学归纳法.n=4时，只有三种情况：(1)4