login
A107877
Column 1 of triangle A107876.
11
1, 1, 2, 7, 37, 268, 2496, 28612, 391189, 6230646, 113521387, 2332049710, 53384167192, 1348601249480, 37291381915789, 1120914133433121, 36406578669907180, 1271084987848923282, 47487293697623885913, 1890771531272515677250, 79947079338974990793060
OFFSET
0,3
COMMENTS
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
REFERENCES
R. P. Stanley, Enumerative Combinatorics volume 1, 2nd edition, Cambridge University Press, 2011, Ch. 3
LINKS
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.
FORMULA
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
EXAMPLE
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]
MAPLE
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
MATHEMATICA
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 *)
PROG
(PARI) {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)}
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Jun 04 2005, Apr 10 2007
STATUS
approved