User:Peter Luschny/TheLostCatalanNumbers

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.

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

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

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

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

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₀₀=1, E_pq=0 if p<0 or p>q, and otherwise

E_pq = E_(p-2)q + [q odd]E_(p-1)(q-1) + E_p(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:

     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.

$\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 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₆ = 1 + 140 + 630 + 132 = 903
S^o₆ = 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

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 
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 A₀ = 1

$\scriptstyle {\text{A Super Schroeder Recurrence}}$ $A_{n}\ =aA_{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

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

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