A103619 -id:A103619 - cp's OEIS frontend

A003483 Number of square permutations of n elements.

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

Offset: 0

N. J. A. Sloane

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

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

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.
H. S. Wilf, Generatingfunctionology, 3rd ed., A K Peters Ltd., Wellesley, MA, 2006, p. 157.

Alois P. Heinz, Table of n, a(n) for n = 0..250 (first 101 terms from N. J. A. Sloane)
Edward A. Bender, Asymptotic methods in enumeration, SIAM Review 16 (1974), no. 4, p. 509.
Joseph Blum, Letters to N. J. A. Sloane, 1974
J. Blum, Enumeration of the square permutations in S_n, J. Combin. Theory, A 17 (1974), 156-161.
Steven R. Finch, Errata and Addenda to Mathematical Constants, p. 36.
Steven Finch, Rounds, Color, Parity, Squares, arXiv:2111.14487 [math.CO], 2021.
P. Flajolet et al., A hybrid of Darboux's method and singularity analysis in combinatorial asymptotics, arXiv:math.CO/0606370, p. 18, Proposition 2.
Yuewen Luo, Counting Permutations in S_{2n} and S_{2n+1}, arXiv:2407.07366 [math.CO], 2024.
M. R. Pournaki, On the number of even permutations with roots, The Australasian Journal of Combinatorics, Volume 45, 2009, pp. 37-42.
N. Pouyanne, On the number of permutations admitting an m-th root, Electron. J. Combin., 9 (2002), #R3.
Bob Smith and N. J. A. Sloane, Correspondence, 1979
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 148, Eq. 4.8.1.

Cf. A103619 (cube root), A103620 (fourth root), A215716 (fifth root), A215717 (sixth root), A215718 (seventh root).
Column k=2 of A247005.
Cf. A246945, A247621.

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

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

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

E.g.f.: sqrt((1 + x)/(1 - x)) * Product_{k>=1} cosh( x^(2*k)/(2*k) ). [Blum, corrected].
a(2*n+1) = (2*n + 1)*a(2*n).
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
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

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

A247005 Number A(n,k) of permutations on [n] that are the k-th power of a permutation; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 6, 1, 1, 1, 2, 3, 24, 1, 1, 1, 1, 4, 12, 120, 1, 1, 1, 2, 3, 16, 60, 720, 1, 1, 1, 1, 6, 9, 80, 270, 5040, 1, 1, 1, 2, 1, 24, 45, 400, 1890, 40320, 1, 1, 1, 1, 6, 4, 96, 225, 2800, 14280, 362880, 1, 1, 1, 2, 3, 24, 40, 576, 1575, 22400, 128520, 3628800, 1

Offset: 0

Alois P. Heinz, Sep 09 2014

Number of permutations p on [n] such that a permutation q on [n] exists with p=q^k.

			A(3,0) = 1: (1,2,3).
A(3,1) = 6: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
A(3,2) = 3: (1,2,3), (2,3,1), (3,1,2).
A(3,3) = 4: (1,2,3), (1,3,2), (2,1,3), (3,2,1).
Square array A(n,k) begins:
  1,    1,    1,    1,    1,    1,    1,    1,    1, ...
  1,    1,    1,    1,    1,    1,    1,    1,    1, ...
  1,    2,    1,    2,    1,    2,    1,    2,    1, ...
  1,    6,    3,    4,    3,    6,    1,    6,    3, ...
  1,   24,   12,   16,    9,   24,    4,   24,    9, ...
  1,  120,   60,   80,   45,   96,   40,  120,   45, ...
  1,  720,  270,  400,  225,  576,  190,  720,  225, ...
  1, 5040, 1890, 2800, 1575, 4032, 1330, 4320, 1575, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
William Y. C. Chen and Elena L. Wang, r-Enriched Permutations and an Inequality of Bóna-McLennan-White, arXiv:2502.04136 [math.CO], 2025. See pp. 3, 14.
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, Theorem 4.8.2.

