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.

Improve this question
$\endgroup$
8
  • $\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
    Commented Aug 14, 2017 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
    Commented Aug 14, 2017 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
    Commented Aug 14, 2017 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
    Commented Aug 14, 2017 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
    Commented Aug 14, 2017 at 22:07

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Aug 14, 2017 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
    Commented Aug 15, 2017 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
    Commented Aug 15, 2017 at 16:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .