OFFSET
0,13
COMMENTS
The value T(0,0) = 0 has no physical meaning. It is there because it makes the formula for the bivariate e.g.f.-o.g.f. (shown below) work.
Since T(n,k) counts even connected graphs with n vertices and k edges, for n >= 2, each vertex must have at least two edges, so k >= n. Hence, T(n,k) = 0 for 0 <= k < n.
We have T(n,n) = (n-1)!/2 for n >= 3 because T(n,n) counts the different labelings of cyclic graphs with n vertices and n edges, and we have (n-1)! cyclic permutations of the numbers 1, 2, ..., n. We divide by 2 because we get the same labeling if we flip the cyclic graph over (like a bracelet).
We have T(n, n*(n-1)/2) = 1, if n is odd, because the complete graph on n vertices is even (each vertex has degree n-1) and has only one non-isomorphic labeling.
We have T(n, n*(n-1)/2 - s) = 0 for s = 0, 1, 2, ..., (n/2)-1, if n is even, because in an even graph with n vertices we cannot have more than n*(n-2)/2 = n*(n-1)/2 - n/2 edges.
Finally, we have T(n, n*(n-2)/2) = A001147(n/2), if n is even >= 4, because any labeling in an even graph with n vertices and n*(n-2)/2 edges corresponds to a perfect matching in a complete graph with n vertices (by considering the pairs of vertices that are not connected).
See the comments for A058878 about the different (and sometimes confusing) terminology regarding even and (connected or not) Euler graphs.
REFERENCES
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973; see Eqs. (1.4.7), (1.4.18), and (1.4.19) on pp. 11-16.
LINKS
P. J. Cameron, Cohomological aspects of two-graphs, Math. Zeit., 157 (1977), 101-119.
C. L. Mallows and N. J. A. Sloane (1975), Two-graphs, switching classes and Euler graphs are equal in number, SIAM Journal on Applied Mathematics, 28(4) (1975), 876-880.
math.stackexchange.com, Is it possible disconnected graph has euler circuit? [sic], August 30, 2015.
Ronald C. Read, Euler graphs on labelled nodes, Canadian Journal of Mathematics, 14 (1962), 482-486; see the discussion in Section 4, following Eq. (8) on p. 486.
FORMULA
Sum_{k=0..n} T(n,k) = A033678(n) for n >= 1.
Bivariate e.g.f.-o.g.f.: Sum_{n,k>=0} T(n,k)*(x^n/n!)*y^k = log(Sum_{n,k>=0} A058878(n,k)*(x^n/n!)*y^k) = log(Sum_{n >= 0} (x^n/n!)*[o.g.f. of n-th row of A058878](y)).
Sum_{s=0..n} Sum_{t=0..k} binomial(n,s) * T(s+1,t) * A058878(n-s,k-t) = A058878(n+1,k) for n >= 0 and 0 <= k <= n*(n+1)/2.
Sum_{s=0..n} Sum_{t=0..k} ((t+1)/(k+1)) * binomial(n,s) * T(s,t+1) * A058878(n-s,k-t) = A058878(n,k+1) for n >= 2 and 0 <= k <= n*(n-1)/2 - 1
T(n,k) = A058878(n,k) - Sum_{s=0..n-2} Sum_{t=0..k} binomial(n-1,s) * T(s+1,t) * A058878(n-1-s,k-t) for n >= 1 and 0 <= k <= n*(n-1)/2, and T(n,k) = 0 otherwise.
T(n,k) = A058878(n,k) - Sum_{s=0..n} Sum_{t=0..k-2} ((t+1)/(k+1)) * binomial(n,s) * T(s,t+1) * A058878(n-s,k-1-t) - Sum_{s=0..n-1} binomial(n,s) * T(s,k) for n >= 2 and 1 <= k <= n*(n-1)/2 (with T(1,0) = 1 and T(n,k) = 0 otherwise).
T(n,k) = 0 for n >= 2 and 0 <= k <= n-1.
T(n,n) = A001710(n-1) = (n-1)!/2 for n >= 3.
T(n, n*(n-1)/2) = 1 if n is odd.
T(n, k) = 0 if n is even and n*(n-1)/2 - n/2 + 1 <= k < n*(n-1)/2.
T(n, n*(n-2)/2) = A001147(n/2) if n is even >= 4.
EXAMPLE
Irregular triangle T(n,k) (with rows n >= 0 and columns k = 0..n*(n-1)/2) begins
0;
1;
0, 0;
0, 0, 0, 1;
0, 0, 0, 0, 3, 0, 0;
0, 0, 0, 0, 0, 12, 15, 10, 0, 0, 1;
0, 0, 0, 0, 0, 0, 60, 180, 195, 120, 90, 60, 15, 0, 0, 0;
...
T(5,5) = 12 because we have (5-1)!/2 = 12 non-isomorphic labelings of the following Eulerian graph with 5 vertices and 5 edges:
*
/ \
/ \
/ \
* *
\ /
\ /
*--*
T(5,6) = 15 because we have 5*3 = 15 non-isomorphic labelings of the following Eulerian graph with 5 vertices and 6 edges:
*______*
/|\ /
/ | \ /
* | \/
\ | *
\|
*
In the above graph, we have 5 choices for the vertex that is common to both triangles and using the other 4 numbers 1, 2, 3, 4 we have the following 3 possible labelings of the other 4 vertices: {{1,2},{3,4}}, {{1,3},{2,4}}, {{1,4},{2,3}}.
T(5,7) = 10 because we have C(5,2) = 10 non-isomorphic labelings of the following Eulerian graph with 5 vertices and 7 edges:
V = {a,b,c,d,e} and E = {{a,b}, {a,c}, {a,d}, {a,e}, {b,c}, {b,d}, {b,e}}.
T(5,10) = 1 because all labelings of the complete graph with 5 vertices (and C(5,2) = 10 edges) are isomorphic.
There are no other (unlabeled) Eulerian graphs with 5 vertices: A003049(5) = 4. (In the name of A003049, the phrase "connected Euler graphs" is according to Mallows and Sloane (1975). According to Harary and Palmer (1973), we only need to say "Euler graphs" because, for them, an Euler graph is connected and even.)
MAPLE
# Slow program based on Eqs. (1.4.7), (1.4.18), and (1.4.19) in Harary and Palmer (1973).
w := proc(n, y) local m: expand(simplify(2^(-n)*(y + 1)^(1/2*n*(n - 1))*add(binomial(n, m)*((1 - y)/(y + 1))^(m*(n - m)), m = 0 .. n))): end proc:
u := proc(x, y, M) local n: add(w(n, y)*x^n/n!, n = 0 .. M): end proc:
T := proc(n, k) coeftayl(log(u(x, y, n + 2)), [x, y] = [0, 0], [n, k])*n!: end proc:
# Another, slightly faster, program based on one of the recurrences:
S := proc(n, k) local s, t: add(binomial(n, s)*add((-1)^t*binomial(s*(n - s), t)*binomial(binomial(s, 2) + binomial(n - s, 2), k - t), t = 0 .. k), s = 0 .. n)/2^n: end proc: # A058878
T := proc(n, k) local x, s, t: option remember: if n = 0 then x := 0: end if: if 1/2*n*(n - 1) < k then x := 0: end if: if 1 <= n and 0 <= k and k <= 1/2*n*(n - 1) then x := S(n, k) - add(add(binomial(n - 1, s)*T(s + 1, t)*S(n - 1 - s, k - t), t = 0 .. k), s = 0 .. n - 2): end if: x: end proc:
# Third program based on another recurrence (the S(n, k) is as above):
T1 := proc(n, k) local x, s, t: option remember: if k = 0 and (n = 0 or 2 <= n) then x := 0: end if: if n = 1 and k = 0 then x := 1: end if; if 1/2*n*(n - 1) < k then x := 0: end if: if 2 <= n and 1 <= k and k <= 1/2*n*(n - 1) then x := S(n, k) - add(add((t + 1)*binomial(n, s)*T1(s, t + 1)*S(n - s, k - 1 - t)/k, t = 0 .. k - 2), s = 0 .. n) - add(binomial(n, s)*T1(s, k), s = 0 .. n - 1): end if: x: end proc:
MATHEMATICA
S[n_, k_] := S[n, k] = Sum[Binomial[n, s]*Sum[(-1)^t* Binomial[s*(n-s), t]*Binomial[Binomial[s, 2] + Binomial[n-s, 2], k-t], {t, 0, k}], {s, 0, n}]/2^n;
T[n_, k_] := T[n, k] = If[n == 0 || k > n(n-1)/2, 0, S[n, k] - Sum[Binomial[n-1, s]*T[s+1, t]*S[n-1-s, k-t], {t, 0, k}, {s, 0, n-2}]];
Table[T[n, k], {n, 0, 8}, {k, 0, n(n-1)/2}] // Flatten (* Jean-François Alcover, Feb 14 2023, after 2nd Maple program *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Petros Hadjicostas, Feb 18 2021
STATUS
approved