A093657 -id:A093657 - cp's OEIS frontend

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

Paul D. Hanna, Aug 22 2004

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.

			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.

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

Cf. A000007, A000225, A093654, A097712.

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

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

/* 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(""))

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

@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

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)

A093654 Lower triangular matrix, read by rows, defined as the convergent of the concatenation of matrices using the iteration: M(n+1) = [[M(n),0*M(n)],[M(n)^2,M(n)^2]], with M(0) = [1].

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 2, 1, 2, 1, 1, 0, 0, 0, 1, 2, 1, 0, 0, 2, 1, 2, 0, 1, 0, 2, 0, 1, 7, 2, 4, 1, 7, 2, 4, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 0, 0, 0, 0, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 2, 0, 1, 7, 2, 4, 1, 0, 0, 0, 0, 7, 2, 4, 1, 2, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 1, 7, 2, 0, 0, 4, 1, 0, 0, 7, 2, 0, 0, 4, 1

Offset: 1

Paul D. Hanna, Apr 08 2004

Related to the number of tournament sequences (A008934). First column forms A093655, where A093655(2^n) = A008934(n) for n>=0. Row sums form A093656, where A093656(2^(n-1)) = A093657(n) for n>=1.

			Let M(n) be the lower triangular matrix formed from the first 2^n rows.
To generate M(3) from M(2), take the matrix square of M(2):
[1,0,0,0]^2=[1,0,0,0]
[1,1,0,0]...[2,1,0,0]
[1,0,1,0]...[2,0,1,0]
[2,1,2,1]...[7,2,4,1]
and append M(2)^2 to the bottom left and bottom right of M(2):
[1],
[1,1],
[1,0,1],
[2,1,2,1],
.........
[1,0,0,0],[1],
[2,1,0,0],[2,1],
[2,0,1,0],[2,0,1],
[7,2,4,1],[7,2,4,1].
Repeating this process converges to triangle A093654.

Cf. A008934, A093655, A093656, A093657, A093658.

First column: T(2^n, 1) = A008934(n) for n>=0.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI