对台阶问题与一类不定方程问题的探讨.docVIP

对台阶问题与一类不定方程问题的探讨 蒋晓云 （广西桂林师专数学与计算机科学系 广西 桂林 541001） 【摘要】文献[1]研究台阶问题时提出了它的两个等价命题，笔者论证了其中的不定方程问题与台阶问题是不等价的，对一般台阶问题和这一类不定方程作了深入讨论，并彻底解决了这两类问题。 【关键词】台阶问题；不定方程；递推数列 中图分类号:Ｏ29 1 台阶问题 台阶问题是一个经典名题，建立它的数学模型,可以用建立递推关系式、差分方程、母函数方法等等，但推广到一般楼梯模型后，求解其通项公式相当复杂，查阅专题文献，只介绍一般台阶问题求解方法，没有给出通项公式。 台阶问题：某楼梯有n级台阶,某人一步最多迈三级,问有多少种不同的方式上楼? 引进递归思想，我们就可找到简单的方法：设上ｎ级台阶的方法有种，某人第1步可迈一至三级。第1步迈一级，而后上n-1级，有种上法；第1步迈二级,而后上n-2级，有种上法；第1步迈三级，而后上n-3级，有种上法。从而得且，为了表述方便规定。 更一般情况： 一般台阶问题：某楼梯有ｎ(ｎ≥1)级台阶，某人一步最多迈ｍ(ｎ≥ｍ≥1)级,有多少种不同的方案上楼。 设上ｎ级台阶的方案有种，则(ｎ≥ｍ)，为了表述方便规定 且有(k≤m) 文献[1]提到：不定方程非负解的个数问题，它等价于台阶问题的命题。分析如下： 设迈i(1≤i≤ｍ)级的步数为次,则可得方程非负解的个数，即为台阶问题的解。 反之，台阶问题的解也即是这类不定方程的非负解的个数,解决了台阶问题,也就解决了这类不定方程的非负解的个数问题,亦即这类不定方程解的个数,可由台阶数列表示。 其实，不定方程问题与台阶问题不是等价命题。 我们给出一个反例：用枚举法写出的所有非负解只有{5，0}，{3，1}，{1，2}，共三个，而m=2的台阶问题f(5)=8。究其原因：不定方程的非负解是不考虑次序的（组合问题），而台阶问题是要考虑次序的（排列问题），如反例中的迈2级台阶步数1次,它在不定方程非负解中只有一组解{3，1}，它在台阶问题上就随着迈2级1次的“位置”不同有如下四种不同的排列方式：（2，1，1，1），（1，2，1，1），（1，1，2，1），（1，1，1，2）。 文献[1]提到的另一个与台阶问题等价的命题是： 连续面值的币值兑换问题： 假设某种货币有1元至ｍ元的各种面值,现要取出ｎ元,有多少种取法。 面值相同的两张货币看作不同的，它就等价于台阶问题（排列问题）；如果面值相同的两张货币看作相同的（组合问题），上述问题与不定方程问题等价。我认为上述命应叙述清楚，避免产生二义性。 2 差分方程方法 我们也可由递推公式得到差分方程： ，其特征方程为：，三个特征根为: ， 互不相同。因此，差分方程的通解为：。可由初始条件，来确定系数C1，C2，C3 取。这时可以得到通项公式，。 从通项公式的表达式看出，这是一个实用性很差的“坏公式”。而且方法不宜推广到一般的台阶问题。 3 一般的台阶问题的求解 现在我们来看一般台阶问题的解， 作形式幂级数： 由于有递推关系： 上式两端同乘以并求和： 又由于,从中解出生成函数： 我们得到一般台阶问题的解就是的形式幂级数展开式中的系数。函数的展开是有些困难的，表达式复杂，来之不易，但我们终于得到了通项公式： 从而我们也得到原台阶问题的解： 。 4 不定方程问题 设不定方程非负解的个数为a(n)，作形式幂级数： = 把这个式子展开以后，它的每一项都是如下形式： ， 其中来自第1个因式，来自第2个因式 ,…, 来自第m个因式,且 都是非负整数，不难看出的展开式中的系数就是方程 的非负解的个数，可以把变形为： = = == 我们得到不定方程 的非负解的个数a(n)就是 的形式幂级数展开式中的系数。 更一般的情况，不定方程 的非负解的个数是 的形式幂级数展开式中的系数。 参考文献： [1] 李辉,吕学强. 台阶问题及其等价命题[J]. 辽宁师专学报,2000,2(3):6-7. [2] 史济怀.母函数[M] .上海：上海教育出版社,1983 作者简介：蒋晓云，1963，男，广西桂林人，桂林师专数学与计算机科学系副教授，桂林市21世纪园丁工程导师，基础教育改革专家成员组成员，主要从事数学与计算机科学教育研究。 相关研究课题 课题：高师数学专业同步实验课程教材建设研究与实践，新世纪广西高等教育教学改革工程立项课题，2000年立项，2004年10月通过验收结题。（主项人：蒋晓云） 课题：同步数学实验，广西高等学校重点教材立项项目。2003年12月立项，正在编写（主项人、主编：蒋晓云） 联系电话025南京） 0773-2855010或 3910080