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

1, 2, 3, 10, 25, 176, 721, 6406, 42561, 436402, 3628801, 48073796, 479001601, 7116730336, 88966701825, 1474541093026, 20922789888001, 400160588853026, 6402373705728001, 133991603578884052, 2457732174030848001, 55735573291977790576, 1124000727777607680001

Offset

1,2

References

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

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

Links

Alois P. Heinz, Table of n, a(n) for n = 1..450

R. K. Guy, Letter to N. J. A. Sloane, Jul 1988

D. P. Walsh, Primality test based on the generating function

D. P. Walsh, A differentiation-based characterization of primes

H. S. Wilf, Three problems in combinatorial asymptotics, J. Combin. Theory, A 35 (1983), 199-207.

Formula

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

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

Example

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.
Also, a(7)=721 since there are 720 permutations with a single cycle of length 7 and 1 permutation with seven 1-cycles.

Maple

a:= n-> n!*add((d/n)^d/d!, d=numtheory[divisors](n)):
seq(a(n), n=1..30);  # Alois P. Heinz, Nov 07 2012

Mathematica

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

Prog

(Maxima) a(n):= n!*lsum((d!*(n/d)^d)^(-1), d, listify(divisors(n)));
makelist(a(n), n, 1, 40); /* Emanuele Munarini, Feb 03 2014 */

Crossrefs

Cf. A038041, A055225, A236696, A317329.

Column k=1 of A218868.

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

Sequence in context: A005158 A370608 A182926 * A211208 A303836 A238937

Adjacent sequences: A005222 A005223 A005224 * A005226 A005227 A005228

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

Additional comments from Dennis P. Walsh, Dec 08 2000

More terms from Vladeta Jovovic, Dec 01 2001

Status

approved