A007838 Number of permutations of n elements with distinct cycle lengths.

1, 1, 1, 5, 14, 74, 474, 3114, 24240, 219456, 2231280, 23753520, 288099360, 3692907360, 51677246880, 775999798560, 12364465397760, 208583679951360, 3770392002048000, 71251563061002240, 1421847102467635200, 29861872557056870400, 655829140087057305600

Offset: 0

Author

Arnold Knopfmacher

Keywords

• nonn

References

• D. H. Greene and D. E. Knuth, Mathematics for the Analysis of Algorithms, 2nd ed., Birkhäuser, Boston, 1982.

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..450 (terms 0..200 from Vincenzo Librandi)
• Philippe Flajolet, Éric Fusy, Xavier Gourdon, Daniel Panario and Nicolas Pouyanne, A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics, arXiv:math/0606370 [math.CO], 2006.
• A. Knopfmacher and R. Warlimont, Counting permutations and polynomials with a restricted factorization pattern, Australasian J. of Combinatorics, 13 (1996), 151-162.
• D. H. Lehmer, On reciprocally weighted partitions, Acta Arithmetica XXI (1972), 379-388.
• A. M. Odlyzko, Asymptotic enumeration methods, pp. 1063-1229 of R. L. Graham et al., eds., Handbook of Combinatorics, 1995; see Examples 8.10 and 11.8 (pdf, ps)

Crossrefs

Cf. A000142, A080130, A087639, A088994, A317166.

Programs

Maple

p := product((1+x^m/m), m=1..100): s := series(p,x,100): for i from 1 to 100 do printf(`%.0f,`,i!*coeff(s,x,i)) od:
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      b(n, i-1) +b(n-i, min(i-1, n-i))/i))
    end:
a:= n-> n!*b(n$2):
seq(a(n), n=0..23);  # Alois P. Heinz, Feb 23 2022

Mathematica

max = 20; p = Product[(1 + x^m/m), {m, 1, max}]; s = Series[p, {x, 0, max}]; CoefficientList[s, x]*Range[0, max]! (* Jean-François Alcover, Oct 05 2011, after Maple *)

PARI

{a(n)=if(n<0, 0, n!*polcoeff( prod(k=1, n, 1+x^k/k, 1+x*O(x^n)), n))} /* Michael Somos, Sep 19 2006 */

Formula

E.g.f.: Product_{m >= 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 13 2002

Asymptotics: a(n) ~ n!(e^{-g} + e^{-g}/n + O((log n)/n^2)), where g is the Euler gamma.

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

Extensions

More terms from James Sellers, Dec 24 1999