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

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.

Links

Michel Marcus, Rows n = 1..50 of triangle, flattened

Alan Edelman and Gilbert Strang, Pascal Matrices, Am. Math. Monthly 111 (2004) 189-197.

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

Example

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)

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

Prog

(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

Crossrefs

Cf. A000295, A005803, A135836.

Sequence in context: A234357 A145596 A186753 * A177696 A134574 A141617

Adjacent sequences: A135832 A135833 A135834 * A135836 A135837 A135838

Keyword

nonn,tabl

Author

John W. Layman, Nov 30 2007

Extensions

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

Status

approved