A289472 Number of gcds-sortable two-rooted graphs on n vertices.

0, 1, 1, 17, 113, 7729, 224689, 61562033, 7309130417, 8013328398001, 3825133597372081, 16776170217003753137, 32072986971771549318833, 562672074981014060438175409, 4304275145962667488546071527089, 302049699050029408242290021253725873

Offset: 1

Author

Sam Heil, Jul 06 2017

Keywords

• nonn

Comments

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.

Links

• 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), 152-164.

Programs

Mathematica

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 *)

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

Formula

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)).