# Number of bounded Dyck paths with “negative length”

Let $$c(n,k)$$ denote the number of Dyck paths of semilength $$n$$ which are contained in the strip $$0 \leq y \leq 2k + 1.$$

They satisfy the recursion $$\sum_{j=0}^{k+1}(-1)^j \binom{2k+2-j}{j}c(n-j,k)=0$$ for $$n>k.$$

We can extend the sequence to negative $$n$$ such that this recursion holds for all $$n \in \mathbb{Z}.$$
I am interested in the generating function of the sequence $${\left( {c( - n,k)} \right)_{n \geq 0}}.$$

It is well known that $$\sum\limits_{n \geq 0} {c(n,k){x^n}} = \frac{{{F_{2k + 1}}( - x)}}{{{F_{2k + 2}}( - x)}}$$ if by $${F_n}(x) = \sum\limits_{j = 0}^{\left\lfloor {\frac{n}{2}} \right\rfloor } \binom{n-j}{j} x^j$$ we denote the Fibonacci polynomials which satisfy $${F_n}(x) = {F_{n - 1}}(x) + x{F_{n - 2}}(x)$$ with initial values $$F_0(x)=F_1(x)=1.$$

Computations for small $$k$$ suggest that $$\sum\limits_{n \geq 0} {c( - n,k){x^n}} = - \frac{1}{x}\frac{{{F_{2k}}( - \frac{1}{x})}}{{{F_{2k + 2}}( - \frac{1}{x})}}.$$ As mentioned in OEIS A080937 and A038213 for $$n=2$$ this result is due to Michael Somos.

These generating functions imply that $$c(n,k)$$ satisfies the recursion for $$\left| n \right| > k.$$

But to show that $$c(-n,k)$$ is the looked for extension we need the recursion for all $$n$$. Any idea how to do this?

If $$f(n)$$ satisfies a linear recurrence with constant coefficients for all $$n\in \mathbb{Z}$$ and we set $$F(x)=\sum_{n\geq 0} f(n)x^n$$, then $$\sum_{n\geq 1}f(-n)x^n = -F(1/x)$$ (as rational functions). See Enumerative Combinatorics, vol. 1, second ed., Prop. 4.2.3.
Addendum. Using Exercise 3.66(d) in Enumerative Combinatorics, vol. 1, second ed., it is not hard to show that $$c(-n,k)$$ is equal to the number of sequences $$(a_1,a_2,\dots,a_{2n-1})$$ of positive integers satisfying $$1\leq a_i\leq k+1$$ and $$a_1\leq a_2 \geq a_3 \leq a_4 \geq \cdots\geq a_{2n-1}$$.
• Thank you very much. Is there a combinatorial interpretation of the numbers $c(-n,k)$ related to Dyck paths? – Johann Cigler Sep 26 at 15:08
• @Martin Rubey:This can be formulated in the following way: Let $M_k$ be the matrix with entries $m(i,j,k)$ for $0\leq{i,j}\leq{k-1}$ such that $m(i,j,k)=0$ for $i+j<k-1$ and $m(i,j,k)=1$ else and let $v_k$ be the vector with all entries $1.$ The claim is that $c(-n,k)$ is the first entry of $M_k^{2n}v_k$.This can be verified for small $k$. The recursions are the same, but I cannot see how the initial values coincide in the general case. – Johann Cigler Sep 27 at 17:13