# 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_1.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^{\text{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^{\text{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 \dots S}_{s_1 \text{ times}} \underbrace{N \dots N}_{n_1 \text{ times}} \underbrace{S \dots S}_{s_2 \text{ times}} \underbrace{N \dots N}_{n_2 \text{ times}} \dots \underbrace{S \dots S}_{s_r \text{ times}} \underbrace{N \dots 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 \dots S}_{s_1-1 \text{ times}} \underbrace{N \dots N}_{n_1 \text{ times}} \underbrace{S \dots S}_{s_2-1 \text{ times}} \underbrace{N \dots N}_{n_2 \text{ times}} \dots \underbrace{S \dots S}_{s_i-1 \text{ times}} \underbrace{N \dots N}_{r \text{ times}} \underbrace{S \dots S}_{n_i-r \text{ times}} \dots \underbrace{S \dots S}_{s_r \text{ times}} \underbrace{N \dots N}_{n_r \text{ times}}$$

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_2.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.