login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A289483 Number of gcds-sortable two-rooted 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 (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.
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)/2) * (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)/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\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
CROSSREFS
Cf. A289472.
Sequence in context: A226666 A366411 A356486 * A216027 A087899 A202759
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 20 03:21 EDT 2024. Contains 373512 sequences. (Running on oeis4.)