A066447 Number of basis partitions (or basic partitions) of n.

1, 1, 2, 2, 3, 4, 6, 8, 10, 13, 16, 20, 26, 32, 40, 50, 61, 74, 90, 108, 130, 156, 186, 222, 264, 313, 370, 436, 512, 600, 702, 818, 952, 1106, 1282, 1484, 1715, 1978, 2278, 2620, 3008, 3448, 3948, 4512, 5150, 5872, 6684, 7600, 8632, 9791, 11094, 12558, 14198, 16036, 18096, 20398

Offset: 0

Author

Herbert S. Wilf, Dec 29 2001

Keywords

• nonn
• easy

Comments

The k-th successive rank of a partition pi = (pi_1, pi_2, ..., pi_s) of the integer n is r_k = pi_k - pi'_k, where pi' denotes the conjugate partition. A partition pi is basic if the number of dots in its Ferrers diagram is the least among all the Ferrers diagrams of partitions with the same rank vector.

The g.f. Sum_{n >= 0} x^(n^2) * Product_{k = 1..n} (1 + x^k)/(1 - x^k) = Sum_{n >= 0} x^(n^2) * Product_{k = 1..n} (1 + x^k)/(1 + x^k - 2*x^k) == Sum_{n >= 0} x^(n^2) (mod 2). It follows that a(n) is odd iff n is a square (Nolan et al., equation 6, p. 282). - Peter Bala, Jan 08 2025

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 0..10000
• George E. Andrews, Partition Identities for Two-Color Partitions, Hardy-Ramanujan Journal, Hardy-Ramanujan Society, 2021, Special Commemorative volume in honour of Srinivasa Ramanujan, 2021, 44, pp.74-80. hal-03498190. See p. 79.
• J. M. Nolan, C. D. Savage and H. S. Wilf, Basis partitions, Discrete Math. 179 (1998), 277-283.

Crossrefs

Row sums of A066448.

Cf. A001130, A001935, A003114, A306734, A333374.

Cf. A192918, A376841.

Programs

Maple

b := proc(n,d); option remember; if n=0 and d=0 then RETURN(1) elif n<=0 or d<=0 then RETURN(0) else RETURN(b(n-d,d)+b(n-2*d+1,d-1)+b(n-3*d+1,d-1)) fi: end: A066447 := n->add(b(n,d),d=0..n);

Mathematica

nmax = 60; CoefficientList[Series[Sum[x^(n^2)*Product[(1 + x^k)/(1 - x^k), {k, 1, n}], {n, 0, Sqrt[nmax]}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Mar 17 2020 *)
nmax = 60; p = 1; s = 1; Do[p = Normal[Series[p*(1 + x^k)/(1 - x^k)*x^(2*k - 1), {x, 0, nmax}]]; s += p;, {k, 1, Sqrt[nmax]}]; Take[CoefficientList[s, x], nmax + 1] (* Vaclav Kotesovec, Mar 17 2020 *)

PARI

N=66; x='x+O('x^N); s=sum(n=0,N,x^(n^2)*prod(k=1,n,(1+x^k)/(1-x^k))); Vec(s) /* Joerg Arndt, Apr 07 2011 */

Formula

G.f.: Sum_{n >= 0} x^(n^2) * Product_{k = 1..n} (1 + x^k)/(1 - x^k) [Given in Nolan et al. reference]. - Joerg Arndt, Apr 07 2011

Limit_{n->infinity} a(n) / A333374(n) = A058265 = (1 + (19+3*sqrt(33))^(1/3) + (19-3*sqrt(33))^(1/3))/3 = 1.839286755214... - Vaclav Kotesovec, Mar 17 2020

a(n) ~ c * d^sqrt(n) / n^(3/4), where d = A376841 = 7.1578741786143524880205... = exp(2*sqrt(log(r)^2 - polylog(2, -r^2) + polylog(2, r^2))) and c = 0.193340468476900308848561788251945... = (log(r)^2 - polylog(2, -r^2) + polylog(2, r^2))^(1/4) * sqrt(1/24 + cosh(arccosh(53*sqrt(11/2)/64)/3) / (3*sqrt(22))) / sqrt(Pi), where r = A192918 = 0.54368901269207636157... is the real root of the equation r^2*(1+r) = 1-r. - Vaclav Kotesovec, Mar 19 2020, updated Oct 10 2024