cp's OEIS Frontend

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.

%I A260509 #26 Mar 03 2025 10:47:44
%S A260509 1,3,23,351,11119,703887,89872847,22945886799,11740984910671,
%T A260509 12014755220129103,24602393557227030863,100754627840184914661711,
%U A260509 825349838279823049359417679,13521969078301639826644261077327,443083578482642171171990600910324047,29037623349739387300519333731237743018319
%N 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.
%C A260509 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.
%C A260509 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.
%H A260509 Caleb Stanford, <a href="/A260509/b260509.txt">Table of n, a(n) for n = 0..150</a>
%F A260509 a(n) + (2^n - 1)*a(n-1) = 2^(binomial(n+2, 2) - 1) = 2^(n^3 + 3n).
%F A260509 a(n) = Sum_{k=0..n} (Product_{i=1..k} 2^(i+1))*(Product_{i=k+1..n} (1 - 2^i)).
%F A260509 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).
%e A260509 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}}.
%o A260509 (Python)
%o A260509 # a_1(n) and a_2(n) both count the same sequence, in two different ways.
%o A260509 def a_1(n) :
%o A260509     # Output the number of 2-rooted graphs in (a) with n+2 vertices
%o A260509     if n == 0 :
%o A260509         return 1
%o A260509     else :
%o A260509         return 2**((n*n + 3*n) // 2) - (2**n - 1) * a_1(n-1)
%o A260509 def a_2(n) :
%o A260509     # Output the number of 2-rooted graphs in (a) with n+2 vertices
%o A260509     # Formula: \sum_{k=0}^n (\prod_{i=1}^k 2^{i+1}) (\prod_{i=k+1}^n (1 - 2^i))
%o A260509     curr_sum = 0
%o A260509     for k in range(0,n+1) :
%o A260509         curr_prod = 1
%o A260509         for i in range(1,k+1) :
%o A260509             curr_prod *= (2**(i+1))
%o A260509         for i in range(k+1,n+1) :
%o A260509             curr_prod *= (1 - (2**i))
%o A260509         curr_sum += curr_prod
%o A260509     return curr_sum
%o A260509 (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
%Y A260509 Cf. A260506 (counts the special case where the graph in question is required to be the overlap graph of some signed permutation).
%Y A260509 Cf. A006125 (the total number of graphs on n labeled vertices).
%K A260509 nonn
%O A260509 0,2
%A A260509 _Caleb Stanford_, Jul 27 2015