A141760 Triangle T, read by rows, where the g.f. of column k in matrix power T^m is given by: 1/(1-x)^m = Sum_{n>=k} [T^m](n,k) * x^(n-k)/(1+x)^{n(n-1)/2 - k(k-1)/2} for k>=0.

1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 6, 6, 3, 1, 1, 26, 26, 13, 4, 1, 1, 154, 154, 77, 23, 5, 1, 1, 1188, 1188, 594, 175, 36, 6, 1, 1, 11474, 11474, 5737, 1678, 336, 52, 7, 1, 1, 134432, 134432, 67216, 19579, 3863, 576, 71, 8, 1, 1, 1863168, 1863168, 931584, 270683, 52944, 7731

Offset

0,7

Links

Table of n, a(n) for n=0..60.

Formula

Matrix powers satisfy: T^m = P(i)^-1 * P(m+i) for all m and i, where P(m) is given by:

[P(m)](n,k) = [x^(n-k)] 1/(1-x)^m * (1+x)^{n(n-1)/2 - k(k-1)/2} for n>=k>=0.

Let U = unsigned matrix inverse (T^-1) with leftmost column dropped, then U = A107876 where [U^k](n,k) = U(n,k-1) for n>=k>0.

G.f. for column k of T: 1/(1-x) = Sum_{n>=0} T(n,k)*x^(n-k)/(1+x)^{n(n-1)/2 - k(k-1)/2}.

T(n,k) = 1 - Sum_{j=k..n-1} T(j,k)*(-1)^(n-j)*C(j(j-1)/2 - k(k-1)/2 + n-j-1, n-j) for n>k with T(k,k)=1 for k>=0.

G.f. for column k of matrix power T^m:

1/(1-x)^m = Sum_{n>=0} [T^m](n,k)*x^(n-k)/(1+x)^{n*(n-1)/2 - k*(k-1)/2}.

[T^m](n,k) = C(m+n-1,n) - Sum_{j=k..n-1} [T^m](j,k)*(-1)^(n-j)*C(j(j-1)/2 - k(k-1)/2 + n-j-1,n-j) for n>k with [T^m](k,k)=1 for k>=0.

Example

Triangle T begins:
1;
1, 1;
1, 1, 1;
2, 2, 1, 1;
6, 6, 3, 1, 1;
26, 26, 13, 4, 1, 1;
154, 154, 77, 23, 5, 1, 1;
1188, 1188, 594, 175, 36, 6, 1, 1;
11474, 11474, 5737, 1678, 336, 52, 7, 1, 1;
134432, 134432, 67216, 19579, 3863, 576, 71, 8, 1, 1;
1863168, 1863168, 931584, 270683, 52944, 7731, 911, 93, 9, 1, 1; ...
Matrix square, T^2, begins:
1;
2, 1;
3, 2, 1;
7, 5, 2, 1;
23, 17, 7, 2, 1;
105, 79, 33, 9, 2, 1;
641, 487, 205, 55, 11, 2, 1;
5034, 3846, 1626, 433, 83, 13, 2, 1; ...
where g.f. for column k of matrix square T^2 is:
1/(1-x)^2 = Sum_{n>=0} [T^2](n,k)*x^(n-k)/(1+x)^{n(n-1)/2 - k(k-1)/2}.
Matrix inverse, T^-1, begins:
1;
-1, 1;
0, -1, 1;
0, -1, -1, 1;
0, -2, -2, -1, 1;
0, -7, -7, -3, -1, 1;
0, -37, -37, -15, -4, -1, 1;
0, -268, -268, -106, -26, -5, -1, 1; ...
Let U = unsigned T^-1 with leftmost column dropped,
then U = A107876 where [U^k](n,k) = U(n,k-1) for n>=k>0.
The g.f. for column k of matrix inverse T^-1 is:
1-x = Sum_{n>=0} [T^-1](n,k) * x^(n-k)/(1+x)^{n(n-1)/2 - k(k-1)/2}.
MATRIX PRODUCTS:
T = P(1)^-1 * P(2) = P(2)^-1 * P(3) = P(m)^-1 * P(m+1);
P(1) begins:
1;
1, 1;
2, 2, 1;
8, 7, 3, 1;
57, 42, 16, 4, 1;
638, 386, 130, 29, 5, 1;
9949, 4944, 1471, 299, 46, 6, 1; ...
where [P(1)](n,k) = [x^(n-k)] 1/(1-x)*(1+x)^{n(n-1)/2-k(k-1)/2};
P(2) begins:
1;
2, 1;
5, 3, 1;
20, 12, 4, 1;
129, 72, 23, 5, 1;
1268, 630, 187, 38, 6, 1;
17548, 7599, 2063, 392, 57, 7, 1; ...
where [P(2)](n,k) = [x^(n-k)] 1/(1-x)^2*(1+x)^{n(n-1)/2-k(k-1)/2};
P(3) begins:
1;
3, 1;
9, 4, 1;
38, 18, 5, 1;
240, 111, 31, 6, 1;
2223, 955, 256, 48, 7, 1;
28672, 11124, 2794, 500, 69, 8, 1; ...
where [P(3)](n,k) = [x^(n-k)] 1/(1-x)^3*(1+x)^{n(n-1)/2-k(k-1)/2}.

Mathematica

T[n_, k_, m_] := T[n, k, m] = If[n<k || k<0, 0, If[n == k, 1, Binomial[m+n- 1, n] - Sum[T[j, k, m]*(-1)^(n-j)*Binomial[j*(j-1)/2 - k*(k-1)/2 + n-j-1, n-j], {j, k, n-1}]]]; Table[T[n, k, 1], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 19 2016, adapted from PARI *)

Prog

(PARI) T(n, k, m=1)=if(n<k || k<0, 0, if(n==k, 1, binomial(m+n-1, n) - sum(j=k, n-1, T(j, k, m)*(-1)^(n-j)*binomial(j*(j-1)/2-k*(k-1)/2+n-j-1, n-j))))

Crossrefs

Cf. columns: A141761, A141762, A141763; A107876 (unsigned inverse).

Sequence in context: A136247 A370207 A086610 * A114626 A221916 A124773

Adjacent sequences: A141757 A141758 A141759 * A141761 A141762 A141763

Keyword

nonn,tabl

Author

Paul D. Hanna, Jul 18 2008

Status

approved