login
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.
12
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.
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. A008934 (column k=0), A093657 (row sums), A097711 (column k=1).
Sequence in context: A103364 A104027 A192363 * A171024 A109198 A081320
KEYWORD
nonn,tabl
AUTHOR
Paul D. Hanna, Aug 22 2004
STATUS
approved