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:

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

 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.

 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 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 $\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}$
 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 $\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

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

 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:

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

 $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) ->
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) ->
seq(XDelannoyNumbers(n),n=0..7);


## Summary

 ClassicTriangle ClassicNumbers ExtendedTriangle ExtendedNumbers 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.