This site is supported by donations to The OEIS Foundation.

# Motzkin Numbers and Riordan Numbers

KEYWORDS: Motzkin numbers, extended Motzkin numbers, complementary Motzkin numbers.

Concerned with sequences:

 A001006 Motzkin numbers A005717 Complementary Motzkin numbers A189912 Extended Motzkin numbers A097610 Motzkin triangle A189913 Extended Motzkin triangle A089627 Motzkin swing A194586 Complementrary Motzkin swing A163649 Extended Motzkin swing A002026 Generalized ballot numbers A025179 Compl. gen. ballot numbers A194587 Ext. gen. ballot numbers

## The extended Motzkin numbers

One way to assure that the extension of the Catalan numbers is meaningful is to look how good the characteristics of the classical Catalan numbers are preserved. Another way is to look how good the extensions fit into the general picture, how good they extend well known relations of the Catalan numbers with other important numbers. Here we will briefly look at the relations with the Motzkin numbers.

The key fact is: The Catalan numbers aerated with 0's at odd positions A126120 are the inverse binomial transform of the Motzkin numbers A001006.

Moreover the complementary Catalan numbers A001700 aerated with 0's at even positions A138364 are the inverse binomial transform of the complementary Motzkin numbers A005717.

In consequence the extended Catalan numbers (A057977=A126120+A138364) are the inverse binomial transform of the extended Motzkin numbers A189912.

These relations are summed up by the three formulas below. (The asterix denotes the extended case and c´ the complementary case.)

 ${\displaystyle \scriptstyle {\text{Motzkin Numbers}}}$ ${\displaystyle {M}_{n}^{\ }{\ =}\sum \limits _{k\geq 0}{\binom {n}{k}}{C}_{k}^{\ast }\left[k\ \operatorname {is\ even} \right]\ }$ ${\displaystyle 1,1,2,4,9,21,51,...}$ ${\displaystyle \scriptstyle {\text{Complementary Motzkin Numbers}}}$ ${\displaystyle {M}_{n}^{c}{\ =}\sum \limits _{k\geq 0}{\binom {n}{k}}{C}_{k}^{\ast }\left[k\ \operatorname {is\ odd} \right]\ }$ ${\displaystyle 0,1,2,6,16,45,126,...}$ ${\displaystyle \scriptstyle {\text{Extended Motzkin Numbers}}}$ ${\displaystyle {M}_{n}^{\ast }{\ =}\sum \limits _{k\geq 0}{\binom {n}{k}}{C}_{k}^{\ast }\ }$ ${\displaystyle 1,2,4,10,25,66,177,...}$
 A001006 Motzkin numbers A005717 Complementary Motzkin numbers A189912 Extended Motzkin numbers

To introduce the extended Motzkin numbers via the Catalan numbers is in the first place a matter of motivation as they can also be expressed more directly as a binomial sum of swinging factorials.

 ${\displaystyle {M}_{n}^{\ast }{\ =}\sum \limits _{k\geq 0}{\binom {n}{k}}{\frac {k\wr }{\lfloor k/2\rfloor +1}}}$ 

With Maple:

ExtendedCatalan := n -> (n!/iquo(n,2)!^2)/(iquo(n,2)+1):

Motzkin := proc(n) local k;
end: seq(Motzkin(i),i=0..9);

ComplementaryMotzkin := proc(n) local k;
end: seq(ComplementaryMotzkin(i),i=0..9);

ExtendedMotzkin := proc(n) local k;
seq(ExtendedMotzkin(i),i=0..9);


The combinatorial interpretation of the Motzkin numbers leads to a recurrence:  Let w(i,j,n) denote walks in N^2 which satisfy the multivariate recurrence

w(i,j,n) = w(i, j+1, n-1) + w(i-1, j, n-1) + w(i+1, j-1, n-1)

with boundary conditions w(0,0,0) = 1 and w(i,j,n) = 0 if i or j or n is < 0. Then a(n) = Sum{i = 0..n, j = 0..n} w(i,j,n) is the number of such walks of length n.

With Maple:

