A007841 Number of factorizations of permutations of n letters into cycles in nondecreasing length order.

1, 1, 3, 11, 56, 324, 2324, 18332, 167544, 1674264, 18615432, 223686792, 2937715296, 41233157952, 623159583552, 10008728738304, 171213653641344, 3092653420877952, 59086024678203264, 1185657912197967744, 25015435198774723584, 552130504313534175744

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..450

Vaclav Kotesovec, Graph - The asymptotic ratio

A. Knopfmacher, J. N. Ridley, Reciprocal sums over partitions and compositions, SIAM J. Discrete Math. 6 (1993), no. 3, 388-399.

D. H. Lehmer, On reciprocally weighted partitions, Acta Arithmetica XXI (1972), 379-388.

Formula

E.g.f.: prod{m >= 1} 1/(1-x^m/m).

a(n) = Sum_{k=1..n} (n-1)!/(n-k)!*b(k)*a(n-k), where b(k) = Sum_{d divides k} d^(1-k/d) and a(0) = 1. - Vladeta Jovovic, Oct 14 2002

a(n) = R(n,1), R(n,m) = R(n,m+1)+binomial(n,m)*(m-1)!*R(n-m,m), R(n,n)=(n-1)!, R(n,m)=0 for n<m. - Vladimir Kruchinin, Sep 09 2014

a(n) ~ c * n! * n, where c = exp(-gamma) = 0.56145948..., where gamma is the Euler-Mascheroni constant A001620 [Lehmer, 1972]. - Vaclav Kotesovec, Mar 05 2016

E.g.f.: exp(Sum_{k>=1} Sum_{j>=1} x^(j*k)/(k*j^k)). - Ilya Gutkovskiy, May 27 2018

Maple

p := product(1/(1-x^m/m), m=1..100):
s := series(p, x, 100):
for i from 0 to 100 do printf(`%.0f, `, i!*coeff(s, x, i)) od:
# second Maple program:
with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
     (i-1)!^j*b(n-i*j, i-1)*multinomial(n, n-i*j, i$j), j=0..n/i)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..30);  # Alois P. Heinz, Jul 21 2014

Mathematica

nmax = 25; CoefficientList[Series[1/Product[(1 - x^k/k), {k, 1, nmax}], {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jul 24 2019 *)
nmax = 25; CoefficientList[Series[Exp[Sum[PolyLog[j, x^j]/j, {j, 1, nmax}]], {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jul 24 2019 *)

Prog

(PARI)
N=66; q='q+O('q^N);
f=1/prod(n=1, N, 1-1/n*q^n );
egf=serlaplace(f);
Vec(egf)
/* Joerg Arndt, Oct 06 2012 */
(Maxima)
R(n, m):=if n=0 then 1 else if n<m then 0 else if n=m then (n-1)! else R(n, m+1)+binomial(n, m)*(m-1)!*R(n-m, m);
makelist(R(n, 1), n, 0, 21); /* Vladimir Kruchinin, Sep 09 2014 */

Crossrefs

Cf. A007837, A007838, A249078, A249480, A249588, A249593, A269791, A269793, A269794.

Sequence in context: A136104 A174627 A302147 * A036760 A000985 A207433

Adjacent sequences: A007838 A007839 A007840 * A007842 A007843 A007844

Keyword

nonn

Author

Arnold Knopfmacher

Extensions

More terms from James A. Sellers, Jan 09 2001

Prepended a(0) = 1, Joerg Arndt, Oct 06 2012

Status

approved