A000933 Genus of complete graph on n nodes. (Formerly M0503 N0182)

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, 50, 55, 59, 63, 68, 73, 78, 83, 88, 94, 100, 105, 111, 118, 124, 130, 137, 144, 151, 158, 165, 173, 181, 188, 196, 205, 213, 221, 230, 239, 248, 257, 266, 276, 286, 295, 305

Offset

1,8

Comments

(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.

References

A. Adem and R. J. Milgram, Cohomology of Finite Groups, Springer-Verlag, 2nd. ed., 200

J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley, 1987; see I(n) p. 221.

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 740.

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).

Links

T. D. Noe, Table of n, a(n) for n = 1..1000

R. K. Guy, Letters to N. J. A. Sloane, June-August 1968

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992

G. Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. USA, 60 (1968), 438-445.

Eric Weisstein's World of Mathematics, Complete Graph

Eric Weisstein's World of Mathematics, Graph Genus

Index entries for linear recurrences with constant coefficients, signature (2,-2,3,-3,2,-2,1).

Formula

Euler transform of length 10 sequence [ 1, 0, 1, 1, 1, 0, 0, 0, 0, -1]. - Michael Somos, Aug 24 2005

G.f.: x^5*(1+x^5)/((1-x)*(1-x^3)*(1-x^4)).

a(n) = ceiling ( (n-3)*(n-4)/12 ) if n>=3.

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

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

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

Example

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

Maple

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

Mathematica

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 *)
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 *)
Join[{0, 0}, Table[Ceiling[(n - 3) (n - 4)/12], {n, 3, 20}]] (* Eric W. Weisstein, Jan 19 2018 *)

Prog

(PARI) {a(n) = if( n<3, 0, ceil((n-3) * (n-4) / 12))}; /* Michael Somos, Aug 24 2005 */
(Magma) [n le 2 select 0 else Ceiling(Binomial(n-3, 2)/6): n in [1..70]]; // G. C. Greubel, Dec 08 2022
(SageMath) [0, 0]+[ceil(binomial(n-3, 2)/6) for n in range(3, 71)] # G. C. Greubel, Dec 08 2022

Crossrefs

Cf. A007997.

Sequence in context: A072666 A075471 A193687 * A253012 A036409 A005423

Adjacent sequences: A000930 A000931 A000932 * A000934 A000935 A000936

Keyword

easy,nonn,nice

Author

N. J. A. Sloane

Status

approved