cp's OEIS Frontend

A289483 Number of gcds-sortable two-rooted graphs on n vertices such that all vertices have even degree.

%I A289483 #22 Jun 03 2018 02:01:09
%S A289483 0,1,1,5,29,365,7565,259533,16766541,1695913805,319025518925,
%T A289483 99428910374221,53629954918196557,51436455420773021005,
%U A289483 81633965668282476025165,234346782219278654389392717,1131832076434284133556933170509
%N A289483 Number of gcds-sortable two-rooted graphs on n vertices such that all vertices have even degree.
%C A289483 This formula comes from the fact that for each possible value of the (n-2)-vertex subgraph G containing all of the non-root vertices, if G has adjacency matrix A over F_2 then there are 2^rank(A) two-rooted gcds-sortable graphs with all vertices of even degree containing the non-root 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 gcds-sortable graphs with all vertices of even degree.
%H A289483 C. A. Brown, C. S. Carrillo Vazquez, R. Goswami, S. Heil, and M. Scheepers, <a href="http://diamond.boisestate.edu/reu/publications/2017CDS.pdf">The Sortability of Graphs and Matrices Under Context Directed Swaps</a>
%H A289483 F. J. MacWilliams, <a href="http://www.jstor.org/stable/2317262">Orthogonal matrices over finite fields</a>, Amer. Math. Monthly, 76 (1969), 152-164.
%F A289483 a(n) = Sum_{s=0..floor(n/2)-1} 2^((s^2+3s)/2) * (Product_{i=0..2s-1} (2^(n-2-i)-1) / Product_{i=1..s} (2^(2i)-1))
%t A289483 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 *)
%o A289483 (PARI) a(n) = sum(s=0, n\2-1, 2^((s^2+3*s)/2)*prod(i=0, 2*s-1, (2^(n-2-i)-1))/prod(i=1, s, 2^(2*i)-1)); \\ _Michel Marcus_, Jul 07 2017
%Y A289483 Cf. A289472.
%K A289483 nonn
%O A289483 1,4
%A A289483 _Sam Heil_, Jul 06 2017