login
Number of square permutations of n elements.
(Formerly M2931)
22

%I M2931 #97 Jul 14 2024 08:42:55

%S 1,1,1,3,12,60,270,1890,14280,128520,1096200,12058200,139043520,

%T 1807565760,22642139520,339632092800,5237183952000,89032127184000,

%U 1475427973219200,28033131491164800,543494606861606400,11413386744093734400,235075995738558374400,5406747901986842611200,126214560713084056012800

%N Number of square permutations of n elements.

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

%C "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

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

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

%D H. S. Wilf, Generatingfunctionology, 3rd ed., A K Peters Ltd., Wellesley, MA, 2006, p. 157.

%H Alois P. Heinz, <a href="/A003483/b003483.txt">Table of n, a(n) for n = 0..250</a> (first 101 terms from N. J. A. Sloane)

%H Edward A. Bender, <a href="http://www.jstor.org/stable/2028691">Asymptotic methods in enumeration</a>, SIAM Review 16 (1974), no. 4, p. 509.

%H Joseph Blum, <a href="/A003483/a003483.pdf">Letters to N. J. A. Sloane, 1974</a>

%H J. Blum, <a href="https://doi.org/10.1016/0097-3165(74)90002-8">Enumeration of the square permutations in S_n</a>, J. Combin. Theory, A 17 (1974), 156-161.

%H Steven R. Finch, <a href="http://arxiv.org/abs/2001.00578">Errata and Addenda to Mathematical Constants</a>, p. 36.

%H Steven Finch, <a href="https://arxiv.org/abs/2111.14487">Rounds, Color, Parity, Squares</a>, arXiv:2111.14487 [math.CO], 2021.

%H P. Flajolet et al., <a href="http://arXiv.org/abs/math.CO/0606370">A hybrid of Darboux's method and singularity analysis in combinatorial asymptotics</a>, arXiv:math.CO/0606370, p. 18, Proposition 2.

%H Yuewen Luo, <a href="https://arxiv.org/abs/2407.07366">Counting Permutations in S_{2n} and S_{2n+1}</a>, arXiv:2407.07366 [math.CO], 2024.

%H M. R. Pournaki, <a href="http://ajc.maths.uq.edu.au/pdf/45/ajc_v45_p037.pdf">On the number of even permutations with roots</a>, The Australasian Journal of Combinatorics, Volume 45, 2009, pp. 37-42.

%H N. Pouyanne, <a href="https://doi.org/10.37236/1620">On the number of permutations admitting an m-th root</a>, Electron. J. Combin., 9 (2002), #R3.

%H Bob Smith and N. J. A. Sloane, <a href="/A003483/a003483_1.pdf">Correspondence, 1979</a>

%H H. S. Wilf, <a href="http://www.math.upenn.edu/~wilf/DownldGF.html">Generatingfunctionology</a>, 2nd edn., Academic Press, NY, 1994, p. 148, Eq. 4.8.1.

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

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

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

%F 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

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

%p with(combinat):

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

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

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

%p end:

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

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Sep 08 2014

%t 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. *)

%t multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[If[Mod[i, 2] == 0 && Mod[j, 2] == 1, 0, (i-1)!^j* multinomial[n, Join[{n-i*j}, Array[i&, j]]]/j!*b[n-i*j, i-1]], {j, 0, n/i}]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Mar 23 2015, after _Alois P. Heinz_ *)

%t a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ Sqrt[ (1 + x) / (1 - x)] Product[ Cosh[ x^k / k], {k, 2, n, 2}], {x, 0, n}]]; (* _Michael Somos_, Jul 11 2018 *)

%o (PARI)

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

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

%o \\ _Joerg Arndt_, Sep 08 2014

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

%Y Column k=2 of A247005.

%Y Cf. A246945, A247621.

%K nonn,easy,nice

%O 0,4

%A _N. J. A. Sloane_

%E More terms from _Vladeta Jovovic_, Mar 28 2001

%E Additional comments from _Michael Somos_, Jun 27 2002

%E Minor edits by _Vaclav Kotesovec_, Sep 16 2014 and Sep 21 2014