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

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, 72, 160, 240, 195, 120, 96, 60, 15, 0, 0, 0, 1, 0, 0, 35, 105, 252, 805, 1935, 3255, 4515, 5481, 5481, 4515, 3255, 1935, 805, 252, 105, 35, 0, 0, 1, 1, 0, 0, 56

Offset: 0

Author

N. J. A. Sloane, Jan 07 2001

Keywords

• nonn
• easy
• nice
• tabf

Comments

From Petros Hadjicostas, Feb 18 2021: (Start)

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

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

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

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

See the links below for more discussion about this confusing topic.

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.

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.

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)

From Petros Hadjicostas, Feb 20 2021: (Start)

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.

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)

Examples

			Irregular triangle T(n,k) (with rows n >= 0 and columns k = 0..n*(n-1)/2) begins
  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, 72, 160, 240, 195, 120, 96, 60, 15, 0, 0, 0;
  ...
		

References

• F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 13, Eq. (1.4.7).

Links

• P. J. Cameron, Cohomological aspects of two-graphs, Math. Zeit., 157 (1977), 101-119; see Proposition 8.5, p. 117.
• 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, How to find the number of perfect matchings in complete graphs?, August 31, 2011.
• Math Stackexchange, 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.
• Wikipedia, Eulerian path.

Crossrefs

Row sums give A006125(n-1) for n>0.

Cf. A001147, A033678, A054669.

Programs

Maple

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

Mathematica

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

Formula

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

From Petros Hadjicostas, Feb 18 2021: (Start)

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.

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-1)/2 - n/2) = A001147(n/2) if n is even.

T(n,k) = A054669(n,k) for n >= 0 and 0 <= k <= n*(n-1)/2 - (n/2)*[0 == n mod 2].

T(n, n*(n-1)/2 - k) = T(n,k) for 0 <= k <= n*(n-1)/2 if n is odd. (End)

Extensions

Rows 0-2 modified by Petros Hadjicostas, Feb 17 2021 so that row n has n*(n-1)/2 numbers