组合数学 第二章母函数与递推关系题目

母函数与递推关系习题1、 有n 阶台阶，一人从下往上走，每次走一或两级，求他走这n 级台阶的方法数。

2、 {1,2,3,}n S n = 的一个子集为交替的：如果按递增次序列出该子集的元素时，它们的奇偶性为：奇、偶、奇、偶、 。

空集也算作交替的。

求n S 的交替自己的树木。

3、 某人有n 元钱，他一天买一样东西，或一元钱的甲、或二元钱的乙、或二元钱的丙，问他用完这n 元钱有多少种方法？4、 求{,,}S a b c =∞⋅的n 排列数，要求在排列中a 与a 不相邻。

5、 设40nn i a i ==∑，0n ≥，求n a 。

6、 求1003102-⎛⎫ ⎪⎝⎭。

7、 平面上有n 条直线，其中任意两条都相交于一点，但没有三条相交于同一点，求这n 条直线将平面分成的区域数。

8、 空间中有n 个平面，其中任意两个都有唯一交线，任意三个都有唯一一个交点，但没有四个相交于同一点。

求这n 个平面将空间分成的区域数。

9、 在平面上画一个圆，然后再依次画n 条与圆都相交的直线，其中当k 是大于1的奇数时，第k 条直线只与前面(1)k -条直线中的一条在圆内相交，当k 是偶数时，第k 条直线与前面(1)k -条直线都在圆内相交，又没有三条直线在圆内相交于同一点。

求这n 直线将圆分成的区域数。

10、求{1,2,3}S =∞⋅的k 排列的个数，要求在排列中同一元素至多连续出现两次。

11、 将一个凸(1)n +边形用它的对角线划分成三角形，要求所用的对角现在多边形内部无交点，求划分的方法数。

12、 设一克、三克、七克重的砝码分别有1枚、3枚、2枚。

问用这些砝码能称出哪些重量？称每一重量又各有几种方案？13、 有两种拆分：（1）1{1,12,3,14,}S =∞⋅⋅∞⋅⋅ ；（2）23{1,2,3,}S =⋅ 。

证明对同一正整数n ，这两种拆分的拆分数相等。

14、证明：周长为2n ，边长为整数的三角形的个数等于将n 拆分成恰好三项的拆分数。

组合数学部分第1章 排列与组合例1：1)、求小于10000的含1的正整数的个数；2、)求小于10000的含0的正整数的个数；解：1)、小于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个2)、“含0”和“含1”不可直接套用。

0019含1但不含0。

在组合的习题中有许多类似的隐含的规定，要特别留神。

不含0的1位数有19个，2位数有29个，3位数有39个，4位数有49个 不含0小于10000的正整数有()()73801919999954321=--=+++个含0小于10000的正整数9999－7380=2619个。

例2：从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？解：将[1,300]分成3类：A={i|i ≡1(mod 3)}={1,4,7,…,298},B={i|i ≡2(mod 3)}={2,5,8,…,299},C={i|i ≡0(mod 3)}={3,6,9,…,300}.要满足条件，有四种解法：1)、3个数同属于A;2)、3个数同属于B ；3)、3个数同属于C;4)、A,B,C 各取一数；故共有3C(100,3)+1003=485100+1000000=1485100。

例3：（Cayley 定理：过n 个有标志顶点的数的数目等于2-n n ）1）、写出右图所对应的序列；2）、写出序列22314所对应的序列；解：1）、按照叶子节点从小到大的顺序依次去掉节点（包含与此叶子节点相连接的线），而与这个去掉的叶子节点相邻的另外一个内点值则记入序列。

如上图所示，先去掉最小的叶子节点②，与其相邻的内点为⑤，然后去掉叶子节点③，与其相邻的内点为①，直到只剩下两个节点相邻为止，则最终序列为51155.。

2）、首先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从小到大顺序依次排列并插入递增序列得到：112223344567。

2.1题（陈兴）求序列{ 0，1，8，27，3n }的母函数。

