0,4

Number of permutations p in S_n such that there exists q in S_n with q^2=p.

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

J. Blum, Enumeration of the square permutations in S_n, J. Combin. Theory, A 17 (1974), 156-161.

Philippe Flajolet, Eric Fusy, Xavier Gourdon, Daniel Panario and Nicolas Pouyanne, A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics, arXiv:math.CO/0606370

N. Pouyanne, On the number of permutations admitting an m-th root, Electron. J. Combin., 9 (2002), #R3.

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.11.

Edward A. Bender, Asymptotic methods in enumeration, SIAM Review 16 (1974), no. 4, 485-515.

H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 148, Eq. 4.8.1.

P. Flajolet et al., A hybrid of Darboux's method and singularity analysis in combinatorial asymptotics

E.g.f.: sqrt((1+x)/(1-x))*Product_{k >= 1} cosh x^(2k)/(2k) [Blum, corrected].

a(2n+1)=(2n+1)a(2n).

Asymptotics: a(n) ~ n! 2/sqrt(n pi) e^G, where e^G = prod_{k>=1} cosh(1/(2k)) ~ 1.22178

a(3)=3: permutations with square roots are identity and two 3-cycles.

Cf. A103619 (cube root), A103620 (fourth root).

Sequence in context: A127918 A069944 A073996 this_sequence A128602 A092803 A020052

Adjacent sequences: A003480 A003481 A003482 this_sequence A003484 A003485 A003486

nonn,easy,nice

N. J. A. Sloane (njas(AT)research.att.com).

More terms from Vladeta Jovovic (vladeta(AT)eunet.rs), Mar 28 2001

Additional comments from Michael Somos, Jun 27, 2002

It would be nice to have cross-references to number of permutations admitting a cube root, etc.! - N. J. A. Sloane (njas(AT)research.att.com), Jan 11 2005