OFFSET
0,2
COMMENTS
a(n) is also the number of graphs on vertices {x, y, 1, 2, ..., n} that can be sorted to the discrete graph by a series of gcdr and even-gcdr moves.
Asymptotically, a(n) is a third of the total number of graphs, i.e., lim_{n->infinity} (a(n) / 2^(binomial(n+2, 2)) = 1/3.
LINKS
Caleb Stanford, Table of n, a(n) for n = 0..150
FORMULA
a(n) + (2^n - 1)*a(n-1) = 2^(binomial(n+2, 2) - 1) = 2^(n^3 + 3n).
a(n) = Sum_{k=0..n} (Product_{i=1..k} 2^(i+1))(Product_{i=k+1..n} (1 - 2^i)).
Exponential generating function A(x) satisfies A(0) = 1 and A'(x) + 2A(2x) - A(x) = 4F(8x). Here F(x) is the exponential generating function counting the graphs on n labeled vertices, and satisfies F(0) = 1 and F'(x) = F(2x).
EXAMPLE
a(2) = 23 because there are 23 graphs on {x, y, 1, 2} that admit a vertex partition separating x and y, such that each vertex in one half of the partition is adjacent to an even number of vertices in the other half. For instance, the graph with four edges (x,y), (x,1), (y,2), (1,2) admits the partition {{x,2},{y,1}}.
PROG
(Python3)
# a_1(n) and a_2(n) both count the same sequence, in two different ways.
def a_1(n) :
# Output the number of 2-rooted graphs in (a) with n+2 vertices
if n == 0 :
return 1
else :
return 2**((n*n + 3*n) // 2) - (2**n - 1) * a_1(n-1)
def a_2(n) :
# Output the number of 2-rooted graphs in (a) with n+2 vertices
# Formula: \sum_{k=0}^n (\prod_{i=1}^k 2^{i+1}) (\prod_{i=k+1}^n (1 - 2^i))
curr_sum = 0
for k in range(0, n+1) :
curr_prod = 1
for i in range(1, k+1) :
curr_prod *= (2**(i+1))
for i in range(k+1, n+1) :
curr_prod *= (1 - (2**i))
curr_sum += curr_prod
return curr_sum
(PARI) a(n) = sum(k=0, n, prod(i=1, k, 2^(i+1))*prod(i=k+1, n, 1 - 2^i)); \\ Michel Marcus, Sep 11 2015
CROSSREFS
KEYWORD
nonn
AUTHOR
Caleb Stanford, Jul 27 2015
STATUS
approved