|
| |
|
|
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
|
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}];
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
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
