This site is supported by donations to The OEIS Foundation.
User:Peter Luschny/TheLostCatalanNumbers
From OeisWiki
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:
A000108  Catalan numbers 
A001700  Complementary Catalan numbers 
A057977  Extended Catalan numbers 
A126120  Aerated Catalan numbers 
A138364  Aerated complementary Catalan numbers 
A000984  Central binomial coefficients 
A001405  Middle binomial coefficients 
A056040  Swinging factorial 
A162246  Swinging 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.
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.
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.
n  0  1  2  3  4  5  
1  *  2  *  6  *  20  *  70  *  252  
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 for the function name, i.e. to write for the swinging factorial similar to the notation n! for the factorial function. Thus the definition is

The sequence of the swinging factorials can be characterized in many different ways. For instance a simple characterization is:
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, . 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
n  0  1  2  3  4  5  
1  *  1  *  2  *  5  *  14  *  42  
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

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

Like in the case of the swinging factorial many equivalent formulas for the extended Catalan numbers can be given. For instance we have
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?
The proof is simple: it reduces to 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.
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.

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

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

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 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.
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 denote the swinging triangle above and [.] the Iverson brackets then for n ≥ 1 and k ≥ 1

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 
A053121  Catalan triangle 
A189230  Complementary Catalan triangle 
A189231  Extended Catalan triangle 
The offset of all three triangles is (1,1). Thus
The triangles implemented with Maple:
SwingPoly := proc(n,k); if abs(k) > n then 0 elif n = k then 1 else SwingPoly(n1,k1) + modp(nk,2)*SwingPoly(n1,k) + SwingPoly(n1,k+1) fi end; CatalanTriangle := (n,k) > `if`(nk mod 2 = 1, 0, k*SwingPoly(n,k) / n): ComplementaryCatalanTriangle := (n,k) > `if`(nk mod 2 = 0, 0, k*SwingPoly(n,k) / n): ExtendedCatalanTriangle := (n,k) > k*SwingPoly(n,k) / n:
Ballot triangles
E_{p0}  1  
E_{p1}  0  1  
E_{p2}  1  0  1  
E_{p3}  0  2  0  3  
E_{p4}  1  0  2  0  2  
E_{p5}  0  3  0  8  0  10  
E_{p6}  1  0  3  0  5  0  5  
E_{p7}  0  4  0  15  0  30  0  35  
E_{p8}  1  0  4  0  9  0  14  0  14  
E_{p9}  0  5  0  24  0  63  0  112  0  126 
E_{pq}  E_{0q}  E_{1q}  E_{2q}  E_{3q}  E_{4q}  E_{5q}  E_{6q}  E_{7q}  E_{8q}  E_{9q} 
A009766  Classic ballot triangle (maroon) 
A238761  Complementary ballot triangle (green) 
A238762  Generalized 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: E_{00}=1, E_{pq}=0 if p<0 or p>q, and otherwise
E_{pq} = E_{(p2)q} + [q odd]E_{(p1)(q1)} + E_{p(q2)}.
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(p2,q) + BallotE(p,q2); if irem(q,2) = 1 then S := S + BallotE(p1,q1) 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:
S_{n} = 1 , 2, 6, 22, 90, 394, ...
S_{n} = 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.

Thus there are two kinds of little Schröder numbers, the even little Schröder numbers S^{e}_{n} and the odd little Schröder numbers S^{o}_{n}; the sequence S^{e} starts with 1 and the sequence S^{o} 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:
S^{e}_{6} = 1 + 140 + 630 + 132 = 903
S^{o}_{6} = 21 + 420 + 462 = 903
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 
A088617  Schröder triangle 
A060693  Transposed Schröder triangle 
The generating function of the Schröder triangle:

With Maple:
gf := (x,y) > (1ysqrt((1y)^24*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,nk)*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[w1]+2*add(a[j]*a[wj1], j=1..w1) 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[w1]+add(a[j]*a[wj1], j=1..w1) 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 A_{0} = 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 SuperSchrö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:

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 
A190907  Extended Schröder triangle 
A190908  Extended Schröder numbers 
With Maple:
ExtendedSchroederTriangle := (n,k) > binomial(n+k,nk)*(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.)

A063007  Delannoy triangle 
A001850  Central Delannoy numbers 
A190909  Extended Delannoy triangle 
A190910  Extended central Delannoy numbers 
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.

With Maple:
DelannoyTriangle := (n,k) > binomial(n+k,nk)*(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,nk)*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 

A008459  A000984  A056040  
Catalan  
A053121  A000108  A189231  A057977  
Motzkin  

A097610  A001006  A189913  A189912  
Schröder  
A088617  A006318  A190907  A190908  
Central Delannoy 

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.