login
A107876
Triangular matrix T, read by rows, that satisfies: [T^k](n,k) = T(n,k-1) for n>=k>0, or, equivalently, (column k of T^k) = SHIFT_LEFT(column k-1 of T) when zeros above the diagonal are ignored.
24
1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 7, 7, 3, 1, 1, 37, 37, 15, 4, 1, 1, 268, 268, 106, 26, 5, 1, 1, 2496, 2496, 975, 230, 40, 6, 1, 1, 28612, 28612, 11100, 2565, 425, 57, 7, 1, 1, 391189, 391189, 151148, 34516, 5570, 707, 77, 8, 1, 1, 6230646, 6230646, 2401365, 544423
OFFSET
0,7
COMMENTS
Remarkably, T equals the product of these triangular matrices: T = A107862^-1*A107867 = A107867^-1*A107870 = A107870^-1*A107873; reversing the order of these products yields triangle A101479.
Column m of T^k is the number of subpartitions of the initial terms of the sequence (k-1)+n(m-1)+n(n-1)/2 (ignoring 0's above the diagonal). E.g., column 4 of T^3 is 1,3,15,106,975,.... The sequence above is 2,5,9,14,20,.... subp([]) = 1, subp([2]) = 3, subp([2,5]) = 15, subp([2,5,9]) = 106, etc. The matrix product of T^(k-1) * T computes the number of such subpartitions by looking at the first part index where the subpartition is maxed - for [2,5,9,14,20] the third term (9 maxed) has subp([1,4]) for the first two values (not maxed), times subp([5,11]) for the last two values (possibly maxed). - Franklin T. Adams-Watters, Jun 26 2006
T(n,k) is the number of Dyck paths whose sequence of ascent lengths is exactly k,k+1,...,n, for example the T(4,3) = 3 paths are UUUdUUUUd^6, UUUddUUUUd^5 and UUUdddUUUUd^4. - David Scambler, May 30 2012
LINKS
FORMULA
G.f. for column k of T^m, the m-th matrix power of this triangle T:
(1) 1 = Sum_{j>=0} T(k+j, k) * x^j * (1-x)^(1+(k+j)*(k+j-1)/2-k*(k-1)/2) for m=1.
(2) 1 = Sum_{j>=0} [T^m](k+j, k)*x^j*(1-x)^(m+(k+j)*(k+j-1)/2-k*(k-1)/2) for all m and k>=0.
(3) 1 = Sum_{j>=0} [T^m](k+j, k)*x^j / C(x)^(m-j+(k+j)*(k+j-1)/2-k*(k-1)/2) where C(x)=2/(1+sqrt(1-4*x)) is g.f. for A000108 (Catalan numbers).
Matrix inverse of this triangle T satisfies:
(4) [T^-1](n,k) = -[T^k](n,k+1) for n>k>=0.
EXAMPLE
G.f. for column 1:
1 = T(1,1)*(1-x)^1 + T(2,1)*x*(1-x)^2 + T(3,1)*x^2*(1-x)^4 + T(4,1)*x^3*(1-x)^7 + T(5,1)*x^4*(1-x)^11 + T(6,1)*x^5*(1-x)^16 +...
= 1*(1-x)^1 + 1*x*(1-x)^2 + 2*x^2*(1-x)^4 + 7*x^3*(1-x)^7 + 37*x^4*(1-x)^11 + 268*x^5*(1-x)^16 +...
G.f. for column 2:
1 = T(2,2)*(1-x)^1 + T(3,2)*x*(1-x)^3 + T(4,2)*x^2*(1-x)^6 + T(5,2)*x^3*(1-x)^10 + T(6,2)*x^4*(1-x)^15 + T(7,2)*x^5*(1-x)^21 +...
= 1*(1-x)^1 + 1*x*(1-x)^3 + 3*x^2*(1-x)^6 + 15*x^3*(1-x)^10 + 106*x^4*(1-x)^15 + 975*x^5*(1-x)^21 +...
Triangle T begins:
1;
1, 1;
1, 1, 1;
2, 2, 1, 1;
7, 7, 3, 1, 1;
37, 37, 15, 4, 1, 1;
268, 268, 106, 26, 5, 1, 1;
2496, 2496, 975, 230, 40, 6, 1, 1;
28612, 28612, 11100, 2565, 425, 57, 7, 1, 1;
391189, 391189, 151148, 34516, 5570, 707, 77, 8, 1, 1; ...
where column 1 of T = SHIFT_LEFT(column 0 of T).
Matrix square T^2 begins:
1;
2, 1;
3, 2, 1;
7, 5, 2, 1;
26, 19, 7, 2, 1;
141, 104, 37, 9, 2, 1;
1034, 766, 268, 61, 11, 2, 1; ...
Compare column 2 of T^2 with column 1 of T.
Matrix inverse begins:
1;
-1, 1;
0, -1, 1;
0, -1, -1, 1;
0, -3, -2, -1, 1;
0, -15, -9, -3, -1, 1;
0, -106, -61, -18, -4, -1, 1; ...
Compare column 1 of T^-1 with column 2 of T and
compare column 2 of T^-1 with column 3 of T^2.
MATHEMATICA
max = 10;
A107862 = Table[Binomial[If[n<k, 0, n*(n-1)/2 - k*(k - 1)/2 + n-k], n-k], {n, 0, max}, {k, 0, max}];
A107867 = Table[Binomial[If[n<k, 0, n*(n-1)/2 - k*(k - 1)/2 + n-k+1], n-k], {n, 0, max}, {k, 0, max}];
t = Inverse[A107862].A107867;
Table[t[[n, k]], {n, 1, max+1}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 12 2012, after first comment, fixed by Vaclav Kotesovec, Jun 13 2018 *)
PROG
(PARI) {T(n, k)=polcoeff(1-sum(j=0, n-k-1, T(j+k, k)*x^j*(1-x+x*O(x^n))^(1+(k+j)*(k+j-1)/2-k*(k-1)/2)), n-k)}
for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print(""))
(PARI) /* Print the Triangular Matrix to the Power p: */
{T(n, k, p)=polcoeff(1- sum(j=0, n-k-1, T(j+k, k, p)*x^j*(1-x+x*O(x^n))^(j*(j-1)/2+j*k+p)), n-k)}
for(n=0, 10, for(k=0, n, print1(T(n, k, 1), ", ")); print(""))
CROSSREFS
Cf. A107862, A107865, A107867, A107870, A107877 (column 1), A107878 (column 2), A107879 (column 3), A107880 (matrix square), A107884 (matrix cube), A107889 (matrix inverse).
Cf. A115728, A115729, A101479 (dual triangle).
T(2n,n) gives A300954.
Sequence in context: A090441 A340591 A155794 * A121554 A365077 A260360
KEYWORD
nonn,tabl,nice
AUTHOR
Paul D. Hanna, Jun 04 2005
STATUS
approved