A116925 Triangle read by rows: row n (n >= 0) consists of the elements g(i, n-i) (0 <= i <= n), where g(r,s) = 1 + Sum_{k=1..r} Product_{i=0..k-1} binomial(r+s-1, s+i) / binomial(r+s-1, i).

1, 1, 2, 1, 2, 3, 1, 2, 4, 4, 1, 2, 5, 8, 5, 1, 2, 6, 14, 16, 6, 1, 2, 7, 22, 42, 32, 7, 1, 2, 8, 32, 92, 132, 64, 8, 1, 2, 9, 44, 177, 422, 429, 128, 9, 1, 2, 10, 58, 310, 1122, 2074, 1430, 256, 10, 1, 2, 11, 74, 506, 2606, 7898, 10754, 4862, 512, 11, 1, 2, 12, 92, 782, 5462, 25202, 60398, 58202, 16796, 1024, 12

Offset: 0

Author

Gary W. Adamson, Feb 26 2006

Keywords

• nonn
• tabl
• nice

Comments

A generalized Catalan number triangle.

An alternative construction of this triangle. Begin with the Pascal triangle array, written as:

1 1 1 1 1 1 ...

1 2 3 4 5 6 ...

1 3 6 10 15 21 ...

1 4 10 20 35 56 ...

1 5 15 35 70 126 ...

...

For each row r (r >= 0) in the above array, construct a triangle U(r) by applying the operation H defined below.

Then the r-th diagonal from the right in the new triangle is given by the row sums of U(r).

To define H, let us use row r=2, {1 3 6 10 15 ...}, as an illustration.

To get the 4th entry, take the first 4 terms of the row, reverse them and write them under the first 4 terms:

A: 1 3 6 10

B: 10 6 3 1

and form a new row C by beginning with 1 and iterating the map C' = C*B/A until we reach 1:

C: 1 10 20 10 1

E.g., 20 = (6 *10) / 3.

The sum of the terms {1 10 20 10 1} is 42, which is the 4th entry in the r=2 diagonal of the new triangle.

The full triangle U(2) begins

1

1 1

1 3 1

1 6 6 1

1 10 20 10 1

...

(this is the Narayana triangle A001263)

and the row sums are the Catalan numbers, which give our r=2 diagonal.

Examples

			The first few rows of the triangle are:
  1
  1 2
  1 2  3
  1 2  4  4
  1 2  5  8   5
  1 2  6 14  16    6
  1 2  7 22  42   32    7
  1 2  8 32  92  132   64    8
  1 2  9 44 177  422  429  128   9
  1 2 10 58 310 1122 2074 1430 256 10
  ...
		

Links

• N. J. A. Sloane, First 30 rows, flattened

Crossrefs

Diagonals of the triangle are generalized Catalan numbers. The first few diagonals (from the right) are A000027, A000079, A000108, A001181, A005362, A005363, ... The intermediate triangles include Pascal's triangle A007318, the Narayana triangle A001263, ...

Row sums give A104253.

Programs

Maple

g:=proc(n,p) local k,i; 1 + add( mul( binomial(n+p-1,p+i) / binomial(n+p-1,i), i=0..k-1 ), k=1..n); end; (N. J. A. Sloane, based on the formula from Hsueh-Hsing Hung)
f:=proc(n,r) local k,b,i; b:=binomial; add( mul( b(n+r-2,k-1+i),i=0..r-1)/ mul( b(n+r-2,i),i=1..r-1),k=1..n); end; M:=30; for j from 0 to M do lprint(seq(f(i,j+1-i),i=1..j+1)); od; # N. J. A. Sloane

Mathematica

rows = 11; t[n_, p_] := 1 + Sum[Product[ Binomial[ n+p-1, p+i] / Binomial[ n+p-1, i], {i, 0, k-1}], {k, 1, n}]; Flatten[ Table[ t[p, n-p], {n, 0, rows}, {p, 0, n}]](* Jean-François Alcover, Nov 18 2011, after Maple *)

Formula

Comment from N. J. A. Sloane, Sep 07 2006: (Start)

The n-th entry in the r-th diagonal from the right (r >= 0, n >= 1) is given by the quotient:

Sum_{k=1..n} Product_{i=0..r-1} binomial(n+r-2, k-1+i)

------------------------------------------------------

Product_{i=1..r-1} binomial(n+r-2, i)

(End)

Extensions

One entry corrected by Hsueh-Hsing Hung (hhh(AT)mail.nhcue.edu.tw), Sep 06 2006

Edited and extended by N. J. A. Sloane, Sep 07 2006

Simpler formula provided by Hsueh-Hsing Hung (hhh(AT)mail.nhcue.edu.tw), Sep 08 2006, which is now taken as the definition of this triangle

Edited by Jon E. Schoenfield, Dec 12 2015