login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000940 Number of n-gons with n vertices.
(Formerly M1260 N0482)
10

%I M1260 N0482

%S 1,2,4,12,39,202,1219,9468,83435,836017,9223092,111255228,1453132944,

%T 20433309147,307690667072,4940118795869,84241805734539,

%U 1520564059349452,28963120073957838,580578894859915650,12217399235411398127,269291841184184374868,6204484017822892034404

%N Number of n-gons with n vertices.

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

%C After a(4) = 2 there are no primes through a(100). - _Jonathan Vos Post_, Feb 06 2011

%D 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.

%D R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H T. D. Noe, <a href="/A000940/b000940.txt">Table of n, a(n) for n = 3..100</a>

%H S. W. Golomb and L. R. Welch, <a href="http://www.jstor.org/stable/2308978">On the enumeration of polygons</a>, Amer. Math. Monthly, 67 (1960), 349-353.

%H S. W. Golomb and L. R. Welch, <a href="/A000939/a000939.pdf">On the enumeration of polygons</a>, Amer. Math. Monthly, 67 (1960), 349-353. [Annotated scanned copy]

%H Samuel Herman, Eirini Poimenidou, <a href="https://arxiv.org/abs/1905.04785">Orbits of Hamiltonian Paths and Cycles in Complete Graphs</a>, arXiv:1905.04785 [math.CO], 2019.

%H E. M. Palmer and R. W. Robinson, <a href="http://dx.doi.org/10.1007/BF02392038">Enumeration under two representations of the wreath product</a>, Acta Math., 131 (1973), 123-143.

%H R. C. Read, <a href="/A002831/a002831.pdf">Letter to N. J. A. Sloane, Feb 04 1971</a> (gives initial terms of this sequence, except he has a(6)=7 instead of 12)

%H R. C. Read, <a href="/A002832/a002832.pdf">Letter to N. J. A. Sloane, 1992</a>

%H R. C. Read, <a href="http://dx.doi.org/10.1016/S0012-365X(96)00255-5">Combinatorial problems in theory of music</a>, Discrete Math. 167 (1997), 543-551.

%H N. J. A. Sloane, <a href="/A000940/a000940.jpg">Illustration of initial terms</a> [Annotated page from Golomb-Welch article]

%H Venta Terauds, J. Sumner, <a href="https://arxiv.org/abs/1712.00858">Circular genome rearrangement models: applying representation theory to evolutionary distance calculations</a>, arXiv preprint arXiv:1712.00858 [q-bio.PE], 2017.

%F For formula see Maple lines.

%e Label the vertices of a regular n-gon 1,2,...,n.

%e For n=3,4,5 representatives for the polygons counted here are:

%e (1,2,3,1),

%e (1,2,3,4,1), (1,2,4,3,1),

%e (1,2,3,4,5,1), (1,2,3,5,4,1), (1,2,4,5,3,1), (1,3,5,2,4,1).

%e For n=6:

%e (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).

%p with(numtheory);

%p # for n odd:

%p 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;

%p # for n even:

%p 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;

%p A000940:=n-> if n mod 2 = 0 then Se(n) else Sd(n); fi;

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

%o (PARI) 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

%Y Cf. A000939. Bisections give A094156, A094157.

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

%K nonn,easy,nice

%O 3,2

%A _N. J. A. Sloane_

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 2 06:08 EST 2021. Contains 341742 sequences. (Running on oeis4.)