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,11

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)

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.

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)

Example

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

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

Prog

(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

Crossrefs

Row sums are A006125(n-1).

Essentially the same table as A058878.

Cf. A001147, A033678, A340312.

Sequence in context: A326477 A285650 A144161 * A131027 A133475 A242106

Adjacent sequences: A054666 A054667 A054668 * A054670 A054671 A054672

Keyword

easy,nonn,tabf

Author

Vladeta Jovovic, Apr 18 2000

Extensions

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

Name edited by Petros Hadjicostas, Feb 18 2021

Status

approved