A097712 Lower triangular matrix T, read by rows, such that T(n,0) = 1 and T(n,k) = T(n-1,k) + T^2(n-1,k-1) for k>0, where T^2 is the matrix square of T.

1, 1, 1, 1, 3, 1, 1, 8, 7, 1, 1, 25, 44, 15, 1, 1, 111, 346, 208, 31, 1, 1, 809, 4045, 3720, 912, 63, 1, 1, 10360, 77351, 99776, 35136, 3840, 127, 1, 1, 236952, 2535715, 4341249, 2032888, 308976, 15808, 255, 1, 1, 9708797, 145895764, 319822055, 189724354, 37329584, 2608864, 64256, 511, 1

Offset

0,5

Comments

This triangle has the same row sums and first column terms as in rows 2^n, for n>=0, of triangle A093662.

Links

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Formula

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

T(n, 1) = A097713(n-1), n >= 1.

Sum_{k=0..n} T(n, k) = A016121(n) (row sums).

Example

T(5,1) = T(4,1) + T^2(4,0) = 25 + 86 = 111.
T(5,2) = T(4,2) + T^2(4,1) = 44 + 302 = 346.
T(5,3) = T(4,3) + T^2(4,2) = 15 + 193 = 208.
Rows of T begin:
  1;
  1,      1;
  1,      3,       1;
  1,      8,       7,       1;
  1,     25,      44,      15,       1;
  1,    111,     346,     208,      31,      1;
  1,    809,    4045,    3720,     912,     63,     1;
  1,  10360,   77351,   99776,   35136,   3840,   127,   1;
  1, 236952, 2535715, 4341249, 2032888, 308976, 15808, 255, 1;
Rows of T^2 begin:
       1;
       2,       1;
       5,       6,       1;
      17,      37,      14,       1;
      86,     302,     193,      30,      1;
     698,    3699,    3512,     881,     62,     1;
    9551,   73306,   96056,   34224,   3777,   126,   1;
  226592, 2458364, 4241473, 1997752, 305136, 15681, 254, 1;
Column 0 of T^2 forms A016121.
Row sums of T^2 form the first differences of A016121.

Mathematica

T[n_, k_] := T[n, k] = If[n < 0 || k > n, 0, If[n == k, 1, If[k == 0, 1, T[n - 1, k] + Sum[T[n - 1, j] T[j, k - 1], {j, 0, n - 1}]]]];
Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Oct 02 2019 *)

Prog

(PARI) T(n, k)=if(n<0 || k>n, 0, if(n==k, 1, if(k==0, 1, T(n-1, k)+sum(j=0, n-1, T(n-1, j)*T(j, k-1)); )))
(SageMath)
@CachedFunction
def T(n, k): # T = A097712
    if k<0 or k>n: return 0
    elif k==0 or k==n: return 1
    else: return T(n-1, k) + sum(T(n-1, j)*T(j, k-1) for j in range(n))
flatten([[T(n, k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Feb 20 2024

Crossrefs

Cf. A016121 (row sums), A093662, A097710, A097713.

Sequence in context: A263859 A124469 A094816 * A238688 A174117 A157210

Adjacent sequences: A097709 A097710 A097711 * A097713 A097714 A097715

Keyword

nonn,tabl

Author

Paul D. Hanna, Aug 24 2004

Status

approved