This site is supported by donations to The OEIS Foundation.

User:Peter Luschny/TheLostCatalanNumbers

From OeisWiki

Jump to: navigation, search

The Lost Catalan Numbers
And The Schröder Tableaux.

KEYWORDS: Catalan numbers, extended Catalan numbers, complementary Catalan numbers, aerated Catalan numbers, Catalan triangle, central binomial, middle binomial, swinging factorial, swinging polynomials.

Concerned with sequences:

A000108Catalan numbers
A001700Complementary Catalan numbers
A057977Extended Catalan numbers
A126120Aerated Catalan numbers
A138364Aerated complementary Catalan numbers
A000984Central binomial coefficients
A001405Middle binomial coefficients
A056040Swinging factorial
A162246Swinging Polynomials

Note: There are many different ways to generalize the Catalan numbers. We look here only at one possible way which we believe is a natural one. Likewise we think that the terminology we use is a natural one as it weaves closely related sequences into a coherent web; it does not necessarily jibe with the terminology used in the database though.

Contents

Swinging factorials

Let us invent a new sequence, just for fun. Where to start? There is no doubt that Pascal's triangle is a very good starting place. As we all know this triangle is full of relations, secrets and wonders.

The binomial coefficients
               1              
             1    1            
          1    2   1          
         1   3   3    1        
       1   4    6   4    1      
     1    5   10   10    5    1    
   1    6   15   20    15    6    1  
 1   7   21   35   35   21   7    1

The eyes fell immediately at the center column, on the central binomials (2n, n). So let us concentrate on this sequence. What is the next obvious observation? There are holes in this sequence! In the second row, in the fourth row, etc. So let us write the central column as 1, *, 2, *, 6, *, 20, *,... and ask: Is there a sensible way to fill these holes?

A possible answer is to fill in the arithmetical mean of the two numbers from the adjacent cells in the same row: 1, 2, 3, 6, 10, 20,... This sequence is called the middle binomials. But there is also a second way to fill the holes to which much less attention is paid: 1, 2, 6, 6, 30, 20,.. It is this sequence at which we will look here.

Table 1: Central binomials
and swinging factorials
n 0   1   2   3   4   5
\scriptstyle \binom{2n}{n} 1 * 2 * 6 * 20 * 70 * 252
\scriptstyle n \wr 1 1 2 6 6 30 20 140 70 630 252
n 0 1 2 3 4 5 6 7 8 9 10

For easier communication let us give this sequence a name, let us call it the swinging factorial. This is a funny name but there are good reasons to call this sequence this way. Factorial because it shares many interesting arithmetical properties with the factorial function and swinging because it is not monotone but proceeds more like a wave. The plot below shows this sequence extended to an analytic function. Because of the rapid growth of the function the logarithm of the function is shown, for comparison together with the logarithm of the factorial function. To complete the intended analogy with the factorial function let us agree to write the symbol \scriptstyle \wr for the function name, i.e. to write \scriptstyle n\wr for the swinging factorial similar to the notation n! for the factorial function. Thus the definition is

 n \wr \ = \ n!\ /\ (\lfloor n/2 \rfloor!)^2  
The logarithm of the swinging factorial.

The sequence of the swinging factorials can be characterized in many different ways. For instance a simple characterization is:

 n \wr \ = \ \text{lcm} \left( \binom{n-1}{ \lfloor (n-1)/2 \rfloor }, \binom{n}{ \lfloor n/2 \rfloor } \right)

Motivated by a recent discussion let me make some remarks. Though this characterization is logical equivalent to the definition a mathematician would not make it the definition of the swinging factorial. The reason is simple: both the conceptual as well as the computational complexity of this formula is clearly higher than the one of the definition given,  \scriptstyle n \wr \ = \ n!\ /\ (\lfloor n/2 \rfloor!)^2  . But a proper definition should be at the lower bound of the complexity of equivalent formulas by well accepted standards of logical systematic.

The swinging factorial can be generalized to a complex function very similar like the factorial function can be generalized to the complex Gamma function. We will not further pursue this subject here as we have promised to look at the Catalan numbers.

The extended Catalan numbers