Columns k=0-10 give: A000012, A000142, A003483, A103619, A103620, A215716, A215717, A215718, A247006, A247007, A247008.
Main diagonal gives A247009.
Cf. A247026 (the same for endofunctions), A155510.

with(combinat): with(numtheory): with(padic):
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      `if`(irem(j, mul(p^ordp(k, p), p=factorset(i)))=0, (i-1)!^j*
      multinomial(n, n-i*j, i$j)/j!*b(n-i*j, i-1, k), 0), j=0..n/i)))
    end:
A:= (n, k)-> `if`(k=0, 1, b(n$2, k)):
seq(seq(A(n, d-n), n=0..d), d=0..14);

multinomial[n_, k_List] := n!/Times @@ (k!); b[, 1, ] = 1; b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[If[Mod[j, Product[ p^IntegerExponent[k, p], {p, FactorInteger[i][[All, 1]]}]] == 0, (i - 1)!^j*multinomial[n, Join[{n-i*j}, Array[i&, j]]]/j!*b[n-i*j, i-1, k], 0], {j, 0, n/i}]]]; A[n_, k_] := If[k == 0, 1, b[n, n, k]]; Table[A[n, d - n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jan 14 2017, after Alois P. Heinz *)

A103620 Number of permutations of n elements admitting a fourth root.

Original entry on oeis.org

1, 1, 1, 3, 9, 45, 225, 1575, 11130, 100170, 897750, 9875250, 108523800, 1410809400, 18332414100, 274986211500, 4127136413400, 70161319027800, 1192076391706200, 22649451442417800, 430247983427262000, 9035207651972502000

Offset: 0

Vladeta Jovovic, Feb 11 2005

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..250
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 149, Eq. 4.8.2.

Cf. A003483, A103619, A102687, A215716, A215717, A215718.

Column k=4 of A247005.

with(combinat): with(numtheory): with(padic):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      `if`(irem(j, mul(p^ordp(4, p), p=factorset(i)))=0, (i-1)!^j*
      multinomial(n, n-i*j, i$j)/j!*b(n-i*j, i-1), 0), j=0..n/i)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..25);  # Alois P. Heinz, Sep 09 2014

CoefficientList[Series[((1+x)/(1-x))^(1/2) * Product[1/2*Cos[1/2*x^(2*m)/m] + 1/2*Cosh[1/2*x^(2*m)/m],{m,1,20}],{x,0,20}],x] * Range[0,20]! (* Vaclav Kotesovec, Sep 13 2014 *)

E.g.f.: ((1+x)/(1-x))^(1/2)*Product(1/2*cos(1/2*x^(2*m)/m)+1/2*cosh(1/2*x^(2*m)/m), m = 1 .. infinity).

A215716 Number of permutations on n points admitting a fifth root.

Original entry on oeis.org

1, 1, 2, 6, 24, 96, 576, 4032, 32256, 290304, 2612736, 28740096, 344881152, 4483454976, 62768369664, 878757175296, 14060114804736, 239021951680512, 4302395130249216, 81745507474735104, 1553164642019966976, 32616457482419306496, 717562064613224742912

Offset: 0

Eric M. Schmidt, Aug 22 2012

nonn

a(n) is the number of permutations of n points such that for all positive m, the number of (5m)-cycles is a multiple of 5.

Eric M. Schmidt, Table of n, a(n) for n = 0..200
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 148-149, Thms. 4.8.2 and 4.8.3.

Cf. A003483, A103619, A103620, A215717, A215718.

Column k=5 of A247005.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(`if`(irem(j, igcd(i, 5))<>0, 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..25);  # Alois P. Heinz, Sep 08 2014

multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[If[Mod[j, GCD[i, 5]] != 0, 0, (i-1)!^j*multinomial[n, Prepend[Table[i, {j}], n-i*j]]/j!*b[n-i*j, i-1]], {j, 0, n/i}]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Oct 21 2016, after Alois P. Heinz *)

{ A215716_list(numterms) = Vec(serlaplace((1 - x^5 + O(x^numterms))^(1/5)/(1-x) * prod(m=1, numterms\5, exp5(x^(5*m)/(5*m), numterms\(5*m)+1)))); }
{ exp5(y, prec) = subst(serconvol(exp(x + O(x^prec)), 1/(1-x^5) + O(x^prec)), x, y); }

