login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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

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), 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.

License Agreements, Terms of Use, Privacy Policy. .

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