|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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).
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 ].
|
|
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):
# second Maple program:
a:= n-> LinearAlgebra:-Determinant(Matrix(n, (i, j)->
binomial(binomial(n+1-i, 2)+1, i-j+1))):
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|