cp's OEIS Frontend

A058878 Triangle T(n,k) is the number of labeled graphs of even degree with n nodes and k edges (n >= 0, 0 <= k <= n(n-1)/2).

%I A058878 #74 Nov 25 2021 12:54:32
%S A058878 1,1,1,0,1,0,0,1,1,0,0,4,3,0,0,1,0,0,10,15,12,15,10,0,0,1,1,0,0,20,45,
%T A058878 72,160,240,195,120,96,60,15,0,0,0,1,0,0,35,105,252,805,1935,3255,
%U A058878 4515,5481,5481,4515,3255,1935,805,252,105,35,0,0,1,1,0,0,56
%N A058878 Triangle T(n,k) is the number of labeled graphs of even degree with n nodes and k edges (n >= 0, 0 <= k <= n(n-1)/2).
%C A058878 From _Petros Hadjicostas_, Feb 18 2021: (Start)
%C A058878 Harary and Palmer (1973, p. 11) define an Euler graph to be a connected even graph (i.e., a connected graph where each vertex/node has an even degree). On the other hand, Mallows and Sloane (1975) and Cameron (1977) define an Euler graph to be an even one (i.e., a non-necessarily connected graph where each node has an even degree).
%C A058878 Read (1962) uses both of the above terminologies, although in his Introduction, he indicates that the second usage (calling an even graph Euler) "is not, strictly speaking, correct."
%C A058878 The name of this irregular triangular array T(n,k) does not assume that the graphs are necessarily connected. Thus, according to Harary and Palmer (1973, p. 11), T(n,k) here would be the number of labeled even graphs with n nodes and k edges, but not the number of labeled Euler graphs with n nodes and k edges. (According to these authors, the total number of labeled Euler graphs with n nodes would be A033678(n).)
%C A058878 On the other hand, according to Cameron (1977, pp. 116-117), T(n,k) here gives the number of labeled Euler graphs with n nodes and k edges. (According to Mallows and Sloane (1975) and Cameron (1977), the total number of labeled connected Euler graphs with n nodes would be A033678(n).)
%C A058878 See the links below for more discussion about this confusing topic.
%C A058878 We have T(n, n*(n-1)/2) = 1, if n is odd, because the complete graph on n nodes is even (each node has degree n-1) and has only one non-isomorphic labeling.
%C A058878 We have T(n, n*(n-1)/2 - s) = 0 for s = 0, 1, 2, ..., (n/2)-1 when n is even, because in an even graph with n nodes we cannot have more than n*(n-2)/2 = n*(n-1)/2 - n/2 edges.
%C A058878 Finally, we have T(n, n*(n-1)/2 - n/2) = A001147(n/2), if n is even, because any labeling in an even graph with n nodes and n*(n-1)/2 - n/2 = n*(n-2)/2 edges corresponds to a perfect matching in a complete graph with n nodes (by considering the pairs of vertices that are not connected). See the link on perfect matchings below. (End)
%C A058878 From _Petros Hadjicostas_, Feb 20 2021: (Start)
%C A058878 To prove that T(n, n*(n-1)/2 - k) = T(n,k) for 0 <= k <= n*(n-1)/2, if n is odd, note that the complement of an even graph is also even. Any even graph counted by T(n,k) has a complement counted by T(n, n*(n-1)/2 - k) and vice versa.
%C A058878 Alternatively, we might use the o.g.f. of the n-th row given by Harary and Palmer (1973) (see the Formula section below) to easily prove that Sum_{k=0..n*(n-1)/2} T(n, n*(n-1)/2 - k)*y^k = Sum_{k=0..n*(n-1)/2} T(n,k)*y^k when n is odd. The proof fails when n is even. (End)
%D A058878 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 13, Eq. (1.4.7).
%H A058878 P. J. Cameron, <a href="https://doi.org/10.1007/BF01215145">Cohomological aspects of two-graphs</a>, Math. Zeit., 157 (1977), 101-119; see Proposition 8.5, p. 117.
%H A058878 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 A058878 Math Stackexchange, <a href="https://math.stackexchange.com/questions/60894/how-to-find-the-number-of-perfect-matchings-in-complete-graphs">How to find the number of perfect matchings in complete graphs?</a>, August 31, 2011.
%H A058878 Math Stackexchange, <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 A058878 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.
%H A058878 Wikipedia, <a href="https://en.wikipedia.org/wiki/Eulerian_path">Eulerian path</a>.
%F A058878 T(n,k) = [x^k] (2^(-n) * (1+x)^(n*(n-1)/2) * Sum_{s=0..n} binomial(n, s)*((1 -x)/(1+x))^(s*(n-s))).
%F A058878 From _Petros Hadjicostas_, Feb 18 2021: (Start)
%F A058878 T(n,k) = (1/2^n) * Sum_{s=0..n} binomial(n,s) * Sum_{t=0..k} (-1)^t * binomial(s*(n-s), t) * binomial(binomial(s,2) + binomial(n-s, 2), k-t) for n >= 0 and 0 <= k <= n*(n-1)/2.
%F A058878 T(n, n*(n-1)/2) = 1 if n is odd.
%F A058878 T(n, k) = 0 if n is even and n*(n-1)/2 - n/2 + 1 <= k < n*(n-1)/2.
%F A058878 T(n, n*(n-1)/2 - n/2) = A001147(n/2) if n is even.
%F A058878 T(n,k) = A054669(n,k) for n >= 0 and 0 <= k <= n*(n-1)/2 - (n/2)*[0 == n mod 2].
%F A058878 T(n, n*(n-1)/2 - k) = T(n,k) for 0 <= k <= n*(n-1)/2 if n is odd. (End)
%e A058878 Irregular triangle T(n,k) (with rows n >= 0 and columns k = 0..n*(n-1)/2) begins
%e A058878   1;
%e A058878   1,
%e A058878   1, 0,
%e A058878   1, 0, 0,  1;
%e A058878   1, 0, 0,  4,  3,  0,   0;
%e A058878   1, 0, 0, 10, 15, 12,  15,  10,   0,   0,  1;
%e A058878   1, 0, 0, 20, 45, 72, 160, 240, 195, 120, 96, 60, 15, 0, 0, 0;
%e A058878   ...
%p A058878 w := p->expand(simplify(2^(-p)*(1+x)^(p*(p-1)/2)*add(binomial(p,n)*( (1-x)/(1+x))^(n*(p-n)), n=0..p))); T := (n,k)->coeff(w(n),x,k);
%t A058878 w[p_] := 2^-p*(1+x)^(p*(p-1)/2)*Sum[Binomial[p, n]*((1-x)/(1+x))^(n*(p-n)), {n, 0, p}]; T[n_, k_] := SeriesCoefficient[w[n], {x, 0, k}]; Table[T[n, k], {n, 0, 8}, {k, 0, n(n-1)/2}] // Flatten (* _Jean-François Alcover_, Jan 12 2015, translated from Maple *) (* Edited by _Petros Hadjicostas_, Feb 18 2021 to make sure the lengths of rows n = 0, 1, 2 are n*(n-1)/2 + 1 = 1, 1, 2, respectively. *)
%Y A058878 Row sums give A006125(n-1) for n>0.
%Y A058878 Cf. A001147, A033678, A054669.
%K A058878 nonn,easy,nice,tabf
%O A058878 0,12
%A A058878 _N. J. A. Sloane_, Jan 07 2001
%E A058878 Rows 0-2 modified by _Petros Hadjicostas_, Feb 17 2021 so that row n has n*(n-1)/2 numbers