

A289483


Number of gcdssortable tworooted graphs on n vertices such that all vertices have even degree.


0



0, 1, 1, 5, 29, 365, 7565, 259533, 16766541, 1695913805, 319025518925, 99428910374221, 53629954918196557, 51436455420773021005, 81633965668282476025165, 234346782219278654389392717, 1131832076434284133556933170509
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

This formula comes from the fact that for each possible value of the (n2)vertex subgraph G containing all of the nonroot vertices, if G has adjacency matrix A over F_2 then there are 2^rank(A) tworooted gcdssortable graphs with all vertices of even degree containing the nonroot subgraph G. Then, we can apply the formula from MacWilliams for the number of symmetric binary matrices with zero diagonal of each rank to get the total number of gcdssortable graphs with all vertices of even degree.


LINKS

Table of n, a(n) for n=1..17.
C. A. Brown, C. S. Carrillo Vazquez, R. Goswami, S. Heil, and M. Scheepers, The Sortability of Graphs and Matrices Under Context Directed Swaps
F. J. MacWilliams, Orthogonal matrices over finite fields, Amer. Math. Monthly, 76 (1969), 152164.


FORMULA

a(n) = Sum_{s=0..floor(n/2)1} 2^((s^2+3s)/2) * (Product_{i=0..2s1} (2^(n2i)1) / Product_{i=1..s} (2^(2i)1))


MATHEMATICA

Table[Sum[2^((s^2 + 3 s)/2) * Product[(2^(n  2  i)  1), {i, 0, 2 s  1}]/Product[(2^(2 j)  1), {j, s}], {s, 0, Floor[n/2]  1}], {n, 2, 17}] (* Michael De Vlieger, Jul 12 2017 *)


PROG

(PARI) a(n) = sum(s=0, n\21, 2^((s^2+3*s)/2)*prod(i=0, 2*s1, (2^(n2i)1))/prod(i=1, s, 2^(2*i)1)); \\ Michel Marcus, Jul 07 2017


CROSSREFS

Cf. A289472.
Sequence in context: A195228 A226668 A226666 * A216027 A087899 A202759
Adjacent sequences: A289480 A289481 A289482 * A289484 A289485 A289486


KEYWORD

nonn


AUTHOR

Sam Heil, Jul 06 2017


STATUS

approved