Table 2: Catalan numbers
and extended Catalan numbers
n 0   1   2   3   4   5
\scriptstyle C_n 1 * 1 * 2 * 5 * 14 * 42
\scriptstyle C^{*}_n 1 1 1 3 2 10 5 35 14 126 42
n 0 1 2 3 4 5 6 7 8 9 10

The Catalan numbers can be expressed as

 C_n \ = \ \frac{1}{n+1} \binom{2n}{n}. 

This is the most commonly used definition. Having generalized the central binomial to the swinging factorial it is natural now to ask what happens when we plug this generalization into the definition of the Catalan numbers. Doing this we have to lower 2n to n and we also have to replace n by floor(n/2). Thus we are led to

 C^{*}_n \ = \frac{ n \wr }{ \lfloor n/2 \rfloor + 1 }. \quad (*)  

Like in the case of the swinging factorial many equivalent formulas for the extended Catalan numbers can be given. For instance we have

 C^{*}_n \ = \ \gcd \left( \binom{n}{\lfloor n/2 \rfloor}, \binom{n+1}{\lfloor (n+1)/2 \rfloor} \right). \quad (**)

This formula has its value if one studies the divisibility properties of the extended Catalan numbers; as a definition it is inapt: it introduces concepts not needed (the gcd) and it is obviously more complex than the definition (*).

But wait a minute, does (*) and (**) not imply a nice identity?

 \scriptstyle \gcd \left( \binom{n}{\lfloor n/2 \rfloor}, \binom{n+1}{\lfloor (n+1)/2 \rfloor} \right) \left( {\lfloor n/2 \rfloor + 1} \right) \ =  \ \text{lcm} \ \left( \binom{n-1}{\lfloor (n-1)/2 \rfloor}, \binom{n} {\lfloor n/2 \rfloor}  \right)

The proof is simple: it reduces to  \scriptstyle n \wr \ = \ n \wr \, if we move the second factor from the left hand side to the right hand side.

Summary I: The extended Catalan numbers can be regarded as extending

A000984(n)/(n+1) to A056040(n)/(floor(n/2)+1)

by replacing the central binomial by the swinging factorial.

The complementary Catalan numbers

Let us look again at

n 0   1   2   3   4   5
  1 * 1 * 2 * 5 * 14 * 42

As long as we have no idea what these `*´ could be it is not entirely inappropriate to fill zeros into these places.

n 0 1 2 3 4 5 6 7 8 9 10
  1 0 1 0 2 0 5 0 14 0 42

This sequence gives the aerated Catalan numbers. Martin Aigner once discussed six ways to look at Catalan numbers and regarded aerated Catalan numbers as the most important way to introduce the Catalan numbers (in a general framework of combinatorial numbers).

The sequence which gives by termwise addition with the aerated Catalan numbers the extended Catalan numbers are the aerated complementary Catalan numbers.

n 0 1 2 3 4 5 6 7 8 9 10
  0 1 0 3 0 10 0 35 0 126 0

Consequently the complementary Catalan numbers are

n 0 1 2 3 4 5 6 7 8 9
  1 3 10 35 126 462 1716 6435 24310 92378

These are the number of binary numbers of length 2n+1 with n+1 1's and n 0's by a comment of Stefan Hollos in A001700.

Table 3: Catalan numbers and
 complementary Catalan numbers
(aerated versions)
n 0 1 2 3 4 5 6 7 8 9 10 11 12
A126120 1 0 1 0 2 0 5 0 14 0 42 0 132
A138364 0 1 0 3 0 10 0 35 0 126 0 462 0

Summary II: The extended Catalan numbers can be regarded as the sum of the Catalan numbers (in aerated form) and the complementary Catalan numbers (in aerated form),

A057977(n) = A126120(n) + A138364(n).


An integral representation of the extended Catalan numbers

Summary (I) in the last paragraph together with summary (II) explain the meaning of the name 'extended Catalan numbers'.

Clearly we have still to assure that this extension is a natural one, i. e. that it also extends the characteristics of the classical Catalan numbers. One way to convince ourselves is to look at high level analytic characterizations of the Catalan numbers. We just give one example based on the work of K. A. Penson and J.-M. Sixdeniers [1]

Penson and Sixdeniers showed the following integral representation of the Catalan numbers.

 C^{*}_{2n} \ = \ \frac{1}{2\pi}{\int_{0}^{4}} x^{n}\frac{\left(4-x\right)^{1/2}}{x^{1/2}}dx 

It is not difficult to prove that the complementary Catalan numbers have an integral representation where the weight function is just inverted

 C^{*}_{2n+1} \ = \ \frac{1}{2\pi}{\int_{0}^{4}}x^{n}\frac{x^{1/2}}{\left(4-x\right)^{1/2}}dx \ . 

These representations show that we have a concept under consideration which can be handled naturally as a single entity and that switching from the `even´ case to the `odd´ case is reflected by a similar basic operation in some operator space.  Putting the even and the odd case together we can write

 C^{*}_{n} \ = \ \frac{1}{2 \pi}{\int\limits_{0}^{4}} \left(x^{2n-1} \left( \left(4-x\right)^{2} x^{-1} \right)^{\cos n \pi}  \right)^{1/4} dx \ . 

Much more is true; based on the analytic version of the swinging factorial also the extended Catalan numbers can be seen as values of a complex function which turns out to be a very interesting object of study in its own right. Some details have been worked out in a paper by the author [2]. The plot below shows the real Catalan function together with upper and lower bounds. It is an aesthetical pleasing function which preserves the `swinging´ character of the subjacent swinging factorial function.

