login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 17 03:16 EST 2022. Contains 350377 sequences. (Running on oeis4.)