Lottery问题的递归方程

继续考虑Lottery问题的第三类（有序、可重复），一个同学根据下边的图列出了一个递归方程如下：

T(n, m) = \left\{ \begin{array}{ll} T(n – 1, m) + T(n, m – 1) & a \geq 2, b \geq 2\\ 1 & n = 1\\ n & m = 1 \end{array} \right.

设前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的值相等），就可以发现跟杨辉三角很相似。可以证明这个方程的解就是

C_{n+m-1}^m

不过，可不可以在不知道结果的情况下把它解出来呢？