A135835 Lower triangular matrix T with first column and diagonal (1,2,3,4,...,n,...) and otherwise satisfying T(i,j) = Sum_{k=1..j} T(i-j+1,k)*T(j,k), read by rows.

1, 2, 2, 3, 8, 3, 4, 22, 22, 4, 5, 52, 82, 52, 5, 6, 114, 254, 254, 114, 6, 7, 240, 677, 1000, 677, 240, 7, 8, 494, 1692, 3176, 3176, 1692, 494, 8, 9, 1004, 3972, 9136, 12182, 9136, 3972, 1004, 9, 10, 2026, 9052, 24202, 40564, 40564, 24202, 9052, 2026, 10, 11, 4072, 19975, 60828, 123414, 155096, 123414, 60828, 19975, 4072, 11

Offset: 1

Author

John W. Layman, Nov 30 2007

Keywords

• nonn
• tabl

Comments

The definition is equivalent to requiring that L'=L*Transpose(L), where L' is formed from L by shifting column j upward j-1 rows for all j. If the first column is (1,1,1,1,...,1,...} then the lower triangular matrix contains Pascal's triangle. Column two and one-half of column two are essentially A005803 (second-order Eulerian numbers 2^n - 2*n) and A000295 (Eulerian numbers 2^n - n - 1), respectively. Column three is A135836.

Examples

			From _Philippe Deléham_, Oct 10 2011: (Start)
Triangle begins:
  1;
  2,   2;
  3,   8,   3;
  4,  22,  22,   4;
  5,  52,  82,  52,   5;
  6, 114, 254, 254, 114,   6;
  ...
(End)
		

Links

• Michel Marcus, Rows n = 1..50 of triangle, flattened
• Alan Edelman and Gilbert Strang, Pascal Matrices, Am. Math. Monthly 111 (2004) 189-197.

Crossrefs

Cf. A000295, A005803, A135836.

Programs

Mathematica

T[n_, k_]:= T[n, k]= If[k<1 || k>n, 0, If[k==1 || k==n, n, Sum[T[n-k+1, j]*T[k, j], {j, k}]]];
Table[T[n, k], {n,12}, {k,n}]//Flatten (* G. C. Greubel, Feb 07 2022 *)

PARI

T(i,j) = if (j>i, 0, if ((j==1) || (i==j), i, sum(k=1, j, T(i-j+1,k)*T(j,k))));
tabl(nn) = for (n=1, nn, for (k=1, n, print1(T(n, k), ", ")); print()); \\ Michel Marcus, Sep 30 2017

Sage

@CachedFunction
def T(n,k): # A135835
    if (k<0 or k>n): return 0
    elif (k==1 or k==n): return n
    else: return sum( T(n-k+1,j)*T(k,j) for j in (1..k) )
flatten([[T(n,k) for k in (1..n)] for n in (1..12)])  # G. C. Greubel, Feb 07 2022

Formula

T(n, 1) = T(n, n) = n, otherwise T(n,k) = Sum_{j=1..k} T(n-k+1, j)*T(k, j).

T(n, n-k) = T(n, k).

T(n, 2) = A005803(n+1) = 2*A000295(n).

T(n, 3) = A135836(n-2).

Extensions

Name and formula corrected, and more terms from Michel Marcus, Sep 30 2017