\documentclass[12pt,a4paper,reqno]{amsart}
\pagenumbering{arabic}
\usepackage{fullpage}
\usepackage{epsfig,color}
\usepackage{graphicx}
\usepackage[english]{babel}
\usepackage{amsmath}
\usepackage{amsthm,amssymb,latexsym}
%\usepackage{t1enc}
\usepackage{fancyheadings}
\usepackage{epic}
\usepackage{eepic}
%\usepackage{showkeys}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%    Theorems and such
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{prop}{Proposition}
\newtheorem{lemma}[prop]{Lemma}
\newtheorem{cor}[prop]{Corollary}
\newtheorem{theorem}[prop]{Theorem}
\newtheorem{thm}[prop]{Theorem}

\theoremstyle{definition}
\newtheorem{defin}[prop]{Definition}
\newtheorem{ex}[prop]{Example}
\newtheorem{remark}[prop]{Remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\N}{\mathbb{N}} \newcommand{\ii}{\mbox{\em\small~in~}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\up}{\ensuremath{x}}
\newcommand{\down}{\ensuremath{\overline{x}}}
\newcommand{\sgUp}{\ensuremath{A}} % Sg interaction superieures
%%\newcommand{\sgLow}{\ensuremath{D}} % Sg interactions inferieures
\newcommand{\sgD}{\ensuremath{B}} % Sg derniere descente
\newcommand{\sgSV}{\ensuremath{C}} % Sg petits creux value par somme
\newcommand{\sgSVS}{\ensuremath{D}} % Sg petits creux value par somme et dernier descente
\newcommand{\sgSVC}{\ensuremath{E}} % Sg petits creux value par constante
\newcommand{\sgSVG}{\ensuremath{G}} % Sg petits creux value geomtriquement
\newcommand{\sgJ}{\ensuremath{J}} % Sg de la nouvelle fonction inconnue pour la linearisation
\newcommand{\sgDP}{\ensuremath{F}} % Sg des demi-pyramides marquee
\newcommand{\sgTH}{\ensuremath{T}} % Sg des empilements triviaux de segments
\newcommand{\gV}{\ensuremath{V}} % Valuation d'une vallee
\newcommand{\gS}{\ensuremath{V_{seg}}} % valuation d'un segment
\newcommand{\bijC}{\ensuremath{f}} % Bijection du lemme cyclique
\newcommand{\bijE}{\ensuremath{h}} % bijection chemins noirs et empilements
\newcommand{\flip}{\ensuremath{g}} % morphisme reflexion axe horizontal
\newcommand{\B}{\ensuremath{\mathcal{B}}}
\newcommand{\X}{\ensuremath{\mathcal{X}}}
\newcommand{\Y}{\ensuremath{\mathcal{Y}}}

\newcommand{\A}{\ensuremath{\mathcal A}}
\newcommand{\I}{\ensuremath{\mathcal I}}
\newcommand{\ov}{\overline}
\newcommand{\un}{\underline}
\def\newop#1{\expandafter\def\csname #1\endcsname{\mathop{\rm#1}\nolimi=
ts}}
\newop{inv}

\newcommand{\aseq}{\A-sequence}
\newcommand{\bseq}{\B-sequence}

\newcommand{\bwx}{\phi}
\newcommand{\BWX}{\psi}
\newcommand{\Sn}{\ensuremath{\mathcal S}}
\newcommand{\p}{permutation}
\newcommand{\ps}{permutations}
\newcommand{\gf}{generating function}
\newcommand{\gfs}{generating functions}
\newcommand{\lseq}{$\ell$-sequence}

