The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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*(n-1)/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 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." 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*(n-1)/2} T(n,k) = A002854(n).] LINKS 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), 38-46. (annotated scanned copy) [In the OEIS, the author contributes under the name Valery A. Liskovets.] Robert W. Robinson, Enumeration of Euler graphs, pp. 147-153 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*(n-1)/2} (-1)^k*T(n,k) = A263626(n). 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). T(n,n*(n-1)/2) = 1 if n is odd. 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). 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((s-1)/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((s-1)/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*(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.) EXAMPLE From Joerg Arndt, Feb 05 2010: (Start) The A002854(4) = 3 even graphs on four nodes are:    1)  o o     2)  o-o     3)  o-o        o o         |/          | |                    o o         o-o (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*(n-1)/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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 21 06:24 EDT 2021. Contains 345358 sequences. (Running on oeis4.)