The Catalan function with bounds.

The extended Catalan triangle

The sequence of Catalan numbers is escorted by the Catalan triangle. As the reader might already suspect we will again layer our treatment on the swinging factorial function, this time in the shape of the swinging polynomials A162246.

The swinging polynomials are in fact Laurent polynomials which have symmetrical coefficients with regard to x^0. Therefore we do not loose much if we look only at the nonnegative coefficients of these polynomials to simplify things.

Coefficients of the swinging polynomials
(offset (0, 0), ascending order of x^n)
               1              
             1    1            
          2    2     1          
         6   3      3     1        
       6   12    4     4    1      
     30   10   20      5     5    1    
   20    60   15   30    6    6     1  
 140   35   105   21   42      7     7     1

As soon as we have the swinging polynomials the Catalan triangle in all three flavors fall like ripe fruit from the tree.

Let  \scriptstyle \tilde{s}(n,k) denote the swinging triangle above and [.] the Iverson brackets then for n ≥ 1 and k ≥ 1

 \scriptstyle \text{Catatalan Triangle}

 {C}_{n,k}  {\ =}\ \tilde{s}(n,k)   \frac{k}{n} [n - k\ \text{is even}]

 \scriptstyle \text{Complementary Catalan Triangle}

 {C}_{n,k}^{c}{\ =}\ \tilde{s}(n,k) \frac{k}{n} [n - k\ \text{is odd}]

 \scriptstyle \text{Extended Catalan Triangel}

 {C}_{n,k}^{\ast}{\ =}\ \tilde{s} (n,k) \frac{k}{n}

Extended Catalan Triangle
offset (1, 1), ascending order of x^n.
maroon: classic, green: complementary
                 1                
               1    1              
             1    2    1            
           3    2    3    1          
         2    8    3  4    1        
       10   5   15     4    5    1      
     5    30    9   24    5    6    1    
   35   14   63   14   35     6    7    1  
14   112   28   112   20   48   7   8   1
A053121Catalan triangle
A189230Complementary Catalan triangle
A189231Extended Catalan triangle

The offset of all three triangles is (1,1). Thus  \scriptstyle C^{*}_{n,1} = C^{*}(n - 1).

The triangles implemented with Maple:

SwingPoly := proc(n,k); 
if abs(k) > n then 0 elif n = k then 1 else
SwingPoly(n-1,k-1) + modp(n-k,2)*SwingPoly(n-1,k)
+ SwingPoly(n-1,k+1) fi end;

CatalanTriangle := (n,k) ->
`if`(n-k mod 2 = 1, 0, k*SwingPoly(n,k) / n):

ComplementaryCatalanTriangle := (n,k) ->
`if`(n-k mod 2 = 0, 0, k*SwingPoly(n,k) / n):

