login
Number of permutations of n elements with distinct cycle lengths.
45

%I #70 Feb 24 2022 20:25:49

%S 1,1,1,5,14,74,474,3114,24240,219456,2231280,23753520,288099360,

%T 3692907360,51677246880,775999798560,12364465397760,208583679951360,

%U 3770392002048000,71251563061002240,1421847102467635200,29861872557056870400,655829140087057305600

%N Number of permutations of n elements with distinct cycle lengths.

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

%H Seiichi Manyama, <a href="/A007838/b007838.txt">Table of n, a(n) for n = 0..450</a> (terms 0..200 from Vincenzo Librandi)

%H Philippe Flajolet, Éric Fusy, Xavier Gourdon, Daniel Panario and Nicolas Pouyanne, <a href="http://arxiv.org/abs/math/0606370">A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics</a>, arXiv:math/0606370 [math.CO], 2006.

%H A. Knopfmacher and R. Warlimont, <a href="http://ajc.maths.uq.edu.au/pdf/13/ocr-ajc-v13-p151.pdf">Counting permutations and polynomials with a restricted factorization pattern</a>, Australasian J. of Combinatorics, 13 (1996), 151-162.

%H D. H. Lehmer, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa21/aa21123.pdf">On reciprocally weighted partitions</a>, Acta Arithmetica XXI (1972), 379-388.

%H 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 (<a href="http://www.dtc.umn.edu/~odlyzko/doc/asymptotic.enum.pdf">pdf</a>, <a href="http://www.dtc.umn.edu/~odlyzko/doc/asymptotic.enum.ps">ps</a>)

%F E.g.f.: Product_{m >= 1} (1+x^m/m).

%F 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

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

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

%p 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:

%p # second Maple program:

%p b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

%p b(n, i-1) +b(n-i, min(i-1, n-i))/i))

%p end:

%p a:= n-> n!*b(n$2):

%p seq(a(n), n=0..23); # _Alois P. Heinz_, Feb 23 2022

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

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

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

%K nonn

%O 0,4

%A _Arnold Knopfmacher_

%E More terms from _James A. Sellers_, Dec 24 1999