# A Lucas analogue of Eulerian numbers

José Agapito Ruiz  Centro de análise funcional, estruturas lineares e
aplicações, faculdade de ciências, universidade de lisboa, 1749-016 Lisboa,
portugal<EMAIL_ADDRESS>
###### Abstract.

The generalized Lucas numbers are polynomials in two variables with
nonnegative integer coefficients. Lucas versions of some combinatorial numbers
with known formulas in terms of quotient and products of nonnegative integers
have been recently given by replacing the integers in those formulas with
their corresponding Lucas analogues. We instead use a recursive approach. In
this sense, we give a recursive formula for Lucas-Narayana numbers derived
from a recent formula in terms of Lucasnomials (the explicit Lucas version of
binomial numbers). We propose a recursive definition for a Lucas analogue of
the classical Eulerian numbers, which shows immediately that they are
polynomials in two variables with nonnegative integer coefficients. We prove
that they are palindromic like their standard counterparts. The recursive
approach allows us to give Lucas analogues of many relevant combinatorial
constants. In particular, Lucas versions for both Stirling numbers of the
second kind and Motzkin numbers are presented.

###### Key words and phrases:

Eulerian numbers, Lucas analogues, Recursive formulas

2020 _Mathematics Subject Classification._ Primary 03, 05, 11

##  1\. Introduction

The generalized Lucas _numbers_ are defined recursively by $\\{0\\}=0$,
$\\{1\\}=1$, and

(1) $\\{n\\}=s\\{n-1\\}+t\\{n-2\\}\,,$

for any integer $n\geq 2$. It follows immediately from (1) that the
generalized Lucas numbers $\\{n\\}$ are polynomials in $s$ and $t$ with
nonnegative integer coefficients. On specialization of $s$ and $t$ one can
recover, for example, the nonnegative integers ($s=2$, $t=-1$), the
$q$-integers $[n]_{q}=\frac{q^{n}-1}{q-1}=1+q+\cdots+q^{n-1}$ ($s=1+q$,
$t=-q$), the Chebyshev polynomials of the second kind $U_{n-1}(x)$
($U_{0}(x)=1$, $U_{1}(x)=2x$, $s=2x$, $t=-1$), and the Fibonacci sequence
$F_{n}$ ($s=t=1$), which is at the core of recursion (1). Here are a few
instances of the generalized Lucas numbers:

$\\{2\\}=s,\quad\\{3\\}=s^{2}+t,\quad\\{4\\}=s^{3}+2st,\quad\\{5\\}=s^{4}+3s^{2}t+t^{2},\quad\\{6\\}=s^{5}+4s^{3}t+3st^{2}\,.$

A useful combinatorial interpretation of $\\{n\\}$ is derived from the
standard interpretation of Fibonacci numbers via tiling. In this regard, we
consider two types of tiles: monominoes (which cover one unit squares) and
dominoes (which cover two unit squares), so that for a given configuration $T$
using these tiles, we define its _weight_ to be