ExtendedCatalanTriangle := (n,k) ->
k*SwingPoly(n,k) / n:

Ballot triangles

Generalized ballot triangle
maroon: classic, green: complementary
Ep0 1                  
Ep1 0 1                
Ep2 1 0 1              
Ep3 0 2 0 3            
Ep4 1 0 2 0 2        
Ep5 0 3 0 8 0 10        
Ep6 1 0 3 0 5 0 5      
Ep7 0 4 0 15 0 30 0 35    
Ep8 1 0 4 0 9 0 14 0 14  
Ep9 0 5 0 24 0 63 0 112 0 126
Epq E0q E1q E2q E3q E4q E5q E6q E7q E8q E9q
A009766Classic ballot triangle (maroon)
A238761Complementary ballot triangle (green)
A238762Generalized ballot triangle

First observe that this triangle without the 0s is just a rearrangement of the extended Catalan triangle above. Diagonals starting at the right hand side there are rows starting at the left hand side here.

Next look at the classical numbers (maroon). This is the triangle from Knuth 7.2.1.6 eq. 22. In the database this is A009766 (also called Catalan triangle) .

The generalized ballot triangle has the following recursive structure: E00=1, Epq=0 if p<0 or p>q, and otherwise

Epq = E(p-2)q + [q odd]E(p-1)(q-1) + Ep(q-2).

With Maple:

BallotE := proc(p,q) local S;
  if (p = 0) and (q = 0) then 1 
elif (p < 0) or  (p > q) then 0
else S := BallotE(p-2,q) + BallotE(p,q-2);
if irem(q,2) = 1 then S := S + BallotE(p-1,q-1) fi;
S fi end:

A first summary

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. For instance the relation with the Motzkin and Riordan numbers is discussed [here].

The Schröder numbers

Two kinds of Schröder numbers can be found in the literature:

     Sn = 1 , 2, 6, 22, 90, 394, ...
     Sn = 1, 1, 3, 11, 45, 197, ...

Apart from the value for n = 0 the terms of the second sequence are half of the terms of the first. There are "two schools of thought" about the value of the first term of the second sequence: 0 or 1? And what is the connection with the extended Catalan numbers? The three formulas below explain all that.

 \scriptstyle \text{Big Schroeder Numbers}

 {S}_{n}^{\ }{\ =}\sum\limits_{0\leq k \leq n}\binom{n+k}{n-k}{C}_{2k}^{\ast}\

1,2,6,22,90,394,...

 \scriptstyle \text{Little even Schroeder Numbers}

 {S}_{n}^{e} {\ =}\sum\limits_{0\leq k \leq n}\binom{n+k}{n-k}{C}_{2k}^{\ast}\left[k\ \operatorname{is\ even}\right]\

1,1,3,11,45,197,...

 \scriptstyle \text{Little odd Schroeder Numbers}

 {S}_{n}^{o} {\ =}\sum\limits_{0\leq k \leq n}\binom{n+k}{n-k}{C}_{2k}^{\ast}\left[k\ \operatorname{is\ odd}\right]\

0,1,3,11,45,197,...

Thus there are two kinds of little Schröder numbers, the even little Schröder numbers Sen and the odd little Schröder numbers Son; the sequence Se starts with 1 and the sequence So starts with 0; in all other cases the two sequences are equal. Note that you will not find this differentiation in the literature (as far as I know). However, the two kinds of little Schröder numbers count different objects, as can be seen from the table below adding the terms in a row with the same color. For instance:

Se6 = 1 + 140 + 630 + 132 = 903
So6 = 21 + 420 + 462 = 903

Schröder triangle, offset (0, 0)
maroon: sums to even little SN; green: sums to odd little SN;
green column: large SN.
               1                  1
             1    1                2
           1    3    2              6
         1    6    10    5            22
       1    10    30    35    14          90
     1    15    70   140   126    42        394
   1    21    140   420    630    462    132      1806
 1    28    252   1050   2310   2772   1716    429    8558
A088617Schröder triangle
A060693Transposed Schröder triangle

The generating function of the Schröder triangle:

  gf(x,y) =  \frac{1 - y - \sqrt{(1-y)^2-4xy}}{2xy}.

