User:Peter Luschny/MotzkinNumbers

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

$\scriptstyle {\text{Motzkin Numbers}}$ ${M}_{n}^{\ }{\ =}\sum \limits _{k\geq 0}{\binom {n}{k}}{C}_{k}^{\ast }\left[k\ \operatorname {is\ even} \right]\$ $1,1,2,4,9,21,51,...$ $\scriptstyle {\text{Complementary Motzkin Numbers}}$ ${M}_{n}^{c}{\ =}\sum \limits _{k\geq 0}{\binom {n}{k}}{C}_{k}^{\ast }\left[k\ \operatorname {is\ odd} \right]\$ $0,1,2,6,16,45,126,...$ $\scriptstyle {\text{Extended Motzkin Numbers}}$ ${M}_{n}^{\ast }{\ =}\sum \limits _{k\geq 0}{\binom {n}{k}}{C}_{k}^{\ast }\$ $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.

${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; 
add(binomial(n,k)*ExtendedCatalan(k)*irem(k+1,2),k=0..n)
end: seq(Motzkin(i),i=0..9);

ComplementaryMotzkin := proc(n) local k; 
add(binomial(n,k)*ExtendedCatalan(k)*irem(k,2),k=0..n)
end: seq(ComplementaryMotzkin(i),i=0..9);

ExtendedMotzkin := proc(n) local k;
add(binomial(n,k)*ExtendedCatalan(k),k=0..n) end: 
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:
[seq( add( add( w(i,j,m), i=0..m),j=0..m),m=0..n)] 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 $\scriptstyle M_{n,k}^{\ast }{\ =}{\binom {n}{k}}C_{k}^{\ast }$, or equivalently:

$\scriptstyle {\text{Extended Motzkin Triangle}}$ ${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.

Extended Motzkin Triangle
offset (0, 0), ascending order of x^n.
maroon: classic, green: complementary

								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 $\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 q^k → 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.

$\scriptstyle {\text{Generalized Ballot Numbers}}$ ${b}_{n}^{\ }{\ =}{M}_{n+1}^{\ }-{M}_{n}^{\ }$ ${b}_{n}^{c}{\ =}{M}_{n+1}^{c}-{M}_{n}^{c}$ ${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.

Generalized ballot numbers

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):

$\scriptstyle {\text{Riordan Numbers}}$ ${R}_{n}^{\ }{\ =}{M}_{n-1}^{\ }-{R}_{n-1}^{\ };\ \ \ \ ({R}_{0}^{\ }=1)$ $1,0,1,1,3,6,15,36,91,...$ $\scriptstyle {\text{Extended Riordan Numbers}}$ ${R}_{n}^{\ast }{\ =}{M}_{n-1}^{\ast }-{R}_{n-1}^{\ast };\ \ \ \ ({R}_{0}^{\ast }=1)$ $1,0,2,2,8,17,49,128,356,...$ $\scriptstyle {\text{Complementary Riordan Numbers}}$ ${R}_{n}^{c}{\ =}{R}_{n}^{\ast }-{R}_{n}^{\ }$ $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.

$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:

$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:

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

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

Extended Riordan Triangle
offset (0, 0), ascending order of x^n.

								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 q^k → 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