E.g.f.: (1 - x^5)^(1/5)/(1 - x) * Product(E_5(x^(5m)/(5m)), m = 1 .. infinity), where E_5(x) = 1 + x^5/5! + x^10/10! + ... .

A215717 Number of permutations on n points admitting a sixth root.

Original entry on oeis.org

1, 1, 1, 1, 4, 40, 190, 1330, 8680, 52920, 340200, 6237000, 76211520, 1098857760, 11677585920, 109679169600, 1497396700800, 41977644508800, 783593969558400, 15973899557616000, 263524120417958400, 3733362595368806400, 64262934423790502400

Offset: 0

Eric M. Schmidt, Aug 23 2012

nonn

a(n) is the number of permutations of n points such that for all positive m, the number of m-cycles is a multiple of gcd(m, 6).

Eric M. Schmidt, Table of n, a(n) for n = 0..200
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 148-149, Thms. 4.8.2 and 4.8.3.

Cf. A003483, A103619, A103620, A215716, A215718.

Column k=6 of A247005.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(`if`(irem(j, igcd(i, 6))<>0, 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..25);  # Alois P. Heinz, Sep 08 2014

multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[If[Mod[j, GCD[i, 6]] != 0, 0, (i-1)!^j*multinomial[n, Prepend[Table[i, {j}], n-i*j]]/j!*b[n-i*j, i - 1]], {j, 0, n/i}]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Oct 21 2016, after Alois P. Heinz *)

{ A215717_list(numterms) = Vec(serlaplace(prod(m=1, numterms, expthin(gcd(m, 6), x^m/m, numterms\m+1))) + O(x^numterms)); }
{ expthin(j, y, prec) = subst(serconvol(exp(x + O(x^prec)), 1/(1-x^j) + O(x^prec)), x, y); }

E.g.f.: prod(m>=1, E_(gcd(m,6))(x^m/m) ), where E_j(x) = 1 + x^j/j! + x^(2j)/(2j)! + ... .

A215718 Number of permutations on n points admitting a seventh root.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 4320, 34560, 311040, 3110400, 34214400, 410572800, 5337446400, 69386803200, 1040802048000, 16652832768000, 283098157056000, 5095766827008000, 96819569713152000, 1936391394263040000, 38727827885260800000, 852012213475737600000

Offset: 0

Eric M. Schmidt, Aug 23 2012

nonn

a(n) is the number of permutations of n points such that for all positive m, the number of (7*m)-cycles is a multiple of 7.

Eric M. Schmidt, Table of n, a(n) for n = 0..200
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 148-149, Thms. 4.8.2 and 4.8.3.

Cf. A003483, A103619, A103620, A215716, A215717.

Column k=7 of A247005.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(`if`(irem(j, igcd(i, 7))<>0, 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..25);  # Alois P. Heinz, Sep 08 2014

multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[If[Mod[j, GCD[i, 7]] != 0, 0, (i-1)!^j*multinomial[n, Prepend[Table[i, {j}], n-i*j]]/j!*b[n-i*j, i - 1]], {j, 0, n/i}]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Oct 21 2016, after Alois P. Heinz *)

{ A215718_list(numterms) = Vec(serlaplace((1 - x^7 + O(x^numterms))^(1/7)/(1-x) * prod(m=1, numterms\7, exp7(x^(7*m)/(7*m), numterms\(7*m)+1)))); }
{ exp7(y, prec) = subst(serconvol(exp(x + O(x^prec)), 1/(1-x^7) + O(x^prec)), x, y); }

E.g.f.: ((1 - x^7)^(1/7)/(1 - x)) * Product_{m>=1} E_7(x^(7*m)/(7*m)), where E_7(x) = 1 + x^7/7! + x^14/14! + ... .

A155510 Possible cardinalities of the set of all k-th powers of the order n permutations, where k and n are some positive integers.

Original entry on oeis.org

