This site is supported by donations to The OEIS Foundation.



Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of 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 counting 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 18 21:51 EST 2017. Contains 294912 sequences.