4
$\begingroup$

‎Let ‎$‎n‎$ ‎be a‎ ‎positive ‎integers and ‎$‎T=T_{n,n}‎$ ‎be the ‎$‎n\times n‎$‎ table in the first quadrant composed of $n^2$ unit squares‎, ‎whose $(x,y)$-blank is locate in the $x^{th}$-column from the left and the $y^{th}$-row from the bottom hand side of $T_{n,n}$ . ‎ Put ‎$‎D(n,n)‎$ ‎be ‎the ‎number ‎of ‎all ‎lattice ‎path ‎from the ‎first ‎column to entry ‎$‎(n,n)‎$‎ ‎of the ‎table ‎‎$‎T‎$ which steps comes from the set $S=\{(1,0)‎, ‎(1,1),(1,-1)\}$.(we allowed to move only to the right (up, down or straight) ). ‎It ‎is ‎easy ‎to ‎see ‎for ‎‎$‎n\geq 2‎$‎ $$D(n,n)=D(n-1,n)+D(n-1,n-1)$$ ‎where ‎$‎D(1,1)=1, D(2,2)=2, D(3,3)=5,‎ D(4,4)=13, \cdots‎‎$‎.

Notice, the entry $(x,y)$ means cordinate $x$ and $y$ in the table $T$ not the row $x$ and column $y$.

For example $$D(3,3)=D(2,3)+D(2,2)=2+3=5$$ and $$D(2,3)=D(1,3)+D(1,2)=1+1=2.$$ For calculating $D(2,3)$ you must consider the table with 3 rows and columns and by using this table calculate all lattice paths reach to entry $(2,3)$ in this table!! in my arXiv paper, there are some references for this sequence!! I ‎think ‎these ‎lattice ‎paths ‎very ‎interesting ‎and ‎obtained ‎some ‎results ‎about ‎them. Put ‎$‎D(n,n)=d_n‎‎$, I check and known that the Hankel determinant evaluation of ‎$‎D(n,n)‎$ is

$$ \det(H_n^1)=\det‎‎ \begin{bmatrix} d_{1} & d_{2} & d_{3} & \dots & d_{n} \\ d_{2} & d_{3} & d_{4} & \dots & d_{n+1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ d_{n} & d_{n+1} & d_{n+2} & \dots & d_{2n-1} \end{bmatrix}‎‎ =1. $$‎‎‎‎ Do you have ideas or comments for proving it?

Thank you so much for any help or comment.

$\endgroup$
  • $\begingroup$ What is $D(n-1, n+1)$? You seem only to have defined $D(n,n)$. If it means what it seems to mean then how can your relation for $D(n,n)$ involve $D(n-1,n+1)$ as that would seem to involve your path leaving the square $T_{n,n}$. $\endgroup$ – Simon Willerton Aug 14 '17 at 21:45
  • $\begingroup$ $D(n,n)$ is the number of all lattice paths from the first column to the entry $(n,n)$, then, $$D(n,n)=D(n-1,n)+D(n-1,n-1)$$. $\endgroup$ – d.y Aug 14 '17 at 21:51
  • $\begingroup$ You have not read my comment. You have not said what $D(n-1, n+1)$ is. The relation you have written in your comment is not the same as the relation you have written in the question. $\endgroup$ – Simon Willerton Aug 14 '17 at 21:56
  • $\begingroup$ I check the relation in question and fixed it. actually, if we have a table with $n$ rows and $m$ columns and let $D(x,y)$ denoted the number of lattice paths from first column to the entra$(x,y)$ we have $$D(x+1,y)=D(x,y-1)+D(x,y)+D(x,y+1)$$ where $D(x,0)=D(x,m+1)=0$ for all $x\geq 1$ and $y=1,2,\cdots , m$. In the above qustion I consider for specail case $m=n$. Also, $D(n-1,n+1)$ is the number of lattice paths with three steps $(1,1),(1,-1),(1,0)$ from the first columns to the entry $(n-1,n+1)$. $\endgroup$ – d.y Aug 14 '17 at 22:05
  • $\begingroup$ You've now changed you relation in the question so it doesn't involve $D(n-1, n+1)$. Can you explain what $D(2,3)$ is? You have not defined it. With the definition I would guess it seems to be 2. That would mean that $D(3,3) = 2 + 2 =4 \ne 5$. $\endgroup$ – Simon Willerton Aug 14 '17 at 22:07
6
$\begingroup$

The $d(n):=D(n,n)$ is OEIS sequence A005773. The Hankel determinant property is given in the sequence entry. Also the recursion $\;nd_{n}=2nd_{n-1}+3(n-2)d_{n-2}$. A proof could come from a similar proof of the Hankel determinant property of the Catalan numbers. A related property is to use $d_0=1$ and take $\det(H_n^0)$ with $d_0$ in the first row and column giving OEIS sequence A163806 $(1,1,1,0,-1,-1,0,1,1,0,-1,-1,0,1,1,\dots)$ with a period of $6$ after the initial $d_0$.

The proof of the Hankel properties could probably use the Lindstrom-Gessel-Viennot Lemma. This can be used to show that the unique solution to $\det(H_n^0)=\det(H_n^1)=1$ for all $n$ is the Catalan numbers. For a reference look at Aigner, Catalan-like numbers and determinants, J. Comb. Th. A 87 (1999), 33-51.

By the way, notice how the diagram for $D(4,4)=13$ is $$ \begin{matrix} 1 & 2 & 5 & 13 \\ 1 & 3 & 8 & 21 \\ 1 & 3 & 8 & 21 \\ 1 & 2 & 5 & 13 \end{matrix}‎‎$$ where each entry is the sum of two or three entries in the preceding column.

Catalan and related sequence proofs are given by J, Cigler in Some nice Hankel determinants.

$\endgroup$
  • $\begingroup$ How proof the Hankel determinant of the Catalan numbers? I can proof the recursion $\;nd_{n}=2nd_{n-1}+3(n-2)d_{n-2}$ with generating function of $D(n,n)$,but I have no combinatorial proof for it? Do you have idea for combinatorial proof this recursion relation? $\endgroup$ – d.y Aug 14 '17 at 23:43
  • $\begingroup$ Such things are discussed in Christian Krattenthaler's "Advanced determinant calculus" (arxiv.org/abs/math/9902004 & arxiv.org/abs/math/0503507). $\endgroup$ – Wadim Zudilin Aug 15 '17 at 9:40
  • $\begingroup$ @Wadim Zudilin I see "Advanced determinant calculus", but I couldn't find the proof of Hankel determinant of Catalan numbers. $\endgroup$ – d.y Aug 15 '17 at 16:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.