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?


1 Answer 1


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

  • $\begingroup$ Thank you very much. Is there a combinatorial interpretation of the numbers $c(-n,k)$ related to Dyck paths? $\endgroup$ Sep 26, 2020 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$ Sep 26, 2020 at 19:37
  • $\begingroup$ For example, the sequence for k=4 is apparently the dissection of oeis.org/A006358 $\endgroup$ Sep 26, 2020 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$ Sep 27, 2020 at 17:13

You must log in to answer this question.

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