login
Number of permutations of length n with equal cycles.
(Formerly M0903)
22

%I M0903 #58 Dec 17 2023 16:05:33

%S 1,2,3,10,25,176,721,6406,42561,436402,3628801,48073796,479001601,

%T 7116730336,88966701825,1474541093026,20922789888001,400160588853026,

%U 6402373705728001,133991603578884052,2457732174030848001,55735573291977790576,1124000727777607680001

%N Number of permutations of length n with equal cycles.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D D. P. Walsh, A differentiation-based characterization of primes, Abstracts Amer. Math. Soc., 25 (No. 2, 2002), p. 339, #975-11-237.

%H Alois P. Heinz, <a href="/A005225/b005225.txt">Table of n, a(n) for n = 1..450</a>

%H R. K. Guy, <a href="/A005225/a005225.pdf">Letter to N. J. A. Sloane, Jul 1988</a>

%H D. P. Walsh, <a href="http://www.mtsu.edu/~dwalsh/primetst.html">Primality test based on the generating function</a>

%H D. P. Walsh, <a href="http://www.mtsu.edu/~dwalsh/primech.html">A differentiation-based characterization of primes</a>

%H H. S. Wilf, <a href="http://dx.doi.org/10.1016/0097-3165(83)90007-9">Three problems in combinatorial asymptotics</a>, J. Combin. Theory, A 35 (1983), 199-207.

%F a(n) = n!*sum(((n/k)!*k^(n/k))^(-1)) where sum is over all divisors k of n. Exponential generating function [for a(1) through a(n)]= sum(exp(t^k/k)-1, k=1..n).

%F a(n) = (n-1)! + 1 iff n is a prime.

%e For example, a(4)=10 since, of the 24 permutations of length 4, there are 6 permutations with consist of a single 4-cycle, 3 permutations that consist of two 2-cycles and 1 permutation with four 1-cycles.

%e Also, a(7)=721 since there are 720 permutations with a single cycle of length 7 and 1 permutation with seven 1-cycles.

%p a:= n-> n!*add((d/n)^d/d!, d=numtheory[divisors](n)):

%p seq(a(n), n=1..30); # _Alois P. Heinz_, Nov 07 2012

%t Table[n! Sum[((n/d)!*d^(n/d))^(-1), {d, Divisors[n]}], {n, 21}] (* _Jean-François Alcover_, Apr 04 2011 *)

%o (Maxima) a(n):= n!*lsum((d!*(n/d)^d)^(-1),d,listify(divisors(n)));

%o makelist(a(n),n,1,40); /* _Emanuele Munarini_, Feb 03 2014 */

%Y Cf. A038041, A055225, A236696, A317329.

%Y Column k=1 of A218868.

%Y Column k=0 of A364967 (for n>=1).

%K nonn,easy,nice

%O 1,2

%A _N. J. A. Sloane_

%E Additional comments from _Dennis P. Walsh_, Dec 08 2000

%E More terms from _Vladeta Jovovic_, Dec 01 2001