|
%I #69 Feb 27 2021 00:43:58
%S 1,1,1,0,1,0,0,1,1,0,0,1,1,0,0,1,0,0,1,1,1,1,1,0,0,1,1,0,0,1,1,1,3,2,
%T 2,1,2,1,1,0,0,0,1,0,0,1,1,1,3,4,4,6,6,6,6,4,4,3,1,1,1,0,0,1,1,0,0,1,
%U 1,1,3,4,7,9,16,18,25,24,29,26,25,16,15,8,5,4,3,1,1,0,0,0,0,1,0,0,1,1,1,3,4,7,13,21,36,58,83,118,156,189,213,228,213,189,156,118,83,58,36,21,13,7,4,3,1,1,1,0,0,1
%N T(n,k) is the number of unlabeled even graphs with n vertices and k edges; irregular triangular array T read by rows (n >= 0, 0 <= k <= n*(n-1)/2).
%C Even graphs are colloquially known as Euler graphs (even though, strictly speaking, that is not correct).
%C Robinson (1969, Section 4, p. 153) actually calculates the o.g.f. of row n=6 of this irregular triangle T(n,k), but he is discouraged by the asymmetry of the coefficients of the polynomial. (The n-th row of this triangle T(n,k) is symmetric only when n is odd). He states: "The processes of Section 1 can be extended brutally to accommodate the line [edge] parameter, but the result does not promise to be pleasing."
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973. [See Fig. 1.4.3 (p. 15, some graphs have typos) and p. 114, Eq. (4.7.1), for Sum_{k=0..n*(n-1)/2} T(n,k) = A002854(n).]
%H Petros Hadjicostas, <a href="/A341941/a341941.txt">Maple program for implementing Liskovec's method</a>, 2021.
%H Valery A. Liskovec, <a href="/A002854/a002854.pdf">Enumeration of Euler Graphs</a>, (in Russian), Akademiia Navuk BSSR, Minsk., 6 (1970), 38-46. (annotated scanned copy) [In the OEIS, the author contributes under the name _Valery A. Liskovets_.]
%H Robert W. Robinson, <a href="/A003049/a003049.pdf">Enumeration of Euler graphs</a>, pp. 147-153 of F. Harary, editor, Proof Techniques in Graph Theory. Academic Press, NY, 1969. (Annotated scanned copy)
%F Conjecture (due to _Peter Luschny_): Sum_{k=0}^{n*(n-1)/2} (-1)^k*T(n,k) = A263626(n).
%F T(n,k) = T(n,n*(n-1)/2 - k) when n is odd (because the complement of an even graph is even when n is odd).
%F T(n,n*(n-1)/2) = 1 if n is odd.
%F T(n,n*(n-2)/2) = 1 while T(n,k) = 0 for n*(n-2)/2 + 1 <= k <= n*(n-1)/2 when n is even (because an even graph with an even n number of vertices can have at most n*(n-2)/2 edges).
%F Write an integer partition a of n into frequency or multiplicity notation: a = Sum_{i=1}^n i*a[i], where 0 <= a[i] <= n for i = 1..n. Following Liskovec (1970, p. 39), let a! = Product_{i=1}^n a[i]! and pi(a) = Product_{i=1}^n i^a[i]. Let also K(a) = Sum_{i=1}^n a[i] (p. 42).
%F For an integer partition a of n and an integer partition b of r, let a[i] = 0 for i = (n+1)..r, if r > n, and b[i] = 0 for i = (r+1)..n, if n > r. Define a + b = [a[i]+b[i], i=1..max(r,n)].
%F In the products and sums below, empty partitions are allowed, and empty products are by definition equal to 1.
%F Define the product p0(a,x) = (Product_{1 <= s < m <= n} (1 + x^lcm(s,m))^(gcd(s,m)*a[s]*a[m])) * (Product_{s=1..n} (1 + x^s)^(s*binomial(a[s],2) + floor((s-1)/2)*a[s])) * (Product_{s even in [1..n]} (1 + x^(s/2))^a[s]) (p. 40).
%F For an integer n, let alpha(n) = 2^A007814(n) (p. 43). (We actually only need the exponent A007814(n) for comparison, but this is how Liskovec defines it.)
%F For integer partitions a of n and b of r, define the product p0(+/-)(a,b,x) = (Product_{s=1..n, m=1..r, alpha(s) > alpha(m)} (1 + x^lcm(s,m))^(gcd(s,m)*a[s]*b[m])) * Product_{s=1..n, m=1..r, alpha(s) <= alpha(m)} (1 - x^lcm(s,m))^(gcd(s,m)*a[s]*b[m])) (p. 43).
%F For an integer partition a of n, define the product p0(-)(a,x) = (Product_{1 <= s < m <= n, alpha(s) = alpha(m)} (1 + x^lcm(s,m))^(gcd(s,m)*a[s]*a[m])) * (Product_{1 <= s < m <= n, alpha(s) <> alpha(m)} (1 - x^lcm(s,m))^(gcd(s,m)*a[s]*a[m])) * (Product_{s=1..n} (1 + x^s)^(s*binomial(a[s],2) + floor((s-1)/2)*a[s])) * (Product_{s even in [1..n]} (1 - x^(s/2))^a[s]) (p. 43).
%F Then the o.g.f. of row n is Sum_{k=0..n*(n-1)/2} T(n,k)*x^k = Sum_{t=0..n, a partition of t, b partition of n-t} 2^(-K(a+b))/(a! * b! * pi(a+b)) * p0(a,x) * p0(+/-)(a,b,x) * p0(-)(b,x) (p. 42). (When t = 0, partition a of t is empty and b is a partition of n; similarly, when t = n, partition b of n-t is empty and a is a partition of n.)
%e From _Joerg Arndt_, Feb 05 2010: (Start)
%e The A002854(4) = 3 even graphs on four nodes are:
%e 1) o o 2) o-o 3) o-o
%e o o |/ | |
%e o o o-o
%e (End)
%e From above, we see that T(4,0) = 1, T(4,1) = T(4,2) = 0, T(4,3) = 1, T(4,4) = 1, and T(4,5) = T(4,6) = 0.
%e The even graphs corresponding to T(5,0) = T(5,3) = T(5,4) = T(5,5) = T(5,6) = T(5,7) = T(5,10) = 1 appear in Fig. 1.4.3 in Harary and Palmer (p. 15). The last two even graphs, however, corresponding to k = 7 and k = 10, are each missing edges!
%e Triangle T(n,k) (with rows n >= 0 and columns k = 0..n*(n-1)/2) begins:
%e n=0: 1;
%e n=1: 1;
%e n=2: 1, 0
%e n=3: 1, 0, 0, 1;
%e n=4: 1, 0, 0, 1, 1, 0, 0;
%e n=5: 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1;
%e n=6: 1, 0, 0, 1, 1, 1, 3, 2, 2, 1, 2, 1, 1, 0, 0, 0;
%e n=7: 1, 0, 0, 1, 1, 1, 3, 4, 4, 6, 6, 6, 6, 4, 4, 3, 1, 1, 1, 0, 0, 1;
%e ...
%e Row n=8 is 1, 0, 0, 1, 1, 1, 3, 4, 7, 9, 16, 18, 25, 24, 29, 26, 25, 16, 15, 8, 5, 4, 3, 1, 1, 0, 0, 0, 0.
%e Row n=9 is 1, 0, 0, 1, 1, 1, 3, 4, 7, 13, 21, 36, 58, 83, 118, 156, 189, 213, 228, 213, 189, 156, 118, 83, 58, 36, 21, 13, 7, 4, 3, 1, 1, 1, 0, 0, 1.
%e Row n=10 is 1, 0, 0, 1, 1, 1, 3, 4, 7, 13, 26, 43, 91, 152, 290, 473, 777, 1157, 1711, 2236, 2846, 3255, 3557, 3493, 3295, 2785, 2275, 1662, 1173, 742, 475, 258, 151, 79, 44, 19, 13, 6, 3, 1, 1, 0, 0, 0, 0, 0.
%p See the links.
%Y Row sums are in A002854.
%Y Cf. A007814, A263626
%K nonn,tabf
%O 0,33
%A _Petros Hadjicostas_, Feb 24 2021
|
