A275334 Number of simple labeled graphs on n vertices that have at least one vertex of odd degree and at least one vertex of even degree.

0, 0, 6, 48, 960, 30720, 2064384, 264241152, 68451041280, 35046933135360, 35993612646875136, 73714918700800278528, 302157667927362455470080, 2475275615660953235210895360, 40562343327224770087344704323584

Offset

1,3

Links

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

Formula

a(n) = 2^binomial(n,2) - 2*2^binomial(n-1,2) if n is even.

a(n) = 2^binomial(n,2) - 2^binomial(n-1,2) if n is odd.

Example

a(4)=48 because there are 64 simple labeled graphs on 4 vertices but the graph with no edges, the 3 labelings of the 4-cycle graph, the 4 labelings of the 3 cycle with an isolated node, and the complements of each of these graphs are not counted.

Maple

A275334 := proc(n)
    if type(n, 'even') then
        2^binomial(n, 2)-2*2^binomial(n-1, 2) ;
    else
        2^binomial(n, 2)-2^binomial(n-1, 2) ;
    end if;
end proc:
seq(A275334(n), n=1..30) ; # R. J. Mathar, Jul 15 2017

Mathematica

Table[If[EvenQ[n], 2^Binomial[n, 2] - 2 2^Binomial[n - 1, 2], 2^Binomial[n, 2] - 2^Binomial[n - 1, 2]], {n, 1, 15}]

Crossrefs

Cf. A122743.

Sequence in context: A108092 A052744 A267620 * A192769 A324461 A084259

Adjacent sequences: A275331 A275332 A275333 * A275335 A275336 A275337

Keyword

nonn

Author

Geoffrey Critzer, Jul 23 2016

Status

approved