# Statistics on Lattice Walks and q-Lassalle Numbers

Lenny Tevlin

► To cite this version:

Lenny Tevlin. Statistics on Lattice Walks and q-Lassalle Numbers. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.841-852, 10.46298/dmtcs.2528 . hal-01337769

HAL Id: hal-01337769

https://hal.science/hal-01337769

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Statistics on Lattice Walks and $q$-Lassalle Numbers

Lenny Tevlin†

Liberal Studies, New York University, New York, N.Y. 10003, U.S.A.

**Abstract.** This paper contains two results. First, I propose a $q$-generalization of a certain sequence of positive integers, related to Catalan numbers, introduced by Zeilberger, see Lassalle (2010). These $q$-integers are palindromic polynomials in $q$ with positive integer coefficients. The positivity depends on the positivity of a certain difference of products of $q$-binomial coefficients.

To this end, I introduce a new inversion/major statistics on lattice walks. The difference in $q$-binomial coefficients is then seen as a generating function of weighted walks that remain in the upper half-plane.

**Résumé.** Cet document contient deux résultats. Tout d'abord, je vous propose un $q$-generalization d'une certaine séquence de nombres entiers positifs, liés à nombres de Catalan, introduites par Zeilberger (Lassalle, 2010). Ces $q$-integers sont des polynômes palindromiques à $q$ à coefficients entiers positifs. La positivité dépend de la positivité d'une certaine différence de produits de $q$-coefficients binomial.

Pour ce faire, je vous présente une nouvelle inversion/major index sur les chemins du réseau. La différence de $q$-binomial coefficients est alors considérée comme une fonction de génération de trajets pondérés qui restent dans le demi-plan supérieur.

**Keywords:** lattice walks, statistics on words, $q$-integers

# 1 Introduction to Lassalle's Sequences and their $q$-analogs.

Michel Lassalle [Las12] has discussed two related sequences of numbers $A_k$ and $\alpha_k$. $\{A_k\}$ is generated by the following recurrence:

$$A_n = (-1)^{n-1}C_n + \sum_{j=1}^{n-1} (-1)^{n-j-1} \binom{2n-1}{2j-1} A_j C_{n-j}, \quad A_1 = 1$$

The second sequence is

$$\alpha_n = \frac{2A_n}{C_n}$$

<footnote>†Email: ltevlin@nyu.edu</footnote>
He proved that both $A_n$ and $\alpha_n$ are positive integers and each sequence is increasing (and more). (It turns out that the second sequence is simply related to power sums of zeros of Bessel function $J_0(z)$). It is intriguing to inquire whether there is a natural $q$-analog of these numbers. It may be generated by a $q$-analog of the above recurrence (with $C_n(q) = \frac{1}{[n+1]_q} \begin{bmatrix} 2n \\ n \end{bmatrix}_q$, a $q$-Catalan):

$$A'_{n}(q) = (-1)^{n-1} q^{n-1} C_{n}(q) + \sum_{j=1}^{n-1} (-1)^{n-j-1} q^{n-j} \begin{bmatrix} 2n-1 \\ 2j-1 \end{bmatrix}_{q} A'_{j}(q) C_{n-j}(q), \quad (1)$$

but a slightly renormalized version looks neater:

$$A_n(q) = (-1)^{n-1}q^{3-2n}C_n(q) + (-1)^n q^{3-2n} [2n-1]_q C_{n-1}(q) \\ + \sum_{j=2}^{n-1} (-1)^{n-j-1} q^{2j-2n} \begin{bmatrix} 2n-1 \\ 2j-1 \end{bmatrix}_q A_j(q) C_{n-j}(q) \quad (2)$$

with $A_1(q) = 1$. It turns out that $A_n(q)$ are monic unimodal palindromic polynomials in $q$ with positive integer coefficients. Here are some examples:

### Example 1

$$A_2(q) = 1$$

$$A_3(q) = 1 + q + q^2 + q^3 + q^4$$

