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,3

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.

Links

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

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)

Example

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

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 *)

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.

Sequence in context: A145111 A104795 A347570 * A309010 A308500 A210950

Adjacent sequences: A116922 A116923 A116924 * A116926 A116927 A116928

Keyword

nonn,tabl,nice

Author

Gary W. Adamson, Feb 26 2006

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

Status

approved