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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

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

If f is a strictly convex function computed on partitions of n (A000041), then a(n)+1 provides a lower bound on the number of distinct values of n taken by f across all partitions of n. - Noah A Rosenberg, Apr 18 2025

Examples

			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 + ...
		

References

• N. A. Rosenberg, Mathematical Properties of Population-Genetic Statistics, Princeton University Press, 2025; page 113.
• 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
• Curtis Greene and Daniel J. Kleitman, Longest chains in the lattice of integer partitions ordered by majorization, Europ. J. Combinator. 7 (1986), 1-10.
• 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

Crossrefs

Cf. A076269, A074909, A010054, A060432.

0 together with the partial sums of A003056.

Programs

Haskell

a006463 n = a006463_list !! n
a006463_list = 0 : scanl1 (+) a003056_list
-- Reinhard Zumkeller, Dec 17 2011

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

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

Python

from math import isqrt
def A006463(n): return (m:=isqrt((n<<3)+1)-1>>1)*(6*n-2-m*(m+3))//6 # Chai Wah Wu, Jun 07 2025

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

Extensions

Edited by Dean Hickerson, Nov 09 2002