A107878 -id:A107878 - cp's OEIS frontend

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

Paul D. Hanna, Jun 04 2005

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

			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.

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

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.

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 *)

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

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

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.

A107877 Column 1 of triangle A107876.

Original entry on oeis.org

1, 1, 2, 7, 37, 268, 2496, 28612, 391189, 6230646, 113521387, 2332049710, 53384167192, 1348601249480, 37291381915789, 1120914133433121, 36406578669907180, 1271084987848923282, 47487293697623885913, 1890771531272515677250, 79947079338974990793060

Offset: 0

Paul D. Hanna, Jun 04 2005, Apr 10 2007

nonn

Also number of subpartitions of partition consisting of first n-1 triangular numbers; e.g., a(4) = subp([1,3,6]) = 37. - Franklin T. Adams-Watters, Jun 26 2006
Number of length-n restricted growth strings (RGS) [s(0),s(1),...,s(n-1)] where s(0)=0 and s(k) <= s(k-1)+k, see Fxtbook link and example. - Joerg Arndt, Apr 30 2011
Number of Dyck paths whose ascent lengths are exactly {1,2,...,n+1}; for example, the a(2) = 2 paths are uduuduuudddd and uduudduuuddd. - David Scambler, May 30 2012
Number of types of cells of a fine mixed subdivision of the Tesler flow polytope. - Alejandro H. Morales, Oct 11 2017

			1 = 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 + 2496*x^6*(1-x)^22 + ...
Also equals the final term in rows of the triangle where row n+1 equals the partial sums of row n with the final term repeated n+1 times, starting with a '1' in row 0, as illustrated by:
1;
1, 1;
1, 2,  2,  2;
1, 3,  5,  7,  7,  7,   7;
1, 4,  9, 16, 23, 30,  37,  37,  37,  37,  37;
1, 5, 14, 30, 53, 83, 120, 157, 194, 231, 268, 268, 268, 268, 268, 268; ...
Restricted growth strings: a(0)=1 corresponds to the empty string; a(1)=1 to [0];
a(2) = 2 to [00] and [01]; a(3)=7 to
  1:  [ 0 0 0 ],
  2:  [ 0 0 1 ],
  3:  [ 0 0 2 ],
  4:  [ 0 1 0 ],
  5:  [ 0 1 1 ],
  6:  [ 0 1 2 ],
  7:  [ 0 1 3 ].
[_Joerg Arndt_, Apr 30 2011]

R. P. Stanley, Enumerative Combinatorics volume 1, 2nd edition, Cambridge University Press, 2011, Ch. 3

Alois P. Heinz, Table of n, a(n) for n = 0..390
Joerg Arndt, Matters Computational (The Fxtbook), section 17.3.6, pp. 368-369
K. Mészáros, A. H. Morales, Volumes and Ehrhart polynomials of flow polytopes, arXiv:1710.00701 [math.CO], 2017, sections 6.1 and 7.

Cf. A107876, A107878, A107879, A115728, A115729.

Cf. A305605, A305601.

b:= proc(n, y) option remember; `if`(n=0, 1, add(
      b(n-1, y+i-n), i=max(1, n-y)..n*(n-1)/2+1-y))
    end:
a:= n-> b(n+1, 0):
seq(a(n), n=0..25);  # Alois P. Heinz, Nov 26 2016
# second Maple program:
a:= n-> LinearAlgebra:-Determinant(Matrix(n,(i,j)->
        binomial(binomial(n+1-i,2)+1,i-j+1))):
seq(a(n), n=0..25); # Alejandro H. Morales, Aug 31 2017

a[ n_, k_: 1, j_: 1] := If[ n < 2, Boole[n >= 0], a[n, k, j] = Sum[a[n - 1, i, j + 1], {i, k + j}]]; (* Michael Somos, Nov 26 2016 *)

{a(n)=polcoeff(1-sum(k=0,n-1,a(k)*x^k*(1-x+x*O(x^n))^(1+k*(k+1)/2)),n)}

G.f.: 1 = Sum_{k>=0} a(k)*x^k*(1-x)^(1 + k*(k+1)/2).
G.f.: 1 = Sum_{k>=0} a(k)*x^k/(1+x)^((k+1)*(k+2)/2).
From Benedict W. J. Irwin, Nov 26 2016: (Start)
Conjecture: a(n) can be expressed with a series of nested sums,
a(3) = Sum_{i=1..2} i+2,
a(4) = Sum_{i=1..2} Sum_{j=1..i+2} j+3,
a(5) = Sum_{i=1..2} Sum_{j=1..i+2} Sum_{k=1..j+3} k+4,
a(6) = Sum_{i=1..2} Sum_{j=1..i+2} Sum_{k=1..j+3} Sum_{l=1..k+4} l+5. (End)
Determinantal formula: a(n) = Det(A) where A is the n X n matrix with entries A(i,j) = binomial(binomial(n+1-i,2)+1,i-j+1). This follows by the formula by MacMahon (see EC1 Ex 3.63) for the number of such subpartitions. -  Alejandro H. Morales, Aug 31 2017