With Maple:

gf := (x,y) -> (1-y-sqrt((1-y)^2-4*x*y))/(2*x*y);
S := (n) -> coeff(series(gf(x,y), y, n+2), y, n);
T := (n,k) -> coeff(S(n), x, k);
seq(print(seq(T(n,k), k=0..n)), n=0..7);

SchroederTriangle := (n,k) -> 
    binomial(n+k,n-k)*binomial(2*k,k)/(k+1):
EvenSchroederTriangle := (n,k) -> 
    `if`(k mod 2 = 0,0,SchroederTriangle(n,k)):
OddSchroederTriangle := (n,k) ->  
    `if`(k mod 2 = 1,0,SchroederTriangle(n,k)):

seq(print(seq(SchroederTriangle(n,k),k=0..n)),n=0..7);
seq(print(seq(EvenSchroederTriangle(n,k),k=0..n)),n=0..7);
seq(print(seq(OddSchroederTriangle(n,k),k=0..n)),n=0..7);

# Small (even) Schroeder numbers:
A001003_list := proc(n) local j, a, w; a:=array(0..n); 
a[0] := 1; for w from 1 to n do 
a[w] := a[w-1]+2*add(a[j]*a[w-j-1], j=1..w-1) od;
convert(a, list) end: A001003_list(12);

# Large Schroeder numbers:
A006318_list := proc(n) local j, a, w; a:=array(0..n); 
a[0] := 1; for w from 1 to n do 
a[w] := 2*a[w-1]+add(a[j]*a[w-j-1], j=1..w-1) od; 
convert(a, list) end: A006318_list(12);

As can be seen from the Maple implementation we used a recurrence to implement the computation of the list of large and small Schröder numbers. Starting with A0 = 1

 \scriptstyle \text{A Super Schroeder Recurrence}

 A_{n} \ = a A_{n-1} + b \sum \limits_{1 \leq k < n} A_{k} A_{n-k-1}

The pair [a = 1, b = 1] gives the Catalan numbers. The small even Schröder numbers are obtained with [a = 1, b = 2]. The big Schröder numbers are obtained with [a = 2, b = 1]. More generally we might look at the pairs [[a = 1, b = n], [a = n, b = 1]]. For example [[a = 1, b = 3], [a = 3, b = 1]] leads to A007564 and A047891 respectively. The case n = 4 leads to the pair A059231 and A082298. This opens up a hierarchy of Super-Schröder numbers.

The extended Schröder triangle

From our point of view the definitions from the last section are unnecessarily restricted. Here the extended version of the Schröder triangle:

 \scriptstyle \text{Extended Schroeder Triangle}

 {S}_{n,k}^{\ast}{\ =}\binom{n+k}{n-k}{C}_{k}^{\ast}\

 \scriptstyle \text{Row sums}

 {S}_{n}^{\ast}{\ =}\sum\limits_{0\leq k \leq n}{S}_{n,k}^{\ast}

1,2,5,15,49,163...

Extended Schröder triangle, offset (0, 0)
               1                  1
             1    1                2
           1    3    1              5
         1    6    5    3            15
       1    10    15    21    2          49
     1    15    35   84   18    10        163
   1    21    70   252    90    110    5      549
 1    28    126   630   330   660   65    35    1875
A190907Extended Schröder triangle
A190908Extended Schröder numbers


With Maple:

ExtendedSchroederTriangle := (n,k) -> 
   binomial(n+k,n-k)*(k!/iquo(k,2)!^2)/(iquo(k,2)+1); 
        
for n from 0 to 7 do 
   seq(ExtendedSchroederTriangle(n,k),k=0..n) od;

The extended Delannoy triangle

The Delannoy triangle is here defined as a decomposition of the central Delannoy numbers. (This triangle should not be confused with the square array of Delannoy numbers A008288.)

 \scriptstyle \text{Delannoy Triangle}

 D_{n,k} = \binom{n+k}{n-k} (2k)\wr

 \scriptstyle \text{Row sums (Delannoy numbers)}

 {D}_{n}\ = \sum\limits_{0\leq k \leq n}{D}_{n,k}