\def\emm#1,{{\em #1}}
\def\lb{\linebreak}
\newcommand\mps[1]{\marginpar{\small\sf#1}}
\newcommand\mpg[1]{\marginpar{\small#1}}
\newcommand{\Ref}[1]{(\ref{#1})}

%\renewcommand{\theenumi}{\upshape (\roman{enumi})}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\newop{BMS} \newop{bwx} \newop{BWX}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%     New style for sections and subsections
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\catcode`\@=3D11
\catcode`\@=11
\def\section{\@startsection{section}{1}%
 \z@{.7\linespacing\@plus\linespacing}{.5\linespacing}%
 {\normalfont\bfseries\scshape\centering}}
%\def\section{\@startsection{section}{1}%
%  \z@{.7\linespacing\@plus\linespacing}{-.5em}%
%  {\normalfont\bfseries}}

%\def\subsection{\@startsection{subsection}{2}%
%  \z@{.5\linespacing\@plus.7\linespacing}{-.5em}%
%  {\normalfont\scshape}}
\def\subsection{\@startsection{subsection}{2}%
  \z@{.5\linespacing\@plus\linespacing}{.5\linespacing}%
  {\normalfont\bfseries\scshape}}


\def\subsubsection{\@startsection{subsubsection}{3}%
  \z@{.5\linespacing\@plus.7\linespacing}{-.5em}%
  {\normalfont\itshape}}
%\catcode`\@=3D12
\catcode`@=12
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\addtolength{\textheight}{-4mm} \topmargin6mm

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title[Counting upper interactions in Dyck paths]
{Counting upper interactions in Dyck paths }

\author{Yvan Le~{B}orgne$^1$} 

\address{LaBRI, Universit\'e Bordeaux 1, 351 cours de la Lib\'eration,
33405 Talence Cedex, France} 

\email{borgne@labri.fr} 

\dedicatory{D\'edi\'e \`a Xavier Viennot$^*$}

\thanks{$^1$The author
was partially supported by the network Algebraic Combinatorics in
Europe (ACE). \newline\indent
$^*$The starting point of this work is an act of faith in the "Viennotique":
Equation~(\ref{eq:solution-functionnal-equation}) 
is an instance of the inversion lemma for a class of
heaps of pieces. This article describes some clues found during the
inverstigation of these heaps of pieces. The frustration, generated
by the lack of a final proof using the bijective method, is eased by
the opportunity to present to Xavier Viennot a problem where it just
remains to find the bijection.
}

\keywords{
 Dyck paths, catalytic parameters, slice functional equations, linearization of $q$-algebraic equations, basic hypergeometric series.
%% Cycle lemma, Heaps models
}

%\subjclass{Primary: subject; Secondary: subject}
\date{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%=

\begin{document}


\begin{abstract}
Upper and lower interactions are parameters of Dyck paths which are
motivated by corresponding parameters in a model of partially directed
polymers. We investigate the problem of obtaining the generating
function for Dyck paths with respect to upper interactions in terms of
basic hypergeometric $q$-series in which an algebraic term occurs.


%% A Dyck word $w$ of size $n$ is a shuffle of $n$ copies of the word
%% $\up\down$.  An upper interaction in $w$ is an occurrence of a factor
%% $\down^k\up^k$ where $k\geq 1$.  We present two different methods to
%% enumerate Dyck words according to the size and the number of upper
%% interactions.  The generating function has a rather unusual form: it
%% is the ratio of two $q$-series where occurs an algebraic term.  
%% %% The
%% %% first method mainly involves calculation over formal power series,
%% %% combining an iteration and the kernel method, to solve a functional
%% %% equation involving a catalytic variable. In the next method we
%% %% partition the set of Dyck words to write a $q$-algebraic equation
%% %% involving an other catalytic variable. We solve this quadratic
%% %% equation.
%% The two methods use recursive description of the words which translate
%% into different kind of functional equations satisfied by the
%% generating function.  The second approach lies on a preliminary
%% transformation of the words so contains a bit more combinatorics.
%% Then we compare these two approaches that seem to be related.
 
\end{abstract}
\maketitle 


%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 54 \rms (2006), Article~B54f\hfill}
\def\thepage{}
%
%

\section{Introduction}


A \emph{Dyck word} $w$ is a word over the alphabet $\{\up,\down\}$
that contains as many letters $\up$ as letters $\down$ and such that
any prefix contains at least as many letters $\up$ as letters $\down$.
The \emph{size} of $w$ is the number of letters $\up$ in $w$.  A
\emph{Dyck path} is a walk in the plane, that starts from the origin,
is made up of \emph{rises}, {\it i.e.} steps $(1,1)$, and \emph{falls},
{\it i.e.} steps $(1,-1)$, remains above the horizontal axis and
finishes on it.  Figure~\ref{fig:def-Dyck} gives an example of a Dyck
path of size $12$.  The Dyck path related to a Dyck word $w$ is the
walk obtained by representing a letter $\up$ by a rise, and a letter
$\down$ by a fall.  In this paper we identify the two
notions.  An \emph{upper interaction}, respectively a \emph{lower
interaction}, in a Dyck word $w$ is an occurrence of a factor
$\down^k\up^k$, respectively $\up^k\down^k$, for any $k\geq 1$. The
example of Figure~\ref{fig:def-Dyck} contains $7$ upper interactions
and $9$ lower interactions.

\begin{figure}[ht!]
\centerline{\scalebox{0.5}{\input{definition_Dyck.pstex_t}}}
\caption{A Dyck path and its upper and lower interactions}
\label{fig:def-Dyck}
\end{figure}

  These upper and lower interactions are translations in terms of Dyck
paths of physical quantities studied by physicists
\cite{dharandco2002}, \cite{foster-yeomans91} in a model of
self-interacting partially directed polymers near a surface.
Enumeration of Dyck paths leads to generating functions syntactically
smaller than those of partially directed polymers without avoiding the
main enumerative difficulty. Thus we restrict ourselves to the study
of Dyck paths. To simplify the enumeration we distinguish
%introduce the distinction 
between upper and lower interactions. We consider both enumerations of
Dyck paths: according to the size and the number of lower
interactions and according to the size and the number of upper
interactions. It remains to consider the enumeration according to the
three parameters to recover a variation of the model suggested by
physicists. It is still an open problem to take into account both
types of interactions.

Lower interactions are the easier kind of interaction to take into
account in enumeration. According to the usual decomposition of Dyck
paths which splits them at the first return to the horizontal axis,
the vertex $A$ in Figure~\ref{fig:def-Dyck}, each lower
interaction is included in one of the two sub-walks.  Denise and
Simion~\cite{denise-simion95} have already used this fact to enumerate
Dyck paths according to their size and their number of lower
interactions. In contrast, there are upper interactions above the
vertex $A$ that belong to the two sub-walks. The number of upper
interactions above the vertex $A$ depends on the numbers of
consecutive falls just before $A$ and consecutive rises just after
$A$. Hence, in contrast to the situation for lower interactions,
counting upper interactions is not directly compatible with the usual
recursive decomposition of Dyck paths. It is the purpose of this paper
to investigate how this additional difficulty may be approached.

%% This explains why upper interactions seemingly do not satisfy the
%% same kind of recursive decomposition as lower interactions and then
%% are more difficult to take into account. From a combinatorial point of
%% view, being able to overcome this difficulty is one of the main
%% interests of this paper.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL }{\SMALL }
%
%

We present two methods to find an expression for the
generating function
\begin{equation}
\label{eq:sg-Up}
\displaystyle \sgUp(t,u) = \sum_{w} t^nu^k
\end{equation}
where $w$ runs over non-empty Dyck paths, $n$ is the size of $w$ and $k$ the number of upper interactions.


In Section~\ref{section:slice-equation}, the first method, inspired by
a work of Bousquet-M{\'e}lou and
Rechnitzer~\cite{bousquet-melou-rechnitzer03}, consists of building
Dyck words by inserting a factor $\up^i\down^i$ after the last letter
$\up$.  This leads to a functional equation that can be solved through
calculations over formal power series involving four main steps: an
iteration, the kernel method~\cite{bousquet-melou-petkovsek00}, a
division and the use of a relation between the roots of a polynomial.
The resulting generating function, see
(\ref{eq:solution-functionnal-equation}), has a rather unusual form:
it is a ratio of $q$-series, with $q=tu$, in which an algebraic
series $\sigma \equiv \sigma(t,u)$ occurs.


\begin{figure}[ht!]
\centerline{\scalebox{0.35}{\input{polyominos.pstex_t}}}
\caption{A staircase polyomino and two kinds of decomposition}
\label{fig:staircase} 
\end{figure}


With the first approach we obtain a formula for the generating
function $A(t,u)$. Before we explain our motivation for other methods,
we briefly summarise the solutions of a similar problem: the
enumeration of staircase polyominos according to their half-perimeter
and their area. The leftmost picture in Figure~\ref{fig:staircase}
gives an example of a staircase polyomino. It is a convex subset of
the plane whose frontier is defined by two walks, made up of North,
$(0,1)$, and East, $(1,0)$ steps that intersect only at their
endpoints $A=(0,0)$ and $B$. The half-perimeter is the common length
of the two walks and the area is the number of unit squares enclosed
by the two walks. Three approaches have been proposed for this
enumeration. Klarner \cite{K67} considers the addition of a column to
the right of the polyomino to write a $q$-linear equation. This
equation is similar to (\ref{eq:slice-decomposition}) of Section
\ref{section:slice-equation}, but is simpler in the sense that its
solution does not require the kernel method, thus there is no
algebraic term like $\sigma$ in the resulting ratio of
$q$-series. Delest and F\'edou \cite{DF93} detect a recursive
factorisation of a polyomino into two smaller polyominos by inspection
of the first column of height $1$ if there is one. This decomposition
leads to a $q$-quadratic equation for which there is no general
solution, but they were able to guess the solution and check that it
was correct. Bousquet-M\'elou and Viennot
\cite{bousquet-melou-viennot92} defined a bijection between polyominos
and certain heaps of segments. Thus the generating function appears as
an instance of the general inversion lemma for heap models
\cite{viennot86}: the numerator and denominator of the formula are
generating functions of certain simpler subsets of heaps which satisfy
solvable $q$-linear equations.


The generating functions for Dyck paths according to their size and
their number of upper interactions, and for polyominos according to
their half-perimeter and their area, are very similar ratios of
$q$-Bessel-like series with, in our case, the additional algebraic
term $\sigma$. 
%% This similarity motivates the act of faith that there
%% also exists the same three approaches for the enumeration of Dyck
%% paths.
This similarity suggests that the same three approaches for the
enumeration of Dyck paths may be feasible. The likelihood of some
hidden combinatorics in $A(t,u)$ is increased by the fact that
$\sigma$, resulting from an application of the kernel method, is the
generating function for Dyck paths according to their size and their
number of \emph{lower} interactions. With regards to the physical
model, we are interested in a more combinatorial derivation of
$A(t,u)$ in order to propose combinatorial objects whose generating
functions reflect the different dominant singularities of $A(t,u)$,
which correspond to different phases of the model. From a
combinatorial point of view, we are looking for another example, in a
more general context, of three derivations of the same result
respectively based on a slice-equation, on a $q$-quadratic equation
and on a bijection with a heap model.  We want to compare these
approaches in order to improve them. For example, the solution of
certain $q$-quadratic equations seems to rely on a Riccatti-like
Ansatz already discussed in particular cases in
\cite{brak-prellberg95}.




%%The next two sections present our new method to compute $\sgUp(t,u)$.
In Section~\ref{section:q-algebraic-equation}, we consider \emph{Dyck
paths with small valleys}, {\it i.e.} Dyck words that avoid the factor
$\down\down\up\up$.  An {\it ad hoc} valuation of the \emph{valleys},
{\it i.e.} the factors $\down\up$, may be chosen in such a way that
the generating function for weighted Dyck paths with small valleys
coincides with the generating function $\sgUp(t,u)$.  We can
recursively split these words, and after the introduction of an
additional parameter we obtain a $q$-algebraic equation.  Solving this
equation requires a change of unknown functions.
%%Section~\ref{section:solve-q-algebraic} is
%%dedicated to the resolution of that $q$-equation which is solvable
%%after a change of unknown function. 
The choice of this change is crucial to the solution. One change,
proposed in~(\ref{eq:sigma_chgt}), implies less calculation than
others, suggested by the literature, in order to obtain the generating
function~(\ref{eq:sol-q-algeq}).

In Section~\ref{section:compare-approaches} we compare the two
methods. First, the additional parameter of the second method can be
taken into account by the first method, leading to the same %%
syntactical generating function as in
Section~\ref{section:q-algebraic-equation}.  In fact, we guessed the
efficient Ansatz~(\ref{eq:sigma_chgt}) by inspecting the generating
function obtained this way. Then we discuss the possible homographic
changes of unknown functions to solve certain quadratic $q$-algebraic
equations, comparing them with previous work \cite{brak-prellberg95},
\cite{janse-van-rensburg01}, \cite{abramov-paule-petkovsek98}.

This work is an extract from the chapter on upper interactions of the
 author's thesis \cite{YLB04}, where the third approach, using heaps
 of pieces introduced by Viennot \cite{viennot86}, is also
 presented. An extended abstract of this chapter is available in
 \cite{YLB05}.



\section{Appending a factor $\up^k\down^k$ and a slice equation}
\label{section:slice-equation}

In~\cite{bousquet-melou-rechnitzer03}, Bousquet-M\'elou and Rechnitzer
use a factorisation of partially directed walks.  We use their method
for the enumeration of Dyck paths according to their size and their
number of upper interactions. In Section~\ref{sec:temperley-eq} we
find the functional equation~(\ref{eq:slice-decomposition}) satisfied
by the generating function and in Section~\ref{sec:temperley-solve} we
solve this equation and obtain in~(\ref{eq:solution-functionnal-equation}) an expression in terms of $q$-series.

\subsection{A decomposition using the last factor $\up^k\down^k$}
\label{sec:temperley-eq}


Let $w$ be a Dyck path/word.  The \emph{height} of a vertex $(i,j)$ in
$w$ is $j$.  A \emph{peak}, respectively a \emph{valley}, is a vertex
of $w$ following a rise and preceding a fall, respectively following a
fall and preceding a rise.  The \emph{length of the last descent}
$l(w)$ of $w$ is the height of the rightmost peak. This is also the
number of letters $\down$ after the last letter $\up$.  In the path
$w_1$ in Figure~\ref{fig:def-Dyck} the rightmost peak is $B = (21,3)$
so $l(w_1) = 3$.


A non-empty Dyck path $w$ is either of the form $\up^k\down^k$ with
$k\geq 1 $, or else contains at least one valley, thus factors as
$u\down\up^k\down^k\down^j$, where $v = u\down^{j+1}$ is a non-empty
Dyck path, $j\geq 0$ and $k\geq 1$.  In the second case we want to
deduce from $v$, $j$ and $k$ the number of upper interactions in
$w$. In addition to the number $up(v)$ of upper interactions in $v$ we
have to know the length $l(v)$ of the last descent of $v$:
$$ up(w) = up(v) + \min(k,l(v)-j).$$ Moreover, the length of the last
descent of $w$ is $l(w) = k+j$.  Thus, given a Dyck path $v$ and an
appropriate choice of $j$ and $k$, we can build the Dyck path $w$.
The knowledge of $l(v)$ allows us to compute the number of added upper
interactions and $l(w)$. We are not interested in the enumeration
according to the length of the last descent but we will use this
parameter as a temporary information in the decomposition the Dyck
path, a terminology proposed by Zeilberger \cite{zeilberger00} calls
it a \emph{catalytic parameter}.



We add the length of the last descent to the enumeration to define the
generating function
$$\displaystyle \sgD(t,u;s) = \sum_{w}
t^nu^ms^l$$ where $w$ runs over non-empty Dyck paths, $n$ is the size of $w$, $m$ the number of upper
interactions in $w$ and $l$ is the length of the last descent.

We will often write $\sgD(s)$ instead of $\sgD(t,u;s)$, and,
accordingly, $\sgD(1)$ instead of $\sgD(t,u;1)$ and $\sgD(uts)$
instead of $\sgD(t,u;uts)$.



\begin{lemma}
\label{lem:slice-decomposition-equation}
The generating function $\sgD(s)$ for non-empty Dyck paths counted
according to their size, their number of upper interactions and their
length of the last descent satisfies
\begin{equation}
\label{eq:slice-decomposition}
\begin{array}{lcl}
\displaystyle \sgD(s) & = & \displaystyle \frac{ts}{1-ts} 
+ \frac{ut}{1-ut}\frac{ts\left(\sgD(s)-\sgD(uts)\right)}{1-ts} \\
\ & \ & \displaystyle 
+ \frac{ut}{1-ut}\left( \frac{s}{1-s}\left(\sgD(1)-\sgD(s)\right) - 
			\frac{uts\left(\sgD(1)-\sgD(uts)\right)}{1-uts} \right).\\
\end{array}
\end{equation}
\end{lemma}

\begin{proof}
We split the set of Dyck paths into three disjoint subsets, as illustrated
on Figure~\ref{fig:slice-decomposition}: the set $\mathcal{B}_1$ of
paths with one peak, the set $\mathcal{B}_2$ of paths where the last
peak is strictly higher than the previous one, and the set
$\mathcal{B}_3$ of paths where the last peak is below the previous
one. For each set we define a generating function $ \displaystyle
B_i(s) \equiv B_i(t,u;s) $ as above.  Thus
$$ \displaystyle \sgD(s) = B_1(s) + B_2(s) + B_3(s).$$

\begin{figure}[ht!]
\centerline{\scalebox{0.5}{\input{slide_decomposition.pstex_t}}}
\caption{The "slice" decomposition of Dyck paths}
\label{fig:slice-decomposition}
\end{figure}

Each path of each subset is obtained by adding a factor $\up^k\down^k$
to a smaller one: to the empty path for the first subset
$\mathcal{B}_1$, or to any non-empty Dyck path otherwise.  The length
of the last descent is sufficient to determine in each case, both the
number of ways in which one can extend a Dyck path and the number of
additional upper interactions.  Figure~\ref{fig:slice-decomposition}
gives examples of each kind of extension leading to paths of each
of the three subsets. The summation of the extensions over all Dyck
paths leads to the generating function for each subset and contains
different evaluations of the series $\sgD(s)$ ($\sgD(s)$, $\sgD(qs)$
and $\sgD(1)$):
\begin{itemize}
\item The paths of $\mathcal{B}_1 = \{ \up^k\down^k,\ \ k \geq 1 \}$
are defined by the height $k$ of their single peak which is also the
rightmost one, thus
$$\displaystyle B_1(s) = \sum_{k=1}^\infty t^ks^k = \frac{ts}{1-ts}.$$
\item Let $v=u\up\down^{l}$ be a non-empty Dyck path whose rightmost
peak is denoted $A$. To build a path $w \in \mathcal{B}_2$ we insert
into the rightmost vertex at height $l-i$ a factor
$\up^{i+j}\down^{j+i}$, $1 \leq i \leq l$ and $j \geq 1$.  We insert a
valley $B$ at height $l-i$ and a peak $C$ at height $l+j$ into the
path $w = u\up\down^{l-i}\up^{i+j}\down^{j+l}$. This insertion
increases the size of $v$ by $i+j$ and creates exactly $i$ upper
interactions.
%%  All vertices in $w$ between the vertices $A$
%% and $B$, $B$ excepted, belongs to an upper interactions since $C$ is
%% above $A$. Thus the insertion adds exactly $i$ upper interactions.
The new rightmost peak is at height $l+j$.  In terms of generating
functions, the previous remark leads to
$$ \displaystyle B_2(s) = \sum_{l \geq 1} \sum_{v \in \mathcal{D}_l}
\left(\sum_{i=1}^l\sum_{j=1}^\infty t^{n+i+j}u^{m+i}s^{l+j}\right),
$$ where $\mathcal{D}_l$ is the set of Dyck paths whose rightmost peak
is at height $l$, $n$ is the size of $v$, $m$ the number of upper
interactions in $v$.  The
summations of geometric sums with respect to $i$ and $j$ give
$$ \displaystyle B_2(s) = \frac{ts}{1-ts}\frac{ut}{1-ut}\sum_{l \geq
1} \sum_{v \in \mathcal{D}_l}\left(t^nu^ms^l-t^{n}u^{m}(tus)^l\right),
$$ where we recognise $\sgD(s)$ and $\sgD(uts)$, thus
$$ \displaystyle B_2(s) =
\frac{ts}{1-ts}\frac{ut}{1-ut}\left(\sgD(s)-\sgD(uts)\right).
$$
\item Let $v = u\up\down^l$ be a non-empty Dyck path whose rightmost
peak is $D$. To build a path $w \in \mathcal{B}_3$ we insert in the
rightmost vertex of height $i-j$ a factor $\up^j\down^j$ where $ j
\leq i \leq l$. We create a valley $F$ at height $i-j$ and a new
rightmost peak $E$ at height $i$ into $w =
u\up\down^{l-i+j}\up^j\down^i$. The size increases by $j$ and the
number of upper interactions also by $j$.
%% $j <
%% i$ is the difference of height between $E$ and $F$ the valley created
%% in $w$. Each vertex in $w$ between $F$ and $E$, $F$ excepted, belongs
%% to an added upper interaction thus there are $j$ new upper
%% interactions. The size increases by $j$ and the height of the new
%% rightmost peak $E$ is $i$.
In terms of generating functions, keeping the same notations, we have
$$ \displaystyle B_3(s) = \sum_{l\geq 1} \sum_{v \in \mathcal{D}_l}
t^nu^m\left(\sum_{i=1}^ls^i\left(\sum_{j=1}^{i}t^ju^j\right)
\right).
$$ In that case the two geometric sums according to $i$ and $j$ are
not independent. Their summations lead to
$$ \displaystyle B_3(s) = \frac{ut}{1-ut}\sum_{l\geq 1}\sum_{ v \in
\mathcal{D}_l} \left(\frac{s}{1-s}\left(t^nu^m - t^nu^ms^l
\right)-\frac{uts}{1-uts}\left(t^nu^m-t^nu^m(uts)^l \right)\right),
$$ where we recognise $\sgD(1)$, $\sgD(s)$ and $\sgD(uts)$.  Thus
$$ \displaystyle B_3(s) =
\frac{ut}{1-ut}\left(\frac{s}{1-s}\left(\sgD(1)-\sgD(s) \right) -
\frac{uts}{1-uts}\left( \sgD(1) - \sgD(uts) \right) \right).
$$
\end{itemize}

The generating function for each subset gives one of the three terms in
the right-hand side of (\ref{eq:slice-decomposition}).
\end{proof}


\subsection{Solution}
\label{sec:temperley-solve}

The solution of (\ref{eq:slice-decomposition}) requires an iteration
to remove $\sgD(uts)$ and then an application of the kernel method,
presented for example in \cite{bousquet-melou-petkovsek00}, to remove
$\sgD(s)$.  As in~\cite{bousquet-melou-rechnitzer03}, we obtain for
$\sgD(1) = \sgUp(t,u)$ a ratio of two $q$-series in which an algebraic
term occurs.  Let $q \equiv ut$ be a notation has used in $q$-calculus
and consistent with the usual notation $(x)_n =
\prod_{k=0}^{n-1}(1-q^kx)$, intensively used here.

\begin{prop}
\label{prop:calculatoire}
The generating function for Dyck paths counted according to their size and their number of upper interactions can be written as

\begin{equation}
\label{eq:solution-functionnal-equation}
\displaystyle \sgUp(t,u) = \sgD(1) =
-\frac{\displaystyle
	t\sum_{n\geq 0}\left(\frac{(q-t)\sigma}{1-q} \right)^n\frac{q^{\binom{n+2}{2}-1}}{(q)_n(qt\sigma^2)_n}
}
{\displaystyle
\sum_{n\geq 0}\left(\frac{(q-t)\sigma}{1-q} \right)^n\frac{q^{\binom{n+2}{2}}}{(q)_n(qt\sigma^2)_n}\frac{1-tq^n\sigma}{(1-q^n\sigma)(1-q^{n+1}\sigma)}
}, 
\end{equation}
where $\displaystyle \sigma =
\frac{1+t-2q-\sqrt{(1-t)(1-t-4q+4q^2)}}{2t(1-q)}.$
\end{prop}

\begin{proof}
(\ref{eq:slice-decomposition}) can be rewritten as
\begin{equation}
\label{eq:base1}
\sgD(s) = a(s) + b(s)\sgD(1) + c(s)\sgD(qs) + d(s)\sgD(s),
\end{equation}
where 
$$ \left \{ \begin{array}{lcl}
a(s) & = & \displaystyle \frac{ts}{1-ts} \\
b(s) & = & \displaystyle \frac{q}{1-q}\left( \frac{s}{1-s} - \frac{qs}{1-qs} \right)\\
c(s) & = & \displaystyle \frac{q}{1-q}\left( \frac{qs}{1-qs} - \frac{ts}{1-ts} \right)\\
d(s) & = & \displaystyle \frac{q}{1-q}\left( \frac{ts}{1-ts} - \frac{s}{1-s} \right). 
\end{array} \right .$$
The calculation of $\sgD(1)$ involves four main steps: an iteration
that removes $\sgD(qs)$, the kernel method that removes $\sgD(s)$, the
relation between the roots of a polynomial which leads to terms
$(q)_n(qt\sigma^2)_n$, and a division that explains the quotient of
$q$-series.


$\bullet$ For $n\geq 1$, the substitution $s \longrightarrow q^ns$ in (\ref{eq:base1}) leads to 
\begin{equation}
\label{eq:iter}
 \displaystyle \sgD(q^ns) = \frac{1}{1-d(q^ns)}\left(a(q^ns) + b(q^ns)\sgD(1) + c(q^ns)\sgD(q^{n+1}s)\right),
\end{equation}
where $1/(1-d(q^ns))$ is a formal power series in $t$ whose coefficients are polynomials in $s$ and $u$.
Using (\ref{eq:iter}) we recursively rewrite $\sgD(q^{n}s)$ in (\ref{eq:base1}), and after $N$ steps we obtain
\begin{equation} 
\label{eq:base2}
\begin{array}{lcl}
\displaystyle \left(1-d(s)\right)\sgD(s) & = & \displaystyle
\sum_{n=0}^{N}\left(\prod_{k=0}^{n-1}
\frac{c(q^ks)}{1-d(q^{k+1}s)}\right)\left(a(q^ns) +
b(q^ns)\sgD(1)\right) \\
\ & \ &  \displaystyle+ \left(\prod_{k=0}^{N-1}
\frac{c(q^ks)}{1-d(q^{k+1}s)}\right)c(q^{N}s)\sgD(q^{N+1}s).
\end{array}
\end{equation}
 
Since $c(s)/(1-d(qs))$ is a formal power series in $t$ that can be
written $$\displaystyle \frac{c(s)}{1-d(qs)} = ust + st^2T(q,s,t),$$
where $T(q,s,t)$ is a series in $t$ whose coefficient are series in
$s$ and $\sgD(q^Ns)$ is a formal power series in $t$, we have
$$ \left(\prod_{k=0}^N\frac{c(q^ks)}{1-d(q^{k+1}s)}\right)\sgD(q^Ns) =
\left(\prod_{k=0}^N(q^{k+1}s+\mathcal{O}(t^{k+2}))\right)\mathcal{O}(1)
= q^{\binom{N}{2}}s^{N} + \mathcal{O}(t^{\binom{N}{2}}).
$$
Thus, as formal power series in $t$, (\ref{eq:base2}) converges towards 
\begin{equation}
\label{eq:base3}
\displaystyle \left(1-d(s)\right)\sgD(s) =
\sum_{n=0}^{\infty}\left(\prod_{k=0}^{n-1}
\frac{c(q^ks)}{1-d(q^{k+1}s)}\right)\left(a(q^ns) +
b(q^ns)\sgD(1)\right),
\end{equation} 
where $\sgD(qs)$ no longer appears.


$\bullet$ The kernel method consists of replacing $s$ by a series $\sigma$ in $t$ and $u$ such that the two following conditions are satisfied:
\begin{enumerate}
 \item[$(i)$] $1-d(\sigma) = 0$
 \item[$(ii)$] the substitution of $s$ by $\sigma$ in the right-hand
 side of (\ref{eq:base3}) yields a well defined series in $t$.
\end{enumerate}
When these conditions are satisfied, the left-hand side of (\ref{eq:base3}) vanishes and we obtain
\begin{equation}
\label{eq:base4}
\displaystyle 0 = \sum_{n=0}^{\infty}\left(\prod_{k=0}^{n-1}
\frac{c(q^k\sigma)}{1-d(q^{k+1}\sigma)}\right)\left(a(q^n\sigma) +
b(q^n\sigma)\sgD(1)\right).
\end{equation}
Let $\sigma$ be the unique power series in $t$ that is a root of the kernel $1-d(s)$:
$$ \displaystyle 
\sigma \equiv \sigma(t,u) =  \frac{1+t-2q-\sqrt{(1-t)(1-t-4q+4q^2)}}{2t(1-q)}.
$$ The right-hand side of (\ref{eq:base3}) is a power series in $t$
where all coefficients are polynomials in $s$, except for the term
$\displaystyle \frac{q}{1-q}\frac{s}{1-s}$ that appears in $b(q^0s)$
and may make the substitution $s = \sigma$ impossible. But, since
$1-d(\sigma) = 0$,
\begin{equation}
\label{eq:serker} \displaystyle \frac{q}{1-q}\frac{\sigma}{1-\sigma} = \frac{q}{1-q}\frac{t\sigma}{1-t\sigma}-1
\end{equation}
 where the right-hand side is a power series in $t$, so the left-hand
side is also a power series in $t$. Thus the substitution $s = \sigma$
leads to (\ref{eq:base4}), where all terms are power series in $t$
(with coefficients that are polynomials in $u$).

$\bullet$ The numerator of $1-d(s)$ is 
\begin{equation}
\label{eq:kernel}
 K(s) = (1-q)+(2q-t-1)s+(1-q)ts^2.
\end{equation} 
Since $K(s) =
t(1-q)(s-\sigma)(s-\sigma')$, where $\sigma'$ is the second root of
$K(s)$, we have the equality of the two coefficients of degree $0$ with respect to $s$:  $$t(1-q)\sigma\sigma' = (1-q),$$ thus
$$ \sigma' = 1/(t\sigma).$$
Then we deduce, for $k\geq 1$,
$$ \displaystyle 1-d(q^k\sigma) = \frac{(1-q^k)(1-q^kt\sigma^2)}{(1-q^k\sigma)(1- q^kt\sigma)}.$$ 
The products that appear during the iteration of the equation become
$$ \displaystyle
\prod_{k=0}^{n-1}\frac{c(q^k\sigma)}{1-d(q^{k+1}\sigma)} =
\left(\frac{(q-t)\sigma}{1-q}\right)^n\frac{q^{\binom{n+1}{2}}}{(q)_n(qt\sigma^2)_n}\frac{1-q^nt\sigma}{1-t\sigma}.$$

$\bullet$ From (\ref{eq:base4}) a division leads to
(\ref{eq:solution-functionnal-equation}).
\end{proof}

Some comments are in order on this result.  For $u=1$, the term $(q-t)
= (u-1)t$ vanishes and (\ref{eq:solution-functionnal-equation})
becomes
$$ \displaystyle A(t,1) =
-\frac{t}{\displaystyle t\frac{1-t\sigma(t,1)}{(1-\sigma(t,1))(1-t\sigma(t,1))}} =
\sigma(t,1)-1.
$$ Thus $\sigma(t,1)$ is the generating function for (possibly empty)
Dyck paths according to their size.

Moreover, we remark that the power series $\sigma(t,u)$ is also the
generating function for (possibly empty) Dyck paths, according to their size
and their number of \emph{lower} interactions, as already computed by Denise
and Simion~\cite{denise-simion95}.




%% The author would like to thanks Mireille Bousquet-M\'elou and Volker
%% Strehl for comments at different stage of this work.


%% Question : L'equation fonctionnelle definie une unique serie formelle
%% en $t$.  L'analyse permet d'isoler une serie formelle en $t$ (mais il
%% peut y en avoir une seconde)




%% Dans ma these il y a une explication combinatoire de ce lien.

\section{Dyck paths with small valleys and a $q$-algebraic equation}
\label{section:q-algebraic-equation}

To be able to write a $q$-algebraic equation for the series
$\sgUp(t,u)$ we consider a subset of Dyck paths, the paths with small
valleys, and another catalytic parameter. First we show in
Section~\ref{sec:chgt-of-object} that for an {\it ad hoc} valuation of
these paths, their generating function is also $\sgUp(t,u)$. Then, in
Section~\ref{sec:q-alg-eq}, we decompose these paths at the first
return to the axis to obtain the $q$-algebraic
equation~(\ref{eq:q-algeq}). Finally in Section \ref{sec:solve-q-eq}
we solve this equation using an Ansatz that will be discussed
further in Section~\ref{section:compare-approaches}.

\subsection{A slight change of combinatorial objects}
\label{sec:chgt-of-object}
\emph{Dyck paths with small valleys} are Dyck paths that avoid the
factor $\down\down\up\up$.  We define an {\it ad hoc} valuation of
such paths: there is a weight $t$ on each rise and a weight
\begin{equation}
\label{eq:val_val}
\gV(k) = \frac{q(1-q^{k+1}y)}{t(1-q)}
\end{equation}
 on each valley at height $k$. The generating function for weighted non-empty Dyck paths with small valleys is
\begin{equation}
\label{eq:def-val-SV}
\sgSV(y) \equiv \sgSV(t,u;y) = \sum_{w} t^n\prod_{k\geq 0}\gV(k)^{v_k},
\end{equation}
where $w$ runs over these Dyck paths, $n$ is the size of $w$ and $v_k$
the number of valleys at height $k$ in $w$.


\begin{lemma}
The generating function $\sgUp(t,u)$ for Dyck paths, defined
by~(\ref{eq:sg-Up}), and the generating function $\sgSV(t,u;y)$ for
Dyck paths with small valleys satisfy
\begin{equation}
\label{eq:model-change}
\sgUp(t,u) = \sgSV(t,u;1).
\end{equation} 
\end{lemma}
\begin{proof}
We group Dyck paths into sets of paths with the same sequence of peak
heights.  In each set $S$ there is a single path $w_S$ of minimal size
and we use it as the representative of the set.  This path is also the
unique path of $S$ that has small valleys.  All paths in $S$ are
obtained by "digging" independently the valleys of $w_S$, that is,
rewriting recursively factors $\down\up$ of $w_S$ in
$\down\down\up\up$ as long as the path remains above the horizontal
axis.


Figure~\ref{fig:toto} gives an example: for the sequence of heights
$2,3,1,3,3$ the path $w_S$ is drawn in black and the other paths in
$S$ are drawn in grey. There are 2 possibilities around the valley
$A$, only one around $B$ and $C$ and three around $D$. Moreover, these
choices are independent, so there are $6$ Dyck paths in $S$.
%% , among them there are ${\bf \up\up\down}\down\up{\bf \up\up\down\down\down\up\down\up\up\up\down}\down\up{\bf \up\down\down\down}$  and ${\bf \up\up\down}{\bf \up\up\down\down\down\up\down\up\up\up\down}\down\down\up\up{\bf \up\down\down\down}$ where bold letters correspond to $w_S$. 


\begin{figure}[ht!]
\begin{center}
\scalebox{0.5}{\input{path_with_small_valleys.pstex_t}}

\caption{The path with small valleys $w_S$ for the sequence of peak heights
   $2,3,1,3,3$.
\label{fig:toto}}
\end{center}
\end{figure}


In $w_S$ there are as many upper interactions as valleys.  Moreover,
each rewriting $\down\up \longrightarrow \down\down\up\up$ increases
the size and the number of upper interactions by one. For a valley $D$
in $w_S$ at height $k$, let $E$ and $F$ be respectively the vertex
preceding $D$ and following $D$ in $w_S$, see
Figure~\ref{fig:toto}. The generating function for all possible
subwalks between $E$ and $F$ obtained by digging is
$$ut + (ut)^2 + \ldots + (ut)^{k+1} = \frac{q(1-q^{k+1})}{(1-q)} =
tV(k)_{|y=1}$$ where $V(k)_{|y=1}$ denotes the valuation of valleys
in~(\ref{eq:val_val}) where $y=1$.  The factor $t$ on the right-hand
side corresponds to the only rise just before $F$ that belongs to
$w_S$.  Thus the generating function for paths of $S$ according to their
size and their number of upper interactions corresponds to the weight of
$w_S$, where a valley at height $k$ is weighted $V(k)_{|y=1}$ and a
rise $t$.  The summation over all the sets $S$, that is, over the paths
with small valleys, leads to~(\ref{eq:model-change}).
\end{proof}

\subsection{A $q$-algebraic equation}
\label{sec:q-alg-eq}

The variable $y$ that occurs in the weight of valleys is another
example of a catalytic variable since it allows us to write a
$q$-algebraic equation for paths with small valleys:

\begin{lemma}
The generating function for non-empty paths with small valleys satisfies
\begin{equation}
\label{eq:q-algeq}
\sgSV(y) = t + t\left(1+q\frac{1-qy}{1-q}\right)\sgSV(qy)
+ q\frac{1-qy}{1-q}\sgSV(y) + \left(q\frac{1-qy}{1-q} \right)^2\sgSV(qy)\sgSV(y).
\end{equation}
\end{lemma}

\begin{proof}
We split a path with small valleys at the first return to the axis,
called $A$ in Figure~\ref{fig:decomposition-SV}.  There are five cases
due to the avoidance of the factor $\down\down\up\up$ around the
vertex $A$.

\begin{figure}[ht!]
\centerline{\scalebox{0.5}{\input{decomposition-q-algebric.pstex_t}}}
\caption{Decomposition of paths with small valleys}
\label{fig:decomposition-SV}
\end{figure}


 A non-empty Dyck path with small valleys $w$ can be written as $w =
\up u \down v$ where $u$ and $v$ are two Dyck paths with small
valleys, possibly empty. We distinguish five cases according to the
emptiness of $u$ and $v$:

\begin{description}
\item[$u$ and $v$ are empty] The weight of the path $\up\down$ is
  $t$.
\item[only $v$ is empty] There is exactly one more rise in $\up u
  \down$ than $u$. Moreover all the valleys are one unit higher, thus
  a valley is weighted $V(k+1)$ in $\up u \down$ instead of $V(k)$ in
  $u$. The relation between the two weights is taken into account by
  the substitution $y \longrightarrow qy$. This explains why we use
  the catalytic variable $y$ in the weight of paths with small
  valleys.  Finally the generating function for paths in this case is
  $tC(qy)$.

\item[only $u$ is empty] There is exactly one more rise and one
  more valley at height $0$ in $\up\down v$ than in $v$, thus the
  generating function in this case is $tV(0)C(y)$.
\item[neither $u$ nor $v$ are empty] This case will be split into two cases
  because $\up\up$ can not be a prefix of $v$ without creating a
  factor $\down\down\up\up$ in the path $\up u \down v$. To avoid this
  case, $v$ begins with $\up\down$, so we factor the path in $\up u
  \down \up \down v'$ and we consider the emptiness of $v'$.
 \begin{description}
 \item[$v'$ is empty] There are two more rises and one more valley at
 height $0$ in $\up u \down \up \down$ than in $u$. Moreover the
 valleys in $u$ are one unit higher in $\up u \down \up \down$. Thus
 the generating function for paths in this case is $t^2V(0)C(qy)$.
 \item[$v'$ is non-empty] There are two more rises and two more
 valleys at height $0$ in $\up u \down\up\down v'$ than in $u$ and
 $v$. Moreover the valleys in the factor $u$ of $w$ are one unit
 higher than in $u$. The generating function for paths of this case is
 $\left(tV(0)\right)^2C(y)C(qy)$.
 \end{description}
\end{description}
These five cases lead to (\ref{eq:q-algeq}).
\end{proof}

\subsection{Solution of the $q$-algebraic equation}
\label{sec:solve-q-eq}


The solution of the $q$-algebraic equation~(\ref{eq:q-algeq}) begins with a change of unknown functions: we look for solutions of the form  
 
\begin{equation}
\label{eq:chgt-unknown}
 \displaystyle \sgSV(y) = \frac{\sgJ(qy)}{\alpha\sgJ(y)+\beta(y)\sgJ(qy)},
\end{equation}
where $\alpha$ is independent of $y$, $\beta(y)$ a polynomial in $y$,
and $\sgJ(y)$ a formal power series in $y$ such that $J(0) = 1$.  A
series $H(y) = \sum_{n \geq 0} h_ny^n$ is a \emph{basic hypergeometric
series} if there is a rational function $F(t,q,X)$
%,its \emph{reason}, 
such that $h_{n+1}/h_n = F(t,q,q^n)$ for all
$n\in\N$.

 
\begin{prop}
\label{prop:sol-q-algeq}
The unique formal power series in $t$ that satisfies the $q$-algebraic equation~(\ref{eq:q-algeq}) is  
\begin{equation}
\label{eq:sol-q-algeq}
\displaystyle \sgSV(y)= \frac{\displaystyle
t\sigma \sum_{n\geq 0}\left(\frac{(q-t)\sigma}{1-q} \right)^n\frac{q^{\binom{n+2}{2}-1}}{(q)_n(qt\sigma^2)_n}y^n
}{\displaystyle
\sum_{n\geq 0}\left(\frac{(q-t)\sigma}{1-q} \right)^n\frac{q^{\binom{n+1}{2}}(q^nt\sigma-q-q^{2n}t^2\sigma^2)}{(q)_n(qt\sigma^2)_n(t-q)}y^n
},
\end{equation}
where again $q \equiv ut$ and $\sigma$ is defined as in Proposition~\ref{prop:calculatoire}.
\end{prop}
\begin{proof}
We consider (\ref{eq:q-algeq}) with $\sgSV(y)$ replaced by its
expression ~(\ref{eq:chgt-unknown}).  This gives a single rational
function $R$ in $y$, $\sgJ(y)$, $\sgJ(qy)$ and $\sgJ(q^2y)$.  The
numerator $N$ of $R$ is a linear combination of $\sgJ(y)\sgJ(qy)$,
$\sgJ(qy)^2$, $\sgJ(q^2y)\sgJ(qy)$ and $\sgJ(q^2y)\sgJ(y)$.  We choose
$\displaystyle \beta(y) = -\frac{1-qy}{1-q}$ to remove the term
$\sgJ(q^2y)\sgJ(y)$, thus we can factor $J(qy)$ in $N$.  The other
factor of $N$ vanishes if and only if the following $q$-linear
equation holds:
\begin{equation}
\label{eq:q-linear}
\displaystyle t\alpha^2\sgJ(y) 
 - \left(1+\frac{(t-q)(1-qy)}{1-q}\right)\alpha \sgJ(qy) 
 + \sgJ(q^2y)  = 0. 
\end{equation}  

The evaluation at $y=0$ of (\ref{eq:q-linear}) implies that $\alpha$
is one of the two roots of a polynomial that is the
kernel~(\ref{eq:kernel}) in the proof of
Proposition~\ref{prop:calculatoire}.  We define $\alpha =
1/(t\sigma)$. We will explain later why we choose this root rather
than $\sigma$.  The change of unknown functions defined by this
analysis is
\begin{equation}
\label{eq:sigma_chgt}
\displaystyle C(y) = \frac{t\sigma\sgJ(qy)}{\displaystyle \sgJ(y) - \frac{1-qy}{1-q}t\sigma\sgJ(qy)},
\end{equation}
and leads to the $q$-linear equation~(\ref{eq:q-linear}) where $\alpha = 1/(t\sigma)$.
Since~(\ref{eq:q-linear}) is of degree $1$ in $y$ and by definition $\sgJ(y) = 1 + \sum_{n\geq 1} j_ny^n$, the extraction of the coefficient of $y^{n+1}$ in~(\ref{eq:q-linear}) gives a relation between $j_n$ and $j_{n+1}$, namely 
$$
\displaystyle j_{n+1} = \frac{(q-t)\sigma q^{n+1}}{(1-q)(1-q^{n+1})(1-q^{n+1}t\sigma^2)}\cdot j_n,
$$  
where we have again used the relation~(\ref{eq:kernel}) between the roots of the kernel to rewrite the denominator.
Thus $\sgJ(y)$ is the following basic hypergeometric series
$$
\displaystyle J(y) = \sum_{n\geq 0}\left(\frac{(q-t)\sigma}{1-q} \right)^n \frac{q^{\binom{n+1}{2}}}{(q)_n(qt\sigma^2)_n}y^n.
$$
We plug this expression in~(\ref{eq:sigma_chgt}) and we obtain~(\ref{eq:sol-q-algeq}). 
\end{proof}



\section{Comments}
\label{section:compare-approaches}

The two approaches used in Section~\ref{section:slice-equation} and
Section~\ref{section:q-algebraic-equation} to solve the same
enumerative problem share some common aspects that we want to
underline in this section.  First we will show in
Section~\ref{sec:slice-and-y} that the additional catalytic parameter,
counted by the variable $y$ and required to write the $q$-algebraic
equation, can also be taken into account by a solvable slice
equation. Then we discuss in Section~\ref{sec:homographic} the
different kinds of ``homographic'' change of unknown functions that
turn a $q$-algebraic equation into a $q$-linear one and we compare
their efficiency in our example. The most efficient Ansatz for our
example was guessed after considering the shape of the generating
function~(\ref{eq:sytemp}) computed in Section~\ref{sec:slice-and-y}.

%% of one of this change, corresponding to the Ansatz used in
%% Section~\ref{sec:solve-q-eq}, was conjectured after considering the
%% shape of the generating function~(\ref{eq:sytemp}) taking into account
%% the additional catalytic parameter and computed from the slice
%% functional equation in Section~\ref{sec:slice-and-y}.


\subsection{A slice equation for paths with small valleys}
\label{sec:slice-and-y}
To add the information on the length of the last descent of a path with small valleys we define the generating function
$$ \displaystyle 
\sgSVS(s) \equiv \sgSVS(t,q,y;s) =  \sum_{w} t^ns^l\prod_{k\geq 0}\gV(k)^{v_k},
$$ where $w$ runs over the non-empty Dyck paths with small valleys,
$n$ the size of $w$, $l$ the height of the last peak in $w$ and $v_k$
the number of valleys at height $k$ in $w$. ($V(k)$ is defined by
(\ref{eq:val_val})) The same kind of slice functional equation as
(\ref{eq:slice-decomposition}) holds for $\sgSVS(s)$. Moreover the
additional variable $y$ does not significantly modify the solution,
which is very similar to the one proposed in
Proposition~\ref{prop:calculatoire}.

\begin{prop}
The generating function for Dyck paths with small valleys counted according to the size, the weight $\gV(k)$ of valleys and the length of the last descent satisfies
\begin{equation}
\label{eq:basey}
\begin{array}{lcl}
\sgSVS(s) & = & \displaystyle \frac{ts}{1-ts} + \frac{ts}{1-ts}\frac{q}{1-q}\left(\sgSVS(s)-y\sgSVS(qs) \right) \\
\ & \ & \displaystyle + \frac{q}{1-q}\left(\frac{s}{1-s}\left(\sgSVS(1)-\sgSVS(s)\right) - y\frac{qs}{1-qs}\left(\sgSVS(1)- \sgSVS(qs) \right) \right)  
\end{array}
\end{equation}
and the elimination of $\sgSVS(qs)$ and $\sgSVS(s)$ leads to the solution
\begin{equation}
\label{eq:sytemp}
\displaystyle \sgSVS(1) = -
\frac{\displaystyle \sum_{n\geq 0} 
  \left(\frac{(q-t)\sigma}{1-q}\right)^n
  \frac{q^{\binom{n+1}{2}}}
       {(q)_n(qt\sigma^2)_n}
  \frac{tq^n\sigma}{1-t\sigma}y^n
}{\displaystyle \sum_{n\geq 0}
  \left(\frac{(q-t)\sigma}{1-q}\right)^n
  \frac{q^{\binom{n+1}{2}}}
       {(q)_n(qt\sigma^2)_n}
  \frac{\left(q^nt\sigma - q - (q^nt\sigma)^2\right)}{(q-t)(1-t\sigma)}
  y^n
} = \sgSV(y).
\end{equation}
\end{prop}
\begin{proof}
Writing down the equation is similar to
Lemma~\ref{lem:slice-decomposition-equation}. We concentrate on the
variations.  We split Dyck paths with small valleys into the set
$\mathcal{T}_1$ of paths with exactly one peak, the set
$\mathcal{T}_2$ of paths where the last peak is higher than the
previous one and the set $\mathcal{T}_3$ of paths where the last peak
is not higher than the previous one. Let $T_i(s)$ be the generating
function defined by considering the paths of $\mathcal{T}_i$.  The
former division leads to
$$
\sgSVS(s) = T_1(s) + T_2(s) + T_3(s).
$$

Figure~\ref{fig:sliceSV} gives examples of each set built by
inserting a factor $\up^k\down^k$ at the end of a possibly empty Dyck
path with small valleys. The avoidance of the factor $\up\up\down\down$
implies that the vertex $B$ is necessarily exactly one unit below the
vertex $A$ and that the vertex $E$ is exactly one unit above the
vertex $F$.

\begin{figure}[ht!]
\scalebox{0.5}{\input{slide_decompositionSV.pstex_t}}
\caption{The partition of Dyck paths with small valleys}
\label{fig:sliceSV}
\end{figure}

In terms of generating functions, the case of $\mathcal{T}_1$ is equal to $\mathcal{S}_1$:
$$ \displaystyle T_1(s) = \frac{ts}{1-ts}.$$ 
When building a path of $\mathcal{T}_2$, it remains only to choose the
difference $j$ between the heights of $A$ and $C$ thus
$$
\displaystyle T_2(s) = \sum_{l \geq 1}\sum_{w \in \mathcal{E}_l}\left(t^ns^l\gV(l-1)\sum_{j\geq 1} (ts)^j\right) = \frac{ts}{1-ts}\sum_{l \geq 1}\sum_{\mathcal{E}_l}t^ns^l\gV(l-1)
$$
where $\mathcal{E}_l$ is the set of Dyck paths with small valleys whose last peak is at height $l$.


The height $i$ of the vertex $E$ is the unique parameter that defines the addition of $\up\down$ creating a path of $\mathcal{T}_3$, thus
$$
\displaystyle T_3(s) = \sum_{l \geq 1}\sum_{w \in \mathcal{E}_l}\left(t^n\sum_{i=1}^lts^i\gV(i-1)\right).
$$  


Intuitively, the valuation of a small valley at height $k$ is linked to
the choice of the height of the valleys $B$ or $F$, between $0$ and
$k$. This choice has disappeared in the building of paths with small
valleys. In fact with this valuation we only anticipate the summation
implied by this choice (and add the catalytic variable $y$). Using
$\gV(k) = q(1-q^{k+1}y)/t/(1-q)$, the two previous summations become
$$
\displaystyle T_2(s) = \frac{ts}{1-ts}\frac{q}{1-q}\left(\sgSVS(s)-y\sgSVS(qs) \right)
$$
and
$$
\displaystyle T_3(s) = \frac{q}{1-q}\left(\frac{s}{1-s}\left(\sgSVS(1)-\sgSVS(s)\right) - y\frac{qs}{1-qs}\left(\sgSVS(1)- \sgSVS(qs) \right) \right).
$$

The functional equation~(\ref{eq:basey}) can be written
\begin{equation}
\displaystyle \sgSVS(s) = a_y(s) + b_y(s)\sgSVS(1) + c_y(s)\sgSVS(qs) + d_y(s)\sgSVS(s)
\end{equation}
where
$$ \left \{ \begin{array}{lclcl}
a_y(s) & = & \displaystyle \frac{ts}{1-ts} & = & a(s) \\
b_y(s) & = & \displaystyle \frac{q}{1-q}\left( \frac{s}{1-s} - y\frac{qs}{1-qs} \right) & \ & \ \\
c_y(s) & = & \displaystyle \frac{q}{1-q}\left( y\frac{qs}{1-qs} - y\frac{ts}{1-ts} \right) & = & yc(s)\\
d_y(s) & = & \displaystyle \frac{q}{1-q}\left( \frac{ts}{1-ts} - \frac{s}{1-s} \right) & = & d(s). 
\end{array} \right .$$
The coefficients $a(s)$, $c(s)$ and $d(s)$ already appeared in the proof of Proposition~\ref{prop:calculatoire}

To solve this equation which is similar to (\ref{eq:slice-decomposition}) we use the same method as in Proposition~\ref{prop:calculatoire}. Since 
$$ \displaystyle \frac{c_y(q^ks)}{1-d_y(q^{k+1}s)} = y
\frac{c(q^ks)}{1-d(q^{k+1}s)},$$ there is an additional factor $y^n$
in the terms of the summation due to the iteration. Moreover $1-d_y(s)
= 1 - d(s)$, thus the kernel method again leads to the substitution $s
= \sigma$ independent of $y$. We have
\begin{align*}
\displaystyle \sgSVS(1) &= -
\frac{\displaystyle \sum_{n\geq 0} 
  \left(\frac{(q-t)\sigma}{1-q}\right)^n
  \frac{q^{\binom{n+1}{2}}}
       {(q)_n(qt\sigma^2)_n}
  \frac{tq^n\sigma}{1-t\sigma}y^n
}{\displaystyle \sum_{n\geq 0}
  \left(\frac{(q-t)\sigma}{1-q}\right)^n
  \frac{q^{\binom{n+1}{2}}}
       {(q)_n(qt\sigma^2)_n}
  \frac{1-q^nt\sigma}{1-t\sigma}\frac{q}{1-q}\left(\frac{q^n\sigma}{1-q^n\sigma} - y\frac{q^{n+1}\sigma}{1-q^{n+1}\sigma}\right)y^n
} \\
&= \frac{P(y)}{Q(y)}.
\end{align*}
To expand the denominator $Q(y)$  according to powers of $y$ we extract the coefficient of $y^{n}$.  For $n \geq 1$ we obtain directly the coefficient that we observe in (\ref{eq:sytemp}) but for $n = 0$ we have
$$
\displaystyle [y^0]Q(y) = \frac{q}{1-q}\frac{\sigma}{1-\sigma} = \frac{t\sigma-q-t^2\sigma^2}{(q-t)(1-t\sigma)} 
$$ 
where the second equality uses the fact that $\sigma$ satisfies (\ref{eq:kernel}). 
Then $P(y)$ and $Q(y)$ are two basic hypergeometric series.
\end{proof}


\subsection{On solution of certain $q$-quadratic equations}
\label{sec:homographic}
The solution of the $q$-algebraic equation (\ref{eq:q-algeq}) requires two main
steps: a Riccatti-like Ansatz and the solution of the resulting
$q$-linear equation. We discuss here the compatibility of these two
methods in the general case of $q$-quadratic equations defined by
 \begin{equation}
\label{eq:generique}
\displaystyle f_1(y)C(qy)C(y) + f_2(y)C(qy) + f_3(y)C(y) + f_4(y) = 0
\end{equation} 
where $f_i(y)$ are polynomials in $y$.  All the following remarks are
 motivated by the question which is open to the best of our knowledge:
 is it possible to check if there exists a solution of
 (\ref{eq:generique}) that could be written
\begin{equation}
\label{eq:homographic}
\displaystyle C(y) = \frac{\alpha(y)H(qy) + \beta(y)H(y)}{\gamma(y)H(qy) + \delta(y)H(y)}
\end{equation} 
where $\alpha(y)$, $\beta(y)$, $\gamma(y)$ and $\delta(y)$ are
polynomials in $y$ and $H(y)$ is a basic hypergeometric series?  In
the case of a positive answer can we compute this solution?

This question, maybe too ambitious, asks for an extension, using the
Riccatti-like Ansatz, of the algorithm proposed by Abramov, Paule and
Petkov{\v s}ek in \cite{abramov-paule-petkovsek98} to find basic
hypergeometric series solution of a $q$-linear equation. We use our
enumeration of Dyck paths according to their size and their number of
upper interactions to present some basic facts around this question.

\subsubsection{On solution of $q$-linear equations}

The aim of the Riccatti-like Ansatz is to turn the equation
(\ref{eq:generique}) into a \emph{solvable} $q$-linear equation. To
understand this goal, we discuss what we mean by the adjective
``solvable'' in this context.

A series $H(y) = \sum_{n\geq 0}h_ny^n$ satisfies a $q$-linear equation
if
\begin{equation}
\label{eq:gen-lin}
\displaystyle \sum_{k=0}^N c_k(y)H(q^ky) = 0.
\end{equation}
where $(c_k(y))_{k=1\ldots N}$ are polynomials in $y$ with rational
functions of $t$ and $q$ as coefficients and without loss of
generality $y$ does not divide all the $c_k(y)$. The extraction of
coefficients of $y^K$ in the equation (\ref{eq:gen-lin}) leads, for
$K$ large enough, to a linear recurrence $(L)$ satisfied by the
coefficients $(h_n)_{n \geq 0}$ with coefficients which are rational
functions of $t$, $q$ and $q^K$.  Let $D$ be the maximal degree with
respect to $y$ of the polynomials $c_k(y)$. The recurrence $(L)$
corresponding to the extraction of the coefficient $y^K$ involves at
least $h_K$ and $h_{K-D}$ and in general some terms $h_{K+i}$, where $
1 \leq i < D$.  The value of $D$ appears as a good approximation of
the difficulty of a $q$-linear equation.


If $D=1$, we recognise a case that corresponds to the $q$-equation
(\ref{eq:q-linear}) that appears in our first solution of the $q$-algebraic
equation (\ref{eq:q-algeq}). The same argument holds in this more general case,
leading to a solution that is a sum of a polynomial and a basic
hypergeometric series.

If $D>1$, there is no systematic way to compute solutions of the
$q$-linear equation without any assumption on them. If one looks for
basic hypergeometric (and polynomial) solutions, Abramov, Paule and
Petkov{\v s}ek proposed in \cite{abramov-paule-petkovsek98} an
algorithm to find them or else to prove that there is no such
solution.

\begin{ex}
\label{ex:pas-sol}
To solve the $q$-quadratic equation (\ref{eq:q-algeq}) we try the
Riccatti-like Ansatz used successfully by Brak and Prellberg for their
problems in \cite{brak-prellberg95}:
\begin{equation}
\label{eq:lin-direct}
\displaystyle C(y) = \frac{(1-q)^2t\sigma}{q^2}\frac{H(qy)}{H(y)} - \frac{t(1-q)(1-q^2y)}{q^2(1-qy)^2}.
\end{equation}
This leads to a $q$-linear equation where $D=6$ and that does not have a
basic hypergeometric series (or a polynomial) as solution. 
\end{ex}

\subsubsection{Riccatti-like Ans\"atze}

The two Riccatti-like Ans\"atze (\ref{eq:sigma_chgt}) and
(\ref{eq:lin-direct}) linearise the same $q$-quadratic equation
(\ref{eq:q-algeq}) but they lead to two different kinds of $q$-linear
equations with regard to their solutions. This fact motivates the
discussion about the variations of the Ans\"atze that we found in the
literature \cite{brak-prellberg95}, \cite{janse-van-rensburg01}. All
these variations correspond to a particular ``homographic'' change of
unknown functions that could be written, with gain of generality as
(\ref{eq:homographic}) without assuming that $H(y)$ is a basic
hypergeometric series.  With this change of unknown functions,
(\ref{eq:generique}) becomes the vanishing of a rational fraction then
of its numerator. This numerator could be factorised in $H(qy)L(y)$
where $L(y)$ is a $q$-linear equation involving $H(q^2y)$, $H(qy)$ and
$H(y)$ provided the following \emph{linearision condition},
corresponding to the coefficient of $H(y)H(q^2y)$ of the numerator, is
satisfied
\begin{equation}
\label{eq:condition-linearisation}
\displaystyle f_1(y)\alpha(qy)\beta(y) + f_2(y)\alpha(qy)\delta(y) +
f_3(y)\beta(y)\gamma(qy) + f_4(y)\gamma(qy)\delta(y) = 0.
\end{equation}
The aim of the change of unknown is to obtain a solvable $q$-linear
equation $L(y)$ that depends on the choice of $\alpha(y)$, $\beta(y)$,
$\gamma(y)$ and $\delta(y)$.

A possible way to prolong the general study of these Ans\"atze is to
deduce from the linearision condition
(\ref{eq:condition-linearisation}) an expression of $\delta(y)$ in
function of $\alpha(y)$, $\beta(y)$ and $\gamma(y)$. We obtain a
$q$-linear equation where $\alpha(y)$, $\beta(y)$ and $\gamma(y)$ are
parameters. Applying the algorithm of Abramov, Paule and Petkov{\v
s}ek to this equation may lead to additional relations between these
parameters to guarantee the existence of a basic hypergeometric
solution or to prove its nonexistence.

Here, we only discuss assumptions made in the literature on the values
$\alpha(y)$, $\beta(y)$, $\gamma(y)$ and $\delta(y)$ with which these
polynomials are almost unambiguously defined by the coefficients of the
given $q$-quadratic equation (\ref{eq:generique}), and that sometimes
lead to a $q$-linear equation with basic hypergeometric solutions.

\begin{itemize}
\item In \cite{brak-prellberg95} Brak and Prellberg suggested 
assuming that $\gamma(y)=0$, and $\alpha(y)/\delta(y)$ is independent of
$y$. The values of $\beta(y)$ and $\delta(y)$ are chosen to satisfy
the linearision condition~(\ref{eq:condition-linearisation}) and
$\alpha(y)/\delta(y)$ is fixed by the evaluation at $y=0$ of the
$q$-linear equation. For our equation (\ref{eq:q-algeq}) for the
enumeration of Dyck paths, it has already been pointed out in Example~\ref{ex:pas-sol} that the resulting $q$-linear equation does not have
a basic hypergeometric series as solution.
\item In~\cite{janse-van-rensburg01} Janse Van Rensburg used a
change of unknown functions where again $\gamma(y)=0$, but now
$\alpha(y)$ is independent of $y$. In our example of
(\ref{eq:q-algeq}) this assumption leads to the third Ansatz
\begin{equation}
\displaystyle C(y) = \frac{(1-q)^2t\sigma}{q^2{\bf (1-qy)^2}}\frac{H(qy)}{H(y)}- \frac{t(1-q)(1-q^2y)}{q^2(1-qy)^2}.
\end{equation}
In the resulting $q$-linear equation, the maximal degree $D$ of the
coefficients is $3$ and we were able to find a basic hypergeometric
solution using the algorithm of Abramov, Paule and Petkov{\v s}ek.
\item With a bit of reverse-engineering on the solution derived in
Section \ref{sec:slice-and-y}, we discovered that the assumption
$\alpha(y) = 1$, $\beta(y)=0$ and $\delta(y)$ independent of $y$ leads
to the most efficient Riccatti-like Ansatz (\ref{eq:sigma_chgt}) for
our example.  (The maximal degree $D$ of the coefficients is $1$ in
the $q$-linear equation (\ref{eq:q-linear}) )
\end{itemize}

%% \subsection{Homographic changes of unknown function for $q$-algebraic equations}
%% \label{sec:homographic}

%% Equation~(\ref{eq:q-algeq}) is an $q$-algebraic equation that could be written 
%% \begin{equation}
%% \label{eq:generique}
%% \displaystyle f_1(y)C(qy)C(y) + f_2(y)C(qy) + f_3(y)C(y) + f_4(y) = 0
%% \end{equation} 
%% where $f_i(y)$ are polynomials in $y$.  Brak and
%% Prellberg~\cite{brak-prellberg95} then Van
%% Rensburg~\cite{janse-van-rensburg01}, have solved many examples of
%% this kind of equations to enumerate sets of polyominos or partially
%% directed walks. All the solution are computed after a ``homographic''
%% change of unknown function that could be written, with gain of
%% generality as
%% \begin{equation}
%% \displaystyle C(y) = \frac{\alpha(y)H(qy) + \beta(y)H(y)}{\gamma(y)H(qy) + \delta(y)H(y)}
%% \end{equation} 
%% where $\alpha(y)$, $\beta(y)$, $\gamma(y)$ and $\delta(y)$ are polynomials in $y$.

%% With this change of unknown function, Equation~(\ref{eq:generique})
%% becomes the vanishing of a rational fraction then of its
%% numerator. This numerator could be factorized in $H(qy)L(y)$ where
%% $L(y)$ is a $q$-linear equation involving $H(q^2y)$, $H(qy)$ and
%% $H(y)$ as soon as the following \emph{linearization condition},
%% corresponding to the coefficient of $H(y)H(q^2y)$ of the numerator, is
%% satisfied
%% \begin{equation}
%% \label{eq:condition-linearisation}
%% \displaystyle f_1(y)\alpha(qy)\beta(y) + f_2(y)\alpha(qy)\delta(y) +
%% f_3(y)\beta(y)\gamma(qy) + f_4(y)\gamma(qy)\delta(y) = 0.
%% \end{equation}
%% The aim of the change of unknown is to obtain a solvable
%% $q$-linear equation $L(y)$. Here we look for a solution $H(y)$ that is
%% a basic hyper-geometric series. The existence of such a solution
%% depends on the choice of $\alpha(y)$, $\beta(y)$, $\gamma(y)$ and
%% $\delta(y)$.


%% Brak et Prellberg suggested to assume that $\delta(y)=0$,
%% $\gamma(y)=1$ and $\alpha$ is independent of $y$. The value $\beta(y)$
%% is chosen to satisfy the linearization
%% condition~(\ref{eq:condition-linearisation}) and $\alpha$ is fixed by
%% the evaluation at $y=0$ of the $q$-linear equation $L(y)$.
%% In~\cite{brak-prellberg95} it always leads to a $q$-linear equation
%% $L(y)$ which is of degree one according to $y$ and the initial
%% conditions are such that $L(y)$ admits a basic hyper-geometric series
%% as solution.  In our case of Equation~(\ref{eq:q-algeq}) those
%% assumptions lead to a $q$-linear equation that do not admit such kind
%% of solution (It was checked using the algorithm proposed
%% in~\cite{abramov-paule-petkovsek98} by Abramov, Paule and Petkovsek).


%% In~\cite{janse-van-rensburg01} Janse Van Rensburg uses a change of
%% unknown function where again $\delta(y)=0$ and $\alpha$ is independent
%% of $y$ but now $\gamma(y)$ depends on $y$. He guess a value for
%% $\gamma(y)$ that leads again to a $q$-linear equation of degree one
%% with respect to $y$ that admit a basic hyper-geometric series as
%% solution. For Equation~(\ref{eq:q-algeq}), motivated by its
%% coefficients, we assume that $\gamma(y) = (1-qy)^2$. An analysis leads
%% to the following change of unknown function
%% \begin{equation} 
%% \displaystyle
%% C(y) = \frac{(1-q)^2t\sigma H(qy)-t(1-q)(1-q^2y)H(y)}{q^2(1-qy)^2H(y)}.
%% \end{equation} 
%% We obtain a $q$-linear equation $L(y)$ whose degree with respect to
%% $y$ is three. It admits a basic hyper-geometric solution computable
%% with the algorithm of Abramov, Paule and
%% Petkovsek~\cite{abramov-paule-petkovsek98}. During this algorithm
%% $\sigma$ is used as a free variable. We only use the
%% relation~(\ref{eq:kernel}) satisfied by $\sigma$ to let appear the
%% terms $(q)_n(qt\sigma^2)_n$ and recover the
%% expression~(\ref{eq:sol-q-algeq}).


%% In Section~\ref{section:q-algebraic-equation} we assumed that
%% $\alpha(y)=1$, $\beta(y)=0$ and $\gamma(y)$ is independent of $y$ to
%% start an analysis that leads to the change of unknown
%% function~(\ref{eq:chgt-unknown}). In this case we obtain, as for the
%% equations solved in~\cite{brak-prellberg95} and
%% \cite{janse-van-rensburg01}, a $q$-linear equation $L(y)$ of degree
%% one in $y$ that admits as solution a basic hypergeometic series.  We
%% ``discovered'' this change of unkown using the work in
%% Section~\ref{sec:slice-and-y}: According to
%% Equation~(\ref{eq:sytemp}), $C(y) = D(1)$ is a quotient of to basic
%% hyper-geometric series whose reasons $F_1(X)$ and $F_2(X)$ are
%% similar. Thus we introduce the series $J(y)$ whose reason is the
%% greater common divisor of $F_1(X)$ and $F_2(X)$.  Inspired by the
%% terms $(q)_n(qt\sigma^2)_n$, we consider an approriate linear sum of
%% $J(y)$, $J(qy)$ and $J(q^2y)$ that leads to
%% Equation~(\ref{eq:q-linear}), where $\alpha=1/(t\sigma)$.  Using this
%% Equation~(\ref{eq:q-linear}) to rewrite the denominator of Equation
%% (\ref{eq:sytemp}) we recognize Equation~(\ref{eq:sigma_chgt}). Then we
%% start the analysis on the change of unknown function with the
%% appropriate assumptions : $\alpha(y)=1$, $\beta(y)=0$ and $\gamma(y)$
%% independent of $y$. The efficiency comes from the fact that the
%% $q$-linear equation $L(y)$, Equation~(\ref{eq:q-linear}), is of degree one with
%% respect to $y$.

%% YLB : Je n�arrive a formuler clairement ta remarque sur le fait que 
%%       E(y) = 1/C(y) il faudrait que je l�ajoute mais pour l�instant c�est
%%       deja assez confus.

%\newpage

\paragraph{ \bf Acknowledgements} 
I thank Mireille Bousquet-M\'elou and Volker Strehl for valuable
comments on this work. I am grateful to Mike Robson who also helped
improving the English.

\begin{thebibliography}{10}

\bibitem{abramov-paule-petkovsek98}
S.~A. Abramov, P.~Paule, and M.~Petkov{\v{s}}ek.
\newblock {$q$}-{H}ypergeometric solutions of {$q$}-difference equations.
\newblock {\em Discrete Math.}, 180(1-3):3--22, 1998.

\bibitem{bousquet-melou-petkovsek00}
M.~Bousquet-M{\'e}lou and M.~Petkov{\v{s}}ek.
\newblock Linear recurrences with constant coefficients: the multivariate case.
\newblock {\em Discrete Math.}, 225:51--75, 2000.

\bibitem{bousquet-melou-rechnitzer03}
M.~Bousquet-M{\'e}lou and A.~Rechnitzer.
\newblock The site-perimeter of bargraphs.
\newblock {\em Adv. in Appl. Math.}, 31(1):86--112, 2003.

\bibitem{bousquet-melou-viennot92}
M.~Bousquet-M{\'e}lou and X.~G. Viennot.
\newblock Empilements de segments et {$q$}-\'enum\'eration de polyominos
  convexes dirig\'es.
\newblock {\em J. Combin. Theory Ser. A}, 60(2):196--224, 1992.

\bibitem{brak-prellberg95}
R.~Brak and T.~Prellberg.
\newblock Critical exponents from nonlinear functional equations for partially
  directed cluster models.
\newblock {\em J. of Stat. Phys.}, 78(3-4):701--730, 1995.

\bibitem{denise-simion95}
A.~Denise and R.~Simion.
\newblock Two combinatorial statistics on {D}yck paths.
\newblock {\em Discrete Math.}, 137(1-3):155--176, 1995.

\bibitem{foster-yeomans91}
D.P. Foster and J.~Yeomans.
\newblock Competition between self-attraction and adsorption in directed
  self-avoiding polymers.
\newblock {\em Physica A}, 177:443--452, 1991.

\bibitem{janse-van-rensburg01}
E.~J. Janse~van Rensburg.
\newblock Interacting columns: generating functions and scaling exponents.
\newblock {\em J. Phys. A}, 33(42):7541--7554, 2000.

\bibitem{K67}
J.~A. Klarner.
\newblock Cell growth problems.
\newblock {\em Can. J. Math.}, 19(4):851--863, 1967.

\bibitem{YLB04}
Y.~Le~Borgne.
\newblock {\em Variation combinatoires sur des classes d'objets compt{\'e}es
  par la suite de Catalan}.
\newblock PhD thesis, Universit{\'e} Bordeaux I, December 2004.
\newblock (French).

\bibitem{YLB05}
Y.~Le~Borgne.
\newblock Counting upper interactions in {D}yck paths.
\newblock In {\em Proceedings FPSAC05}, June 2005.

\bibitem{DF93}
Delest M.-P. and F\'edou J.-M.
\newblock Enumeration of skew Ferrers diagrams.
\newblock {\em Discrete Math}, 112:65--79, 1993.

\bibitem{dharandco2002}
R.~Rajesh, D.~Dhar, D.~Giri, S.~Kumar, and Y.~Singh.
\newblock Adsorption and collapse transitions in a linear polymer chain near an
  attractive wall.
\newblock {\em Physical Review E}, 65:056124, 2002.

\bibitem{viennot86}
G.~X. Viennot.
\newblock Heaps of pieces. {I}. {B}asic definitions and combinatorial lemmas.
\newblock In {\em Combinatoire \'enum\'erative}, volume 1234 of {\em Lecture
  Notes in Math.}, pages 321--350. Springer, Berlin, 1986.

\bibitem{zeilberger00}
D.~Zeilberger.
\newblock The umbral transfer-matrix method. {I}. {F}oundations.
\newblock {\em J. Combin. Theory Ser. A}, 91(1-2):451--463, 2000.

\end{thebibliography}


\end{document}

