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.

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

Author

Paul D. Hanna, Jun 04 2005

Keywords

• nonn
• tabl
• nice

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

Examples

			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.
		

Links

• Alois P. Heinz, Rows n = 0..50, flattened

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.

Programs

Mathematica

max = 10;
A107862 = Table[Binomial[If[nA107867 = Table[Binomial[If[nA107862].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 *)

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

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.