login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003483 Number of square permutations of n elements.
(Formerly M2931)
19
1, 1, 1, 3, 12, 60, 270, 1890, 14280, 128520, 1096200, 12058200, 139043520, 1807565760, 22642139520, 339632092800, 5237183952000, 89032127184000, 1475427973219200, 28033131491164800, 543494606861606400, 11413386744093734400, 235075995738558374400, 5406747901986842611200, 126214560713084056012800 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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

"A permutation P has a square root if and only if the numbers of cycles of P that have each even length are even numbers." [Theorem 4.8.1. on p.147 from the Wilf reference]. - Joerg Arndt, Sep 08 2014

REFERENCES

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

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

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

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

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

LINKS

N. J. A. Sloane and Alois P. Heinz, Table of n, a(n) for n = 0..250 (first 101 terms from N. J. A. Sloane)

Steven R. Finch, Errata and Addenda to Mathematical Constants, p. 36.

P. Flajolet et al., A hybrid of Darboux's method and singularity analysis in combinatorial asymptotics, arXiv:math.CO/0606370, p. 18, Proposition 2.

M. R. Pournaki, On the number of even permutations with roots, The Australasian Journal of Combinatorics, Volume 45, 2009, pp. 37-42.

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

FORMULA

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

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

Asymptotics: a(n) ~ n! * sqrt(2/(n*Pi)) * e^G, where e^G = prod_{k>=1} cosh(1/(2k)) ~ 1.22177951519253683396485298445636121278881... (see A246945). - corrected by Vaclav Kotesovec, Sep 13 2014

G = Sum_{j>=1} (-1)^(j+1) * Zeta(2*j)^2 * (1-1/2^(2*j)) / (j * Pi^(2*j)). - Vaclav Kotesovec, Sep 20 2014

EXAMPLE

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

MAPLE

with(combinat):

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

      add(`if`(irem(i, 2)=0 and irem(j, 2)=1, 0, (i-1)!^j*

      multinomial(n, n-i*j, i$j)/j!*b(n-i*j, i-1)), j=0..n/i)))

    end:

a:= n-> b(n$2):

seq(a(n), n=0..30);  # Alois P. Heinz, Sep 08 2014

MATHEMATICA

max = 20; f[x_] := Sqrt[(1 + x)/(1 - x)]*  Product[ Cosh[x^(2*k)/(2*k)], {k, 1, max}]; se = Series[ f[x], {x, 0, max}]; CoefficientList[ se, x]*Range[0, max]! (* Jean-Fran├žois Alcover, Oct 05 2011, after g.f. *)

PROG

(PARI)

N=66; x='x+O('x^66);

Vec(serlaplace( sqrt((1+x)/(1-x))*prod(k=1, N, cosh(x^(2*k)/(2*k)))))

\\ Joerg Arndt, Sep 08 2014

CROSSREFS

Cf. A103619 (cube root), A103620 (fourth root), A215716 (fifth root), A215717 (sixth root), A215718 (seventh root).

Column k=2 of A247005.

Cf. A246945, A247621.

Sequence in context: A127918 A069944 A073996 * A128602 A092803 A181282

Adjacent sequences:  A003480 A003481 A003482 * A003484 A003485 A003486

KEYWORD

nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms from Vladeta Jovovic, Mar 28 2001

Additional comments from Michael Somos, Jun 27, 2002

Minor edits by Vaclav Kotesovec, Sep 16 2014 and Sep 21 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 1 12:17 EDT 2014. Contains 247510 sequences.