A002619 -id:A002619 - cp's OEIS frontend

A064852 Number of orbits in A002619 consisting of n permutations.

1, 0, 0, 1, 4, 18, 102, 624, 4476, 36248, 329890, 3326054, 36846276, 444783906, 5811885808, 81729607680, 1230752346352, 19760412095328, 336967037143578, 6082255011151724, 115852476579789984, 2322315553090615850, 48869596859895986086, 1077167364116800207968

Offset: 1

Michael Steyer (m.steyer(AT)osram.de), Oct 06 2001

Also, the number of aperiodic oriented cycles on n nodes up to rotation of the nodes. See A324513 for illustrations of aperiodic undirected cycles. - Andrew Howroyd, Aug 16 2019

			n=6: The orbit {(124635)(235146)(346251)(451362)(562413)(613524)} consists of 6 single permutations.

Harry J. Smith, Table of n, a(n) for n = 1..100

Cf. A000010, A002619, A008683, A047918, A324513.

a[n_] := Sum[ MoebiusMu[n/k] * EulerPhi[n/k] * (n/k)^k * (k!/n^2), {k, Divisors[n]}]; Table[a[n], {n, 1, 22}] (* Jean-François Alcover, Jun 26 2012, after PARI *)

for(n=1,23,print(sumdiv(n,d,moebius(n/d)*eulerphi(n/d)*(n/d)^d*d!/n^2)))

{ for (n=1, 100, a=sumdiv(n, d, moebius(n/d)*eulerphi(n/d)*(n/d)^d*d!/n^2); write("b064852.txt", n, " ", a) ) } \\ Harry J. Smith, Sep 28 2009

a(n) = Sum_{k|n} mu(n/k)*phi(n/k)*(n/k)^k*k!/n^2 = A047918(n, n)/n^2.

Corrected and extended by Jason Earls and Vladeta Jovovic, Oct 08 2001

A349225 Numbers k such that k | A002619(k).

Original entry on oeis.org

1, 6, 8, 19, 28, 30, 80, 93, 119, 126, 136, 156, 186, 192, 205, 312, 351, 384, 448, 483, 567, 774, 820, 896, 945, 1081, 1100, 1187, 1240, 1375, 1464, 2268, 2628, 2720, 2898, 3197, 3744, 3840, 4544, 4992, 5079, 6200, 6567, 7296, 7832, 9184, 12288, 12636, 16578

Offset: 1

Amiram Eldar, Nov 11 2021

nonn

Chao (1982) proved that k | Sum_{d|k} phi(d)^2*d^(k/d-1)*(k/d-1)! for all k. The quotients are A002619(k). This sequence consists of numbers k such that this sum is divisible by k^2.

There are terms k such that k^2 | A002619(k): 1, 8, 1081, ...

			6 is a term since A002619(6) = 24 is divisible by 6.

József Sándor and Borislav Crstici, Handbook of Number theory II, Kluwer Academic Publishers, 2004, Chapter 3, p. 192.

Amiram Eldar, Table of n, a(n) for n = 1..200
Chong-Yun Chao, Generalizations of theorems of Wilson, Fermat and Euler, Journal of Number Theory, Vol. 15, No. 1 (1982), pp. 95-114.

Cf. A000010 (phi), A002619.

