login
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).
3
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
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.
Sequence in context: A326477 A285650 A144161 * A131027 A133475 A242106
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