cp's OEIS Frontend

A000940 Number of n-gons with n vertices.

%I A000940 M1260 N0482 #113 Jun 12 2025 10:13:26
%S A000940 1,2,4,12,39,202,1219,9468,83435,836017,9223092,111255228,1453132944,
%T A000940 20433309147,307690667072,4940118795869,84241805734539,
%U A000940 1520564059349452,28963120073957838,580578894859915650,12217399235411398127,269291841184184374868,6204484017822892034404
%N A000940 Number of n-gons with n vertices.
%C A000940 Number of inequivalent undirected Hamiltonian cycles in complete graph on n labeled nodes under action of dihedral group of order 2n acting on nodes.
%D A000940 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 A000940 R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
%D A000940 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000940 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000940 Ludovic Schwob, <a href="/A000940/b000940.txt">Table of n, a(n) for n = 3..500</a> (terms 3..100 from T. D. Noe).
%H A000940 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 A000940 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 A000940 Samuel Herman and 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 A000940 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 A000940 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 A000940 R. C. Read, <a href="/A002832/a002832.pdf">Letter to N. J. A. Sloane, 1992</a>
%H A000940 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 A000940 Ludovic Schwob, <a href="https://arxiv.org/abs/2506.04007">On the enumeration of double cosets and self-inverse double cosets</a>, arXiv:2506.04007 [math.CO], 2025. See p. 9.
%H A000940 N. J. A. Sloane, <a href="/A000940/a000940.jpg">Illustration of initial terms</a> [Annotated page from Golomb-Welch article]
%H A000940 Venta Terauds and 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.
%H A000940 Venta Terauds and Jeremy Sumner, <a href="https://arxiv.org/abs/2012.11665">A new algebraic approach to genome rearrangement models</a>, arXiv:2012.11665 [q-bio.PE], 2020.
%F A000940 For formula see Maple lines.
%F A000940 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
%F A000940 a(n) ~ sqrt(2*Pi)/4 * n^(n-3/2) / e^n. - _Ludovic Schwob_, Nov 03 2022
%e A000940 Label the vertices of a regular n-gon 1,2,...,n.
%e A000940 For n=3,4,5 representatives for the polygons counted here are:
%e A000940   (1,2,3,1),
%e A000940   (1,2,3,4,1), (1,2,4,3,1),
%e A000940   (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 A000940 For n=6:
%e A000940   (1,2,3,4,5,6,1), (1,2,3,4,6,5,1), (1,2,3,5,6,4,1),
%e A000940   (1,2,3,6,5,4,1), (1,2,4,3,6,5,1), (1,2,4,6,3,5,1),
%e A000940   (1,2,4,6,5,3,1), (1,2,5,3,6,4,1), (1,2,5,4,6,3,1),
%e A000940   (1,2,5,6,3,4,1), (1,2,6,4,5,3,1), (1,3,5,2,6,4,1).
%p A000940 with(numtheory);
%p A000940 # for n odd:
%p A000940 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 A000940 # for n even:
%p A000940 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 A000940:=n-> if n mod 2 = 0 then Se(n) else Sd(n); fi;
%t A000940 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 A000940 (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
%o A000940 (Python)
%o A000940 from sympy import factorial, divisors, totient
%o A000940 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
%Y A000940 Cf. A000939, A007619. Bisections give A094156, A094157.
%Y A000940 For permutation classes under various symmetries see A089066, A262480, A002619.
%K A000940 nonn,easy,nice
%O A000940 3,2
%A A000940 _N. J. A. Sloane_
%E A000940 More terms from Pab Ter (pabrlos(AT)yahoo.com), May 05 2004