(2) $\operatorname{\mathbf{wt}}T=s^{\text{$\\#$ of monominoes in
}T}\,\,t^{\text{$\\#$ of dominoes in }T}\,.$

Furhermore, for any set $\mathscr{T}$ of tilings of this kind, the _weight_ of
$\mathscr{T}$ is defined to be

(3)
$\operatorname{\mathbf{wt}}\mathscr{T}=\displaystyle\sum_{T\in\mathscr{T}}\operatorname{\mathbf{wt}}T\,.$

Clearly, $\operatorname{\mathbf{wt}}\mathscr{T}$ is a polynomial in $s$ and
$t$ when $\mathscr{T}$ is finite, otherwise it is a formal power series.

Figure 1. The tilings in $\mathscr{T}(4)$

Let $\mathscr{T}(n)$ be the set of all tilings of a row of $n$ squares. Figure
1 shows all possible tilings for $n=4$. It is then easy to see by induction
that for every $n\geq 1$, we have

$\\{n\\}=\operatorname{\mathbf{wt}}\mathscr{T}(n-1)\,.$

The cardinality of $\mathscr{T}(n-1)$ is precisely the Fibonacci number
$F_{n}$ (clearly, for $\mathscr{T}(0)=\emptyset$ we assume
$|\mathscr{T}(0)|=1$). Now, by tiling rows with a decreasing number of squares
and piling them up we can make sense of the expression

(4) $\\{n\\}!=\\{n\\}\\{n-1\\}\cdots\\{2\\}\\{1\\}\,.$

This is the Lucas analogue of the factorial, the _Lucastorial_ number. By
convention $\\{0\\}!=1$. Using the setting of Young diagrams, Identity (4)
gives the weight of the set of all tilings of the standard staircase partition
$\delta_{n}=(n-1,n-2,\ldots,1)$; namely

$\operatorname{\mathbf{wt}}\mathscr{T}(\delta_{n})=\\{n\\}!$

Likewise, one can obtain a Lucas version of any expression given in terms of
products and quotients of nonnegative integers by simply replacing each
ocurrence of $n$ in the expression with $\\{n\\}$. For instance, given $0\leq
k\leq n$, the _Lucasnomial_ is defined by

(5) $\begin{Bmatrix}n\\\
k\end{Bmatrix}=\frac{\\{n\\}!}{\\{k\\}!\\{n-k\\}!}\,.$

From this point of view, Lucasnomials are rational expressions in $s$ and $t$
a priori. However they are indeed polynomials in $s$ and $t$ with nonnegative
integer coefficients. This follows from some combinatorial interpretations
given by Gessel and Viennot [6], Benjamin and Plott [3], and Sagan and Savage
[7]). More recently, using a model that involves lattice paths inside tilings
of Young diagrams, Bennett et al.[4] have given another combinatorial
interpretation for Lucasnomials that not only is simpler than the previous
ones but also is more flexible for combinatorial proofs of identities
involving Lucasnomials. Their combinatorial interpretation is also extendable
to other familiar sequences of numbers like the Catalan numbers and their
relatives. It is worth mentioning that Amdeberhan et. al. [2] have also
studied the generalized Lucas sequence and the Lucas analogues of Binomial and
Catalan numbers from an algebraic and number theoretical perspective.

In general, given any array of numbers $A_{n,k}$, its Lucas analogue will be
denoted by $A_{\\{n,k\\}}$. An alternative natural way to obtain Lucas
analogues of standard arrays of numbers is by generalizing their recursive
relations in a straightforward manner. For instance, it is well-known that the
following formula holds for binomial numbers $B_{n,k}=\binom{n}{k}$,

(6) $B_{n,k}=B_{n-1,k}+B_{n-1,k-1}\,.$

However, since $\\{1\\}=1$, we do not get anything new by replacing $1$ with
$\\{1\\}$ in (6). Therefore, we have to choose a different recursive relation.
In this regard, there is a less familiar recursive formula for binomial
numbers that we can work with; that is

(7) $B_{n,k}=(k+1)B_{n-1,k}-(n-k-1)B_{n-1,k-1}\,.$

Keeping in mind that $\\{n\\}=n$ when $s=2$ and $t=-1$, a natural way of
defining the Lucas analogue of (7) is

(8) $B_{\\{n,k\\}}=\\{k+1\\}B_{\\{n-1,k\\}}+t\\{n-k-1\\}B_{\\{n-1,k-1\\}}\,.$

An immediate conclusion from (8) is that $B_{\\{n,k\\}}$ is a polynomial in
$s$ and $t$ with nonnegative integer coefficients. Moreover, using as initial
conditions $B_{\\{n,0\\}}=B_{\\{n,n\\}}=1$ for $n\geq 0$ and $B_{\\{n,k\\}}=0$
whenever $n<k$ or $k<0$, we can recover by induction the formula

$B_{\\{n,k\\}}=\frac{\\{n\\}!}{\\{k\\}!\\{n-k\\}!}\,.$

Hence, the Lucas version for binomial numbers obtained from generalizing the
recursive relation (7) agrees with the explicit formula for Lucasnomials.

Another familiar array of nonnegative integers with combinatorial
interpretations is the array of Narayana numbers, defined for $1\leq k\leq n$
as

(9) $N_{n,k}=\frac{1}{n}\binom{n}{k}\binom{n}{k-1}\,.$

The corresponding Lucas-Narayana numbers are then given by

(10) $N_{\\{n,k\\}}=\frac{1}{\\{n\\}}\begin{Bmatrix}n\\\
k\end{Bmatrix}\begin{Bmatrix}n\\\ k-1\end{Bmatrix}\,.$

The fact that Lucas-Narayana numbers are indeed polynomials in $s$ and $t$
with nonnegative integer coefficients was conjectured in [4], and later proved
by Sagan and Tirrell [8] using special factoring properties of $\\{n\\}$.
Recently, Garret and Killpatrick [5] gave a combinatorial proof of this fact
by showing that the Lucas-Narayana numbers $N_{\\{n,k\\}}$ satisfy the formula

(11) $N_{\\{n,k\\}}=\begin{Bmatrix}n-1\\\
k-1\end{Bmatrix}^{2}+t\begin{Bmatrix}n-1\\\
k\end{Bmatrix}\begin{Bmatrix}n-1\\\ k-2\end{Bmatrix}\,,$

for $2\leq k\leq n-1$ and $n\geq 1$. Formula (11) shows that $N_{\\{n,k\\}}$
is a polynomial in $s$ and $t$ with nonnegative integer coefficients because
it is expressed as a sum of products of Lucasnomials with coefficients in
$\mathds{N}[s,t]$. Now, manipulating Formula (11) algebraically, we get a
recursive formula for Lucas-Narayana numbers.

######  Proposition 1.

For any integers $2\leq k\leq n-1$ and $n\geq 1$, the Lucas-Narayana numbers
are given by

(12)
$N_{\\{n,k\\}}=\frac{\\{k\\}\\{n-1\\}}{\\{n-k\\}}\,N_{\\{n-1,k\\}}+t\,\frac{\\{n-k\\}\\{n-1\\}}{\\{k\\}}N_{\\{n-1,k-1\\}}\,,$

with initial conditions $N_{\\{0,0\\}}=1$, $N_{\\{n,k\\}}=1$ for $n=k$ or
$k=1$, $N_{\\{j,0\\}}=0$ for $j>0$, and $N_{\\{n,k\\}}=0$ for $n<k$.

Formula (12) is the Lucas analogue of the not well-known recurrence relation
satisfied by the classical Narayana numbers,

$N_{n,k}=\frac{k(n-1)}{n-k}N_{n-1,k}-\frac{(n-k)(n-1)}{k}N_{n-1,k-1}\quad.$

We can recover from Proposition 1 the closed formula (10), by using induction
again. Note that the polynomial nature of $N_{\\{n,k\\}}$ with nonnegative
integer coefficients is not immediate from the recursive formula (12) this
time.

These two examples illustrate the elementary approach we will take for the
rest of the paper. We show in Section 2 that a straightforward Lucas version
of a recursive relation satisfied by the classical Eulerian numbers $E_{n,k}$
gives a way of defining the Lucas-Eulerian numbers $E_{\\{n,k\\}}$. It follows
immediately from the definition that they are polynomials in $s$ and $t$ with
nonnegative integer coefficients. We show that they are palindromic. Using the
recursive definition of $E_{\\{n,k\\}}$, we get a formula for $E_{\\{n,1\\}}$
that encourage us to conjecture a similar formula for the general case
$E_{\\{n,k\\}}$. In Section 3, we elaborate on the difficulties that arise
when trying to give a Lucas analogue of a known alternating sum formula for
Eulerian numbers that be compatible with our Lucas-Eulerian numbers. We end in
Section 4 by making further comments on open problems and on Lucas analogues
of Stirling numbers of the second kind and Motzkin numbers.

##  2\. Lucas-Eulerian numbers

Among several equivalent variants of a known recurrence relation satisfied by
the classical Eulerian numbers, we have the following formula

(13) $E_{n,k}=(k+1)E_{n-1,k}+(n-k+1)E_{n-1,k-1}\,.$

A straightforward Lucas analogue of Formula 13 defines the Lucas-Eulerian
numbers.

######  Definition 1.

The Lucas-Eulerian numbers are defined recursively by the formula

(14) $E_{\\{n,k\\}}=\\{k+1\\}E_{\\{n-1,k\\}}+\\{n-k+1\\}E_{\\{n-1,k-1\\}}\,,$

for any integers $0\leq k\leq n$, with initial conditions
$E_{\\{n,0\\}}=E_{\\{n,n\\}}=1$ for $n\geq 0$ and $E_{\\{n,k\\}}=0$ for $n<k$
or $k<0$.

$\bm{n\backslash k}$ | ${\color[rgb]{1,0,0}0}$ | ${\color[rgb]{1,0,0}1}$ | ${\color[rgb]{1,0,0}2}$ | ${\color[rgb]{1,0,0}3}$ | ${\color[rgb]{1,0,0}4}$ |  ${\color[rgb]{1,0,0}5}$
---|---|---|---|---|---|---
0 | 1 | 0 | 0 | 0 | 0 |  0
1 | 1 | 1 | 0 | 0 | 0 |  0
2 | 1 | $2s$ | 1 | 0 | 0 |  0
3 | 1 | $3s^{2}+t$ | $3s^{2}+t$ | 1 | 0 |  0
4 | 1 | $4s^{3}+3st$ | $6s^{4}+8s^{2}t+2t^{2}$ | $4s^{3}+3st$ | 1 |  0
5 | 1 | $5s^{4}+6s^{2}t+t^{2}$ | $10s^{6}+25s^{4}t+16s^{2}t^{2}+2t^{3}$ | $10s^{6}+25s^{4}t+16s^{2}t^{2}+2t^{3}$ | $5s^{4}+6s^{2}t+t^{2}$ |  1
Table 1. A sample of Lucas-Eulerian numbers

It immediately follows from Definition 1 that the Lucas-Eulerian numbers are
polynomials in $s$ and $t$ with nonnegative integer coefficients. Moreover,
Table 1 indicates that they are palindromic. Note that for Lucasnomials
$B_{\\{n,k\\}}$ and Lucas-Narayana numbers $N_{\\{n,k\\}}$, this property is
immediate because they both have closed formulas from where it is easy to
check that $B_{\\{n,k\\}}=B_{\\{n,n-k\\}}$ and
$N_{\\{n,k\\}}=N_{\\{n,n-k+1\\}}$.

######  Theorem 2.

The Lucas-Eulerian numbers are palindromic.

###### Proof.

This is an immediate consequence of the bijection $k\mapsto n-k=k^{\prime}$,
which amounts to write

$E_{\\{n,n-k\\}}=\\{n-k+1\\}E_{\\{n-1,n-k\\}}+\\{n-n+k+1\\}E_{\\{n-1,n-k-1\\}}$

as

$E_{\\{n,k^{\prime}\\}}=\\{k^{\prime}+1\\}E_{\\{n-1,k^{\prime}\\}}+\\{n-k^{\prime}+1\\}E_{\\{n-1,k^{\prime}-1\\}}\,.$

∎

Unlike Binomial and Narayana numbers, whose Lucas analogues have
straightforward generalizations of their explicit closed formulas, there is
not an equivalent formula known for the classical Eulerian numbers; that is,
in terms of a quotient of products of nonnegative integers. There is a formula
in terms of alternating sums though, but unfortunately the natural extension
of the Lucas recurrence to negative numbers does not give a Lucas analogue of
such formula that be polynomial in $s$ and $t$ with nonnegative integer
coefficients. We elaborate more on this observation in Section 3.

Using Definition 1 repeatedly we get an interesting formula for
$E_{\\{n,1\\}}$. We have

(15)
$E_{\\{n,1\\}}=\\{2\\}E_{\\{n-1,1\\}}+\\{n\\}=\sum_{j=0}^{n}\\{n-j\\}\\{2\\}^{j}\,.$

Expanding out the sum in Formula (15), and replacing $\\{2\\}$ with $x$, we
get the polynomial

$\big{\\{}A_{n,1}\big{\\}}(x)=\\{n\\}x^{0}+\\{n-1\\}x^{1}+\cdots+\\{1\\}x^{n-1}+\\{0\\}x^{n}\,,$

which is the Lucas version of the polynomial
$A_{n,1}(x)=x^{n}P_{n,1}\left(\frac{1}{x}\right)$, where

$P_{n,1}(x)=\left(x\frac{d}{dx}\right)\left(\frac{1-x^{n+1}}{1-x}\right)=x+2x^{2}+\cdots+nx^{n}\,.$

Therefore, we have $E_{\\{n,1\\}}=\big{\\{}A_{n,1}\big{\\}}(\\{2\\})$. Note
that when $n+1$ is prime, the polynomials

$\varphi_{n}(x)=1+x+x^{2}+\cdots+x^{n}=\frac{1-x^{n+1}}{1-x}\,,$

are the cyclotomic polynomials $\Phi_{n+1}(x)$ used in the definition of Lucas
atoms [8]. They provide a convenient factorization of $\\{n\\}$. Recall also
that there is a well-known formula that generates the classical Eulerian
polynomials, here denoted by $E_{n}(x)$, in terms of the operator
$x\frac{d}{dx}$ and the geometric series $\frac{1}{1-x}$; namely

$\left(x\frac{d}{dx}\right)\left(\frac{1}{1-x}\right)=\frac{E_{n}(x)}{(1-x)^{n+1}}\,.$

It is then reasonable to think that a general formula for $E_{\\{n,k\\}}$ may
be given by the Lucas version of a polynomial obtained by applying the
operator $x\frac{d}{dx}$ to a suitable transformation of $\varphi_{n}(x)$.

Conjecture. The Lucas-Eulerian numbers are given by
$E_{\\{n,k\\}}=\big{\\{}A_{n,k}\big{\\}}(\\{k+1\\})$, where
$\big{\\{}A_{n,k}\big{\\}}$ is the Lucas version of the polynomial
$A_{n,k}(x)$ defined as

$A_{n,k}(x)=\left(x\frac{d}{dx}\right)\Big{(}T(\varphi_{n}(x))\Big{)}\,,$

where $T$ is a suitable transformation of $\varphi_{n}(x)$.

##  3\. On an alternating sum formula for Eulerian numbers

For any integers $0\leq k<n$, setting $E_{n,n}=1$ for all $n\geq 0$ and
$E_{n,k}=0$ for $n<k$, a classical formula that holds for Eulerian numbers is

(16) $E_{n,k}=\sum_{j=0}^{k+1}(-1)^{k+1-j}\binom{n+2}{k+1-j}j^{n+1}\,.$

A natural question that comes to mind is what the Lucas analogue of this
formula should be. An immediate answer is to replace binomial coefficients and
powers of nonnegative integers with their Lucas versions. But what is the
Lucas version of $-1$?

$\bm{n\backslash k}$ | ${\color[rgb]{1,0,0}1}$
---|---
0 | 0
1 | 1
2 | $s^{3}+s^{3}t++2st^{2}$
3 | $s^{4}+s^{4}t+3s^{2}t^{2}+t^{3}$
4 | $s^{5}+s^{5}t+4s^{3}t^{2}+3st^{3}$
5 | $s^{6}+s^{6}t+5s^{4}t^{2}+6s^{2}t^{3}+t^{4}$
Table 2. $E^{\prime}_{\\{n,1\\}}$

$\bm{n\backslash k}$ | ${\color[rgb]{1,0,0}1}$
---|---
0 | 0
1 | 1
2 | $2s+s^{3}+\frac{s^{3}}{t}$
3 | $3s^{2}+t+s^{4}+\frac{s^{4}}{t}$
4 | $4s^{3}+3st+s^{5}+\frac{s^{5}}{t}$
5 | $5s^{4}+6s^{2}t+t^{2}+s^{6}+\frac{s^{6}}{t}$
Table 3. $E^{\prime\prime}_{\\{n,1\\}}$

We have seen in Section 1 that for convenient recursive formulas that hold for
Binomial and Narayana numbers, using Lucasnomials and replacing $-1$ with $t$
was enough to get consistent formulas for their Lucas analogues. Hence, let us
do the same here. Define the Lucas number

$E^{\prime}_{\\{n,k\\}}=\sum_{j=0}^{k+1}t^{k+1-j}\begin{Bmatrix}n+2\\\
k+1-j\end{Bmatrix}\\{j\\}^{n+1}\,.$

We can easily check that $E_{\\{n,k\\}}\neq E^{\prime}_{\\{n,k\\}}$ (compare
Table 1 with Table 3). Another plausible Lucas version of formula (16) is
obtained by extending the recurrence (1) to negative integers. In particular,
we have $\\{-1\\}=\frac{1}{t}$ so that we get the Lucas number

$E^{\prime\prime}_{\\{n,k\\}}=\sum_{j=0}^{k+1}\left(\tfrac{1}{t}\right)^{k+1-j}\begin{Bmatrix}n+2\\\
k+1-j\end{Bmatrix}\\{j\\}^{n+1}\,.$

Once more, we have $E^{\prime\prime}_{\\{n,k\\}}\neq E_{\\{n,k\\}}$ (compare
Table 1 with Table 3). This time though, we see that
$E^{\prime\prime}_{\\{n,1\\}}$ and $E_{\\{n,1\\}}$ are almost equal except for
an extra term $s^{n+1}+\frac{s^{n+1}}{t}$ for $n\geq 2$.

We wonder what the Lucas version of the alternating sum formula (16) is that
be compatible with our Lucas analogue of Eulerian numbers.

##  4\. Further comments

We expect to find an uncomplicated formula for Lucas-Eulerian numbers in
general by using induction. It is not easy to obtain a formula for
$E_{\\{n,k\\}}$ similar to the one given for $E_{\\{n,1\\}}$, as stated in the
conjecture. This difficulty is due in part to the fact that Lucas generalized
numbers are neither additive nor multiplicative, for instance
$\\{2\\}+\\{3\\}\neq\\{5\\}$ and $\\{2\\}\\{3\\}\neq\\{6\\}$. Moreover, Lucas-
Eulerian numbers are not always factorized in terms of Lucas atoms (we refer
to [8] for definitions and notations). Try for example to factorize
$E_{\\{3,1\\}}=3s^{2}+t$. Nevertheless, we can write $E_{\\{3,1\\}}$ as a
linear combination of Lucas atoms as follows

$3s^{2}+t=4(s^{2}+t)-(s^{2}+3t)=4P_{3}(s,t)-P_{6}(s,t)\,.$

Despite the elementary way of defining Lucas-Eulerian numbers, we have been
unable to find a combinatorial interpretation for them. We hope that the
reader will be tempted to find such an interpretation.

The recursive approach used here to define Lucas-Eulerian numbers can be used
to define Lucas versions of a vast collection of combinatorial constants for
which recursive relations are known. For instance, the Lucas analogue of the
Stirling numbers $St2_{n,k}$ of the second kind are given by

(17) $St2_{\\{n,k\\}}=\\{k\\}St2_{\\{n-1,k\\}}+St2_{\\{n-1,k-1\\}}\,,$

with the usual initial conditions $St2_{\\{0,0\\}}=1$, $St2_{\\{n,k\\}}=1$ for
$n=k$ or $k=1$, $St2_{\\{j,0\\}}=0$ for $j>0$, and $St2_{\\{n,k\\}}=0$ for
$n<k$.

$\bm{n\backslash k}$ | ${\color[rgb]{1,0,0}0}$ | ${\color[rgb]{1,0,0}1}$ | ${\color[rgb]{1,0,0}2}$ | ${\color[rgb]{1,0,0}3}$ | ${\color[rgb]{1,0,0}4}$ |  ${\color[rgb]{1,0,0}5}$
---|---|---|---|---|---|---
0 | 1 | 0 | 0 | 0 | 0 |  0
1 | 0 | 1 | 0 | 0 | 0 |  0
2 | 0 | $1$ | $1+s$ | 0 | 0 |  0
3 | 0 | $1$ | $1+s+s^{2}$ | 1 | 0 |  0
4 | 0 | $1$ | $1+s+s^{2}+s^{3}$ | $1+s+s^{2}+t$ | 1 |  0
5 | 0 | $1$ | $1+s+s^{2}+s^{3}+s^{4}$ | $1+s+2s^{2}++s^{3}+s^{4}+t+st+2s^{2}t+t^{2}$ | $1+s+s^{2}+s^{3}+t+2st$ |  1
Table 4. A sample of Lucas-Stirling numbers of the second kind

It follows from (17) that the Lucas-Stirling numbers of the second kind are
polynomials in $s$ and $t$ with nonnegative integer coefficients. Table 4
shows some of them. We are not aware of any work on these numbers in the
literature.

Here is another enlightening example; for $n\geq 2$ and with initial
conditions $M_{0}=M_{1}=1$, the standard Motzkin numbers $M_{n}$ are known to
satisfy the following recursive formula,

(18) $M_{n}=\frac{2n+1}{n+2}M_{n-1}+\frac{3n-3}{n+2}M_{n-2}\,.$

The natural Lucas analogue of relation (18) is

(19)
$M_{\\{n\\}}=\frac{\\{2n+1\\}}{\\{n+2\\}}M_{\\{n-1\\}}+\frac{\\{3n-3\\}}{\\{n+2\\}}M_{\\{n-2\\}}\,,$

with initial conditions $M_{\\{0\\}}=M_{\\{1\\}}=1$. Formula (19) gives
rational expressions in $s$ and $t$ for $M_{\\{n\\}}$ in general. For
instance,

$M_{\\{2\\}}=\frac{s^{4}+3s^{2}t+t^{2}+s^{2}+t}{s^{3}+2st}\,.$

On the other hand, Motzkin numbers also satisfy a formula in terms of
binomials coefficients and Catalan numbers, whose straightforward Lucas
analogue is

(20) $M_{\\{n\\}}=\sum_{k=0}^{\lfloor n/2\rfloor}\begin{Bmatrix}n\\\
2k\end{Bmatrix}C_{\\{k\\}}\,,$

where $C_{\\{k\\}}={\mbox{\tiny$\frac{1}{k+1}$}}{\tiny\begin{Bmatrix}2k\\\
k\end{Bmatrix}}$. Since Lucasnomials and Lucas-Catalan numbers are polynomials
in $s$ and $t$ with nonnegative integer coefficients [4], so are the Lucas-
Motzkin numbers by Formula (20). This apparent contradiction with (19) is due
to the fact that the recursive formula used to define the Lucas numbers
$M_{\\{n\\}}$ is not the right one. In the same way we did in Section 1, by
using a recursive relation different from the common one that holds for
binomial numbers, here we have to pick a different recursive relation whose
Lucas analogue be compatible with Formula (20).

In ongoing work, we elaborate more on this observation [1].

## References

  * [1] J. Agapito, A Lucas analogue of Riordan arrays. Preprint 2023.
  * [2] T. Amdeberhan, X. Chen, V. H. Moll, B. Sagan, Generalized Fibonacci Polynomials and Fibonomial Coefficients. _Ann. Comb._ 18 (2014), 541–562.
  * [3] A. Benjamin, S. Plott, A combinatorial approach to Fibonomial coefficients, _Fibonacci Quart._ , 46/47 (2008/2009), no. 1, 7–9.
  * [4] C. Bennett, J. Carrillo, J. Machacek, B. Sagan, Combinatorial interpretations of Lucas analogues of binomial coefficients and Catalan numbers. _Ann. Comb._ 24 (2020), no. 3, 503–530.
  * [5] K. Garret, K. Killpatrick, A combinatorial proof of a formula for the Lucas-Narayana polynomials. _Discrete Math._ 345 (2022), no. 12, 7 pp.
  * [6] I. Gessel, G. Viennot, Binomial determinants, paths, and hook length formulae, _Adv. in Math._ 58 (1985), no. 3, 300–321.
  * [7] B. Sagan, C. Savage, Combinatorial interpretations of binomial coefficient analogues related to Lucas sequences. _Integers_ , 10:A52 (2010), 697–703.
  * [8] B. Sagan and J. Tirrell, Lucas atoms, _Adv. Math._ 372 (2020) 107387