A097710 Lower triangular matrix T, read by rows, such that row (n) is formed from the sums of adjacent terms in row (n-1) of the matrix square T^2, with T(0,0)=1.

1, 1, 1, 2, 3, 1, 7, 13, 7, 1, 41, 88, 61, 15, 1, 397, 951, 781, 257, 31, 1, 6377, 16691, 15566, 6231, 1041, 63, 1, 171886, 484490, 500057, 231721, 48303, 4161, 127, 1, 7892642, 23701698, 26604323, 13843968, 3406505, 374127, 16577, 255, 1

Offset

0,4

Comments

Column 0 is equal to sequence A008934, which is the number of tournament sequences.

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

Links

Paul D. Hanna, Table of n, a(n) for n = 0..495, of rows 0..30 of triangle in flattened form.

Formula

T(n, k) = T^2(n-1, k-1) + T^2(n-1, k) for n>=1 and k>1, with T(n, 1) = T^2(n-1, 1) and T(n,n) = 1 for n>=0, where T^2 is the matrix square of this triangle T.

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

T(n, 0) = A008934(n).

T(n, 1) = A097711(n).

Sum_{k=0..n} T(n, k) = A093657(n+1) (row sums).

From G. C. Greubel, Feb 21 2024: (Start)

T(n, n-1) = A000225(n).

Sum_{k=0..n} (-1)^k*T(n, k) = A000007(n). (End)

Example

Rows of this triangle T begin:
       1;
       1,      1;
       2,      3,      1;
       7,     13,      7,      1;
      41,     88,     61,     15,     1;
     397,    951,    781,    257,    31,    1;
    6377,  16691,  15566,   6231,  1041,   63,   1;
  171886, 484490, 500057, 231721, 48303, 4161, 127, 1;
Rows of T^2 begin:
        1;
        2,        1;
        7,        6,        1;
       41,       47,       14,       1;
      397,      554,      227,      30,      1;
     6377,    10314,     5252,     979,     62,     1;
   171886,   312604,   187453,   44268,   4035,   126,   1;
  7892642, 15809056, 10795267, 3048701, 357804, 16323, 254, 1;
The sums of adjacent terms in row (n) of T^2 forms row (n+1) of T:
  T(5,0) = T^2(4,0) = 397;
  T(5,1) = T^2(4,0) + T^2(4,1) = 397 + 554 = 951;
  T(5,2) = T^2(4,1) + T^2(4,2) = 554 + 227 = 781.
Rows of matrix inverse T^(-1) begins:
   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; ...
which is a signed version of A097712.

Mathematica

T[n_, k_] := T[n, k] = Which[n<0 || k>n, 0, n == k, 1, k == 0, Sum[T[n-1, j]*T[j, 0], {j, 0, n-1}], True, Sum[T[n-1, j]*T[j, k-1], {j, 0, n-1}] + Sum[T[n-1, j]*T[j, k], {j, 0, n-1}]]; Table[T[n, k], {n, 0, 8}, {k, 0, n}] // Flatten (* Jean-François Alcover, Nov 23 2016, adapted from PARI *)

Prog

(PARI) /* Using Recurrence relation: */
{T(n, k) = if(n<0||k>n, 0, if(n==k, 1, if(k==0, sum(j=0, n-1, T(n-1, j)*T(j, 0)),  sum(j=0, n-1, T(n-1, j)*T(j, k-1)) + sum(j=0, n-1, T(n-1, j)*T(j, k)); )))}
for(n=0, 8, for(k=0, n, print1(T(n, k), ", ")); print(""))
(PARI) /* Faster: using Matrix generating method: */
{T(n, k) = my(M=matrix(2, 2, r, c, if(r>=c, 1))); for(i=1, n,
N=matrix(#M+1, #M+1, r, c, if(r>=c, if(r<=#M, M[r, c], if(c>1, (M^2)[r-1, c-1]) + if(c<=#M, (M^2)[r-1, c])) ));
M=N; ); M[n+1, k+1]}
for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print("")) \\ Paul D. Hanna, Nov 27 2016
(SageMath)
@CachedFunction
def T(n, k): # T = A097710
    if n< 0 or k<0 or k>n: return 0
    elif k==n: return 1
    elif k==0: return sum(T(n-1, j)*T(j, 0) for j in range(n))
    else: return sum(T(n-1, j)*(T(j, k-1)+T(j, k)) for j in range(n))
flatten([[T(n, k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Feb 21 2024

Crossrefs

Cf. A000007, A000225, A093654, A097712.

Cf. A008934 (column k=0), A093657 (row sums), A097711 (column k=1).

Sequence in context: A103364 A104027 A192363 * A171024 A109198 A081320

Adjacent sequences: A097707 A097708 A097709 * A097711 A097712 A097713

Keyword

nonn,tabl

Author

Paul D. Hanna, Aug 22 2004

Status

approved