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
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
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.
Bradley K. Moon and Noah A. Rosenberg, Integer Sequences for Diversity Statistics, J. Int. Seq. 29(1) (2026), 26.1.5. See p. 7.
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
(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
CROSSREFS
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
Edited by Dean Hickerson, Nov 09 2002
STATUS
approved