A107884 Matrix cube of triangle A107876; equals the product of triangular matrices: A107876^3 = A107862^-1*A107873.

Original entry on oeis.org

1, 3, 1, 6, 3, 1, 16, 9, 3, 1, 63, 37, 12, 3, 1, 351, 210, 67, 15, 3, 1, 2609, 1575, 498, 106, 18, 3, 1, 24636, 14943, 4701, 975, 154, 21, 3, 1, 284631, 173109, 54298, 11100, 1689, 211, 24, 3, 1, 3909926, 2381814, 745734, 151148, 22518, 2688, 277, 27, 3, 1

Offset: 0

Paul D. Hanna, Jun 04 2005

Column 0 is A107885.
Column 1 is A107886.
Column 2 equals A107887.
Column 3 equals SHIFT_LEFT(A107878), where A107878 is column 2 of A107876.
Column 4 equals A107888.

			G.f. for column 0:
1 = T(0,0)*(1-x)^3 + T(1,0)*x*(1-x)^3 + T(2,0)*x^2*(1-x)^4 + T(3,0)*x^3*(1-x)^6 + T(4,0)*x^4*(1-x)^9 + T(5,0)*x^5*(1-x)^13 + ...
  = 1*(1-x)^3 + 3*x*(1-x)^3 + 6*x^2*(1-x)^4 + 16*x^3*(1-x)^6 + 63*x^4*(1-x)^9 + 351*x^5*(1-x)^13 + ...
G.f. for column 1:
1 = T(1,1)*(1-x)^3 + T(2,1)*x*(1-x)^4 + T(3,1)*x^2*(1-x)^6 + T(4,1)*x^3*(1-x)^9 + T(5,1)*x^4*(1-x)^13 + T(6,1)*x^5*(1-x)^18 + ...
  = 1*(1-x)^3 + 3*x*(1-x)^4 + 9*x^2*(1-x)^6 + 37*x^3*(1-x)^9 + 210*x^4*(1-x)^13 + 1575*x^5*(1-x)^18 + ...
Triangle begins:
       1;
       3,      1;
       6,      3,     1;
      16,      9,     3,     1;
      63,     37,    12,     3,    1;
     351,    210,    67,    15,    3,   1;
    2609,   1575,   498,   106,   18,   3,  1;
   24636,  14943,  4701,   975,  154,  21,  3, 1;
  284631, 173109, 54298, 11100, 1689, 211, 24, 3, 1;
  ...

Cf. A107862, A107870, A107873, A107867, A107876, A107880, A107884, A107885, A107886, A107887, A107888.

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 = MatrixPower[Inverse[A107862].A107867, 3];
Table[T[[n+1, k+1]], {n, 0, max}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 31 2024 *)

{T(n,k)=polcoeff(1-sum(j=0,n-k-1, T(j+k,k)*x^j*(1-x+x*O(x^n))^(3+(k+j)*(k+j-1)/2-k*(k-1)/2)),n-k)}

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

A209440 G.f.: 1 = Sum_{n>=0} a(n)x^n (1-x)^((n+1)^2).

Original entry on oeis.org

1, 1, 4, 30, 340, 5235, 102756, 2464898, 70120020, 2313120225, 86962820000, 3674969314090, 172615622432040, 8928295918586815, 504561763088722500, 30946605756915149850, 2048137516834986743700, 145535818715694311408181, 11054204297079333714850260

Offset: 0

Paul D. Hanna, Apr 07 2012

nonn

Compare to a g.f. of the Catalan numbers: 1 = Sum_{n>=0} A000108(n)*x^n*(1-x)^(n+1).

			G.f.: 1 = 1*(1-x) + 1*x*(1-x)^4 + 4*x^2*(1-x)^9 + 30*x^3*(1-x)^16 + 340*x^4*(1-x)^25 +...

G. C. Greubel, Table of n, a(n) for n = 0..350

Cf. A000108, A107878, A177450, A180716.

Column k=2 of A355614.

a:= proc(n) option remember; `if`(n=0, 1, -add(a(j)
      *(-1)^(n-j)*binomial((j+1)^2, n-j), j=0..n-1))
    end:
seq(a(n), n=0..19);  # Alois P. Heinz, Jul 08 2022

a[0] := 1; a[n_] := a[n] = Sum[(-1)^(n + 1 - k)*a[k]*Binomial[(k + 1)^2, n - k], {k, 0, n - 1}]; Table[a[n], {n,0,50}] (* G. C. Greubel, Jan 02 2018 *)

