A005289 Number of graphs on n nodes with 3 cliques. (Formerly M3440)

0, 0, 1, 4, 12, 31, 67, 132, 239, 407, 657, 1019, 1523, 2211, 3126, 4323, 5859, 7806, 10236, 13239, 16906, 21346, 26670, 33010, 40498, 49290, 59543, 71438, 85158, 100913, 118913, 139398, 162609, 188817, 218295, 251349, 288285

Offset

1,4

References

R. K. Guy, personal communication.

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

Links

Table of n, a(n) for n=1..37.

R. K. Guy, Letter to N. J. A. Sloane, Apr 1988

R. K. Guy, Monthly research problems, 1969-73, Amer. Math. Monthly, 80 (1973), 1120-1128.

R. K. Guy, Monthly research problems, 1969-75, Amer. Math. Monthly, 82 (1975), 995-1004.

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

K. B. Reid, The number of graphs on N vertices with 3 cliques, J. London Math. Soc. (2) 8 (1974), 94-98.

Eric Weisstein's World of Mathematics, Clique.

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

Formula

G.f.: x^3*(1+x+3*x^3+x^2) / ( (1+x+x^2)*(1+x)^2*(x-1)^6 ). - Simon Plouffe in his 1992 dissertation

288*a(n) = -4*n^3+12*n^2-21*n/5-14+6*n^5/5+(-1)^n*9*(n-2) +32*A057078(n). - R. J. Mathar, Jul 30 2024

Maple

A005289p := proc(n)
    n*(2*n^2+3*n-6)/72 ;
    round(%) ;
end proc:
A005289 := proc(n)
    if type(n, 'even') then
        n*(n^2-4)*(n^2-6)/240+A005289p(n) ;
    else
        n*(n^2-1)*(n^2-9)/240+A005289p(n) ;
    end if;
end proc:
seq(A005289(n), n=1..40) ; # R. J. Mathar, Aug 23 2015

Mathematica

s = x^2*(3*x^3+x^2+x+1) / ((x-1)^6*(x+1)^2*(x^2+x+1)) + O[x]^40; CoefficientList[s, x] (* Jean-François Alcover, Nov 27 2015 *)

Crossrefs

Sequence in context: A297079 A074210 A299053 * A037255 A027658 A001982

Adjacent sequences: A005286 A005287 A005288 * A005290 A005291 A005292

Keyword

nonn,nice,easy

Author

N. J. A. Sloane

Status

approved