This site is supported by donations to The OEIS Foundation.



Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

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



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.


Table of n, a(n) for n=1..17.

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.


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


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


(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


Cf. A289472.

Sequence in context: A195228 A226668 A226666 * A216027 A087899 A202759

Adjacent sequences:  A289480 A289481 A289482 * A289484 A289485 A289486




Sam Heil, Jul 06 2017



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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 11 17:01 EST 2018. Contains 318049 sequences. (Running on oeis4.)