|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|