Lattice paths inside a table

Abstract

A lattice path in $\Z^d$ is a sequence $\nu_1,\nu_2,\ldots,\nu_k\in\Z^d$ such that the steps $\nu_i-\nu_{i-1}$ lie in a subset $\S$ of $\Z^d$ for all $i=2,\ldots,k$. Let $T_{m,n}$ be the $m\times n$ table in the first area of the $xy$-axis and put $\S=\{(1,1),(1,0),(1,-1)\}$. Accordingly, let $\I_m(n)$ denote the number of lattice paths starting from the first column and ending at the last column of $T$. We will study the numbers $\I_m(n)$ and give explicit formulas for special values of $m$ and $n$. As a result, we prove a conjecture of \textit{Alexander R. Povolotsky} involving $\I_n(n)$. Finally, we present some relationships between the number of lattice paths and Fibonacci and Pell-Lucas numbers, and pose several conjectures.