Двумерная последовательность, заданная рекуррентно

[Rubik]

Есть такая двумерная последовательность (или как это грамотно называется) $\{\Phi_m^n\}:\Phi_1^1=1;\Phi_m^n=\sum\limits_{j=1}^{n-1}\Phi_m^j+\sum\limits_{i=1}^{m-1}\Phi_i^n$. Требуется найти общий член $\Phi_m^n$.
Очевидно, что $\Phi_n^m=\Phi_m^n$, т. е. формула общего члена должна быть симметрична относительно $m$и $n$. При $m>1$ $\Phi_m^0=2^{m-2}$. А вот что делать, со всей остальной плоскостью?

[Sonic86]

В принципе, можете найти рекуррентное соотношение для $\Phi_m^n$, не содержащее сумм (для его построения сначала рассмотрите разность $\Phi_m^n$ по одному аргументу) и потом постройте двумерную производящую функцию и потом дифференцируйте ее, в принципе там все получается, только очень страшные формулы (я не досчитал).
Вообще, если есть где-то книжка с 2-мерными линейными рекуррентными соотношениями - нужно обращаться к ней, я умею решать только одномерные Если кто знает - подскажите!

[RIP]

A035002

[deep blue]

Получилось упростить метод Sonic86, подглядывая в oeis. Из
$\{\Phi_m^n\}:\Phi_0^0=1;\Phi_m^n=\sum\limits_{j=0}^{n-1}\Phi_m^j+\sum\limits_{i=0}^{m-1}\Phi_i^n$
Вполне ясно следует уравнение, которому должна удовлетворять ПФ:
$F \left( x,y \right) ={\frac {xF \left( x,y \right) }{1-x}}+{\frac {yF \left( x,y \right) }{1-y}}+1$
Откуда
$F \left( x,y \right) ={\frac { \left( x-1 \right) \left( y-1 \right) }{1-2\,x-2\,y+3\,xy}} $
Поскольку функция рациональна, то можно сразу получить из нее простое (без сумм) рекуррентное соотношение, которому должны удовлетворять ее коэффициенты.
$\left( 1-2\,x-2\,y+3\,xy \right) F \left( x,y \right) =1-y \left( 1-x \right) $
Откуда очевидно, что для $n,m>1$ выполняется:
$\Phi_m^n-2\Phi_m^{n-1}-2\Phi_{m-1}^n+3\Phi_{m-1}^{n-1}= 0$

P.S. А в статье по ссылке из oeis, там из ПФ сразу получают явную формулу для $\Phi_n^m$. В принципе, понятно как это сделать, надо одну из переменных в ПФ положить за параметр и т. д.

[Sonic86]

deep blue писал(а):

Откуда очевидно, что для $n,m>1$ выполняется:
$\Phi_m^n-2\Phi_m^{n-1}-2\Phi_{m-1}^n+3\Phi_{m-1}^{n-1}= 0$

Ага! А я разность рассматривал
Только у меня получилось $\Phi_m^n-2\Phi_m^{n-1}-2\Phi_{m-1}^n+3\Phi_{m-1}^{n-1}= [n=m=1]$ для $n,m>1$ (может я ошибся?)
Интересно, есть ли методы решения линейных двумерных рекуррентностей? Соответствующий диффур имеет вид $\frac{\partial ^2 f}{\partial x^2} = 2\frac{\partial f}{\partial t}$ и решается методом разделения переменных. Ну я и попробовал взять $\Phi_m^n = a^mb^n$, но тогда получается характеристическое уравнение от 2-х переменных, дальше в общем случае неясно как (я наверное какую-то деталь упустил), в данном случае по симметрии $a=b, k=1;3$ - и $\Phi_m^n = C+D3^{n+m}$, что явно лажа. И частное решение как искать (потому что правая часть равна $[n=m=1]$) непонятно как...