A006463 Convolve natural numbers with characteristic function of triangular numbers.

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

Offset

0,4

Comments

Ramanujan theta functions: f(q) (see A121373), phi(q) (A000122), psi(q) (A010054), chi(q) (A000700).

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

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Jeffrey Shallit, Letter to N. J. A. Sloane with attachment, Aug. 1979

Michael Somos, Introduction to Ramanujan theta functions

Eric Weisstein's World of Mathematics, Ramanujan Theta Functions

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

a(n) = Sum_(k=0..n-1) A003056(k). - Daniele Parisse, Jul 10 2007

a(n+1) - 2*a(n) + a(n-1) = A010054(n) if n>0. - Michael Somos, May 07 2016

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

a[n_] := (x = Quotient[ Sqrt[1+8*n]-1, 2]; x*(x^2-1+3*(n-x*(x+1)/2))/3); Table[a[n], {n, 0, 58}] (* Jean-François Alcover, Apr 11 2013, after Michael Somos *)
t = {0}; Do[Do[AppendTo[t, t[[-1]]+n], {k, 0, n}], {n, 0, 11}]; t (* Jean-François Alcover, May 10 2016, after Vladimir Joseph Stephan Orlovsky *)
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
-- Reinhard Zumkeller, Dec 17 2011

Crossrefs

Cf. A076269, A074909, A010054, A060432.

0 together with the partial sums of A003056.

Sequence in context: A134421 A092777 A186380 * A237886 A212555 A328787

Adjacent sequences: A006460 A006461 A006462 * A006464 A006465 A006466

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

Edited by Dean Hickerson, Nov 09 2002

Status

approved