$$A_4(q) = 1 + 2q + 3q^2 + 5q^3 + 6q^4 + 7q^5 + 8q^6 + 7q^7 + 6q^8 + 5q^9 + 3q^{10} + 2q^{11} + q^{12}$$

$$A_5(q) = 1 + 3q + 6q^2 + 12q^3 + 19q^4 + 29q^5 + 41q^6 + 54q^7 + 67q^8 + 80q^9 + 89q^{10} + 96q^{11} + 98q^{12} \\ + 96q^{13} + 89q^{14} + 80q^{15} + 67q^{16} + 54q^{17} + 41q^{18} + 29q^{19} + 19q^{20} + 12q^{21} + 6q^{22} + 3q^{23} + q^{24}$$

The second Lassalle's sequence $\alpha_k$ has the following $q$-analog:

$$\alpha_n = \frac{(1 + q^n) A_n(q)}{C_n(q)} \quad (3)$$

And each of $\alpha_n(q)$ is also a monic unimodal palindromic polynomial in $q$ with positive integer coefficients. Here are examples of $\alpha_n(q)$.

### Example 2

$$\alpha_1(q) = 1 + q$$

$$\alpha_2(q) = 1$$

$$\alpha_3(q) = 1 + q$$

$$\alpha_4(q) = 1 + 2q + 2q^2 + 2q^3 + q^4$$

$$\alpha_5(q) = 1 + 3q + 5q^2 + 8q^3 + 9q^4 + 9q^5 + 8q^6 + 5q^7 + 3q^8 + q^9$$
The proof of positivity of $\alpha_k$ relies (in addition to certain divisibility properties) on the positivity of

$$ \binom{n}{k-1} \binom{n}{k} - \binom{n}{k-2} \binom{n}{k+1} $$

and Lassalle used the combinatorial interpretation of this difference of binomial coefficients as a generating function of the number of NSEW walks on a square lattice that start at the origin and finish at $(2k - n - 1, 1)$ [GKS92].

Similarly, the positivity of $\alpha_k(q)$ requires the positivity of

$$ \left[ \binom{n}{k-1} \right]_q \left[ \binom{n}{k} \right]_q - q^2 \left[ \binom{n}{k-2} \right]_q \left[ \binom{n}{k+1} \right]_q \quad (4) $$

However in this case a combinatorial interpretation has to be developed.

## 2 Introduction to q-enumeration of Lattice walks

To understand the positivity of (4) combinatorially, i.e. as a generating function of certain weighted lattice walks, I first interpret the q-version of the generating function of all NSEW walks as a generating function of a certain (new) inversion statistics on lattice walks.

The total number of lattice walks from $(0, 0)$ to $(c, d)$ of length $n$ is given by [DR84]

$$ \binom{n}{\frac{1}{2}(n-c+d)} \binom{n}{\frac{1}{2}(n-c-d)} $$

Think of a given walk as a word $w$ composed of letters $N, S, E, W$. Then, the walk inversion statistics is defined

**Definition 1**

$$ \mathrm{winvN}(w) = \sum_{N \in w} \#S \text{ to the left of } N $$

$$ \mathrm{winvW}(w) = \sum_{W \in w} \#S + \#N + \#E \text{ to the left of } W $$

$$ \mathrm{winvE}(w) = \sum_{E \in w} \#S + \#N + 2\#W \text{ to the left of } E $$

$$ \mathrm{wpinv}(w) = \mathrm{winvN}(w) + \mathrm{winvW}(w) + \mathrm{winvE}(w) $$

**Example 3** Here are the inversions of the walks (from left to right) on Fig. 1:

$$ \mathrm{WNEN} = 2 \cdot 1 + 1 = 3 $$

$$ \mathrm{ENWN} = 1 + 1 = 2 $$

$$ \mathrm{NWNE} = 1 + (2 + 2 \cdot 1) = 5 $$