1, 2, 3, 4, 6, 9, 12, 16, 21, 24, 25, 36, 40, 45, 46, 56, 60, 80, 81, 96, 106, 120, 126, 145, 190, 225, 256, 270, 351, 400, 505, 576, 610, 666, 720, 721, 826, 855, 946, 1071, 1072, 1170, 1225, 1233, 1330, 1338, 1345, 1386, 1450, 1575, 1576, 1792, 1890, 2080, 2241

Offset: 1

Vladimir Letsko, Jan 23 2009

nonn

			80 is in the sequence because the set {a^3|a in S_5} has 80 elements.

Vladimir Letsko, Mathematical Marathon at VSPU, Problem 100 (in Russian)
Vladimir Letsko, Mathematical Marathon at dxdy (in Russian)

Set of elements of A247005.

Cf. A000012, A000142, A003483, A103619, A103620, A215716, A215717, A215718, A247006, A247007, A247008, A247009.

Corrected and extended by Max Alekseyev, Feb 08 2009

Some missing terms added by Max Alekseyev, Jan 24 2010

A348191 Triangular array read by rows: T(n,k) is the number of cubic n-permutations possessing exactly k cycles; n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 0, 3, 1, 0, 6, 3, 6, 1, 0, 24, 30, 15, 10, 1, 0, 0, 234, 105, 45, 15, 1, 0, 720, 504, 1134, 315, 105, 21, 1, 0, 5040, 7020, 5292, 3969, 840, 210, 28, 1, 0, 0, 89424, 48572, 29484, 11529, 2016, 378, 36, 1, 0, 362880, 299376, 724140, 275120, 118125, 29673, 4410, 630, 45, 1

Offset: 0

Steven Finch, Nov 27 2021

A permutation p in S_n is a cube if there exists q in S_n with q^3=p.

			The four cubic 3-permutations are (1, 2, 3) with three cycles (fixed points) and (1, 3, 2), (3, 2, 1) & (2, 1, 3), each with two cycles (a fixed point & a transposition).
Triangle begins:
[0]  1;
[1]  0,   1;
[2]  0,   1,   1;
[3]  0,   0,   3,    1;
[4]  0,   6,   3,    6,   1;
[5]  0,  24,  30,   15,  10,   1;
[6]  0,   0, 234,  105,  45,  15,  1;
[7]  0, 720, 504, 1134, 315, 105, 21, 1;

Alois P. Heinz, Rows n = 0..150, flattened

Columns k=0-1 give: A000007, |A194770|.
Row sums give A103619.
Cf. A246948.

with(combinat):
b:= proc(n, i) option remember; expand(`if`(n=0, 1, `if`(i<1, 0,
      add(`if`(irem(j, igcd(i, 3))<>0, 0, x^j*(i-1)!^j*
      multinomial(n, n-i*j, i$j)/j!*b(n-i*j, i-1)), j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n$2)):
seq(T(n), n=0..10);  # Alois P. Heinz, Nov 30 2021

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = Expand[If[n == 0, 1, If[i<1, 0,
     Sum[If[Mod[j, GCD[i, 3]] != 0, 0, x^j*(i-1)!^j*multinomial[n,
     Join[{n-i*j}, Table[i, {j}]]]/j!*b[n-i*j, i-1]], {j, 0, n/i}]]]];
T[n_] := With[{p = b[n, n]}, Table[Coefficient[p, x, i], {i, 0, n}]];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Dec 28 2021, after Alois P. Heinz *)

More terms from Alois P. Heinz, Nov 30 2021

cp's OEIS Frontend

A003483 Number of square permutations of n elements.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A247005 Number A(n,k) of permutations on [n] that are the k-th power of a permutation; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A103620 Number of permutations of n elements admitting a fourth root.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A215716 Number of permutations on n points admitting a fifth root.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A215717 Number of permutations on n points admitting a sixth root.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A215718 Number of permutations on n points admitting a seventh root.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A155510 Possible cardinalities of the set of all k-th powers of the order n permutations, where k and n are some positive integers.

Views

Author

Keywords

Examples

Links

Crossrefs