login
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.
1

%I #8 Jul 15 2017 09:56:19

%S 0,0,6,48,960,30720,2064384,264241152,68451041280,35046933135360,

%T 35993612646875136,73714918700800278528,302157667927362455470080,

%U 2475275615660953235210895360,40562343327224770087344704323584

%N 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.

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

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

%e 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.

%p A275334 := proc(n)

%p if type(n,'even') then

%p 2^binomial(n,2)-2*2^binomial(n-1,2) ;

%p else

%p 2^binomial(n,2)-2^binomial(n-1,2) ;

%p end if;

%p end proc:

%p seq(A275334(n),n=1..30) ; # _R. J. Mathar_, Jul 15 2017

%t 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}]

%Y Cf. A122743.

%K nonn

%O 1,3

%A _Geoffrey Critzer_, Jul 23 2016