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,4

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)

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

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 *)

Prog

(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 */

Crossrefs

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

Sequence in context: A197876 A370761 A305017 * A306751 A305341 A316611

Adjacent sequences: A007835 A007836 A007837 * A007839 A007840 A007841

Keyword

nonn

Author

Arnold Knopfmacher

Extensions

More terms from James A. Sellers, Dec 24 1999

Status

approved