A054669 Triangular array T(n,k) giving the number of labeled even graphs with n nodes and k edges for n >= 0 and 0 <= k <= n*(n-1-[0 == n mod 2])/2 (with no trailing zeros).

1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 4, 3, 1, 0, 0, 10, 15, 12, 15, 10, 0, 0, 1, 1, 0, 0, 20, 45, 72, 160, 240, 195, 120, 96, 60, 15, 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, 210, 672, 2800, 9320, 24087

Offset: 0

Author

Vladeta Jovovic, Apr 18 2000

Keywords

• easy
• nonn
• tabf

Comments

From Petros Hadjicostas, Feb 18 2021: (Start)

This is the same as irregular array A058878 but without the (n/2)*[0 == n mod 2] trailing zeros at the end of each row n.

For n odd, we have T(n,n*(n-1)/2) = 1 at end of row n because a complete graph with n nodes and n*(n-1)/2 edges is even and has only one labeling.

For n even, the maximum number of edges an even graph with n nodes can have is n*(n-2)/2 = n*(n-1)/2 - n/2. We have T(n,n*(n-2)/2) = A001147(n/2) because each labeling of an even graph that has n nodes and n*(n-2)/2 edges corresponds to a perfect matching of the complete graph with n vertices (by considering the pairs of vertices that are not connected).

For a discussion about the confusion in defining Euler graphs, see the comments for A058878. (End)

Examples

			Triangle T(n,k) (with rows n >= 0 and columns k = 0..n*(n-1-[0==n mod 2])/2) begins:
  1;
  1;
  1;
  1, 0, 0,  1;
  1, 0, 0,  4,  3;
  1, 0, 0, 10, 15, 12,  15,  10,   0,   0,  1;
  1, 0, 0, 20, 45, 72, 160, 240, 195, 120, 96, 60, 15;
  ...
		

References

• F. Harary and E. Palmer, Graphical Enumeration, Academic Press, New York, 1973; pp. 13-15.

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1295
• P. J. Cameron, Cohomological aspects of two-graphs, Math. Zeit., 157 (1977), 101-119. [See pp. 116-117, where he uses the informal term "labelled Eulerian graph" for "labelled even graph".]
• 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.

Crossrefs

Row sums are A006125(n-1).

Essentially the same table as A058878.

Cf. A001147, A033678, A340312.

Programs

Maple

CoeffList := p -> op(PolynomialTools:-CoefficientList(p, x)):
w := p -> factor(2^(-p)*(1 + x)^(p*(p - 1)/2)*
          add(binomial(p, n)*((1 - x)/(1 + x))^(n*(p - n)), n=0..p)):
seq(print(CoeffList(w(n))), n = 0..6); # Peter Luschny, Feb 18 2021

Mathematica

T[n_] := (1/2^n)(1+x)^Binomial[n, 2] Sum[Binomial[n, k] ((1-x)/(1+x))^(k(n-k)), {k, 0, n}] // CoefficientList[#, x]&;
T /@ Range[0, 8] // Flatten (* Jean-François Alcover, Feb 20 2021, after Andrew Howroyd *)

PARI

Row(n)=Vecrev(2^(-n)*(1+x)^binomial(n, 2)*sum(k=0, n, binomial(n, k)*((1-x)/(1+x))^(k*(n-k)))) \\ Andrew Howroyd, Jan 05 2021

Formula

T(n,k) = [y^k] 2^(-n)*(1+y)^C(n, 2)*Sum_{s=0..n} C(n, s)*((1-y)/(1+y))^(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).

T(n, n*(n-1)/2) = 1 if n is odd.

T(n, n*(n-2)/2) = A001147(n/2) if n is even.

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

Extensions

T(0,0) = 1 prepended by Andrew Howroyd, Jan 09 2021

Name edited by Petros Hadjicostas, Feb 18 2021