$$ \mathrm{NENW} = 1 + (2 + 1) = 4 $$

$$ \mathrm{WNNE} = 2 + 2 \cdot 1 = 4 $$

$$ \mathrm{ENNW} = 1 + 2 = 3 $$
<figure><img src="image_2.png" /><figcaption>Fig. 1: Some walks from (0, 0) to (0, 2) with $n = 4$ steps.</figcaption></figure>

Denote the set of all lattice walks from $(a, b)$ to $(c, d)$ in $n$ letters (steps) by $P_n((a, b) | (c, d))$. The $q$-analog of the walk enumeration formula is the following generating function.

**Proposition 1**

$$ \left[ \frac{n}{2}(n-c+d) \right]_q \left[ \frac{n}{2}(n-c-d) \right]_q = \sum_{w \in P_n((0,0)|(c,d))} q^{\mathrm{winv}(w)} \quad (5) $$

The following is true for the walks restricted to the upper half plane. Denote the set of walks starting at $(0, 0)$ and ending at $(c, d)$ in $n$ steps and never going below the $x$-axis by $P_n^+((0, 0) | (c, d))$, then

**Proposition 2**

$$ \left[ \frac{n}{2}(n+c+d) \right]_q \left[ \frac{n}{2}(n+c-d) \right]_q - q^{d+1} \left[ \frac{n}{2}(n+c+d)+1 \right]_q \left[ \frac{n}{2}(n+c-d)-1 \right]_q \\ = \sum_{w \in P_n^+((0,0)|(c,d))} q^{\mathrm{winv}(w)} \quad (6) $$

In Section 6 I will also introduce an analog of a major index, $wmaj(w)$, which is, conjecturally, equally distributed with $winv(w)$ over lattice walks.

## 3 $q$-Lassalle Numbers

The purpose of this section is to derive a bilinear recursion relations for $A_k(q)$ and $\alpha_k(q)$, from which the positivity and integrality follow.

The strategy is to rewrite the recursion relation between $A'(q)$ (as in (1)) as a difference equation. Then, using the $q$-difference equation for the generating function of $q$-Catalan, to obtain the $q$-difference equation for the generating function of the $q$-Lassalle numbers.

$$ \begin{aligned} A'_{n}(q) = & (-1)^{n-1} q^{n-1} C_{n}(q) + \sum_{j=1}^{n-1} (-1)^{n-j-1} q^{n-j} \left[ \frac{2n-1}{2j-1} \right]_{q} A'_{j}(q) C_{n-j}(q) \\ & - \frac{(-1)^{n} q^{n} [2n]_{q} C_{n}(q)}{[2n]_{q}!} = \frac{q A'_{n}(q)}{[2n-1]_{q}!} + \sum_{j=1}^{n-1} \frac{q A'_{j}(q)}{[2j-1]_{q}!} \frac{(-1)^{n-j} q^{n-j} C_{n-j}(q)}{[2n-2j]_{q}!} \end{aligned} \quad (7) $$
Introduce generating functions and the finite q-difference operator:

