This site is supported by donations to The OEIS Foundation.

User:Peter Luschny/SeidelTriangles

From OeisWiki

Jump to: navigation, search

The Catalan-Seidel connection

Some entries related to the Seidel transform and its variants

... which we discussed in the last two blog posts Seidel Transform, BernoulliNumbers and will discuss in this post. We assume that the reader is familiar with the discussion in Seidel Transform.

A000108 A000111 A000182 A000245 A000364 A000367 A000657
A000660 A000667 A000734 A000737 A000795 A001003 A002084
A002445 A005439 A006318 A006319 A008280 A008313 A009747
A014781 A035011 A039598 A039599 A062161 A062162 A062272
A086616 A090192 A099363 A099960 A110501 A112554 A126120
A165621 A181131 A212196

Contents

The Catalan triangle

Consider the classical Catalan triangle A053121. The zeros in the triangle can be filled with the complementary Catalan numbers A189230 to give the extended Catalan triangle A189231. For now we will just ignore the zeros and show the Seidel way of computing this compacted form, which is A008313.

def SeidelCatalanTriangle(n) :
    D = [0]*((n+5)//2); D[1] = 1
    b = True; h = 1 
    for i in range(n) :
        if b : 
            for k in range(h,0,-1) : D[k] += D[k-1] 
            h += 1
        else : 
            for k in range(1,h, 1) : D[k] += D[k+1]
        b = not b
        print [D[z] for z in (1..h-1)] 
SeidelCatalanTriangle(13)

[1]
[1]
[1, 1]
[2, 1]
[2, 3, 1]
[5, 4, 1]
[5, 9, 5, 1]
[14, 14, 6, 1]
[14, 28, 20, 7, 1]
[42, 48, 27, 8, 1]
[42, 90, 75, 35, 9, 1]
[132, 165, 110, 44, 10, 1]
[132, 297, 275, 154, 54, 11, 1]

Same with Maple:

SeidelCatalanTriangle := proc(n) local d,b,i,h,k:
    d := array(0..iquo(n+4,2)); 
    d[0] := 0; d[1] := 1; 
    b := true;
    for i from 0 to n do
        h := iquo(i+4,2);
        d[h] := 0;
        if b then
            for k from h-1 by -1 to 1 do d[k] := d[k] + d[k-1] od;
        else 
            for k from 1 to h-1 do  d[k] := d[k] + d[k+1] od;
        fi;
        b := not b;
        print([i],seq(d[k], k= 1..h-1));
od end: 

Catalan numbers (A000108)

By simply applying a filter to the Catalan triangle function the Catalan numbers will be generated in Seidel's algorithmic way.

def A000108_list(n) :
    D = [0]*(n+1); D[1] = 1
    b = True; h = 1; R = []
    for i in range(2*n-1) :
        if b :
            for k in range(h, 0, -1) : D[k] += D[k-1]
            h += 1; R.append(D[1])
        else :
            for k in range(1, h, 1) : D[k] += D[k+1]
        b = not b
    return R

The charm of this algorithm is that no division and no multiplication is needed.

First differences of Catalan numbers (A000245)

def A000245_list(n) :
    D = [0]*(n+1); D[1] = 1
    b = False; h = 1; R = [] 
    for i in range(2*n-1) :
        if b : 
            for k in range(h,0,-1) : D[k] += D[k-1] 
            h += 1; R.append(D[2])
        else : 
            for k in range(1,h, 1) : D[k] += D[k+1] 
        b = not b
    return R

q-Catalan numbers for q = -1 (A090192)

def A090192_list(n) :
    D = [0]*(n+2); D[1] = 1
    b = True; h = 1; R = []
    for i in range(2*n-1) :
        if b :
            for k in range(h, 0, -1) : D[k] -= D[k-1]
            h += 1; R.append(D[1])
        else :
            for k in range(1, h, 1) : D[k] += D[k+1]
        b = not b
    return R

Aerated Catalan numbers. (A126120)

Also integral(x=-2..2, x^n*sqrt((2-x)*(2+x)))/(2*Pi).

def A126120_list(n) :
    D = [0]*(n+2); D[1] = 1
    b = True; h = 2; R = []
    for i in range(2*n-1) :
        if b :
            for k in range(h, 0, -1) : D[k] -= D[k-1]
            h += 1; R.append(abs(D[1]))
        else :
            for k in range(1, h, 1) : D[k] += D[k+1]
        b = not b
    return R

An inverse Chebyshev transform of 1-x (A099363)

def A099363_list(n) :
    D = [0]*(n+2); D[1] = 1
    b = True; h = 2; R = []
    for i in range(2*n-1) :
        if b :
            for k in range(h, 0, -1) : D[k] -= D[k-1]
            h += 1; R.append((-1)^(h//2)*D[2])
        else :
            for k in range(1, h, 1) : D[k] += D[k+1]
        b = not b
    return R

Little Schröder numbers (A001003)

As I remarked in Schröder Numbers there are two kinds of little Schröder numbers, the even little Schröder numbers and the odd little Schröder numbers counting different combinatorial objects, for example
Seven(6) = 1 + 140 + 630 + 132 = 903
Sodd(6) = 21 + 420 + 462 = 903
Here we count the even little Schröder numbers which start with 1 (see the link for more on this).

def A001003_list(n) :
    D = [0]*(n+1); D[1] = 1/2
    b = True; h = 2; R = [1] 
    for i in range(2*n-2) :
        if b : 
            for k in range(h,0,-1) : D[k] += D[k-1] 
            h += 1;  
        else : 
            for k in range(1,h, 1) : D[k] += D[k-1]
            R.append(D[h-1]); 
        b = not b
    return R

Large Schröder numbers (A006318)

Almost identical is the computation of the large Schröder numbers.

def A006318_list(n) :
    D = [0]*(n+1); D[1] = 1
    b = True; h = 1; R = [] 
    for i in range(2*n) :
        if b : 
            for k in range(h,0,-1) : D[k] += D[k-1] 
            h += 1; 
        else : 
            for k in range(1,h, 1) : D[k] += D[k-1]
            R.append(D[h-1]); 
        b = not b
    return R

Royal paths in a lattice (convolution of large Schröder numbers) (A006319).

def A006319_list(n) :
    D = [0]*(n+1); D[1] = 1
    b = True; h = 2; R = [1]
    for i in range(2*n-2) :
        if b :
            for k in range(h, 0, -1) : D[k] += D[k-1]
            h += 1;
        else :
            for k in range(1, h, 1) : D[k] += D[k-1]
            R.append(D[h-2]);
        b = not b
    return R

Partial sums of the large Schröder numbers (A086616)

def A086616_list(n) :
    D = [0]*(n+2); D[1] = 1
    b = True; h = 2; R = []
    for i in range(2*n) :
        if b :
            for k in range(h, 0, -1) : D[k] += D[k-1]
        else :
            for k in range(1, h, 1) : D[k] += D[k-1]
            R.append(D[h-1]); h += 1;
        b = not b
    return R

Large Schröder numbers minus 1 (A035011)

def A035011_list(n) :
    D = [0]*(n+2); D[1] = 1
    b = True; h = 2; R = []
    for i in range(2*n) :
        if b :
            for k in range(h, 0, -1) : D[k] += D[k-1]
        else :
            for k in range(1, h, 1) : D[k] += D[k-1]
            R.append(D[h-2]); h += 1;
        b = not b
    return R

Powers of x in terms of Chebyshev's U-polynomials (A039598, A039599)

Because of the importance of the Catalan numbers we indicate also two popular variants which can be derived from the above function. Looking only at the even case one gets A039599, a triangle formed from even-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials Un(x).

def A039599_triangle(n) :
    D = [0]*(n+2); D[1] = 1
    b = True; h = 1
    for i in range(2*n-1) : 
        if b : 
            for k in range(h,0,-1) : D[k] += D[k-1] 
            h += 1
        else : 
            for k in range(1,h, 1) : D[k] += D[k+1]
        if b : print [D[z] for z in (1..h-1)] 
        b = not b       
         
A039599_triangle(10)
[1]
[1, 1]
[2, 3, 1]
[5, 9, 5, 1]
[14, 28, 20, 7, 1]
[42, 90, 75, 35, 9, 1]
[132, 297, 275, 154, 54, 11, 1]
[429, 1001, 1001, 637, 273, 77, 13, 1]
[1430, 3432, 3640, 2548, 1260, 440, 104, 15, 1]
[4862, 11934, 13260, 9996, 5508, 2244, 663, 135, 17, 1]

Looking only at the odd case one gets A039598, a triangle formed from odd-numbered columns of triangle of expansions of powers of x in terms of Chebyshev polynomials Un(x).

def A039598_triangle(n) :
    D = [0]*(n+2); D[1] = 1
    b = True; h = 1 
    for i in range(2*n) :
        if b : 
            for k in range(h,0,-1) : D[k] += D[k-1] 
            h += 1
        else : 
            for k in range(1,h, 1) : D[k] += D[k+1]
        b = not b        
        if b : print [D[z] for z in (1..h-1)] 

A039598_triangle(10)
[1]
[2, 1]
[5, 4, 1]
[14, 14, 6, 1]
[42, 48, 27, 8, 1]
[132, 165, 110, 44, 10, 1]
[429, 572, 429, 208, 65, 12, 1]
[1430, 2002, 1638, 910, 350, 90, 14, 1]
[4862, 7072, 6188, 3808, 1700, 544, 119, 16, 1]
[16796, 25194, 23256, 15504, 7752, 2907, 798, 152, 18, 1]

Two Riordan arrays of Paul Barry (A165621, A112554)

We give a closely related signed version of Paul Barry's A165621, Riordan array (c(x^2)*(1+xc(x^2)), xc(x^2)).

def Signed_A165621_triangle(n) :
    D = [0]*(n+4); D[1] = 1
    b = False; h = 3
    for i in range(2*n) : 
        if b : 
            for k in range(h,0,-1) : D[k] += D[k-1] 
            h += 1
        else : 
            for k in range(1,h, 1) : D[k] -= D[k+1]
        if b : print [D[z] for z in (2..h-2)] 
        b = not b
	
Signed_A165621_triangle(11) 
[1]
[1, 1]
[-1, 1, 1]
[-2, -2, 1, 1]
[2, -3, -3, 1, 1]
[5, 5, -4, -4, 1, 1]
[-5, 9, 9, -5, -5, 1, 1]
[-14, -14, 14, 14, -6, -6, 1, 1]
[14, -28, -28, 20, 20, -7, -7, 1, 1]
[42, 42, -48, -48, 27, 27, -8, -8, 1, 1]
[-42, 90, 90, -75, -75, 35, 35, -9, -9, 1, 1]

If one compares this procedure with Barry's formula the powerful simplicity of Seidel's approach impresses again.

T(n,k) = sum{j = 0..n, b(n - j)*sum{i = 0..k, (-1)^(k - i)*
         C(k, i)*sum{m = 0..i, C(i, m)*(C(i - m, m + k) 
         - C(i - m,i + k + 2))}}}<br />
where b(n) is the sequence beginning with 1 followed by the 
aerated Catalan numbers: 1,1,0,1,0,2,0,5,0,14,...

Similarly Barry's triangle A112554, Riordan array (c(x^2)^2, xc(x^2)), c(x) the g. f. of the Catalan numbers A000108, can be computed as follows.

def Signed_A112554_triangle(n) :
    D = [0]*(n+4); D[1] = 1
    b = False; h = 2
    for i in range(2*n+2) :
        if b : 
            for k in range(h,0,-1) : D[k] += D[k-1] 
            h += 1
        else : 
            for k in range(1,h, 1) : D[k] -= D[k+1]
        b = not b
        if b and i > 0 : print [D[z] for z in (2..h-1)] 
            
Signed_A112554_triangle(13)  
[1]
[0, 1]
[-2, 0, 1]
[0, -3, 0, 1]
[5, 0, -4, 0, 1]
[0, 9, 0, -5, 0, 1]
[-14, 0, 14, 0, -6, 0, 1]
[0, -28, 0, 20, 0, -7, 0, 1]
[42, 0, -48, 0, 27, 0, -8, 0, 1]
[0, 90, 0, -75, 0, 35, 0, -9, 0, 1]
[-132, 0, 165, 0, -110, 0, 44, 0, -10, 0, 1]
[0, -297, 0, 275, 0, -154, 0, 54, 0, -11, 0, 1]
[429, 0, -572, 0, 429, 0, -208, 0, 65, 0, -12, 0, 1]
Personal tools