A247005 -id:A247005 - 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

A247026 Number A(n,k) of endofunctions on [n] that are the k-th power of an endofunction; 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, 4, 1, 1, 1, 3, 27, 1, 1, 1, 4, 12, 256, 1, 1, 1, 3, 19, 100, 3125, 1, 1, 1, 4, 12, 116, 1075, 46656, 1, 1, 1, 3, 21, 73, 985, 13356, 823543, 1, 1, 1, 4, 10, 148, 580, 11026, 197764, 16777216, 1, 1, 1, 3, 21, 44, 1281, 5721, 145621, 3403576, 387420489, 1

Offset: 0

Alois P. Heinz, Sep 09 2014

Number of endofunctions f on [n] such that an endofunction g on [n] exists with f=g^k.

			A(3,2) = 12: (1,1,1), (1,1,3), (1,2,1), (1,2,2), (1,2,3), (1,3,3), (2,2,2), (2,2,3), (2,3,1), (3,1,2), (3,2,3), (3,3,3).
A(3,6) = 10: (1,1,1), (1,1,3), (1,2,1), (1,2,2), (1,2,3), (1,3,3), (2,2,2), (2,2,3), (3,2,3), (3,3,3).
A(4,4) = 73: (1,1,1,1), (1,1,1,4), (1,1,3,1), (1,1,3,3), ..., (4,4,1,3), (4,4,2,3), (4,4,3,4), (4,4,4,4).
Square array A(n,k) begins:
  1,      1,      1,      1,     1,      1,     1,      1, ...
  1,      1,      1,      1,     1,      1,     1,      1, ...
  1,      4,      3,      4,     3,      4,     3,      4, ...
  1,     27,     12,     19,    12,     21,    10,     21, ...
  1,    256,    100,    116,    73,    148,    44,    148, ...
  1,   3125,   1075,    985,   580,   1281,   295,   1305, ...
  1,  46656,  13356,  11026,  5721,  12942,  3136,  13806, ...
  1, 823543, 197764, 145621, 69244, 150955, 42784, 169681, ...

Columns k=0-10 give: A000012, A000312, A102687, A163859, A163860, A163861, A247053, A247054, A247055, A247056, A247057.
Rows n=0+1, 2-7 give: A000012, A103947, A103948, A103949, A102709, A103950, A247058.
Main diagonal gives A247059.
Cf. A247005 (the same for permutations).

(* This program is not suitable to compute a large number of terms. *)
nmax = 8;
f[a_][b_] /; Length[a]==Length[b] := Table[b[[a[[i]]]], {i, 1, Length[a]}];
A[n_, k_] := Nest[f[#], Range[n], k]& /@ Tuples[Range[n], {n}] // Union // Length;
Table[A[n-k, k], {n, 0, nmax}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, May 05 2019 *)

A103619 Number of permutations of n elements admitting a cube root.

Original entry on oeis.org

1, 1, 2, 4, 16, 80, 400, 2800, 22400, 181440, 1814400, 19958400, 218803200, 2844441600, 39822182400, 556972416000, 8911558656000, 151496497152000, 2579172973977600, 49004286505574400, 980085730111488000, 19584861165821952000, 430866945648082944000

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, A103620, A102687, A215716, A215717, A215718.

Column k=3 of A247005.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(`if`(irem(j, igcd(i, 3))<>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

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

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

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! + ... .

A247007 Number of permutations on [n] admitting a ninth root.

Original entry on oeis.org

1, 1, 2, 4, 16, 80, 400, 2800, 22400, 179200, 1792000, 19712000, 216832000, 2818816000, 39463424000, 552487936000, 8839806976000, 150276718592000, 2554704216064000, 48539380105216000, 970787602104320000, 19415752042086400000, 427146544925900800000, 9824370533295718400000, 225960522265801523200000, 5649013056645038080000000, 146874339472770990080000000, 3818732827816549381939200000

Offset: 0

Alois P. Heinz, Sep 09 2014

nonn

Differs from A102736 first at n=27.

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

Column k=9 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(9, 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..27);

A247006 Number of permutations on [n] admitting an eighth root.

Original entry on oeis.org

1, 1, 1, 3, 9, 45, 225, 1575, 11025, 99225, 893025, 9823275, 108056025, 1404728325, 18261468225, 273922023375, 4108832377650, 69850150420050, 1187452281465450, 22561593347843550, 428670250038780750, 9002075250814395750, 189043575317350503750

Offset: 0

Alois P. Heinz, Sep 09 2014

nonn

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

Column k=8 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(8, 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);

A247008 Number of permutations on [n] admitting a tenth root.

Original entry on oeis.org

1, 1, 1, 3, 12, 36, 126, 1386, 10248, 92232, 805896, 9862776, 107908416, 1428755328, 17338793472, 184781653056, 2707269941376, 58956779097216, 931404051946368, 18440063711701632, 369535355215842816, 8290691125502962176, 161390500012170164736

Offset: 0

Alois P. Heinz, Sep 09 2014

nonn

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

Column k=10 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(10, 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);

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

A247026 Number A(n,k) of endofunctions on [n] that are the k-th power of an endofunction; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A103619 Number of permutations of n elements admitting a cube root.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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