$$
\begin{align*}
H(t; q) &= \sum_{k \ge 0} \frac{(-1)^k q^k C_k(q) t^{2k}}{[2k]_q!} \\
&\equiv \sum_{k \ge 0} \frac{(-1)^k q^k t^{2k}}{[k]_q! [k+1]_q!} \\
P(t; q) &= \sum_{k \ge 1} \frac{q A'_k(q) t^{2k-1}}{[2k-1]_q!} \\
D_q f(t) &= \frac{f(t) - f(qt)}{(1-q)t}
\end{align*}
$$

then (7) is equivalent to

$$
-D_q H(t, q) = P(t; q) H(t; q) \quad (8)
$$

Recall Jackson’s basic q-Bessel function ([Ism82]):

$$
J_{\nu}^{(1)}(x; q) = \frac{(q^{\nu+1}; q)_{\infty}}{(q; q)_{\infty}} \sum_{n \ge 0} \frac{(-1)^n}{(q; q)_n (q^{\nu+1}; q)_n} \left(\frac{x}{2}\right)^{2n+\nu}, \quad \text{where} \quad (a; q)_n = \prod_{j=0}^{n-1} (1 - aq^j) \quad (9)
$$

For $\nu = 1$

$$
J_1^{(1)}(x;q) = \frac{1}{1-q} \sum_{n \ge 0} \frac{(-1)^n}{(q;q)_n (q^2;q)_n} \left(\frac{x}{2}\right)^{2n+1} = \sum_{n \ge 0} \frac{(-1)^n}{[n]_q! [n+1]_q!} \left(\frac{x}{2(1-q)}\right)^{2n+1}
$$

So that

$$
H(t; q) = \frac{1}{\sqrt{q} t} J_{1}^{(1)}(2(1-q)\sqrt{q} t; q), \text{ i.e.}
$$

q-Bessel function $J_1^{(1)}(x; q)$ is a generating function for q-Catalan numbers.

$J_1^{(1)}(x; q)$ satisfies the following $q$-Bessel difference equation:

$$
J_1^{(1)}(qx; q) - \left(q^{\frac{1}{2}} + q^{-\frac{1}{2}}\right) J_1^{(1)}(\sqrt{q} x; q) + \left(1 + \frac{x^2}{4}\right) J_1^{(1)}(x; q) = 0 \quad (10)
$$

For $H(t; q)$, (10) translates to:

$$
H(qt; q) - \left(1 + \frac{1}{q}\right) H(\sqrt{qt}; q) + \left(\frac{1}{q} + (1-q)^2 t^2\right) H(t; q) = 0 \quad (11)
$$

Through the *q*-difference equation (8) this implies the following ungainly looking *q*-difference equation
for $P(t; q)$:

$$
\begin{align*}
& (1 + q + q(1 - q)^2 t^2) q(1 - q) \sqrt{qt} P(\sqrt{qt}; q) + q^2 (1 - q)^2 t P(t; q) \sqrt{qt} P(\sqrt{qt}; q) + \\
& \qquad + (1 + q + q(1 - q)^2 t^2) q^2 (1 - q)^2 t^2 + q^2 (1 - q)^2 t^2 q(1 - q) P(t; q) \\
&= (1 - q^2) t P(t; q) - q(1 - q)(1 - q^2) t^2
\end{align*}
$$
But collecting coefficients of $t^{2n}$ on both sides makes things look better:

$$A'_{1}(q) = 1$$

$$A'_{2}(q) = q^{2}$$

$$\frac{[2]_q[s+1]_q}{[2s-1]_q!} A'_s(q) = \frac{q^3 + q^{s+1}}{[2s-3]_q!} A'_{s-1}(q) + \sum_{k=2}^{s-2} \frac{q^{k+3} A'_{k}(q) A'_{s-k}(q)}{[2k-1]_q![2s-2k-1]_q!}$$

It's time to rescale, so let

$$A'_{k}(q) = q^{3k-4} A_{k}(q)$$

then the recursion relation for $A_k(q)$ is:

$$A_s(q) = \frac{[2s-1]_q}{[2]_q[s+1]_q} \sum_{k=1}^{s-1} q^{k-1} \frac{[2s-2]_q!}{[2k-1]_q![2s-2k-1]_q!} A_k(q) A_{s-k}(q) \quad (12)$$

Translating this recursion into that for $\alpha_n(q)$ (as in (3)) produces:

$$\alpha_n(q) = \frac{1}{[2]_q[n]_q} \sum_{k=1}^{n-1} q^{k-1} \begin{bmatrix} n \\ k+1 \end{bmatrix}_q \begin{bmatrix} n \\ k-1 \end{bmatrix}_q \alpha_k(q) \alpha_{n-k}(q) \quad (13)$$

The ratio of the q-binomial coefficients can be rewritten as

$$\frac{1}{[n]_q} \begin{bmatrix} n \\ k+1 \end{bmatrix}_q \begin{bmatrix} n \\ k-1 \end{bmatrix}_q = \frac{1}{[2]_q} \left( \begin{bmatrix} n-1 \\ r-1 \end{bmatrix}_q \begin{bmatrix} n-1 \\ r \end{bmatrix}_q - q^2 \begin{bmatrix} n-1 \\ r-2 \end{bmatrix}_q \begin{bmatrix} n-1 \\ r+1 \end{bmatrix}_q \right)$$

Therefore, the proof depends on

* positivity and integrality of

$$c_{n,k}(q) = \begin{bmatrix} n-1 \\ r-1 \end{bmatrix}_q \begin{bmatrix} n-1 \\ k \end{bmatrix}_q - q^2 \begin{bmatrix} n-1 \\ k-2 \end{bmatrix}_q \begin{bmatrix} n-1 \\ k+1 \end{bmatrix}_q$$

* divisibility of $c_{n,k}(q)$ and $\alpha_k(q)$ by powers of $[2]_q$.

As may be seen from (6), the positivity and integrality of $c_{n,k}(q)$ follows from its combinatorial interpretation as the generating function of winv statistics of upper half-plane lattice walks, namely the walks that start at (0, 0) and end up at $(2k - n - 1, 1)$ in $(n-1)$ steps. Therefore I continue with the lattice walk part of the story.

# 4 Walk Inversion Generating Function

In order to prove the walk inversion generating function formula, as in (5)

$$\left[ \frac{n}{2}(n-c+d) \right]_q \left[ \frac{n}{2}(n-c-d) \right]_q = \sum_{w \in P_n((0,0)|(c,d))} q^{winv(w)}$$
I will need the following lemma. Denote the set of all walks of length $n$ from $(0, 0)$ to $(c, d)$ with exactly $k$ W steps by $P_n((c, d); k)$. Of course this fixes the number of S steps, $r$ as well. The total number of steps in $n$, $(c+k)$ of which are E, $k-W$, $(d+r)-N$, and $r-S$.

$$r = \frac{1}{2}(n - c - d) - k$$

As words, these walks are permutations of each other. Their total number is $\frac{n!}{(c+k)!k!(d+r)!r!}$.

**Lemma 1** The generating function of the walk inversion statistics of n-step walks with k W steps is given by

$$q^{k^2+ck} \frac{[n]_q!}{[c+k]_q![\frac{1}{2}(n-c+d)-k]_q![k]_q![\frac{1}{2}(n-c-d)-k]_q!} = \sum_{w \in P_n((c,d);k)} q^{\mathrm{winv}(w)} \quad (14)$$

Now, in general, to get to $(c, d)$ from $(0, 0)$ in $n$ steps one might take just one W step, or two, etc. The maximal number of W steps (i.e. no S steps) is

$$\frac{1}{2}(n-c-d)$$

So that

**Lemma 2** The walk inversion generating function is

$$\sum_{w \in P_n((0,0)|(c,d))} q^{\mathrm{winv}(w)} = \sum_{k=0}^{\frac{1}{2}(n-c-d)} q^{k^2+ck} \frac{[n]_q!}{[c+k]_q![\frac{1}{2}(n-c+d)-k]_q![k]_q![\frac{1}{2}(n-c-d)-k]_q!} \quad (15)$$

Now, consider how a walk can end up at $(c, d)$ in $n$ steps, i.e. where could it be at the previous step?

* either at $(c-1, d)$, with the last step E; adding an E step changes $winv$ by $\#S + \#N + 2\#W = r + (d+r) + 2k = d + 2r + 2k = n - c$
The contribution of walks coming from the West is

$$q^{n-c} \sum_{k=0}^{\frac{1}{2}(n-c-d)} q^{k^2+(c-1)k} \frac{[n-1]_q!}{[c-1+k]_q! [\frac{1}{2}(n-c-d)-k]_q! [k]_q! [\frac{1}{2}(n-c+d)-k]_q!}$$

* or at $(c, d+1)$ with the last step S; adding an S step does not change $winv$. The contribution of the walks coming from the North:

$$\sum_{k=0}^{\frac{1}{2}(n-c-d)-1} q^{k^2+ck} \frac{[n-1]_q!}{[c+k]_q! [\frac{1}{2}(n-c+d)-k-1]_q! [k]_q! [\frac{1}{2}(n-c-d)-k-1]_q!}$$
* or at $(c+1, d)$ with the last step W; adding a W step changes $winv$ by $\#S + \#N + \#E = r + (d+r) + (k+c+1) = d+2r+c+k+1 = n-1-k$

The contribution of walks coming from the East is

$$q^{n-1} \sum_{k=0}^{\frac{1}{2}(n-c-d)-1} q^{k^2+ck} \frac{[n-1]_q!}{[c+1+k]_q! [\frac{1}{2}(n-c+d)-k-1]_q! [k]_q! [\frac{1}{2}(n-c-d)-k-1]_q!}$$

* or at $(c, d-1)$ with the last step N; an addition of an N step with $r$ prior S steps changes $winv$ by $\frac{1}{2}(n-c-d)-k$.

The contribution of the walks coming from the South:

$$q^{\frac{1}{2}(n-c-d)} \sum_{k=0}^{\frac{1}{2}(n-c-d)} q^{k^2+(c-1)k} \frac{[n-1]_q!}{[c+k]_q! [\frac{1}{2}(n-c-d)-k]_q! [k]_q! [\frac{1}{2}(n-c+d)-k]_q!}$$

The sum of these contributions gives a recursion that establishes (5).

# 5 Upper Half-Plane walks

Following the logic of walks reflection [GKS92], to every negative path from $(0, 0)$ to $(c, d)$ will associate a walk from $(-2, 0)$ to $(c, d)$ so that the change in $winv$ is the same for every walk.

Here is the algorithm.

1. Separate each negative walk in two segments $w = w_1 \cdot w_2$, where $\cdot$ means concatenation of words:

(a) $w_1$: the part of the walk that starts at $(0, 0)$ and ends at $(*, 0)$ (before it dips below the x-axis the first time)

(b) $w_2$: the rest of the walk that runs from $(*, 0)$ to $(c, d)$; Notice that $w_2$ starts with S and necessarily has at least $d+1$ N steps. More precisely, if the walk has $k$ S steps, it has $d+k$ N steps.

2. $\tilde{w}_1$: move $w_1$ down two steps, so that it starts at $(0, -2)$ and ends at $(*, -2)$;

3. attach $\tilde{w}_2$ to the combined walk. The walk modified this way runs from $(0, -2)$ to $(c, d)$

Consider the simplest (negative) walk $w = w_1 \cdot w_2$: after dipping down below the x-axis it goes straight up to $d$, i.e. the part after reaching the x-axis ($w_2$) looks like

$$w_2 = S \underbrace{NN \dots NN}_{d+1 \text{ times}}$$

Transform this walk into

$$\tilde{w}_2 = \underbrace{NN \dots NN S}_{d+1 \text{ times}}$$

Suppose that $w_1$ contained $k$ S steps. Then $(\tilde{w} = \tilde{w}_1 \cdot \tilde{w}_2)$

$$winv(w) - winv(\tilde{w}) = (d+1)(k+1) - (d+1)k = d+1$$
Now consider a generic w with blocks of S and N letters:

$$w_2 = \underbrace{S...S}_{s_1 \text{ times}} \underbrace{N...N}_{n_1 \text{ times}} \underbrace{S...S}_{s_2 \text{ times}} \underbrace{N...N}_{n_2 \text{ times}} \dots \underbrace{S...S}_{s_r \text{ times}} \underbrace{N...N}_{n_r \text{ times}}$$

where

$$\sum_{i}^{r} n_i - s_i = d$$

By swapping the last S in the each string of sᵢ with the last N letter in nᵢ until d + 1 letters N have been moved, transforms w₂

$$\tilde{w}_2 = \underbrace{S...S}_{s_1-1 \text{ times}} \underbrace{N...N}_{n_1 \text{ times}} \underbrace{S...S}_{s_2-1 \text{ times}} \underbrace{N...N}_{n_2 \text{ times}} \dots \underbrace{S...S}_{s_i-1 \text{ times}} \underbrace{N...N}_{r \text{ times}} \underbrace{S...S}_{n_i-r \text{ times}} \underbrace{N...N}_{n_i-r \text{ times}} \dots \underbrace{S...S}_{s_r \text{ times}} \underbrace{N...N}_{n_r \text{ times}}$$

$$\text{with } n_1 + n_2 + \dots + r = d + 1$$

$$\begin{aligned} \mathrm{winv}(w) - \mathrm{winv}(\tilde{w}) = & \{n_1(s_1+k) - n_1(s_1-1+k)\} + \{n_2(s_1+s_2+k) - n_2(s_1+s_2-1+k)\} \\ & + \dots + \{r(s_1+\dots+s_i+k) - r(s_1+\dots+s_i-1+k)\} \\ & + \{(n_i-r)(s_1+\dots+s_i+k) - (n_i-r)(s_1+\dots+s_i+k)\} + \\ & + \dots + \{n_r(s_1+\dots+s_r) - n_r(s_1+\dots+s_r)\} = \sum_i n_i + r = d+1 \end{aligned}$$

$$\mathrm{winv}(\tilde{w}) = q^{-(d+1)} \mathrm{winv}(w)$$

So the total contribution of negative walks is

$$q^{d+1} P_n((0, -2) | (c, d)) = q^{d+1} \left[ \frac{n}{2} (n + 2 + c + d) \right]_q \left[ \frac{n}{2} (n - 2 + c - d) \right]_q$$

Hence (6).

# 6 Major Walk Index

Setting up the following order $S > N > E > W$, and with the usual definition of a descent set

$$\mathrm{desN}(w) = \{i : \text{S occurs as } i^{\text{th}} \text{ letter and N occurs as } i + 1^{\text{st}} \text{ letter}\}$$

$$\mathrm{majN}(w) = \sum_{i \in \mathrm{desN}(w)} i$$

$$\mathrm{desE}(w) = \{i : \text{S or N occur as } i^{\text{th}} \text{ letter and E occurs as } i + 1^{\text{st}} \text{ letter}\}$$

$$\mathrm{majE}(w) = \sum_{i \in \mathrm{desE}(w)} i$$

$$\mathrm{desW}(w) = \{i : \text{S, N, or E occur as } i^{\text{th}} \text{ letter and W occurs as } i + 1^{\text{st}} \text{ letter}\}$$

$$\mathrm{majW}(w) = \sum_{i \in \mathrm{desW}(w)} i$$

one can give the following
**Definition 2**

$$wmaj(w) = majN(w) + majE(w) + majW(w) + \#E \times \#W \quad (16)$$

Notice the unusual last term... Nevertheless, experiments show that *winv* and *wmaj* are equally distributed over all lattice walks as well as over upper half-plane walks.

**Conjecture 1**

$$\sum_{w \in P_n((0,0)|(c,d))} q^{winv(w)} = \sum_{w \in P_n((0,0)|(c,d))} q^{wmaj(w)} \quad (17)$$

<figure><img src="image_3.png" /></figure>

$$\sum_{w \in P_n^+((0,0)|(c,d))} q^{winv(w)} = \sum_{w \in P_n^+((0,0)|(c,d))} q^{wmaj(w)} \quad (18)$$

# 7 q-Integers Associated with q-super Ballot Numbers

Computer experiments indicate that there is a family of *q*-numbers related to several generalizations of *q*-Catalan. For instance, following [Ges92] define *q*-super Ballot numbers

$$B_{n,k,r}(q) = \frac{[k+2r]_q![2n+k-1]_q!}{(k-1)_q!r_q!n_q![n+k+r]_q!}$$

Then, I venture to make the following conjecture

**Conjecture 2** Define a new sequence $A_{n,k,r}(q)$ with $A_{1,k,r} = B_{0,k,r}(q)$ through the recurrence

$$(-1)^{n-1} A_{n,k,r}(q) = q^{n-1} B_{n,k,r}(q) + \sum_{j=1}^{n-1} (-1)^j q^{n-j-1} \begin{bmatrix} 2n-1 \\ 2j-1 \end{bmatrix}_q A_{j,k,r}(q) B_{n-j,k,r}(q) \quad (19)$$

then the $A_{n,k,r}(q)$ are polynomials in $q$ with positive integers coefficients for all values of $n, k, r > 0$.

**Example 4**

$$A_{2,1,1}(q) = 1 + 2q + 4q^2 + 4q^3 + 3q^4 + q^5$$

$$A_{2,2,1}(q) = 1 + 3q + 7q^2 + 11q^3 + 13q^4 + 12q^5 + 8q^6 + 4q^7 + q^8$$

$$A_{2,2,2}(q) = 1 + 3q + 9q^2 + 18q^3 + 33q^4 + 51q^5 + 72q^6 + 89q^7 + 100q^8 + 101q^9 + 93q^{10} + 77q^{11} + 57q^{12} + 38q^{13} + 22q^{14} + 11q^{15} + 4q^{16} + q^{17}$$

$$A_{3,1,1}(q) = 1 + 3q + 9q^2 + 17q^3 + 28q^4 + 38q^5 + 44q^6 + 43q^7 + 35q^8 + 24q^9 + 13q^{10} + 5q^{11} + q^{12}$$

$$A_{3,2,1}(q) = 1 + 5q + 19q^2 + 51q^3 + 110q^4 + 199q^5 + 307q^6 + 412q^7 + 484q^8 + 499q^9 + 452q^{10} + 358q^{11} + 245q^{12} + 143q^{13} + 69q^{14} + 26q^{15} + 7q^{16} + q^{17}$$

$$A_{3,2,2}(q) = 1 + 5q + 22q^2 + 68q^3 + 181q^4 + 414q^5 + 848q^6 + 1567q^7 + 2652q^8 + 4134q^9 + 5980q^{10} + 8058q^{11} + 10155q^{12} + 11997q^{13} + 13313q^{14} + 13892q^{15} + 13639q^{16} + 12597q^{17} + 10937q^{18} + 8913q^{19} + 6802q^{20} + 4845q^{21} + 3206q^{22} + 1958q^{23} + 1094q^{24} + 552q^{25} + 247q^{26} + 95q^{27} + 30q^{28} + 7q^{29} + q^{30}$$
Acknowledgements

I would like to thank Jean-Christophe Novelli and Jean-Yves Thibon for an interesting and useful conversation.

References

[DR84] D. DeTemple and J. Robertson. Equally likely fixed length paths in graphs. *Ars Comb.*, 17:243–254, 1984.

[Ges92] I. Gessel. Super ballot numbers. 1992.

[GKS92] R. K. Guy, C. Krattenthaler, and B.E. Sagan. Lattice paths, reflections, and dimension-changing bijections. *Ars Comb.*, 34:3–15, 1992.

[Ism82] M.E.H. Ismail. The zeros of basic bessel functions, the functions $j_{\nu+\alpha x}(x)$, and associated orthogonal polynomials. *Journal of Mathematical Analysis and Applications*, 86(1-19), 1982.

[Las12] M. Lassalle. Two integer sequences related to Catalan numbers. *Journal of Combinatorial Theory, Series A*, 119:923–935, 2012.