Motzkin_list := proc(n) local w, m, j, i;
w := proc(i, j, n) option remember;
if min(i, j, n) < 0 or max(i, j) > n then 0
elif n = 0 then if i = 0 and j = 0 then 1 else 0 fi else
w(i,j+1,n-1) + w(i-1,j,n-1) + w(i+1,j-1,n-1) fi end:
Motzkin_list(9);


## The extended Motzkin triangle

The sequence of Motzkin numbers is escorted by the Motzkin triangle A097610, the M(n, k)  counting the number of Motzkin paths of length n and having k horizontal steps.

Row sums are the Motzkin numbers A001006 and the left border gives the aerated Catalan numbers A000108.

The extended Motzkin triangle A189913 is defined as ${\displaystyle \scriptstyle M_{n,k}^{\ast }{\ =}{\binom {n}{k}}C_{k}^{\ast }}$, or equivalently:

 ${\displaystyle \scriptstyle {\text{Extended Motzkin Triangle}}}$ ${\displaystyle {M}_{n,k}^{\ast }{\ =}{\binom {n}{k}}{\frac {k\wr }{\lfloor k/2\rfloor +1}}}$

Row sums are the extended Motzkin numbers A189912 and right border gives the extended Catalan numbers A057977.

 1 1 1 1 2 1 1 3 3 3 1 4 6 12 2 1 5 10 30 10 10 1 6 15 60 30 60 5 1 7 21 105 70 210 35 35 14 280 140 560 140 168 28 8 1
 A097610 Motzkin triangle A189913 Extended Motzkin triangle

## The swinging Motzkin triangles

There are also three other triangles closely related to the Motzkin numbers.

 A089627 Motzkin Swing A194586 Complementary Motzkin Swing A163649 Extended Motzkin Swing

For example let us look at A163649 in it's unsigned version.  (n$is the poor man's notation for the swinging factorial ${\displaystyle \scriptstyle n\wr .)}$ ms(q) = Sum_{k=0..n} binomial(n,k)*(k$)*q^k. 
                        1
1 + q
1 + 2 q + 2 q^2
1 + 3 q + 6 q^2  + 6 q^3
1 + 4 q + 12 q^2  + 24 q^3  + 6 q^4
1 + 5 q + 20 q^2  + 60 q^3  + 30 q^4  + 30 q^5
1 + 6 q + 30 q^2  + 120 q^3  + 90 q^4  + 180 q^5  + 20 q^6


Substituting qk → 1/(floor(k/2) + 1) in the polynomials gives the extended Motzkin numbers. The other two cases refer to aerated versions of this triangle. The same substitution leads then to the Motzkin and to the complementary Motzkin numbers respectively.

## Generalized ballot numbers

The first differences of Motzkin numbers are the generalized ballot numbers A002026.

 ${\displaystyle \scriptstyle {\text{Generalized Ballot Numbers}}}$ ${\displaystyle {b}_{n}^{\ }{\ =}{M}_{n+1}^{\ }-{M}_{n}^{\ }}$ ${\displaystyle {b}_{n}^{c}{\ =}{M}_{n+1}^{c}-{M}_{n}^{c}}$ ${\displaystyle {b}_{n}^{\ast }{\ =}{M}_{n+1}^{\ast }-{M}_{n}^{\ast }}$

Note a technical point because there is quite some confusion in the database concerning the term 'first differences': Some use it in the sense of a forward difference Δa(n) = a(n+1) − a(n) and some in the sense of a backward difference Δa(n) = a(n) − a(n-1). A002026 is defined as a forward difference and we adopt this convention here also. In particular this means that if the original sequence starts at n = 0 so will the sequence of first differences.

Now let us look at the three cases.

 n 0 1 2 3 4 5 6 7 A002026 0 1 2 5 12 30 76 196 A025179 1 1 4 10 29 81 231 659 A194587 1 2 6 15 41 111 307 855

We see that A025179 should be rectified by prepending a 1 and shifting the sequence one index to the left (to fit in our scheme of things).

The nice thing is that the exponential generating function for A025179 given by Vladeta Jovovic exp(x)(BesselI(0, 2x)+BesselI(2, 2x)) is in total agreement with our point of view. And Jovovic's binomial formula also. As is Paul Barry's formula. Therefore I think the name and the offset of A025179 should be revised.

## The Riordan numbers

