

A341941


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*(n1)/2).


3



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,33


COMMENTS

Even graphs are colloquially known as Euler graphs (even though, strictly speaking, that is not correct).
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 nth 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."


REFERENCES

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*(n1)/2} T(n,k) = A002854(n).]


LINKS

Table of n, a(n) for n=0..129.
Petros Hadjicostas, Maple program for implementing Liskovec's method, 2021.
Valery A. Liskovec, Enumeration of Euler Graphs, (in Russian), Akademiia Navuk BSSR, Minsk., 6 (1970), 3846. (annotated scanned copy) [In the OEIS, the author contributes under the name Valery A. Liskovets.]
Robert W. Robinson, Enumeration of Euler graphs, pp. 147153 of F. Harary, editor, Proof Techniques in Graph Theory. Academic Press, NY, 1969. (Annotated scanned copy)


FORMULA

Conjecture (due to Peter Luschny): Sum_{k=0}^{n*(n1)/2} (1)^k*T(n,k) = A263626(n).
T(n,k) = T(n,n*(n1)/2  k) when n is odd (because the complement of an even graph is even when n is odd).
T(n,n*(n1)/2) = 1 if n is odd.
T(n,n*(n2)/2) = 1 while T(n,k) = 0 for n*(n2)/2 + 1 <= k <= n*(n1)/2 when n is even (because an even graph with an even n number of vertices can have at most n*(n2)/2 edges).
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).
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)].
In the products and sums below, empty partitions are allowed, and empty products are by definition equal to 1.
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((s1)/2)*a[s])) * (Product_{s even in [1..n]} (1 + x^(s/2))^a[s]) (p. 40).
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.)
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).
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((s1)/2)*a[s])) * (Product_{s even in [1..n]} (1  x^(s/2))^a[s]) (p. 43).
Then the o.g.f. of row n is Sum_{k=0..n*(n1)/2} T(n,k)*x^k = Sum_{t=0..n, a partition of t, b partition of nt} 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 nt is empty and a is a partition of n.)


EXAMPLE

From Joerg Arndt, Feb 05 2010: (Start)
The A002854(4) = 3 even graphs on four nodes are:
1) o o 2) oo 3) oo
o o /  
o o oo
(End)
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.
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!
Triangle T(n,k) (with rows n >= 0 and columns k = 0..n*(n1)/2) begins:
n=0: 1;
n=1: 1;
n=2: 1, 0
n=3: 1, 0, 0, 1;
n=4: 1, 0, 0, 1, 1, 0, 0;
n=5: 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1;
n=6: 1, 0, 0, 1, 1, 1, 3, 2, 2, 1, 2, 1, 1, 0, 0, 0;
n=7: 1, 0, 0, 1, 1, 1, 3, 4, 4, 6, 6, 6, 6, 4, 4, 3, 1, 1, 1, 0, 0, 1;
...
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.
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.
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.


MAPLE

See the links.


CROSSREFS

Row sums are in A002854.
Cf. A007814, A263626
Sequence in context: A154395 A214609 A152159 * A090341 A251092 A175632
Adjacent sequences: A341938 A341939 A341940 * A341942 A341943 A341944


KEYWORD

nonn,tabf


AUTHOR

Petros Hadjicostas, Feb 24 2021


STATUS

approved



