This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A289472 Number of gcds-sortable two-rooted graphs on n vertices. 1
 0, 1, 1, 17, 113, 7729, 224689, 61562033, 7309130417, 8013328398001, 3825133597372081, 16776170217003753137, 32072986971771549318833, 562672074981014060438175409, 4304275145962667488546071527089, 302049699050029408242290021253725873 (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 (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. 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)). 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 *) PROG (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 CROSSREFS Sequence in context: A298332 A299223 A197360 * A172521 A226688 A070144 Adjacent sequences:  A289469 A289470 A289471 * A289473 A289474 A289475 KEYWORD nonn AUTHOR Sam Heil, Jul 06 2017 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 20 03:10 EDT 2019. Contains 323412 sequences. (Running on oeis4.)