The Riordan numbers are defined as (again the asterix denotes the extended and c´ the complementary case):

 ${\displaystyle \scriptstyle {\text{Riordan Numbers}}}$ ${\displaystyle {R}_{n}^{\ }{\ =}{M}_{n-1}^{\ }-{R}_{n-1}^{\ };\ \ \ \ ({R}_{0}^{\ }=1)}$ ${\displaystyle 1,0,1,1,3,6,15,36,91,...}$ ${\displaystyle \scriptstyle {\text{Extended Riordan Numbers}}}$ ${\displaystyle {R}_{n}^{\ast }{\ =}{M}_{n-1}^{\ast }-{R}_{n-1}^{\ast };\ \ \ \ ({R}_{0}^{\ast }=1)}$ ${\displaystyle 1,0,2,2,8,17,49,128,356,...}$ ${\displaystyle \scriptstyle {\text{Complementary Riordan Numbers}}}$ ${\displaystyle {R}_{n}^{c}{\ =}{R}_{n}^{\ast }-{R}_{n}^{\ }}$ ${\displaystyle 0,0,1,1,5,11,34,92,265,...}$
 A005043 Riordan numbers A194589 Complementary Riordan numbers A194588 Extended Riordan numbers

With Maple:

Riordan := n -> if(n=0,1,Motzkin(n-1)-Riordan(n-1)):
ExtendedRiordan := n -> if(n=0, 1,
ExtendedMotzkin(n-1) - ExtendedRiordan(n-1)):
ComplementaryRiordan := n->ExtendedRiordan(n)-Riordan(n):


We can also give a definition of the complementary Riordan numbers which does not refer to the extended Riordan numbers.

${\displaystyle R_{n}^{c}={\frac {1}{2}}\sum \limits _{k=0}^{n}(-1)^{k}{\binom {n}{k}}\left((k+1)\wr \left({\frac {k+1}{2}}\right)^{k{\bmod {2}}}-2^{k}\right)}$

This formula has interesting relations to A194590, A100071 and to D. P. Robbins proposed formula for the degree of generalized Heron polynomials.

Similarly we can obtain a formula for the extended Riordan numbers:

${\displaystyle R_{n}^{\ast }=\left[n{\text{ even}}\right]+{\frac {1}{2}}\sum \limits _{k=1}^{n}(-1)^{k}{\binom {n}{k}}\left((k+1)\wr \left({\frac {k+1}{2}}\right)^{k{\bmod {2}}}+(-1)^{n}{\frac {2(2k)\wr }{k+1}}\right)}$

## The extended Riordan triangle

The extended Riordan triangle A000000 is defined as:

 ${\displaystyle \scriptstyle {\text{Extended Riordan Triangle}}}$ ${\displaystyle {R}_{n,k}^{\ast }{\ =}{\binom {n}{k}}{R}_{n}^{\ast }}$

The row sum is 1 if n = 0 and otherwise A077587(n-1).

 1 1 0 1 0 2 1 0 6 2 1 0 12 8 8 1 0 20 20 40 17 1 0 30 40 120 102 49 1 0 42 70 280 357 343 128 1 0 56 112 560 952 1372 1024 356
 A124926 Binomial Riordan triangle A000000 Extended Binomial Riordan triangle

## The swinging Riordan triangles

As in the Motzkin case there are also three polynomial based triangles closely related to the Riordan numbers.

 A000000 Riordan Swing
              1
0
1
2 q^2
1 + 4 q^2
8 q^2  + 6 q^4
1 + 12 q^2  + 24 q^4
18 q^2  + 66 q^4  + 20 q^6
1 + 24 q^2  + 144 q^4  + 120 q^6


Substituting qk → 1/(floor(k/2) + 1) in the polynomials gives the Riordan numbers. Similarly the extended and the complementary Riordan numbers can be computed. The triangles are still missing in OEIS.

 A000000 Extended Riordan Swing
                      1
0
1 + q
q + 2 q^2
1 + 2 q + 4 q^2  + 6 q^3
2 q + 8 q^2  + 18 q^3  + 6 q^4
1 + 3 q + 12 q^2  + 42 q^3  + 24 q^4  + 30 q^5
3 q + 18 q^2  + 78 q^3  + 66 q^4  + 150 q^5  + 20 q^6