Is there any known solution for the recursive formula $$A(n,k)=A(n-1,k)+A(n,k-1)+A(n-1,k-1)$$ for given initial values A(0,0), A(1,0) and A(0,1)? Does this formula have any geometric or combinatorial known meaning?
12
-
4$\begingroup$ There's an obvious meaning as walks in an $n\times k$ grid from bottom-left to top-right with the allowed steps being up, right, and diagonal up-right. $\endgroup$– Will SawinCommented Oct 2, 2022 at 21:13
-
6$\begingroup$ This is not enough boundary data to uniquely specify A in the interior if the quadrant $\{ (n,m): n,m \geq 0\}$. Specifying A on the entire boundary of the quadrant would create a well posed problem, however. $\endgroup$– Terry TaoCommented Oct 2, 2022 at 22:04
-
2$\begingroup$ One obvious thing to do is put 1's on boundary $\{(n,m):n,m\geq 0\}$, run the computation, and then feed the diagonal entries A(n,n) into the online encyclopedia of integer sequences. If you do this, you would get this sequence oeis.org/A001850. You also get oeis.org/A050146 from a slightly different computation. $\endgroup$– Joseph Van NameCommented Oct 2, 2022 at 22:32
-
3$\begingroup$ @JosephVanName, it's often more useful to build a table and search for an antidiagonal. E.g. searching for 1,9,25,25,9,1 finds A008288 $\endgroup$– Peter TaylorCommented Oct 2, 2022 at 23:57
-
3$\begingroup$ The generating function $F(x,y)=\sum_{k,n\geq 0} A(n,k)x^n y^k$ is rational and has the form $$ F(x,y)=\frac{a+bx+cy}{1+x+y-xy} $$. The coefficients $a,b,c,d$ can be described explicitly in terms of $A(0,0), A(0,1), A(1,0)$. $\endgroup$– Liviu NicolaescuCommented Oct 3, 2022 at 11:24
|
Show 7 more comments