This site is supported by donations to The OEIS Foundation.

User:Peter Luschny/MotzkinNumbers

From OeisWiki

Jump to: navigation, search

Motzkin Numbers
and Riordan Numbers

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

Concerned with sequences:

A001006Motzkin numbers
A005717Complementary Motzkin numbers
A189912Extended Motzkin numbers
A097610Motzkin triangle
A189913Extended Motzkin triangle
A089627Motzkin swing
A194586Complementrary Motzkin swing
A163649Extended Motzkin swing
A002026Generalized ballot numbers
A025179Compl. gen. ballot numbers
A194587Ext. gen. ballot numbers

Contents

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\geq0}\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\geq0}\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\geq0}\binom{n}{k} {C}_{k}^{\ast}\

1,2,4,10,25,66,177,...

A001006Motzkin numbers
A005717Complementary Motzkin numbers
A189912Extended 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\geq0}\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
A097610Motzkin triangle
A189913Extended Motzkin triangle

The swinging Motzkin triangles

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

A089627Motzkin Swing
A194586Complementary Motzkin Swing
A163649Extended 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 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.

 \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,...

A005043Riordan numbers
A194589Complementary Riordan numbers
A194588Extended 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^{c}_{n} = \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^{\ast}_{n} = \left[ n \text{ even} \right]  +  \frac12 \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
A124926Binomial Riordan triangle
A000000Extended 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.

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

A000000Extended 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
Personal tools