1,3,13,63,321,...

 \scriptstyle \text{Extended Delannoy Triangle}

 D_{n,k}^{\ast} = \binom{n+k}{n-k} k\wr

 \scriptstyle \text{Row sums}

 D_{n}^{\ast} \  = \sum\limits_{0\leq k \leq n}{D}_{n,k}^{\ast}

1,2,6,23,89,338,...

A063007Delannoy triangle
A001850Central Delannoy numbers
A190909Extended Delannoy triangle
A190910Extended central Delannoy numbers
Extended Delannoy triangle, offset (0, 0)
               1                  1
             1    1                2
           1    3    2              6
         1    6    10    6            23
       1    10    30    42    6          89
     1    15    70   168   54    30        338
   1    21    140   504    270    330    20      1286
 1    28    252   1260   990   1980   260    140    4911

The relation between the Delannoy triangles and the Schroeder triangles is simple enough.

 D_{n,k} \  = (k+1) S_{n,k}

 D_{n,k}^{\ast} \  = \Big\lfloor \frac{k+2}{2} \Big\rfloor S_{n,k}^{\ast}

With Maple:

DelannoyTriangle := (n,k) -> 
binomial(n+k,n-k)*(2*k)!/k!^2:
seq(print(seq(DelannoyTriangle(n,k),k=0..n)),n=0..7);

DelannoyNumbers := (n) -> 
add(DelannoyTriangle(n,k),k=0..n): 
seq(DelannoyNumbers(n),n=0..7);

XDelannoyTriangle := (n,k) -> 
binomial(n+k,n-k)*k!/iquo(k,2)!^2:
seq(print(seq(XDelannoyTriangle(n,k),k=0..n)),n=0..7);

XDelannoyNumbers := (n) -> 
add(XDelannoyTriangle(n,k),k=0..n): 
seq(XDelannoyNumbers(n),n=0..7);

Summary

  Classic
Triangle
Classic
Numbers
Extended
Triangle
Extended
Numbers
Central
Pascal
\scriptstyle \binom{n}{k}^2 \scriptstyle \binom{2n}{n}   \scriptstyle n \wr
A008459 A000984   A056040
Catalan \scriptstyle {C}_{n,k}{\ =}\ \tilde{s}(n,k) \frac{k}{n}

\scriptstyle \times [n - k\ \text{is even}]
\scriptstyle {C}_{n} \scriptstyle {C}_{n,k}^{\ast} {\ =}\ \tilde{s}(n,k) \frac{k}{n} \scriptstyle {C}_{n}^{\ast}
A053121 A000108 A189231 A057977
Motzkin \scriptstyle M_{n,k}^{\ }{\ =}\binom{n}{k}{C}_{k}^{\ast}

\scriptstyle \times \left[k\ \text{is even}\right]
\scriptstyle {M}_{n}^{\ } \scriptstyle M_{n,k}^{\ast}{\ =}\binom{n}{k}{C}_{k}^{\ast} \scriptstyle {M}_{n}^{\ast}
A097610 A001006 A189913 A189912
Schröder \scriptstyle {S}_{n,k}^{\ }{\ =} \binom{n+k}{n-k}{C}_{2k}^{\ast} \scriptstyle {S}_{n}^{\ } \scriptstyle {S}_{n,k}^{\ast}{\ =}\binom{n+k}{n-k}{C}_{k}^{\ast} \scriptstyle {S}_{n}^{\ast}
A088617 A006318 A190907 A190908
Central
Delannoy
\scriptstyle D_{n,k} = \binom{n+k}{n-k} (2k)\wr \scriptstyle {D}_{n}^{\ } \scriptstyle D_{n,k}^{\ast} = \binom{n+k}{n-k} k\wr \scriptstyle {D}_{n}^{\ast}
A063007 A001850 A190909 A190910

On the summary table there is a white spot near the upper right corner, a terra incognita. We will explore this unknown land next month on this blog.

References

  1. K. A. Penson and J.-M. Sixdeniers, Integral Representations of Catalan and Related Numbers. Journal of Integer Sequences, 4, 2001.
  2. Peter Luschny, Divide, swing and conquer the factorial and the lcm{1,2,..,n}, preprint April 2008, available from the author.
Personal tools