f[n_] := DivisorSum[n, EulerPhi[#]^2 * #^(n/#) * (n/#)! &]/n^2; Select[Range[1000], Divisible[f[#], #] &]

from itertools import count, islice
from sympy import divisors, totient, factorial
def A349225_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n:not sum(totient(m:=n//d)**2*factorial(d)*m**d for d in divisors(n,generator=True)) % n**3, count(max(startvalue,1)))
A349225_list = list(islice(A349225_gen(),10)) # Chai Wah Wu, Nov 07 2022

A002618 a(n) = n*phi(n).

Original entry on oeis.org

1, 2, 6, 8, 20, 12, 42, 32, 54, 40, 110, 48, 156, 84, 120, 128, 272, 108, 342, 160, 252, 220, 506, 192, 500, 312, 486, 336, 812, 240, 930, 512, 660, 544, 840, 432, 1332, 684, 936, 640, 1640, 504, 1806, 880, 1080, 1012, 2162, 768, 2058, 1000

Offset: 1

N. J. A. Sloane

Also Euler phi function of n^2.
For n >= 3, a(n) is also the size of the automorphism group of the dihedral group of order 2n. This automorphism group is isomorphic to the group of transformations x -> ax + b, where a, b and x are integers modulo n and a is coprime to n. Its order is n*phi(n). - Ola Veshta (olaveshta(AT)my-deja.com), Mar 18 2001
Order of metacyclic group of polynomial of degree n. - Artur Jasinski, Jan 22 2008
It appears that this sequence gives the number of permutations of 1, 2, 3, ..., n that are arithmetic progressions modulo n. - John W. Layman, Aug 27 2008
The conjecture by Layman is correct. Obviously any such permutation must have an increment that is prime to n, and almost as obvious that any such increment will work, with any starting value; hence phi(n) * n total. - Franklin T. Adams-Watters, Jun 09 2009
Consider the numbers from 1 to n^2 written line by line as an n X n square: a(n) = number of numbers that are coprime to all their horizontal and vertical immediate neighbors. - Reinhard Zumkeller, Apr 12 2011
n -> a(n) is injective: a(m) = a(n) implies m = n. - Franz Vrabec, Dec 12 2012 (See Mathematics Stack Exchange link for a proof.)
a(p) = p*(p-1) a pronic number, see A036689 and A002378. - Fred Daniel Kline, Mar 30 2015
Conjecture: All the rational numbers Sum_{i=j..k} 1/a(i) with 0 < min{2,k} <= j <= k have pairwise distinct fractional parts. - Zhi-Wei Sun, Sep 24 2015
From Jianing Song, Aug 25 2023: (Start)
a(n) is the order of the holomorph (see the Wikipedia link) of the cyclic group of order n. Note that Hol(C_n) and Aut(D_{2n}) are isomorphic unless n = 2, where D_{2n} is the dihedral group of order 2*n. See the Wordpress link.
The odd-indexed terms form a subsequence of A341298: the holomorph of an abelian group of odd order is a complete group. See Theorem 3.2, Page 618 of the W. Peremans link. (End)

			a(4) = 8 since phi(4) = 2 and 4 * 2 = 8.
a(5) = 20 since phi(5) = 4 and 5 * 4 = 20.

Peter Giblin, Primes and Programming: An Introduction to Number Theory with Computing. Cambridge: Cambridge University Press (1993) p. 116, Exercise 1.10.
J. L. Lagrange, Oeuvres, Vol. III Paris 1869.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Michael De Vlieger, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Daniel Fischer, answer to Injectivity of the function n times the Euler Totient of n, Mathematics Stack Exchange, October 2013.
Mikhail R. Gabdullin and Vitalii V. Iudelevich, Numbers of the form kf(k), arXiv:2201.09287 [math.NT] (2022).
Dmitry Krachun and Zhi-Wei Sun, Each positive rational number has the form phi(m^2)/phi(n^2), arXiv:2001.03736 [math.HO], 2020. See also The American Mathematical Monthly (2020) Vol. 127, Issue 9, 847-849.
F. Luca and A. O. Munagi, The number of permutations which form arithmetic progressions modulo m, Annals of the Alexandru Ioan Cuza University, 2014, DOI: 10.2478/aicu-2014-0053. [Broken link]
C. L. Mallows and N. J. A. Sloane, Notes on A002618, A002619, etc.
W. Peremans, Completeness of Holomorphs, Nederl. Akad. Wetensch. Indag. Math. Proc. Ser. A, 60. (1957) 608-619.
N. J. A. Sloane, Notes on A002618, A002619, etc.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61. [Annotated scanned copy. Note that the scanned pages are out of order]
Wikipedia, Holomorph.
Wordpress, Automorphisms of dihedral groups.

First column of A047916.
Cf. A002619, A011755 (partial sums), A047918, A000010, A053650, A053191, A053192, A036689, A058161, A009262, A082473 (same terms, sorted into ascending order), A256545, A327172 (a left inverse), A327173, A065484.
Subsequence of A323333.

a002618 n = a000010 n * n  -- Reinhard Zumkeller, Dec 21 2012

[n*EulerPhi(n): n in [1..150]]; // Vincenzo Librandi, Apr 04 2011

with(numtheory):a:=n->phi(n^2): seq(a(n), n=1..50); # Zerinvary Lajos, Oct 07 2007

Table[n EulerPhi[n], {n, 100}] (* Artur Jasinski, Jan 22 2008 *)

numlib::phi(n^2)$ n=1..81 // Zerinvary Lajos, May 13 2008

a(n)=n*eulerphi(n) \\ Charles R Greathouse IV, Nov 20 2012

from sympy import totient as phi
def a(n): return n*phi(n)
print([a(n) for n in range(1, 51)]) # Michael S. Branicky, Mar 16 2022

[euler_phi(n^2) for n in range(1,51)] # Zerinvary Lajos, Jun 06 2009

Multiplicative with a(p^e) = (p-1)*p^(2e-1). - David W. Wilson, Aug 01 2001
Dirichlet g.f.: zeta(s-2)/zeta(s-1). - R. J. Mathar, Feb 09 2011
a(n) = A173557(n) * A102631(n). - R. J. Mathar, Mar 30 2011
From Wolfdieter Lang, May 12 2011: (Start)
a(n)/2 = A023896(n), n >= 2.
a(n)/2 = (1/n) * Sum_{k=1..n-1, gcd(k,n)=1} k, n >= 2 (see A023896 and A076512/A109395). (End)
a(n) = lcm(phi(n^2),n). - Enrique Pérez Herrero, May 11 2012
a(n) = phi(n^2). - Wesley Ivan Hurt, Jun 16 2013
a(n) = A009195(n) * A009262(n). - Michel Marcus, Oct 24 2013
G.f.: -x + 2*Sum_{k>=1} mu(k)*k*x^k/(1 - x^k)^3. - Ilya Gutkovskiy, Jan 03 2017
a(n) = A082473(A327173(n)), A327172(a(n)) = n. -- Antti Karttunen, Sep 29 2019
Sum_{n>=1} 1/a(n) = 2.203856... (A065484). - Amiram Eldar, Sep 30 2019
Define f(x) = #{n <= x: a(n) <= x}. Gabdullin & Iudelevich show that f(x) ~ c*sqrt(x) for c = Product_{p prime} (1 + 1/(p*(p - 1 + sqrt(p^2 - p)))) = 1.3651304521525857... - Charles R Greathouse IV, Mar 16 2022
a(n) = Sum_{d divides n} A001157(d)*A046692(n/d); that is, the Dirichlet convolution of sigma_2(n) and the Dirichlet inverse of sigma_1(n). - Peter Bala, Jan 26 2024

Better description from Labos Elemer, Feb 18 2000

A000939 Number of inequivalent n-gons.

Original entry on oeis.org

1, 1, 1, 2, 4, 14, 54, 332, 2246, 18264, 164950, 1664354, 18423144, 222406776, 2905943328, 40865005494, 615376173184, 9880209206458, 168483518571798, 3041127561315224, 57926238289970076, 1161157777643184900, 24434798429947993054, 538583682082245127336

Offset: 1

N. J. A. Sloane

Here two n-gons are said to be equivalent if they differ in starting point, orientation, or by a rotation (but not by a reflection - for that see A000940).

Number of cycle necklaces on n vertices, defined as equivalence classes of (labeled, undirected) Hamiltonian cycles under rotation of the vertices. The path version is A275527. - Gus Wiseman, Mar 02 2019

			Possibilities for n-gons without distinguished vertex can be encoded as permutation classes of vertices, two permutations being equivalent if they can be obtained from each other by circular rotation, translation mod n or complement to n+1.
n=3: 123.
n=4: 1234, 1243.
n=5: 12345, 12354, 12453, 13524.
n=6: 123456, 123465, 123564, 123645, 123654, 124365, 124635, 124653, 125364, 125463, 125634, 126435, 126453, 135264.

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

Georg Fischer, Table of n, a(n) for n = 1..450 (first 100 terms by T. D. Noe)
S. W. Golomb and L. R. Welch, On the enumeration of polygons, Amer. Math. Monthly, 67 (1960), 349-353.
S. W. Golomb and L. R. Welch, On the enumeration of polygons, Amer. Math. Monthly, 67 (1960), 349-353. [Annotated scanned copy]
Samuel Herman and Eirini Poimenidou, Orbits of Hamiltonian Paths and Cycles in Complete Graphs, arXiv:1905.04785 [math.CO], 2019.
A. Stoimenow, Enumeration of chord diagrams and an upper bound for Vassiliev invariants, J. Knot Theory Ramifications, 7 (1998), no. 1, 93-114.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Wikipedia, Hamiltonian path.
Wikipedia, Polygon.
Gus Wiseman, Inequivalent representatives of the a(6) = 14 cycle necklaces.
Gus Wiseman, Inequivalent representatives of the a(7) = 54 n-gons.

Cf. A000940. Bisections give A094154, A094155.
For star polygons see A231091.
Cf. A000031, A002619, A002866, A006125, A008965, A059966, A060223, A192332, A275527, A323858, A323870, A324461.

with(numtheory):
# for n odd:
Ed:= proc(n) local t1, d; t1:=0; for d from 1 to n do
       if n mod d = 0 then t1:= t1+phi(n/d)^2*d!*(n/d)^d fi od:
       t1/(2*n^2)
     end:
# for n even:
Ee:= proc(n) local t1, d; t1:= 2^(n/2)*(n/2)*(n/2)!; for d
       from 1 to n do if n mod d = 0 then t1:= t1+
       phi(n/d)^2*d!*(n/d)^d; fi od: t1/(2*n^2)
     end:
A000939:= n-> if n mod 2 = 0 then ceil(Ee(n)) else ceil(Ed(n)); fi:
seq(A000939(n), n=1..25);

a[n_] := (t = If[OddQ[n], 0, 2^(n/2)*(n/2)*(n/2)!]; Do[If[Mod[n, d]==0, t = t+EulerPhi[n/d]^2*d!*(n/d)^d], {d, 1, n}]; t/(2*n^2)); a[1] := 1; a[2] := 1; Print[a /@ Range[1, 450]] (* Jean-François Alcover, May 19 2011, after Maple prog. *)
rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
Table[Length[Select[Union[Sort[Sort/@Partition[#,2,1,1]]&/@Permutations[Range[n]]],#==First[Sort[Table[Nest[rotgra[#,n]&,#,j],{j,n}]]]&]],{n,8}] (* Gus Wiseman, Mar 02 2019 *)

a(n)={if(n<3, n>=0, (if(n%2, 0, (n/2-1)!*2^(n/2-2)) + sumdiv(n, d, eulerphi(n/d)^2 * d! * (n/d)^d)/n^2)/2)} \\ Andrew Howroyd, Aug 17 2019

For formula see Maple lines.
a(2*n + 1) =  A002619(2*n + 1)/2 for n > 0; a(2*n) = (A002619(2*n) + A002866(n-1))/2 for n > 1. - Andrew Howroyd, Aug 17 2019
a(n) ~ sqrt(2*Pi)/2 * n^(n-3/2) / e^n. - Ludovic Schwob, Nov 03 2022

More terms from Pab Ter (pabrlos(AT)yahoo.com), May 05 2004

Added a(1) = 1 and a(2) = 1 by Gus Wiseman, Mar 02 2019

A000940 Number of n-gons with n vertices.

Original entry on oeis.org

1, 2, 4, 12, 39, 202, 1219, 9468, 83435, 836017, 9223092, 111255228, 1453132944, 20433309147, 307690667072, 4940118795869, 84241805734539, 1520564059349452, 28963120073957838, 580578894859915650, 12217399235411398127, 269291841184184374868, 6204484017822892034404

Offset: 3

N. J. A. Sloane

Number of inequivalent undirected Hamiltonian cycles in complete graph on n labeled nodes under action of dihedral group of order 2n acting on nodes.

			Label the vertices of a regular n-gon 1,2,...,n.
For n=3,4,5 representatives for the polygons counted here are:
  (1,2,3,1),
  (1,2,3,4,1), (1,2,4,3,1),
  (1,2,3,4,5,1), (1,2,3,5,4,1), (1,2,4,5,3,1), (1,3,5,2,4,1).
For n=6:
  (1,2,3,4,5,6,1), (1,2,3,4,6,5,1), (1,2,3,5,6,4,1),
  (1,2,3,6,5,4,1), (1,2,4,3,6,5,1), (1,2,4,6,3,5,1),
  (1,2,4,6,5,3,1), (1,2,5,3,6,4,1), (1,2,5,4,6,3,1),
  (1,2,5,6,3,4,1), (1,2,6,4,5,3,1), (1,3,5,2,6,4,1).

J. H. Kwak and J. Lee, Enumeration of graph coverings, surface branched coverings and related group theory, in Combinatorial and Computational Mathematics (Pohang, 2000), ed. S. Hong et al., World Scientific, Singapore 2001, pp. 97-161.
R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Ludovic Schwob, Table of n, a(n) for n = 3..500 (terms 3..100 from T. D. Noe).
S. W. Golomb and L. R. Welch, On the enumeration of polygons, Amer. Math. Monthly, 67 (1960), 349-353.
S. W. Golomb and L. R. Welch, On the enumeration of polygons, Amer. Math. Monthly, 67 (1960), 349-353. [Annotated scanned copy]
Samuel Herman and Eirini Poimenidou, Orbits of Hamiltonian Paths and Cycles in Complete Graphs, arXiv:1905.04785 [math.CO], 2019.
E. M. Palmer and R. W. Robinson, Enumeration under two representations of the wreath product, Acta Math., 131 (1973), 123-143.
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence, except he has a(6)=7 instead of 12)
R. C. Read, Letter to N. J. A. Sloane, 1992
R. C. Read, Combinatorial problems in theory of music, Discrete Math. 167 (1997), 543-551.
Ludovic Schwob, On the enumeration of double cosets and self-inverse double cosets, arXiv:2506.04007 [math.CO], 2025. See p. 9.
N. J. A. Sloane, Illustration of initial terms [Annotated page from Golomb-Welch article]
Venta Terauds and J. Sumner, Circular genome rearrangement models: applying representation theory to evolutionary distance calculations, arXiv preprint arXiv:1712.00858 [q-bio.PE], 2017.
Venta Terauds and Jeremy Sumner, A new algebraic approach to genome rearrangement models, arXiv:2012.11665 [q-bio.PE], 2020.

Cf. A000939, A007619. Bisections give A094156, A094157.

For permutation classes under various symmetries see A089066, A262480, A002619.

with(numtheory);
# for n odd:
Sd:=proc(n) local t1,d; t1:=2^((n-1)/2)*n^2*((n-1)/2)!; for d from 1 to n do if n mod d = 0 then t1:=t1+phi(n/d)^2*d!*(n/d)^d; fi; od: t1/(4*n^2); end;
# for n even:
Se:=proc(n) local t1,d; t1:=2^(n/2)*n*(n+6)*(n/2)!/4; for d from 1 to n do if n mod d = 0 then t1:=t1+phi(n/d)^2*d!*(n/d)^d; fi; od: t1/(4*n^2); end;
A000940:=n-> if n mod 2 = 0 then Se(n) else Sd(n); fi;

a[n_] := (t1 = If[OddQ[n], 2^((n - 1)/2)*n^2*((n - 1)/2)!, 2^(n/2)*n*(n + 6)*(n/2)!/4]; For[ d = 1 , d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[n/d]^2*d!*(n/d)^d]]; t1/(4*n^2)); Table[a[n], {n, 3, 25}] (* Jean-François Alcover, Jun 19 2012, after Maple *)

a(n)={if(n<3, 0, (2^(n\2-2)*(n\2)!*n*if(n%2, 4*n, n + 6) + sumdiv(n, d, eulerphi(n/d)^2*d!*(n/d)^d))/(4*n^2))} \\ Andrew Howroyd, Sep 09 2018

from sympy import factorial, divisors, totient
def A000940(n): return 1 if n == 3 else ((sum(totient(m:=n//d)**2*factorial(d)*m**d for d in divisors(n,generator=True))+(1<<(k:=n>>1)-2)*n*(n<<2 if n&1 else (n+6))*factorial(k))>>2)//n//n # Chai Wah Wu, Nov 07 2022

For formula see Maple lines.
a(p) = ((((p-1)! + 1)/p) + p - 2 + (2^((p-1)/2)*((p-1)/2)!))/4 for prime p. See A007619. - Ian Mooney, Oct 05 2022
a(n) ~ sqrt(2*Pi)/4 * n^(n-3/2) / e^n. - Ludovic Schwob, Nov 03 2022

More terms from Pab Ter (pabrlos(AT)yahoo.com), May 05 2004

A275527 Number of distinct classes of permutations of length n under reversal and complement to n+1.

Original entry on oeis.org

1, 1, 1, 4, 12, 64, 360, 2544, 20160, 181632

Offset: 1

Olivier Gérard, Jul 31 2016

Let us consider two permutations to be equivalent if they can be obtained from each other by cyclic rotation (12345->(23451,34512,45123,51234) or n+1-complement (31254->35412), or a combination of those two transformations (they commute with each other). a(n) is the number of classes.
We obtain the same number of classes if the transformations are (addition of a constant modulo n and reversal (12345->54321)) but not the same set of representatives.
It seems probable that a(2n+1) = (2n)!/2
This sequence may be related to A113247 (and A113248) as they share a common dissection 1, 4, 64, 2544, 181632. The fact that they count permutation classes for the major index is a further indication.
Number of path necklaces, defined as equivalence classes of (labeled, undirected) Hamiltonian paths under rotation of the vertices. The cycle version is A000939. - Gus Wiseman, Mar 02 2019

			Examples of permutation representatives. The representative is chosen to be the first of the class in lexicographic order.
n=4 case addition mod n and reversal
1234, 1243, 1324, 1423.
n=4 case rotation and complement
1234, 1243, 1324, 1342.
.
n=5 case addition mod n and reversal
12345, 12354, 12435, 12453, 12534, 13245, 13425, 13452, 13524, 14235, 14523, 15234.
n=5 case rotation and complement
12345, 12354, 12435, 12453, 12534, 13245, 13425, 13452, 13524, 14235, 14325, 14352.

Wikipedia, Hamiltonian path.
Wikipedia, Necklace (combinatorics).
Gus Wiseman, Inequivalent representatives of the a(5) = 12 path necklaces.
Gus Wiseman, Inequivalent representatives of the a(6) = 54 path necklaces.

Cf. A000939, A000940, A002619, A089066, A262480 (other symmetry classes of permutations).
Cf. A193651 (inspiration for a(2n)).
Cf. A000031, A006125, A008965, A059966, A060223, A192332, A323858, A323870, A324461.

rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
Table[Length[Select[Union[Sort[Sort/@Partition[#,2,1]]&/@Permutations[Range[n]]],#==First[Sort[Table[Nest[rotgra[#,n]&,#,j],{j,n}]]]&]],{n,8}] (* Gus Wiseman, Mar 02 2019 *)

(Conjecture). If n odd a(n)=((n - 1))!/2. If n even a(n)= 1/2 (n - 2)!! (1 + ( n - 1)!!).

A047916 Triangular array read by rows: a(n,k) = phi(n/k)(n/k)^kk! if k|n else 0 (1<=k<=n).

Original entry on oeis.org

1, 2, 2, 6, 0, 6, 8, 8, 0, 24, 20, 0, 0, 0, 120, 12, 36, 48, 0, 0, 720, 42, 0, 0, 0, 0, 0, 5040, 32, 64, 0, 384, 0, 0, 0, 40320, 54, 0, 324, 0, 0, 0, 0, 0, 362880, 40, 200, 0, 0, 3840, 0, 0, 0, 0, 3628800, 110, 0, 0, 0, 0, 0, 0, 0, 0, 0, 39916800, 48, 144

Offset: 1

N. J. A. Sloane

T(n,k) = A054523(n,k) * A010766(n,k)^A002260(n,k) * A166350(n,k). - Reinhard Zumkeller, Jan 20 2014

			1; 2,2; 6,0,6; 8,8,0,24; 20,0,0,0,120; 12,36,48,0,0,720; ...

J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
C. L. Mallows and N. J. A. Sloane, Notes on A002618, A002619, etc.
N. J. A. Sloane, Notes on A002618, A002619, etc.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61. [Annotated scanned copy. Note that the scanned pages are out of order]

A064649 gives the row sums.
Cf. A002618 (left edge), A000142 (right edge), A049820 (zeros per row), A000005 (nonzeros per row).
See also A247917, A047918, A047919.

import Data.List (zipWith4)
a047916 n k = a047916_tabl !! (n-1) !! (k-1)
a047916_row n = a047916_tabl !! (n-1)
a047916_tabl = zipWith4 (zipWith4 (\x u v w -> x * v ^ u * w))
               a054523_tabl a002260_tabl a010766_tabl a166350_tabl
-- Reinhard Zumkeller, Jan 20 2014

a[n_, k_] := If[Divisible[n, k], EulerPhi[n/k]*(n/k)^k*k!, 0]; Flatten[ Table[ a[n, k], {n, 1, 12}, {k, 1, n}]] (* Jean-François Alcover, May 04 2012 *)

a(n,k)=if(n%k, 0, eulerphi(n/k)*(n/k)^k*k!) \\ Charles R Greathouse IV, Feb 09 2017

A047918 Triangular array read by rows: a(n,k) = Sum_{d|k} mu(d)*U(n,k/d) if k|n else 0, where U(n,k) = A047916(n,k) (1<=k<=n).

Original entry on oeis.org

1, 2, 0, 6, 0, 0, 8, 0, 0, 16, 20, 0, 0, 0, 100, 12, 24, 36, 0, 0, 648, 42, 0, 0, 0, 0, 0, 4998, 32, 32, 0, 320, 0, 0, 0, 39936, 54, 0, 270, 0, 0, 0, 0, 0, 362556, 40, 160, 0, 0, 3800, 0, 0, 0, 0, 3624800, 110, 0, 0, 0, 0, 0, 0, 0, 0, 0, 39916690, 48, 96

Offset: 1

N. J. A. Sloane

J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
C. L. Mallows and N. J. A. Sloane, Notes on A002618, A002619, etc.
N. J. A. Sloane, Notes on A002618, A002619, etc.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61. [Annotated scanned copy. Note that the scanned pages are out of order]

Cf. A008683, A027750, A225817.

a047918 n k = sum [a008683 (fromIntegral d) * a047916 n (k `div` d) |
                   mod n k == 0, d <- [1..k], mod k d == 0]
a047918_row n = map (a047918 n) [1..n]
a047918_tabl = map a047918_row [1..]
-- Reinhard Zumkeller, Mar 19 2014

U[n_, k_] := If[ Divisible[n, k], EulerPhi[n/k]*(n/k)^k*k!, 0]; a[n_, k_] := Sum[ If[ Divisible[n, k], MoebiusMu[d]*U[n, k/d], 0], {d, Divisors[k]}]; Flatten[ Table[ a[n, k], {n, 1, 12}, {k, 1, n}]] (* Jean-François Alcover, May 04 2012 *)

Offset corrected by Reinhard Zumkeller, Mar 19 2014

A064649 Row sums of the table A047916.

Original entry on oeis.org

1, 4, 12, 40, 140, 816, 5082, 40800, 363258, 3632880, 39916910, 479052528, 6227020956, 87178936992, 1307674429440, 20922800222848, 355687428096272, 6402373892575992, 121645100408832342, 2432902011892837920

Offset: 1

Antti Karttunen, Oct 04 2001

nonn

Harry J. Smith, Table of n, a(n) for n=1..100

Also n*A061417[n]. Cf. A047918, A002619.

a064649 = sum . a047916_row  -- Reinhard Zumkeller, Mar 19 2014

A064649 := proc(n) local d, s; s := 0; for d in divisors(n) do s := s + phi(n/d)*(n/d)^d*d!; od; RETURN(s); end;

a[n_] := DivisorSum[n, EulerPhi[n/#]*(n/#)^#*#!&]; Array[a, 20] (* Jean-François Alcover, Mar 06 2016 *)

{ for (n=1, 100, a=0; v=divisors(n); for (i=1, length(v), d=v[i]; a+=eulerphi(n/d)*(n/d)^d*d!); write("b064649.txt", n, " ", a) ) } \\ Harry J. Smith, Sep 21 2009

a(n) = sumdiv(n, d, eulerphi(n/d)*(n/d)^d*d!); \\ Michel Marcus, Mar 06 2016

a(n) = Sum_{d|n} phi(n/d)*(n/d)^d*d!. - Michel Marcus, Mar 06 2016

A089066 Number of distinct classes of permutations of length n under reversal, rotation and complement to n+1.

Original entry on oeis.org

1, 1, 1, 3, 8, 38, 192, 1320, 10176, 91296, 908160, 9985920, 119761920, 1556847360, 21794734080, 326920043520, 5230700052480, 88921882828800, 1600593472880640, 30411275613143040, 608225502973132800

Offset: 1

Ray Jerome, Dec 02 2003, Jul 17 2007

nonn

Contribution from Olivier Gérard, Jul 31 2016: (Start)
Let us consider two permutations to be equivalent if they can be obtained from each other by reversal (12345->54321), cyclic rotation (12345->(23451,34512,45123,51234), n+1-complement (31254->35412), or a combination of those three transformations (they commute with each other). a(n) is the number of classes. It is strictly inferior to (n-1)! for n>1.
If rotation is replaced by addition of a constant modulo n, one obtains the same number of classes but not exactly the same permutations starting n=5.
(End)
Original explanation by R. Jerome : Generate all permutations of a string of length n, such as 1234, which has length 4; there are n!=24 of these. Now remove all that have cycles less than 4 characters long; if you only use cyclic notation and not array notation then of the n! possibly only (n-1)! need to be considered. Then calculate the Inverse, Vertical reflection, [VErt reflection inverse], Rotation by 180 degree and [ROt by 180 deg inverse]. If any of these already exist on the list then this permutation is not distinct. Items in []'s are unnecessary since VE(x)=V(I(x))=I(V(x))=R(x) and RO(x)=R(I(x))=I(R(x))=V(x). There are some that are rotationally symmetric and some that are vertically symmetric (only possible for even lengths), but the majority are nonsymmetric.

			Examples of permutations (notations of R. Jerome):
Rotationally symmetric: x1=R(x1)=124356=VE(x1), I(x1)=165342=V(x1)=RO(x1)
Vertically symmetric: x2=V(x2)=132645=RO(x2)), I(x2)=154623=R(x2)=VE(x2)
Nonsymmetric: x3=135264, I(x3)=146253, R(x3)=152463=VE(x3), V(x3)=136425=RO(x3)
a(4)=3: there are 3 distinct permutations of exactly length 4, out of a field of 4!=24 possible permutations. In cyclic notation they are designated (1234), (1243) and (1324). The others, (1342), (1423) and (1432), are equal to inverses, vertical mirror images or 180-degree rotations of those 3. The remaining 18 have cycles of length 1, 2 or 3, such as (143)(2) having a permutation of length 3 and a fixed cycle and (14)(23) having 2 permutations of length 2.
Examples of permutation representatives (from Olivier Gerard)
The representative is chosen to be the first of the class in lexicographic order.
n=4 both cases
1234,1243,1324
n=5 case rotation, reversal, complement
12345,12354,12435,12453,12534,13425,13524,14325
n=5 case translation mod, reversal, complement
12345,12354,12435,12453,12534,13425,13452,13524

J. Gebel, Integer points on Mordell curves [Cached copy, after the original web site tnt.math.se.tmu.ac.jp was shut down in 2017]
Samuel Herman, Eirini Poimenidou, Orbits of Hamiltonian Paths and Cycles in Complete Graphs, arXiv:1905.04785 [math.CO], 2019.
R. Jerome, Information for Unique Permutations.

Apart from initial terms, same as A099030. - Ray Jerome, Feb 25 2005
Cf. A000939 (same idea under (rotation, addition mod n and reversal) or (rotation, addition mod n and complement)).
Cf. A000940 (same idea under (rotation, addition mod n, reversal and complement)).
Cf. A001710 (shifted, same idea under (rotation and reversal) or (addition mod n and complement)).
Cf. A002619 (same idea under (rotation and addition mod n)).
Cf. A262480 (same idea under (reversal and complement)).
cf. A275527 (same idea under (rotation and complement) or (addition mod n and reversal)).

(* From the formula in A099030 *)
a[n_] := If[n < 3, 1, 1/4 If[Mod[n, 2] == 0,((n - 1)! + (n/2 + 1) (n - 2)!!), ((n - 1)! + (n - 1)!!)]]; Table[a[n], {n, 1, 20}]

Definition changed and cross-references added by Olivier Gérard, Jul 31 2016

cp's OEIS Frontend

A064852 Number of orbits in A002619 consisting of n permutations.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A349225 Numbers k such that k | A002619(k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

A002618 a(n) = n*phi(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

MuPAD

PARI

Python

Sage

Formula

Extensions

A000939 Number of inequivalent n-gons.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A000940 Number of n-gons with n vertices.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A275527 Number of distinct classes of permutations of length n under reversal and complement to n+1.

Views

A047916 Triangular array read by rows: a(n,k) = phi(n/k)(n/k)^kk! if k|n else 0 (1<=k<=n).