组合计数.doc

6月1日和6月8日讨论的问题胡山立要求：做好发言准备，省队选手分二次交4, 5, 6, 7, 9, 10 题的解题报告。设计算法并编程解决以下问题：一. 某些计数问题1 先从简单而经典的单堆栈问题谈起有n列车厢a1, a2, a3, , an 从右端进入轨道，由于有堆栈D，可以改变轨道左端车厢的出轨顺序，向有多少种不同的出轨序列？a1, a2, a3, , anD问题： （1）递推关系，初始条件。（2）解。（3）等价的组合学问题。2设在圆上选择2n个（等间隔的）点，求将这些点成对连接起来，使得所得到的 n条线段不相交（没有公共点）的方法数。3 NOI 2001 福建省选手选拔赛试题2 ：盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。按售票处规定，每位购票者限购一张门票，且每张票售价50元。在排成长龙的球迷中有m个人手持面值50元的钱币，另有n 个人手持面值100元的钱币。假设售票处在开始受票时没有零钱。试问这m+n 个球迷有多少种排队方式可使售票处不致出现找不出钱的尴尬局面。4求能够由数1, 2, 3, , 2n构造且满足 x11 x12 x1n x21 x22 x2n以及x11 x21, x12 x22, ., x1n x2n 的2行n列矩阵x11 x12 x1n x21 x22 x2n的个数。5 大城市公务员在他家(A)以北m个街区和以东n个街区(B)工作，如图所示 (m = 4, n = 5).假设街区成正方块网格，如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？BA二 求解某些部分和的方法6 我们要求计算1 + 2 + 3 + + n, 而n很大（例如1000000）时，大概我们会用求和公式 S1(n) = 1 + 2 + 3 + + n = n (n+1)/2 计算，而不会直接去累加。对于 12 + 22 + 32 + + n2 , 我们有求和公式 S2 (n) = 12 + 22 + 32 + + n2 = n (n+1) (2n+1)/6现在考虑较一般点的问题 Sp (n) = 1P + 2P+ 3P + + nP （p是正整数）有求和公式吗，又如何求得它呢 （例如p = 4，7，13 等）?请编程解决（p由外部给出）。7 求通项为P次多项式f(n) = ap nP + ap-1 nP-1 + + a1n + a0的部分和 f (0) + f (1) + f (2) + + f (n) 的快速计算法。例如设 f(n) = n3 + 3 n2 -2n + 1, 对较大的N（例如N = 1000000 ）计算S (N) = f (0) + f (1) + f (2) + + f (N) 问题：方法介绍和讨论。 三 递推关系和生成函数法8确定每位数字都是奇数的n位数的个数 ，其中1和3出现偶数次。9确定用红色，白色和蓝色对1行n列棋盘的方格涂色的方法数 ，其中红方格的个数是偶数并且至少有一个蓝方格。10h (n) 表示具有n+2条边的凸多边形区域被其对角线所分成的区域数，假设没有三条对角线共点。定义h (0) = 0 , 对较大的N（例如N = 1000000