A341743 T(n,k) is the number of labeled Eulerian graphs with n vertices and k edges (according to Harary and Palmer) or the number of labeled connected Eulerian graphs with n vertices and k edges (according to Mallows and Sloane); irregular triangle T, read by rows (n >= 0 and 0 <= k <= n*(n-1)/2).
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, 0, 0, 0, 0, 0, 0, 0, 360, 1890, 3675, 4830, 5061, 4410, 3255, 1935, 805, 252, 105, 35, 0, 0, 1
Offset: 0
Examples
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.)
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.
Programs
-
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 *)
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.
Comments