cp's OEIS Frontend

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

%I A341743 #93 Feb 14 2023 12:01:59
%S A341743 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,
%T A341743 60,180,195,120,90,60,15,0,0,0,0,0,0,0,0,0,0,360,1890,3675,4830,5061,
%U A341743 4410,3255,1935,805,252,105,35,0,0,1
%N 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).
%C A341743 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.
%C A341743 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.
%C A341743 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).
%C A341743 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.
%C A341743 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.
%C A341743 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).
%C A341743 See the comments for A058878 about the different (and sometimes confusing) terminology regarding even and (connected or not) Euler graphs.
%D A341743 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.
%H A341743 P. J. Cameron, <a href="https://doi.org/10.1007/BF01215145">Cohomological aspects of two-graphs</a>, Math. Zeit., 157 (1977), 101-119.
%H A341743 C. L. Mallows and N. J. A. Sloane (1975), <a href="http://neilsloane.com/doc/MallowsSloane.pdf">Two-graphs, switching classes and Euler graphs are equal in number</a>, SIAM Journal on Applied Mathematics, 28(4) (1975), 876-880.
%H A341743 math.stackexchange.com, <a href="https://math.stackexchange.com/questions/1414667/is-it-possible-disconnected-graph-has-euler-circuit">Is it possible disconnected graph has euler circuit? [sic]</a>, August 30, 2015.
%H A341743 Ronald C. Read, <a href="https://doi.org/10.4153/CJM-1962-039-0">Euler graphs on labelled nodes</a>, Canadian Journal of Mathematics, 14 (1962), 482-486; see the discussion in Section 4, following Eq. (8) on p. 486.
%F A341743 Sum_{k=0..n} T(n,k) = A033678(n) for n >= 1.
%F A341743 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)).
%F A341743 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.
%F A341743 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
%F A341743 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.
%F A341743 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).
%F A341743 T(n,k) = 0 for n >= 2 and 0 <= k <= n-1.
%F A341743 T(n,n) = A001710(n-1) = (n-1)!/2 for n >= 3.
%F A341743 Conjecture: T(n,n+1) = n!*(n-4)/8 = 15*A062199(n-5) for n >= 4 (with A062199(-1) = 0).
%F A341743 T(n, n*(n-1)/2) = 1 if n is odd.
%F A341743 T(n, k) = 0 if n is even and n*(n-1)/2 - n/2 + 1 <= k < n*(n-1)/2.
%F A341743 T(n, n*(n-2)/2) = A001147(n/2) if n is even >= 4.
%e A341743 Irregular triangle T(n,k) (with rows n >= 0 and columns k = 0..n*(n-1)/2) begins
%e A341743   0;
%e A341743   1;
%e A341743   0, 0;
%e A341743   0, 0, 0, 1;
%e A341743   0, 0, 0, 0, 3,  0,  0;
%e A341743   0, 0, 0, 0, 0, 12, 15,  10,   0,   0,  1;
%e A341743   0, 0, 0, 0, 0,  0, 60, 180, 195, 120, 90, 60, 15, 0, 0, 0;
%e A341743   ...
%e A341743 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:
%e A341743         *
%e A341743        /  \
%e A341743       /    \
%e A341743      /      \
%e A341743     *        *
%e A341743      \      /
%e A341743       \    /
%e A341743        *--*
%e A341743 T(5,6) = 15 because we have 5*3 = 15 non-isomorphic labelings of the following Eulerian graph with 5 vertices and 6 edges:
%e A341743          *______*
%e A341743         /|\    /
%e A341743        / | \  /
%e A341743       *  |  \/
%e A341743        \ |  *
%e A341743         \|
%e A341743          *
%e A341743 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}}.
%e A341743 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:
%e A341743 V = {a,b,c,d,e} and E = {{a,b}, {a,c}, {a,d}, {a,e}, {b,c}, {b,d}, {b,e}}.
%e A341743 T(5,10) = 1 because all labelings of the complete graph with 5 vertices (and C(5,2) = 10 edges) are isomorphic.
%e A341743 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.)
%p A341743 # Slow program based on Eqs. (1.4.7), (1.4.18), and (1.4.19) in Harary and Palmer (1973).
%p A341743 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:
%p A341743 u := proc(x, y, M) local n: add(w(n, y)*x^n/n!, n = 0 .. M): end proc:
%p A341743 T := proc(n, k) coeftayl(log(u(x, y, n + 2)), [x, y] = [0, 0], [n, k])*n!: end proc:
%p A341743 # Another, slightly faster, program based on one of the recurrences:
%p A341743 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
%p A341743 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:
%p A341743 # Third program based on another recurrence (the S(n,k) is as above):
%p A341743 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:
%t A341743 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 A341743 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}]];
%t A341743 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 *)
%Y A341743 Cf. A001147, A001710, A003049, A033678, A058878, A062199.
%K A341743 nonn,tabf
%O A341743 0,13
%A A341743 _Petros Hadjicostas_, Feb 18 2021