Рекуррентное соотношение двух переменных

[Aael]

Подскажите, что можно сделать с этим рекуррентным соотношением (желательно найти его нерекуррентный вид), чтобы увеличить скорость его вычисления:
$ \begin{array}{l} f(n,m) = 1+f(n-1,m-1)+f(n,m-1) \\ f(0,m) = f(n,0) = 0 \end{array}.$

выходит, что $f(n,m)$ есть количество узлов в совершенном бинарном дереве высотой $m$, число левых поворотов до которых (считая от вершины) меньше $n$.

[kotenok gav]

По реккурентности, получается что $f(1,2)=1+f(0,1)+f(1,1)=1+1+f(0,0)+f(1,0)=2$. А у вас, eugensk, 1.

[eugensk]

$f(n,m) = 2^m-1 \text{, при } n \ge m \ge 0$ (спасибо, kotenok gav, вот теперь всё правильно :)

При $n<m$ выходит что-то сложное, не могу сообразить.

[grizzly]

Aael в сообщении #1324318 писал(а):

Подскажите, что можно сделать с этим рекуррентным соотношением

Посмотрите A180975 с ссылками, может что-то ещё полезное попадётся.

[Aael]

grizzly, спасибо большое. Собственно, здесь Michael Boardman. The Egg-Drop Numbers (DOI: 10.2307/3219201) приводится доказательство (через производящую функцию) того, что

$$\displaystyle f(n, m)=\sum_{k=1}^{n}C_m^k$$

Еще в вестнике бгу нашел статью, там рассказывают про РС $q(m,n)=q(m-1,n)+q(m-1,n-1)=C^m_n$ и приводят несколько методов решения РС многих переменных (правда немного другого вида, без свободных коэффициентов). Попробую походить по ссылкам, поискать методы для общего вида. Спасибо еще раз!

[grizzly]

Aael
Ещё больше информации можно найти в этом обсуждении на MO..