login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; table; graph; refs; listen; history; text; internal format)
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

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

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 A260360 A011296

Adjacent sequences:  A107873 A107874 A107875 * A107877 A107878 A107879

KEYWORD

nonn,tabl,nice

AUTHOR

Paul D. Hanna, Jun 04 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 15 18:33 EDT 2021. Contains 345049 sequences. (Running on oeis4.)