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

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

空集也算作交替的。

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

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

5、 设40n n 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 拆分成恰好三项的拆分数。

15、
证明：将n 拆分成k 项，并且要求考虑各项次序的个数为11k n C --。

16、 设n a 为多重集{1,2,,}S m =∞⋅ 的n -组合数，要求在组合当中，每一元素出现
偶数次。

求n a 的母函数，进而求n a 。

17、
求多重集{53S =⋅⋅黑，红,⋅2白}的5-组合数和5-排列数。

18、 求下列两个方程的整数解的个数：
123123123123()5;05,03,02;
()8;16,03,2 4.a x x x x x x b x x x x x x ++=≤≤≤≤≤≤++=≤≤≤≤≤≤ 19、
求n 位四进制数的个数，要求在其中2和3都出现偶数次。

20、 把1到n 按顺序排成一圈，然后从中取出k 个数，要求两两之间另有至少两个数。

求方法数。