{a(n)=if(n==0, 1, -polcoeff(sum(m=0, n-1, a(m)*x^m*(1-x+x*O(x^n))^((m+1)^2)), n))}

{a(n)=if(n==0,1,sum(k=0,n-1,(-1)^(n+1-k)*a(k)*binomial((k+1)^2,n-k)))}
for(n=0,20,print1(a(n),", "))

a(n) = Sum_{k=0..n-1} (-1)^(n+1-k) * a(k) * binomial((k+1)^2,n-k) for n>=1, with a(0)=1.

A107879 Column 3 of triangle A107876.

Original entry on oeis.org

1, 1, 4, 26, 230, 2565, 34516, 544423, 9857583, 201664780, 4603336725, 116059191472, 3204682702923, 96226940232235, 3122975927539860, 108970956192622980, 4069312064491308140, 161969813446983961395, 6846708764857861662741, 306381118887919045527510

Offset: 0

Paul D. Hanna, Jun 04 2005

nonn

			1 = 1*(1-x)^1 + 1*x*(1-x)^4 + 4*x^2*(1-x)^8 + 26*x^3*(1-x)^13 + 230*x^4*(1-x)^19 + 2565*x^5*(1-x)^26 + 34516*x^6*(1-x)^34 +...

Alois P. Heinz, Table of n, a(n) for n = 0..389

Cf. A107876, A107877, A107878.

a:= proc(n) option remember; `if`(n=0, 1, add(a(j-1)*
      (-1)^(n-j)*binomial((j+1)*(j+2)/2-2, n-j+1), j=1..n))
    end:
seq(a(n), n=0..22);  # Alois P. Heinz, Jul 10 2022

{a(n)=polcoeff(1-sum(k=0,n-1,a(k)*x^k*(1-x+x*O(x^n))^((k+2)*(k+3)/2-2)),n)}

G.f.: 1 = Sum_{k>=0} a(k)*x^k*(1-x)^((k+2)*(k+3)/2 - 2).

A107889 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. Also, matrix inverse of triangle A107876.

Original entry on oeis.org

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, 0, -975, -550, -154, -30, -5, -1, 1, 0, -11100, -6195, -1689, -310, -45, -6, -1, 1, 0, -151148, -83837, -22518, -4005, -545, -63, -7, -1, 1, 0, -2401365, -1326923, -353211, -61686, -8105, -875, -84, -8, -1, 1

Offset: 0

Paul D. Hanna, Jun 05 2005

SHIFT_LEFT(column 1) = -A107878.
SHIFT_LEFT(column 2) = -A107883.
SHIFT_LEFT(column 3) = -A107888.

			G.f. for column 1:
1 = T(1,1)*(1-x)^-1 + T(2,1)*x*(1-x)^0 + T(3,1)*x^2*(1-x)^2 + T(4,1)*x^3*(1-x)^5 + T(5,1)*x^4*(1-x)^9 + T(6,1)*x^5*(1-x)^14 + ...
  = 1*(1-x)^-1 - 1*x*(1-x)^0 - 1*x^2*(1-x)^2 - 3*x^3*(1-x)^5 - 15*x^4*(1-x)^9 - 106*x^5*(1-x)^14 - 975*x^6*(1-x)^20 + ...
G.f. for column 2:
1 = T(2,2)*(1-x)^-1 + T(3,2)*x*(1-x)^1 + T(4,2)*x^2*(1-x)^4 + T(5,2)*x^3*(1-x)^8 + T(6,2)*x^4*(1-x)^13 + T(7,2)*x^5*(1-x)^19 + ...
  = 1*(1-x)^-1 - 1*x*(1-x)^1 - 2*x^2*(1-x)^4 - 9*x^3*(1-x)^8 - 61*x^4*(1-x)^13 - 550*x^5*(1-x)^19 - 6195*x^6*(1-x)^26 + ...
Triangle 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;
   0,   -975,  -550,  -154,  -30,  -5, -1,  1;
   0, -11100, -6195, -1689, -310, -45, -6, -1, 1;
  ...

Cf. A107876, A107880, A107884.

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[Inverse[A107862].A107867];
Table[T[[n + 1, k + 1]], {n, 0, max}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 31 2024 *)

{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)}

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

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A107877 Column 1 of triangle A107876.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A107884 Matrix cube of triangle A107876; equals the product of triangular matrices: A107876^3 = A107862^-1*A107873.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A209440 G.f.: 1 = Sum_{n>=0} a(n)*x^n * (1-x)^((n+1)^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A107879 Column 3 of triangle A107876.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A107889 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. Also, matrix inverse of triangle A107876.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A209440 G.f.: 1 = Sum_{n>=0} a(n)x^n (1-x)^((n+1)^2).