|
| |
|
|
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
|
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
|
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
|
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
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
