cp's OEIS Frontend

A000933 Genus of complete graph on n nodes.

%I A000933 M0503 N0182 #75 Feb 16 2025 08:32:22
%S A000933 0,0,0,0,1,1,1,2,3,4,5,6,8,10,11,13,16,18,20,23,26,29,32,35,39,43,46,
%T A000933 50,55,59,63,68,73,78,83,88,94,100,105,111,118,124,130,137,144,151,
%U A000933 158,165,173,181,188,196,205,213,221,230,239,248,257,266,276,286,295,305
%N A000933 Genus of complete graph on n nodes.
%C A000933 (1+x)*(1+x^3)*(1+x^5)/((1-x^2)*(1-x^4)*(1-x^6)) is the Poincaré series [or Poincare series] (or Molien series) for symmetric invariants in F_2(b_1, b_2, ... b_n) ⊗ E(e_1, e_2, ... e_n) with b_i 2-dimensional, e_i one-dimensional and the permutation action of S_n, in the case n=3.
%D A000933 A. Adem and R. J. Milgram, Cohomology of Finite Groups, Springer-Verlag, 2nd. ed., 200
%D A000933 J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley, 1987; see I(n) p. 221.
%D A000933 J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 740.
%D A000933 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000933 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000933 T. D. Noe, <a href="/A000933/b000933.txt">Table of n, a(n) for n = 1..1000</a>
%H A000933 R. K. Guy, <a href="/A002186/a002186.pdf">Letters to N. J. A. Sloane, June-August 1968</a>
%H A000933 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A000933 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A000933 G. Ringel and J. W. T. Youngs, <a href="http://www.pnas.org/content/60/2/438.full.pdf">Solution of the Heawood map-coloring problem</a>, Proc. Nat. Acad. Sci. USA, 60 (1968), 438-445.
%H A000933 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CompleteGraph.html">Complete Graph</a>
%H A000933 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GraphGenus.html">Graph Genus</a>
%H A000933 <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (2,-2,3,-3,2,-2,1).
%F A000933 Euler transform of length 10 sequence [ 1, 0, 1, 1, 1, 0, 0, 0, 0, -1]. - _Michael Somos_, Aug 24 2005
%F A000933 G.f.: x^5*(1+x^5)/((1-x)*(1-x^3)*(1-x^4)).
%F A000933 a(n) = ceiling ( (n-3)*(n-4)/12 ) if n>=3.
%F A000933 a(n) = 2*a(n-1) - 2*a(n-2) + 3*a(n-3) - 3*a(n-4) + 2*a(n-5) - 2*a(n-6) + a(n-7) for n >= 10. - _Harvey P. Dale_, Dec 18 2011
%F A000933 G.f.: x^5*(1-x+x^2+x^4-x^3) / ((1+x^2) * (1+x+x^2) * (1-x)^3). - _R. J. Mathar_, Dec 18 2014
%F A000933 a(n) = (49 + 3*(n - 7)*n - 9*cos(n*Pi/2) - 4*cos(2*n*Pi/3) + 9*sin(n*Pi/2) - 4*sqrt(3)*sin(2*n*Pi/3))/36 for n > 2. - _Stefano Spezia_, Dec 14 2021
%e A000933 a(1)=a(2)=a(3)=a(4)=0 because K_4 is planar. a(5)=a(6)=a(7)=1 because K_7 can be embedded on the torus of genus 1.
%e A000933 G.f. = x^5 + x^6 + x^7 + 2*x^8 + 3*x^9 + 4*x^10 + 5*x^11 + 6*x^12 + 8*x^13 + ...
%p A000933 A000933:=-z**4*(1-z+z**2-z**3+z**4)/(z**2+z+1)/(1+z**2)/(z-1)**3; # _Simon Plouffe_ in his 1992 dissertation
%t A000933 CoefficientList[Series[x^5(1+x^5)/((1-x)(1-x^3)(1-x^4)), {x, 0, 70}], x] (* _Harvey P. Dale_, Dec 18 2011 *)
%t A000933 Join[{0, 0}, LinearRecurrence[{2, -2, 3, -3, 2, -2, 1}, {0, 0, 1, 1, 1, 2, 3}, 70]] (* _Harvey P. Dale_, Dec 18 2011 *)
%t A000933 Join[{0, 0}, Table[Ceiling[(n - 3) (n - 4)/12], {n, 3, 20}]] (* _Eric W. Weisstein_, Jan 19 2018 *)
%o A000933 (PARI) {a(n) = if( n<3, 0, ceil((n-3) * (n-4) / 12))}; /* _Michael Somos_, Aug 24 2005 */
%o A000933 (Magma) [n le 2 select 0 else Ceiling(Binomial(n-3,2)/6): n in [1..70]]; // _G. C. Greubel_, Dec 08 2022
%o A000933 (SageMath) [0,0]+[ceil(binomial(n-3,2)/6) for n in range(3,71)] # _G. C. Greubel_, Dec 08 2022
%Y A000933 Cf. A007997.
%K A000933 easy,nonn,nice
%O A000933 1,8
%A A000933 _N. J. A. Sloane_