cp's OEIS Frontend

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

%I A007838 #71 Jul 02 2025 16:01:55
%S A007838 1,1,1,5,14,74,474,3114,24240,219456,2231280,23753520,288099360,
%T A007838 3692907360,51677246880,775999798560,12364465397760,208583679951360,
%U A007838 3770392002048000,71251563061002240,1421847102467635200,29861872557056870400,655829140087057305600
%N A007838 Number of permutations of n elements with distinct cycle lengths.
%D A007838 D. H. Greene and D. E. Knuth, Mathematics for the Analysis of Algorithms, 2nd ed., Birkhäuser, Boston, 1982.
%H A007838 Seiichi Manyama, <a href="/A007838/b007838.txt">Table of n, a(n) for n = 0..450</a> (terms 0..200 from Vincenzo Librandi)
%H A007838 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 A007838 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 A007838 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 A007838 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 A007838 E.g.f.: Product_{m >= 1} (1+x^m/m).
%F A007838 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 A007838 Asymptotics: a(n) ~ n!(e^{-g} + e^{-g}/n + O((log n)/n^2)), where g is the Euler gamma.
%F A007838 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 A007838 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 A007838 # second Maple program:
%p A007838 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A007838       b(n, i-1) +b(n-i, min(i-1, n-i))/i))
%p A007838     end:
%p A007838 a:= n-> n!*b(n$2):
%p A007838 seq(a(n), n=0..23);  # _Alois P. Heinz_, Feb 23 2022
%t A007838 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 A007838 (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 A007838 Cf. A000142, A080130, A087639, A088994, A317166.
%K A007838 nonn
%O A007838 0,4
%A A007838 _Arnold Knopfmacher_
%E A007838 More terms from _James Sellers_, Dec 24 1999