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

Author

Paul D. Hanna, Aug 24 2004

Keywords

• nonn
• tabl

Comments

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

Examples

			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.
		

Links

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

Crossrefs

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

Programs

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

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

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