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!)
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). 5
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,12
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)
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.
Ronald C. Read, Euler graphs on labelled nodes, Canadian Journal of Mathematics, 14 (1962), 482-486.
Wikipedia, Eulerian path.
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)
EXAMPLE
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;
...
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. *)
CROSSREFS
Row sums give A006125(n-1) for n>0.
Sequence in context: A284947 A261099 A030120 * A236289 A257536 A019983
KEYWORD
nonn,easy,nice,tabf
AUTHOR
N. J. A. Sloane, Jan 07 2001
EXTENSIONS
Rows 0-2 modified by Petros Hadjicostas, Feb 17 2021 so that row n has n*(n-1)/2 numbers
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)