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}$.

| cite | improve this answer | |
  • $\begingroup$ Thank you very much. Is there a combinatorial interpretation of the numbers $c(-n,k)$ related to Dyck paths? $\endgroup$ – Johann Cigler Sep 26 at 15:08
  • 1
    $\begingroup$ there seems to be an interpretation in the OEIS, which links to home.wxs.nl/~lamoen/wiskunde/wave.htm $\endgroup$ – Martin Rubey Sep 26 at 19:37
  • $\begingroup$ For example, the sequence for k=4 is apparently the dissection of oeis.org/A006358 $\endgroup$ – Martin Rubey Sep 26 at 19:42
  • $\begingroup$ @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. $\endgroup$ – Johann Cigler Sep 27 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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