|
|
A006463
|
|
Convolve natural numbers with characteristic function of triangular numbers.
|
|
13
|
|
|
0, 0, 1, 2, 4, 6, 8, 11, 14, 17, 20, 24, 28, 32, 36, 40, 45, 50, 55, 60, 65, 70, 76, 82, 88, 94, 100, 106, 112, 119, 126, 133, 140, 147, 154, 161, 168, 176, 184, 192, 200, 208, 216, 224, 232, 240, 249, 258, 267, 276, 285, 294, 303, 312, 321, 330, 340, 350, 360
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
a(n) = length (i.e., number of elements minus 1) of longest chain in partition lattice Par(n). Par(n) is the set of partitions of n under "dominance order": partition P is <= partition Q iff the sum of the largest k parts of P is <= the corresponding sum for Q for all k.
If C_n(q, t) are the (q, t)-Catalan polynomials, then p_n(x) := C_n(x, x) is a polynomial in x such that a(n) is the degree of the lowest degree term. The sequence of polynomials p_n(x) = 1, 1, 2*x, x^2 + 4*x^3, 3*x^4 + 4*x^5 + 7*x^6 + ... while the coefficient of the lowest degree term is A074909(n). - Michael Somos, Jan 09 2019
|
|
REFERENCES
|
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.2(f).
|
|
LINKS
|
|
|
FORMULA
|
Let n=binomial(m+1, 2)+r, 0<=r<=m; then a(n) = (1/3)*m*(m^2+3*r-1).
G.f.: (psi(x) - 1) * x / (1 - x)^2 where psi() is a Ramanujan theta function. - Michael Somos, Mar 06 2006
|
|
EXAMPLE
|
a(6)=8; one longest chain consists of these 9 partitions: 6, 5+1, 4+2, 3+3, 3+2+1, 2+2+2, 2+2+1+1, 2+1+1+1+1, 1+1+1+1+1+1. Others are obtained by changing 3+3 to 4+1+1 or 2+2+2 to 3+1+1+1.
G.f. = x^2 + 2*x^3 + 4*x^4 + 6*x^5 + 8*x^6 + 11*x^7 + 14*x^8 + 17*x^9 + ...
|
|
MATHEMATICA
|
Join[{0}, Table[ListConvolve[Range[x], Table[If[OddQ[Sqrt[8n+1]], 1, 0], {n, x}]], {x, 0, 60}]//Flatten] (* Harvey P. Dale, Jan 14 2019 *)
|
|
PROG
|
(PARI) {a(n) = my(x); if( n<0, 0, x = (sqrtint(8*n + 1) - 1)\2; x * (x^2 - 1 + 3 * (n - x*(x+1)/2)) / 3)}; /* Michael Somos, Mar 06 2006 */
(Haskell)
a006463 n = a006463_list !! n
a006463_list = 0 : scanl1 (+) a003056_list
|
|
CROSSREFS
|
0 together with the partial sums of A003056.
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|