|
%I #17 Aug 26 2017 08:31:22
%S 0,1,1,17,113,7729,224689,61562033,7309130417,8013328398001,
%T 3825133597372081,16776170217003753137,32072986971771549318833,
%U 562672074981014060438175409,4304275145962667488546071527089,302049699050029408242290021253725873
%N Number of gcds-sortable two-rooted graphs on n vertices.
%C 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 4^rank(A) two-rooted gcds-sortable graphs containing the non-root subgraph G. 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.
%H 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 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 a(n) = Sum_{s=0..floor(n/2)-1} 2^(s^2+3s) * (Product_{i=0..2s-1} (2^(n-2-i)-1) / Product_{i=1..s} (2^(2i)-1)).
%t Table[Sum[2^(s^2 + 3 s) (Product[(2^(n - 2 - i) - 1), {i, 0, 2 s - 1}]/Product[(2^(2 i) - 1), {i, s}]), {s, 0, Floor[n/2] - 1}], {n, 16}] (* _Michael De Vlieger_, Jul 30 2017 *)
%o (PARI) a(n) = sum(s=0, n\2-1, 2^(s^2+3*s)*prod(i=0, 2*s-1, (2^(n-2-i)-1))/prod(i=1, s, 2^(2*i)-1)); \\ _Michel Marcus_, Jul 07 2017
%K nonn
%O 1,4
%A _Sam Heil_, Jul 06 2017
|
