This site is supported by donations to The OEIS Foundation.
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:
|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|
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.
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 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.
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
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
by replacing the central binomial by the swinging factorial.
The complementary Catalan numbers
Let us look again at
As long as we have no idea what these `*´ could be it is not entirely inappropriate to fill zeros into these places.
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.
Consequently the complementary Catalan numbers are
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.
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),
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 
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 . 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.
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
|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(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:
|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 188.8.131.52 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).
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.
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
|A060693||Transposed Schröder triangle|
The generating function of the Schröder triangle:
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 := 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 := 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
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:
|A190907||Extended Schröder triangle|
|A190908||Extended Schröder numbers|
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.)
|A001850||Central Delannoy numbers|
|A190909||Extended Delannoy triangle|
|A190910||Extended central Delannoy numbers|
The relation between the Delannoy triangles and the Schroeder triangles is simple enough.
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);
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.