解：由序列可得到32333()23n G x x x x n x =+++++因为23111n x x x x x =++++++- 2311()'12341n x x x nx x-=++++++-设 2311()()'23(1)1n np x x x x x n x nx x-==++++-+-2222221[()]'123(1)n n p x x x x n x n x --=+++++-+设 2223212()[()]'23(1)n nq x x p x x x x n x n x -==++++-+3323231[()]'123(1)n n q x x x n x n x --=++++-+ 3233313[()]'23(1)n n x q x x x x n x n x -=+++-+ 由以上推理可知[()]'x q x =,[7*94*(6)],n n +-所以可通过求得[()]'x q x 得到序列的母函数：32()4G x x x x =++2321()()[34(3)]6n H x F x dx x x n x +==++++⎰2.2题（陈兴）已知序列343,,,,333n ⎧+⎛⎫⎛⎫⎛⎫⎫⎨⎬ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎭⎩，求母函数 解： 3*2*14*3*2(3)*(2)*(1)()3*2*13*2*13*2*1nn n n G x x +++=+++=1[3.2.1 4.3.2(3)(2)(1)]6n x n n n x ++++++211()()[3.2 4.3(3)(2)]6n F x G x dx x x n n x +==+++++⎰ 2321()()[34(3)]6n H x F x dx x x n x +==++++⎰3431()()[]6n I x H x dx x X x ++==++⎰因为23111n x x x x+=+++++-所以211()(1)61I x x x x=----所以31()[]'''61x G x x=-就是所求序列的母函数。

第二章母函数及其应用问题：对于不尽相异元素的部分排列和组合，用第一章的方法新方法：母函数方法。

基本思想：把离散的数列同多项式或幂级数一一对应起来，算。

2.1 母函数（一）母函数（1）定义【定义2.1.1】对于数列{}n a ，称无穷级数()∑∞=≡0n n n x a x G 为该数列的（普通型）母函数，简称普母函数或母函数。

（2）例【例2.1.1】有限数列rn C （r ＝0, 1, 2, …, n ）的普母函数：()x G ＝nn n n n nx C x C x C C ++++ 2210＝()nx +1【例2.1.2】无限数列{1, 1. …, 1, …}的普母函数：()x G ＝ +++++nx x x 21＝x-11（3）说明● n a 可以为有限个或无限个。

● 数列{}n a 与母函数一一对应。

{0, 1, 1, …, 1, …}↔ +++++n x x x 20＝xx -1 ● 将母函数视为形式函数，目的是利用其有关运算性质完成计数问题，故不考虑“收敛问题”。

（4）常用母函数（二） 组合问题 （1）组合的母函数【定理2.1.1】组合的母函数：设{}m m e n e n e n S ⋅⋅⋅=,,,2211 ,且n 1＋n 2＋…＋n m ＝n ，则S 的r 可重组合的母函数为()x G ＝∏∑==⎪⎪⎭⎫ ⎝⎛mi n j j i x 10＝∑=n r r r x a 0其中，r 可重组合数为rx 之系数r a ，r ＝0, 1, 2, …, n 。

理论依据：多项式的任何一项与组合结果一一对应。

【例2.1.3】设有6个红球，7个黑球，8个白球，问 （1） 共有多少种不同的选取方法，试加以枚举？ （2） 若每次从中任取3个，有多少种不同的取法？ （解）（1）元素符号化（x ，y ，z ↔红、黑、白球），元素的个数以符号的指数区分。

母函数G (x , y , z ) ＝(1＋x ＋x 2) (1＋y ) (1＋z )＝1＋(x ＋y ＋z )＋(x 2＋xy ＋xz ＋yz )＋(x 2x ＋x 2x ＋xxx )＋( x 2yz )5种情况：① 数字1表示一个球也不取的情况，共有1种方案； ② 取1个球的方案有3种，即红、黑、白三种球只取1个； ③ 取2个球的方案有4种，即2红、1红1黑、1红1白、1黑1白； ④ 取3个球的方案有3种，即2红1黑、2红1白、三色球各一； ⑤ 取4个球的方案有1种，即全取。

2.1 求序列{0，1，8，27，…3n …}的母函数。

解：()()++++++=++++++=nn n x n x x x x G x a x a x a x a a x G 3323322102780()046414321313=+-+--==-----n n n n n n n a a a a a n a n a左右同乘再连加：464:0464:0464:0464:4321543211123455012344=+-+-=+-+-=+-+-=+-+-----------n n n n n n n n n n n n a a a a a x a a a a a x a a a a a x a a a a a x母函数：()()42162036-+-=x x x x G2.2 已知序列()()3433{,,……()33,,n +……}，求母函数。

解：1(1)nx -的第k 项为：11()k n n +-- ，对于本题，n=4， ∴母函数为：41(1)x - 2.3 已知母函数G （X ）= 25431783x x x--+,求序列{ n a }解：G （X ）=)61)(91(783x x x +-+=)61()91(x Bx A ++-从而有： ⎩⎨⎧-==⇒⎩⎨⎧=-=+4778963B A B A B AG （X ）=)61(4)91(7x x +-+-G （X ）=7)999x (13322 ++++x x -4))6((-6)(-6)x (13322 +-+++x xn a =7*n )6(*49n -- 2.4．已知母函数239156xx x---，求对应的序列{}n a 。

解：母函数为239()156x G x x x -=--39(17)(18)xx x -=+- A BG(x)17x 18xA(18x)B(17x)39x=++--++=-令 A B 38A +7B =9+=⎧⎨--⎩解得：A=2 B=1所以 ii i 0i 021G(x)2*(7x)(8x)17x 18x ∞∞===+=-++-∑∑n n n a 2*(7)8=-+2.5 设n n F G 2=，其中F n 是第n 个Fibonacci 数。

第二章 母函数及其应用问题：对于不尽相异元素的部分排列和组合，用第一章的方法是比较麻烦的（参见表2.0.1）。

新方法：母函数方法，问题将显得容易多了。

其次，在求解递推关系的解、整数分拆以及证明组合恒等式时，母函数方法是一种非常重要的手段。

母函数方法的基本思想是把离散的数列同多项式或幂级数一一对应起来，从而把离散数列间的结合关系转化为多项式或幂级数之间的运算。

2.1 母 函 数（一）母函数（1）定义定义2.1.1 对于数列{}n a ，称无穷级数()∑∞=≡0n nnxax G 为该数列的（普通型）母函数，简称普母函数或母函数。

（2）例例2.1.1 有限数列C (n ,r )，r ＝0,1,2, …,n 的普母函数是()nx +1。

例2.1.2 无限数列{1，1，…，1，…}的普母函数是+++++=-nxx x x2111（3）说明● n a 可以为有限个或无限个； ● 数列{}n a 与母函数一一对应，即给定数列便得知它的母函数；反之，求得母函数则数列也随之而定；例如，无限数列{0，1，1，…，1，…}的普母函数是 +++++n x x x 20＝xx -1● 这里将母函数只看作一个形式函数，目的是利用其有关运算性质完成计数问题，故不考虑“收敛问题”，而且始终认为它是可“逐项微分”和“逐项积分”的。

（4）常用母函数（二）组合问题（1）组合的母函数定理2.1.1 组合的母函数：设{}m m e n e n e n S ⋅⋅⋅=,,,2211 ,且n 1＋ n 2＋…＋ n m ＝n ，则S 的r 可重组合的母函数为()x G ＝∏∑==⎪⎪⎭⎫ ⎝⎛mi n j ji x 10＝∑=n r r r x a 0 (2.1.1) 其中，r 可重组合数为rx 之系数r a ，r ＝0,1,2, …,n .定理2.1.1的最大优点在于：● 将无重组合与重复组合统一起来处理；● 使处理可重组合的枚举问题变得非常简单。

习题11、 基本题：1～9，14，16，19，22～23，29，312、 加强题：11～12，17，18，21，283、 关联题：10，27，4、 提高题：13，15，20，24～26，30，321-1 在1到9999之间，有多少个每位上数字全不相同而且由奇数构成的整数？（解）问题相当于求在相异元素{}9,7,5,3,1中不重复地取1个、2个、…、4个元素的所有排列数，答案为45352515P P P P +++＝5+20+60+120＝2051-2 比5400小并具有下列性质的正整数有多少个？(1) 每位的数字全不同；(2) 每位数字不同且不出现数字2与7。

（解）（1）分类统计：①一位正整数有919=P 个；②两位正整数有1919P P ⨯＝81个；③三位正整数有2919P P ⨯＝9×9×8＝648个；④千位数小于5的四位数有3914P P ⨯＝4×9×8×7＝2016个；⑤千位数等于5，百位数小于4的数有28141P P ⨯⨯＝4×8×7＝224个。

由乘法法则，满足条件的数的总个数为9＋81＋648＋2016＋224＝2978（2）仿（1），总个数为17P ＋1717P P ⨯＋2717P P ⨯＋3713P P ⨯＋26131P P ⨯⨯＝7＋49＋294＋630＋150＝11301-3 一教室有两排，每排8个坐位，今有14名学生，问按下列不同的方式入座，各有多少种坐法？(1) 规定某5人总坐在前排，某4人总在后排，但每人具体坐位不指定；(2) 要求前排至少坐5人，后排至少坐4人。

（解）（1）5人在前排就座，其坐法数为 ()58,P ，4人在后排就座，其坐法数为 ()48,P ，还空7个坐位，让剩下的54514=--个人入坐，就座方式为 ()57,P 种，由乘法法则，就座方式总数为()58,P ()48,P ()57,P ＝28 449 792 000 （2）因前排至少需坐6人，最多坐8人，后排也如此。