A028342 Expansion of Product_{i>=1} (1 - x^i)^(-1/i); also of exp(Sum_{n>=1} (d(n)*x^n/n)) where d is number of divisors function.

1, 1, 3, 11, 59, 339, 2629, 20677, 202089, 2066201, 24322931, 296746251, 4193572723, 59806188571, 954679763829, 15845349818789, 285841314451409, 5293203821406897, 106976406006818659, 2201383054398314251

Offset

0,3

Comments

From Peter Bala, Nov 14 2017: (Start)

It appears that the sequence taken modulo 10 is periodic with period 10. More generally, we conjecture

(1) for k odd, a(n+k) + a(n) is divisible by k: if true, then for k odd, the sequence a(n) taken modulo k would be periodic with period dividing 2*k.

(2) for even k congruent to 0, 2 or 6 modulo 8 then a(n+k) - a(n) is divisible by k; in these cases the sequence a(n) taken modulo k would be periodic with period dividing k.

(3) for even k congruent to 4 modulo 8 then 2*( a(n+k) - a(n) ) is divisible by k; in this case the sequence 2*a(n) taken modulo k would be periodic with period dividing k. (End)

a(n) is the number of colored permutations by number of divisors, that is, permutations whose decomposition into a product of cycles gives the result that each cycle carries a label that is a divisor of its corresponding length. - Ricardo Gómez Aíza, Mar 08 2023

Links

Vaclav Kotesovec, Table of n, a(n) for n = 0..445

L. Ahmadi, R. Gómez Aíza, and M. D. Ward. A unified treatment of families of partition functions, arXiv:2303.02240 [math.CO], 2023.

N. J. A. Sloane, Transforms

Formula

This is an expansion as an exponential generating function, i.e., as sum a(n)*x^n/n!.

Equivalently, a(n)/n! is the Euler transform of [1, 1/2, 1/3, 1/4, ...].

a(n) = (n-1)!*Sum_{i=0..n-1} d(i+1)*a(n-i-1)/(n-i-1)!, a(0)=1, where d(i) is number of divisors function. - Vladimir Kruchinin, Feb 27 2015

Conjecture: log(a(n)/n!) ~ log(2)/2 * log(n)^2. - Vaclav Kotesovec, Sep 15 2018

From Ricardo Gómez Aíza, Mar 08 2023: (Start)

The above conjecture is incorrect:

a(n)/n! ~ (w(n) / n)^(1 - gamma)/sqrt(2 * Pi * abs(log(w(n) / n))) * exp(c + w(n) + (log(w(n) / n))^2 / 2), where w(n) = W(e^gamma * n), W is the Lambert W function, gamma is the Euler-Mascheroni constant, c = Pi^2 / 12 - gamma^2 / 2 - 2 * gamma(1), and gamma(1) is the 1st Stieltjes number.

log(a(n)/n!) ~ (1/2) * log(n)^2. (End)

Example

For n = 3, there are 6 permutations that written as product of cycles are (1)(2)(3), (1)(23), (2)(13), (3)(12), (123), (132). Cycles of length one can only carry the label 1. Cycles of length two can carry the label either 1 or 2. Cycles of length three can carry the label either 1 or 3. Then a(3) = 11. - Ricardo Gómez Aíza, Mar 08 2023

Mathematica

nmax=20; CoefficientList[Series[Product[1/(1-x^k)^(1/k), {k, 1, nmax}], {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, May 28 2015 *)
a[n_] := a[n] = If[n == 0, 1, Sum[DivisorSigma[0, k]*a[n-k], {k, 1, n}]/n]; Table[n!*a[n], {n, 0, 20}] (* Vaclav Kotesovec, Sep 07 2018 *)
nmax = 20; CoefficientList[Series[Exp[Sum[DivisorSigma[0, k]*x^k/k, {k, 1, nmax}]], {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jun 26 2019 *)

Prog

(Maxima)
a(n):=if n=0 then 1 else (n-1)!*sum(length(divisors(i+1))*a(n-i-1)/(n-i-1)!, i, 0, n-1); /* Vladimir Kruchinin, Feb 27 2015 */

Crossrefs

Cf. A000005.

Sequence in context: A340865 A290484 A156560 * A137982 A193364 A074509

Adjacent sequences: A028339 A028340 A028341 * A028343 A028344 A028345

Keyword

nonn,easy

Author

Jeffrey Shallit

Extensions

Edited by Franklin T. Adams-Watters, Jul 03 2009

Status

approved