cp's OEIS Frontend

A003483 Number of square permutations of n elements.

%I A003483 M2931 #97 Jul 14 2024 08:42:55
%S A003483 1,1,1,3,12,60,270,1890,14280,128520,1096200,12058200,139043520,
%T A003483 1807565760,22642139520,339632092800,5237183952000,89032127184000,
%U A003483 1475427973219200,28033131491164800,543494606861606400,11413386744093734400,235075995738558374400,5406747901986842611200,126214560713084056012800
%N A003483 Number of square permutations of n elements.
%C A003483 Number of permutations p in S_n such that there exists q in S_n with q^2=p.
%C A003483 "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 A003483 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A003483 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.11.
%D A003483 H. S. Wilf, Generatingfunctionology, 3rd ed., A K Peters Ltd., Wellesley, MA, 2006, p. 157.
%H A003483 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 A003483 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 A003483 Joseph Blum, <a href="/A003483/a003483.pdf">Letters to N. J. A. Sloane, 1974</a>
%H A003483 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 A003483 Steven R. Finch, <a href="http://arxiv.org/abs/2001.00578">Errata and Addenda to Mathematical Constants</a>, p. 36.
%H A003483 Steven Finch, <a href="https://arxiv.org/abs/2111.14487">Rounds, Color, Parity, Squares</a>, arXiv:2111.14487 [math.CO], 2021.
%H A003483 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 A003483 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 A003483 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 A003483 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 A003483 Bob Smith and N. J. A. Sloane, <a href="/A003483/a003483_1.pdf">Correspondence, 1979</a>
%H A003483 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 A003483 E.g.f.: sqrt((1 + x)/(1 - x)) * Product_{k>=1} cosh( x^(2*k)/(2*k) ). [Blum, corrected].
%F A003483 a(2*n+1) = (2*n + 1)*a(2*n).
%F A003483 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 A003483 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 A003483 a(3) = 3: permutations with square roots are identity and two 3-cycles.
%p A003483 with(combinat):
%p A003483 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A003483       add(`if`(irem(i, 2)=0 and irem(j, 2)=1, 0, (i-1)!^j*
%p A003483       multinomial(n, n-i*j, i$j)/j!*b(n-i*j, i-1)), j=0..n/i)))
%p A003483     end:
%p A003483 a:= n-> b(n$2):
%p A003483 seq(a(n), n=0..30);  # _Alois P. Heinz_, Sep 08 2014
%t A003483 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 A003483 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 A003483 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 A003483 (PARI)
%o A003483 N=66; x='x+O('x^66);
%o A003483 Vec(serlaplace( sqrt((1+x)/(1-x))*prod(k=1,N, cosh(x^(2*k)/(2*k)))))
%o A003483 \\ _Joerg Arndt_, Sep 08 2014
%Y A003483 Cf. A103619 (cube root), A103620 (fourth root), A215716 (fifth root), A215717 (sixth root), A215718 (seventh root).
%Y A003483 Column k=2 of A247005.
%Y A003483 Cf. A246945, A247621.
%K A003483 nonn,easy,nice
%O A003483 0,4
%A A003483 _N. J. A. Sloane_
%E A003483 More terms from _Vladeta Jovovic_, Mar 28 2001
%E A003483 Additional comments from _Michael Somos_, Jun 27 2002
%E A003483 Minor edits by _Vaclav Kotesovec_, Sep 16 2014 and Sep 21 2014