login
This site is supported by donations to The OEIS Foundation.

 

Logo

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

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
1, 3, 23, 351, 11119, 703887, 89872847, 22945886799, 11740984910671, 12014755220129103, 24602393557227030863, 100754627840184914661711, 825349838279823049359417679, 13521969078301639826644261077327, 443083578482642171171990600910324047, 29037623349739387300519333731237743018319 (list; graph; refs; listen; history; text; internal format)
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., limit_(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 number of 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

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

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

Sequence in context: A118184 A027486 A092664 * A073588 A068338 A255881

Adjacent sequences:  A260506 A260507 A260508 * A260510 A260511 A260512

KEYWORD

nonn

AUTHOR

Caleb Stanford, Jul 27 2015

STATUS

approved

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.