继续考虑Lottery问题的第三类（有序、可重复），一个同学根据下边的图列出了一个递归方程如下：
设前n个自然数填充m个空，按照要求有T(n, m)种填充方法。图中只给出了n=3, m=3的情况，树的高度为m，从根到每一个叶节点的路径上的标号序列就是一种方法，所以叶节点的个数即为填充方法的个数。用蓝线将图分成两半，则可以发现，左边的子树与T(3, 2)相同，右边子树结构与T(2, 3)相同。可以想象对任意n>=2, m>=2这个式子都成立。
一行行列举T(n, m)的值（按每行m+n的值相等），就可以发现跟杨辉三角很相似。可以证明这个方程的解就是
不过，可不可以在不知道结果的情况下把它解出来呢？
This entry was posted
on Tuesday, November 14th, 2006 at 9:34 pm and is filed under Algorithm.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
ft a ft, 竟然在blog上写这种东西…
不事先猜答案的话，可以用母函数方法，直接把结果算出来
呵呵，就是在等人来给解答呢:-P
如果不太复杂，把答案email给我吧？想看看，多谢