Enumerating a class of lattice paths (Q1408864): Difference between revisions

It is well known that the number of paths in the \(xy\)-plane with steps \((1,0)\) and \((0,1)\), that start in \((0,0)\), end in \((n,n)\) and do not go above the line \(y=x\) is given by the Catalan number \(C_n\). In the paper under review the above class of paths (also known as Dyck paths) is modified by replacing the allowed step set by the set consisting of all horizontal and vertical steps. If \(d_n\) is the total number of admissible paths, with generating function \(D(t)=\sum_{n\geq 0}t^n d_n\), then it is shown using standard techniques that \[ D(t)=\frac{1+3t-\sqrt{9t^2-10t+1}}{8t}. \] This is used to obtain a number of equivalent formulae for the number \(d_n\). For example, \[ d_n=\frac{1}{n}\sum_{k=1}^n 4^{n-k}\binom{n}{k}\binom{n}{k-1}. \] Moreover, it is shown that if \(d_{n,j}\) is the subset of paths counted by \(d_n\) that consist of exactly \(j\) steps (so that \(d_{n,2n}=C_n\)), then \[ d_{n,j}=\frac{1}{n}\sum_{k=1}^n \binom{n}{k}\binom{n}{k-1} \binom{2n-2k}{j-2k}. \] By the binomial theorem this implies the generating function \[ P_n(x)=\sum_{j=0}^{2n} x^j d_{n,j}= \frac{1}{n}\sum_{k=1}^n \binom{n}{k}\binom{n}{k-1}x^{2k}(1+x)^{2n-2k} \] from which the result for \(d_n\) follows after taking \(x=1\). A few closely related lattice path problems are also studied in the paper.