Timeline for How to solve the recursive formula $$A(n,k)=A(n-1,k)+A(n,k-1)+A(n-1,k-1)$$
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 4, 2022 at 12:02 | comment | added | Liviu Nicolaescu | @EmilJeřábek Yes. | |
| Oct 3, 2022 at 21:16 | comment | added | Emil Jeřábek | @LiviuNicolaescu All right. Though now I wonder about the denominator as well: shouldn’t it rather be $1-x-y-xy$? | |
| Oct 3, 2022 at 16:42 | comment | added | Liviu Nicolaescu | @EmilJeřábek I was obviously wrong. The numerator should be $a+b(x)+c(y)$, $b,c$ power series. | |
| Oct 3, 2022 at 15:08 | comment | added | Emil Jeřábek | @LiviuNicolaescu How does your comment square with Terry Tao’s comment above? | |
| Oct 3, 2022 at 11:24 | comment | added | Liviu Nicolaescu | 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)$. | |
| Oct 3, 2022 at 7:34 | comment | added | Emil Jeřábek | Let $A_0(n,k)$ be the solution for boundary conditions $A_0(0,0)=1$, $A_0(n,0)=A_0(0,k)=0$ for $n,k>0$. Then the general solution is $A(n,k)=A(0,0)A_0(n,k)+\sum_{i>0}A(i,0)A_0(n-i,k)+\sum_{j>0}A(0,j)A_0(n,k-j)$. | |
| Oct 2, 2022 at 23:57 | comment | added | Peter Taylor | @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 | |
| Oct 2, 2022 at 23:35 | comment | added | Joseph Van Name | There are many different choices of the set of points (i,j) where A(i,j) is given initial values. There are also different choices of the domain of the set $A$. Do we want the domain of $A$ to be $\mathbb{Z}^2$ or $\mathbb{N}^2$? | |
| Oct 2, 2022 at 22:44 | comment | added | Joseph Van Name | If we set all boundary points equal to 1, then my calculations indicate that the determinant of the $n\times n$-matrix $A(i,j)$ will be $2^{n(n-1)/2}$. It looks like this is related to the determinant of Pascal's triangle which is 1 (Timothy Gowers had fun with this determinant youtube.com/watch?v=byjhpzEoXFs ). It therefore seems like when we consider A(i,j) as a matrix, then A(i,j) can be factored as a product of n(n-1)/2 matrices of determinant 2 (or something like that). | |
| Oct 2, 2022 at 22:32 | comment | added | Joseph Van Name | 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. | |
| Oct 2, 2022 at 22:04 | comment | added | Terry Tao | 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. | |
| Oct 2, 2022 at 21:13 | comment | added | Will Sawin | 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. | |
| Oct 2, 2022 at 21:07 | history | asked | Nan | CC BY-SA 4.0 |