A260509 Number of graphs on labeled vertices {x, y, 1, 2, ..., n}, such that there is a partition of the vertices into V_1 and V_2 with x in V_1, y in V_2, every v in V_1 adjacent to an even number of vertices in V_2, and every v in V_2 adjacent to an even number of vertices in V_1.

1, 3, 23, 351, 11119, 703887, 89872847, 22945886799, 11740984910671, 12014755220129103, 24602393557227030863, 100754627840184914661711, 825349838279823049359417679, 13521969078301639826644261077327, 443083578482642171171990600910324047, 29037623349739387300519333731237743018319

Offset: 0

Author

Caleb Stanford, Jul 27 2015

Keywords

• nonn

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.

Examples

			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}}.
		

Links

• Caleb Stanford, Table of n, a(n) for n = 0..150

Crossrefs

Cf. A260506 (counts the special case where the graph in question is required to be the overlap graph of some signed permutation).

Cf. A006125 (the total number of graphs on n labeled vertices).

Programs

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

Python

# 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

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