A003049 -id:A003049 - cp's OEIS frontend

A002854 Number of unlabeled Euler graphs with n nodes; number of unlabeled two-graphs with n nodes; number of unlabeled switching classes of graphs with n nodes; number of switching classes of unlabeled signed complete graphs on n nodes; number of Seidel matrices of order n.

1, 1, 2, 3, 7, 16, 54, 243, 2038, 33120, 1182004, 87723296, 12886193064, 3633057074584, 1944000150734320, 1967881448329407496, 3768516017219786199856, 13670271807937483065795200, 94109042015724412679233018144, 1232069666043220685614640133362240

Offset: 1

N. J. A. Sloane

Also called Eulerian graphs of strength 1.
"Switching" a graph at a node complements all the edges incident with that node. The illustration (see link) shows the 3 switching classes on 4 nodes. Switching at any node is the equivalence relation.
"Switching" a signed simple graph at a node negates the signs of all edges incident with that node.
A graph is an Euler graph iff every node has even degree. It need not be connected. (Note that some graph theorists require an Euler graph to be connected so it has an Euler circuit, and call these graphs "even" graphs.)
The objects being counted in this sequence are unlabeled.

			From _Joerg Arndt_, Feb 05 2010: (Start)
The a(4) = 3 Euler graphs on four nodes are:
   1)  o o     2)  o-o     3)  o-o
       o o         |/          | |
                   o o         o-o
(End)

F. Buekenhout, ed., Handbook of Incidence Geometry, 1995, p. 881.
F. C. Bussemaker, R. A. Mathon and J. J. Seidel, Tables of two-graphs, T.H.-Report 79-WSK-05, Technological University Eindhoven, Dept. Mathematics, 1979; also pp. 71-112 of "Combinatorics and Graph Theory (Calcutta, 1980)", Lect. Notes Math. 885, 1981.
CRC Handbook of Combinatorial Designs, 1996, p. 687.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 114, Eq. (4.7.1).
R. W. Robinson, Enumeration of Euler graphs, pp. 147-153 of F. Harary, editor, Proof Techniques in Graph Theory. Academic Press, NY, 1969.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1979.
J. J. Seidel, A survey of two-graphs, pp. 481-511 of Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Vol. I, Accademia Nazionale dei Lincei, Rome, 1976; also pp. 146-176 in Geometry and Combinatorics: Selected Works of J.J. Seidel, ed. D.G. Corneil and R. Mathon, Academic Press, Boston, 1991..
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Max Alekseyev, Table of n, a(n) for n = 1..88 (terms 1..26 from R. W. Robinson).
P. J. Cameron, Cohomological aspects of two-graphs, Math. Zeit., 157 (1977), 101-119.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs., 3 (2000), #00.1.5.
P. J. Cameron and C. R. Johnson, The number of equivalence patterns of symmetric sign patterns, Discr. Math., 306 (2006), 3074-3077.
G. Greaves, J. H. Koolen, A. Munemasa, and F. Szöllősi, Equiangular lines in Euclidean spaces, arXiv:1403.2155 [math.CO], 2014.
Akihiro Higashitani and Kenta Ueyama, Combinatorial classification of (+/-1)-skew projective spaces, arXiv:2107.12927 [math.RA], 2021.
Akihiro Higashitani and Kenta Ueyama, Combinatorics of graded module categories over skew polynomial algebras at roots of unity, arXiv:2409.10904 [math.RA], 2024. See p. 11.
T. R. Hoffman and J. P. Solazzo, Complex Two-Graphs via Equiangular Tight Frames, arXiv:1408.0334 [math.CO], 2014.
Michael Hofmeister, Counting double covers of graphs, Journal of Graph Theory 12.3 (1988), 437-444. (Beware of a typo!)
V. A. Liskovec, Enumeration of Euler Graphs, (in Russian), Akademiia Navuk BSSR, Minsk., 6 (1970), 38-46. (annotated scanned copy)
C. L. Mallows and N. J. A. Sloane, Two-graphs, switching classes and Euler graphs are equal in number, SIAM J. Appl. Math., 28 (1975), 876-880. (copy at N. J. A. Sloane's home page)
Brendan D. McKay, Eulerian graphs
R. E. Peile, Letter to N. J. A. Sloane, Feb 1989.
R. C. Read, Letter to N. J. A. Sloane, Nov. 1976.
R. W. Robinson, Enumeration of Euler graphs, pp. 147-153 of F. Harary, editor, Proof Techniques in Graph Theory. Academic Press, NY, 1969. (Annotated scanned copy)
N. J. A. Sloane, Switching classes of graphs with 4 nodes.
F. Szöllosi and Patric R. J. Östergård, Enumeration of Seidel matrices, arXiv:1703.02943 [math.CO], 2017.
E. Weisstein's World of Mathematics, Eulerian Graph.
T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982), 47-74.

Cf. A000666, A003049, A085618, A085619, A085620, A007127, A133736.
Bisections: A182012, A182055.
Row sums of A341941.

A002854(n)={ /* Robinson's formula, simplified */ local(s=vector(n)); my( S=0, M()=sum( j=2,n, s[j]*sum( i=1,j-1, s[i]*gcd(i,j))) + sum( i=1,n, i*binomial(s[i],2)+(i\2-1)*s[i]) + !!vecextract(s,4^round(n/2)\3), inc()=!forstep(i=n,1,-1,s[i]n, s[i]=n); next(2))); t==n && S+=2^M()/prod(i=1,n,i^s[i]*s[i]!)); S} \\ M. F. Hasler, Apr 09 2012, adapted for current PARI version on Apr 12, 2018

from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A002854(n): return int(sum(Fraction(1<>1)-1)*r+(q*r*(r-1)>>1) for q, r in p.items())+any(q&1 for q in p),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 03 2024

a(n) = Sum_{s} 2^M(s)/Product_{i} i^s(i)*s(i)!, where the sum is over n-tuples s in [0..n]^n such that n = Sum i*s(i), M(s) = Sum_{iM. F. Hasler, Apr 15 2012; corrected by Sean A. Irvine, Nov 05 2014

Terms up to a(18) confirmed by Vladeta Jovovic, Apr 18 2000
Name edited (changed "2-graph" to "two-graph" to avoid confusion with other 2-graphs) and comments on Eulerian graphs by Thomas Zaslavsky, Nov 21 2013
Name clarified by Thomas Zaslavsky, Apr 18 2019

A133736 Number of graphs on n unlabeled nodes that have an Eulerian cycle, i.e., a cycle that goes through every edge in the graph exactly once.

Original entry on oeis.org

1, 1, 2, 3, 7, 15, 52, 236, 2018, 33044, 1181670, 87720798, 12886156666, 3633055848955, 1944000061673516, 1967881435350411681, 3768516013573481061951, 13670271805989797561408684

Offset: 1

N. J. A. Sloane, based on email from Max Alekseyev, Jan 28 2010

nonn

Any such graph consists of a single connected Euler graph (see A003049) plus a number of isolated vertices.

Chai Wah Wu, Table of n, a(n) for n = 1..88 (terms 1..60 from Max Alekseyev)

A variant of A002854. See also A003049.

a(n) = Sum_{k=1..n} A003049(k).

Edited and extended by Max Alekseyev, Jan 28 2010

A341941 T(n,k) is the number of unlabeled even graphs with n vertices and k edges; irregular triangular array T read by rows (n >= 0, 0 <= k <= n*(n-1)/2).

Original entry on oeis.org

1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 3, 2, 2, 1, 2, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 3, 4, 4, 6, 6, 6, 6, 4, 4, 3, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 3, 4, 7, 9, 16, 18, 25, 24, 29, 26, 25, 16, 15, 8, 5, 4, 3, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 3, 4, 7, 13, 21, 36, 58, 83, 118, 156, 189, 213, 228, 213, 189, 156, 118, 83, 58, 36, 21, 13, 7, 4, 3, 1, 1, 1, 0, 0, 1

Offset: 0

Petros Hadjicostas, Feb 24 2021

Even graphs are colloquially known as Euler graphs (even though, strictly speaking, that is not correct).

Robinson (1969, Section 4, p. 153) actually calculates the o.g.f. of row n=6 of this irregular triangle T(n,k), but he is discouraged by the asymmetry of the coefficients of the polynomial. (The n-th row of this triangle T(n,k) is symmetric only when n is odd). He states: "The processes of Section 1 can be extended brutally to accommodate the line [edge] parameter, but the result does not promise to be pleasing."

			From _Joerg Arndt_, Feb 05 2010: (Start)
The A002854(4) = 3 even graphs on four nodes are:
   1)  o o     2)  o-o     3)  o-o
       o o         |/          | |
                   o o         o-o
(End)
From above, we see that T(4,0) = 1, T(4,1) = T(4,2) = 0, T(4,3) = 1, T(4,4) = 1, and T(4,5) = T(4,6) = 0.
The even graphs corresponding to T(5,0) = T(5,3) = T(5,4) = T(5,5) = T(5,6) = T(5,7) = T(5,10) = 1 appear in Fig. 1.4.3 in Harary and Palmer (p. 15). The last two even graphs, however, corresponding to k = 7 and k = 10, are each missing edges!
Triangle T(n,k) (with rows n >= 0 and columns k = 0..n*(n-1)/2) begins:
n=0: 1;
n=1: 1;
n=2: 1, 0
n=3: 1, 0, 0, 1;
n=4: 1, 0, 0, 1, 1, 0, 0;
n=5: 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1;
n=6: 1, 0, 0, 1, 1, 1, 3, 2, 2, 1, 2, 1, 1, 0, 0, 0;
n=7: 1, 0, 0, 1, 1, 1, 3, 4, 4, 6, 6, 6, 6, 4, 4, 3, 1, 1, 1, 0, 0, 1;
...
Row n=8 is 1, 0, 0, 1, 1, 1, 3, 4, 7, 9, 16, 18, 25, 24, 29, 26, 25, 16, 15, 8, 5, 4, 3, 1, 1, 0, 0, 0, 0.
Row n=9 is 1, 0, 0, 1, 1, 1, 3, 4, 7, 13, 21, 36, 58, 83, 118, 156, 189, 213, 228, 213, 189, 156, 118, 83, 58, 36, 21, 13, 7, 4, 3, 1, 1, 1, 0, 0, 1.
Row n=10 is 1, 0, 0, 1, 1, 1, 3, 4, 7, 13, 26, 43, 91, 152, 290, 473, 777, 1157, 1711, 2236, 2846, 3255, 3557, 3493, 3295, 2785, 2275, 1662, 1173, 742, 475, 258, 151, 79, 44, 19, 13, 6, 3, 1, 1, 0, 0, 0, 0, 0.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973. [See Fig. 1.4.3 (p. 15, some graphs have typos) and p. 114, Eq. (4.7.1), for Sum_{k=0..n*(n-1)/2} T(n,k) = A002854(n).]

Petros Hadjicostas, Maple program for implementing Liskovec's method, 2021.
Valery A. Liskovec, Enumeration of Euler Graphs, (in Russian), Akademiia Navuk BSSR, Minsk., 6 (1970), 38-46. (annotated scanned copy) [In the OEIS, the author contributes under the name _Valery A. Liskovets_.]
Robert W. Robinson, Enumeration of Euler graphs, pp. 147-153 of F. Harary, editor, Proof Techniques in Graph Theory. Academic Press, NY, 1969. (Annotated scanned copy)

Row sums are in A002854.

Cf. A007814, A263626

Maple
```
See the links.
```

Conjecture (due to Peter Luschny): Sum_{k=0}^{n*(n-1)/2} (-1)^k*T(n,k) = A263626(n).
T(n,k) = T(n,n*(n-1)/2 - k) when n is odd (because the complement of an even graph is even when n is odd).
T(n,n*(n-1)/2) = 1 if n is odd.
T(n,n*(n-2)/2) = 1 while T(n,k) = 0 for n*(n-2)/2 + 1 <= k <= n*(n-1)/2 when n is even (because an even graph with an even n number of vertices can have at most n*(n-2)/2 edges).
Write an integer partition a of n into frequency or multiplicity notation: a = Sum_{i=1}^n i*a[i], where 0 <= a[i] <= n for i = 1..n. Following Liskovec (1970, p. 39), let a! = Product_{i=1}^n a[i]! and pi(a) = Product_{i=1}^n i^a[i]. Let also K(a) = Sum_{i=1}^n a[i] (p. 42).
For an integer partition a of n and an integer partition b of r, let a[i] = 0 for i = (n+1)..r, if r > n, and b[i] = 0 for i = (r+1)..n, if n > r. Define a + b = [a[i]+b[i], i=1..max(r,n)].
In the products and sums below, empty partitions are allowed, and empty products are by definition equal to 1.
Define the product p0(a,x) = (Product_{1 <= s < m <= n} (1 + x^lcm(s,m))^(gcd(s,m)*a[s]*a[m])) * (Product_{s=1..n} (1 + x^s)^(s*binomial(a[s],2) + floor((s-1)/2)*a[s])) * (Product_{s even in [1..n]} (1 + x^(s/2))^a[s]) (p. 40).
For an integer n, let alpha(n) = 2^A007814(n) (p. 43). (We actually only need the exponent A007814(n) for comparison, but this is how Liskovec defines it.)
For integer partitions a of n and b of r, define the product p0(+/-)(a,b,x) = (Product_{s=1..n, m=1..r, alpha(s) > alpha(m)} (1 + x^lcm(s,m))^(gcd(s,m)*a[s]*b[m])) * Product_{s=1..n, m=1..r, alpha(s) <= alpha(m)} (1 - x^lcm(s,m))^(gcd(s,m)*a[s]*b[m])) (p. 43).
For an integer partition a of n, define the product p0(-)(a,x) = (Product_{1 <= s < m <= n, alpha(s) = alpha(m)} (1 + x^lcm(s,m))^(gcd(s,m)*a[s]*a[m])) * (Product_{1 <= s < m <= n, alpha(s) <> alpha(m)} (1 - x^lcm(s,m))^(gcd(s,m)*a[s]*a[m])) * (Product_{s=1..n} (1 + x^s)^(s*binomial(a[s],2) + floor((s-1)/2)*a[s])) * (Product_{s even in [1..n]} (1 - x^(s/2))^a[s]) (p. 43).
Then the o.g.f. of row n is Sum_{k=0..n*(n-1)/2} T(n,k)*x^k = Sum_{t=0..n, a partition of t, b partition of n-t} 2^(-K(a+b))/(a! * b! * pi(a+b)) * p0(a,x) * p0(+/-)(a,b,x) * p0(-)(b,x) (p. 42). (When t = 0, partition a of t is empty and b is a partition of n; similarly, when t = n, partition b of n-t is empty and a is a partition of n.)

A158007 Number of simple connected noneulerian graphs on n nodes.

Original entry on oeis.org

0, 1, 1, 5, 17, 104, 816, 10933, 259298, 11685545, 1005551939, 163973291348, 50323109433351, 28999867293155772, 31395440775755417399, 63967594175789887438112, 245868065133951888388878298

Offset: 1

Eric W. Weisstein, Mar 11 2009

nonn

Euler transform of a(n) gives A007126(n+1). [From Vladeta Jovovic, Mar 17 2009]

Chai Wah Wu, Table of n, a(n) for n = 1..82
Eric Weisstein's World of Mathematics, Noneulerian Graph

Cf. A007126, A001349, A003049.

a(n) = A001349(n) - A003049(n). [From Vladeta Jovovic, Mar 17 2009]

More terms via inverse Euler transform of A007126 by R. J. Mathar, Mar 29 2009

A341743 T(n,k) is the number of labeled Eulerian graphs with n vertices and k edges (according to Harary and Palmer) or the number of labeled connected Eulerian graphs with n vertices and k edges (according to Mallows and Sloane); irregular triangle T, read by rows (n >= 0 and 0 <= k <= n*(n-1)/2).

Original entry on oeis.org

0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 12, 15, 10, 0, 0, 1, 0, 0, 0, 0, 0, 0, 60, 180, 195, 120, 90, 60, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 360, 1890, 3675, 4830, 5061, 4410, 3255, 1935, 805, 252, 105, 35, 0, 0, 1

Offset: 0

Petros Hadjicostas, Feb 18 2021

The value T(0,0) = 0 has no physical meaning. It is there because it makes the formula for the bivariate e.g.f.-o.g.f. (shown below) work.
Since T(n,k) counts even connected graphs with n vertices and k edges, for n >= 2, each vertex must have at least two edges, so k >= n. Hence, T(n,k) = 0 for 0 <= k < n.
We have T(n,n) = (n-1)!/2 for n >= 3 because T(n,n) counts the different labelings of cyclic graphs with n vertices and n edges, and we have (n-1)! cyclic permutations of the numbers 1, 2, ..., n. We divide by 2 because we get the same labeling if we flip the cyclic graph over (like a bracelet).
We have T(n, n*(n-1)/2) = 1, if n is odd, because the complete graph on n vertices is even (each vertex 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, if n is even, because in an even graph with n vertices we cannot have more than n*(n-2)/2 = n*(n-1)/2 - n/2 edges.
Finally, we have T(n, n*(n-2)/2) = A001147(n/2), if n is even >= 4, because any labeling in an even graph with n vertices and n*(n-2)/2 edges corresponds to a perfect matching in a complete graph with n vertices (by considering the pairs of vertices that are not connected).
See the comments for A058878 about the different (and sometimes confusing) terminology regarding even and (connected or not) Euler graphs.

			Irregular triangle T(n,k) (with rows n >= 0 and columns k = 0..n*(n-1)/2) begins
  0;
  1;
  0, 0;
  0, 0, 0, 1;
  0, 0, 0, 0, 3,  0,  0;
  0, 0, 0, 0, 0, 12, 15,  10,   0,   0,  1;
  0, 0, 0, 0, 0,  0, 60, 180, 195, 120, 90, 60, 15, 0, 0, 0;
  ...
T(5,5) = 12 because we have (5-1)!/2 = 12 non-isomorphic labelings of the following Eulerian graph with 5 vertices and 5 edges:
        *
       /  \
      /    \
     /      \
    *        *
     \      /
      \    /
       *--*
T(5,6) = 15 because we have 5*3 = 15 non-isomorphic labelings of the following Eulerian graph with 5 vertices and 6 edges:
         *______*
        /|\    /
       / | \  /
      *  |  \/
       \ |  *
        \|
         *
In the above graph, we have 5 choices for the vertex that is common to both triangles and using the other 4 numbers 1, 2, 3, 4 we have the following 3 possible labelings of the other 4 vertices: {{1,2},{3,4}}, {{1,3},{2,4}}, {{1,4},{2,3}}.
T(5,7) = 10 because we have C(5,2) = 10 non-isomorphic labelings of the following Eulerian graph with 5 vertices and 7 edges:
V = {a,b,c,d,e} and E = {{a,b}, {a,c}, {a,d}, {a,e}, {b,c}, {b,d}, {b,e}}.
T(5,10) = 1 because all labelings of the complete graph with 5 vertices (and C(5,2) = 10 edges) are isomorphic.
There are no other (unlabeled) Eulerian graphs with 5 vertices: A003049(5) = 4. (In the name of A003049, the phrase "connected Euler graphs" is according to Mallows and Sloane (1975). According to Harary and Palmer (1973), we only need to say "Euler graphs" because, for them, an Euler graph is connected and even.)

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973; see Eqs. (1.4.7), (1.4.18), and (1.4.19) on pp. 11-16.

P. J. Cameron, Cohomological aspects of two-graphs, Math. Zeit., 157 (1977), 101-119.
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.
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; see the discussion in Section 4, following Eq. (8) on p. 486.

Cf. A001147, A001710, A003049, A033678, A058878, A062199.

# Slow program based on Eqs. (1.4.7), (1.4.18), and (1.4.19) in Harary and Palmer (1973).
w := proc(n, y) local m: expand(simplify(2^(-n)*(y + 1)^(1/2*n*(n - 1))*add(binomial(n, m)*((1 - y)/(y + 1))^(m*(n - m)), m = 0 .. n))): end proc:
u := proc(x, y, M) local n: add(w(n, y)*x^n/n!, n = 0 .. M): end proc:
T := proc(n, k) coeftayl(log(u(x, y, n + 2)), [x, y] = [0, 0], [n, k])*n!: end proc:
# Another, slightly faster, program based on one of the recurrences:
S := proc(n, k) local s, t: add(binomial(n, s)*add((-1)^t*binomial(s*(n - s), t)*binomial(binomial(s, 2) + binomial(n - s, 2), k - t), t = 0 .. k), s = 0 .. n)/2^n: end proc: # A058878
T := proc(n, k) local x, s, t: option remember: if n = 0 then x := 0: end if: if 1/2*n*(n - 1) < k then x := 0: end if: if 1 <= n and 0 <= k and k <= 1/2*n*(n - 1) then x := S(n, k) - add(add(binomial(n - 1, s)*T(s + 1, t)*S(n - 1 - s, k - t), t = 0 .. k), s = 0 .. n - 2): end if: x: end proc:
# Third program based on another recurrence (the S(n,k) is as above):
T1 := proc(n, k) local x, s, t: option remember: if k = 0 and (n = 0 or 2 <= n) then x := 0: end if: if n = 1 and k = 0 then x := 1: end if; if 1/2*n*(n - 1) < k then x := 0: end if: if 2 <= n and 1 <= k and k <= 1/2*n*(n - 1) then x := S(n, k) - add(add((t + 1)*binomial(n, s)*T1(s, t + 1)*S(n - s, k - 1 - t)/k, t = 0 .. k - 2), s = 0 .. n) - add(binomial(n, s)*T1(s, k), s = 0 .. n - 1): end if: x: end proc:

S[n_, k_] := S[n, k] = Sum[Binomial[n, s]*Sum[(-1)^t* Binomial[s*(n-s), t]*Binomial[Binomial[s, 2] + Binomial[n-s, 2], k-t], {t, 0, k}], {s, 0, n}]/2^n;
T[n_, k_] := T[n, k] = If[n == 0 || k > n(n-1)/2, 0, S[n, k] - Sum[Binomial[n-1, s]*T[s+1, t]*S[n-1-s, k-t], {t, 0, k}, {s, 0, n-2}]];
Table[T[n, k], {n, 0, 8}, {k, 0, n(n-1)/2}] // Flatten (* Jean-François Alcover, Feb 14 2023, after 2nd Maple program *)

Sum_{k=0..n} T(n,k) = A033678(n) for n >= 1.
Bivariate e.g.f.-o.g.f.: Sum_{n,k>=0} T(n,k)*(x^n/n!)*y^k = log(Sum_{n,k>=0} A058878(n,k)*(x^n/n!)*y^k) = log(Sum_{n >= 0} (x^n/n!)*[o.g.f. of n-th row of A058878](y)).
Sum_{s=0..n} Sum_{t=0..k} binomial(n,s) * T(s+1,t) * A058878(n-s,k-t) = A058878(n+1,k) for n >= 0 and 0 <= k <= n*(n+1)/2.
Sum_{s=0..n} Sum_{t=0..k} ((t+1)/(k+1)) * binomial(n,s) * T(s,t+1) * A058878(n-s,k-t) = A058878(n,k+1) for n >= 2 and 0 <= k <= n*(n-1)/2 - 1
T(n,k) = A058878(n,k) - Sum_{s=0..n-2} Sum_{t=0..k} binomial(n-1,s) * T(s+1,t) * A058878(n-1-s,k-t) for n >= 1 and 0 <= k <= n*(n-1)/2, and T(n,k) = 0 otherwise.
T(n,k) = A058878(n,k) - Sum_{s=0..n} Sum_{t=0..k-2} ((t+1)/(k+1)) * binomial(n,s) * T(s,t+1) * A058878(n-s,k-1-t) - Sum_{s=0..n-1} binomial(n,s) * T(s,k) for n >= 2 and 1 <= k <= n*(n-1)/2 (with T(1,0) = 1 and T(n,k) = 0 otherwise).
T(n,k) = 0 for n >= 2 and 0 <= k <= n-1.
T(n,n) = A001710(n-1) = (n-1)!/2 for n >= 3.
Conjecture: T(n,n+1) = n!*(n-4)/8 = 15*A062199(n-5) for n >= 4 (with A062199(-1) = 0).
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-2)/2) = A001147(n/2) if n is even >= 4.

cp's OEIS Frontend

A002854 Number of unlabeled Euler graphs with n nodes; number of unlabeled two-graphs with n nodes; number of unlabeled switching classes of graphs with n nodes; number of switching classes of unlabeled signed complete graphs on n nodes; number of Seidel matrices of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A133736 Number of graphs on n unlabeled nodes that have an Eulerian cycle, i.e., a cycle that goes through every edge in the graph exactly once.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A341941 T(n,k) is the number of unlabeled even graphs with n vertices and k edges; irregular triangular array T read by rows (n >= 0, 0 <= k <= n*(n-1)/2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

A158007 Number of simple connected noneulerian graphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A341743 T(n,k) is the number of labeled Eulerian graphs with n vertices and k edges (according to Harary and Palmer) or the number of labeled connected Eulerian graphs with n vertices and k edges (according to Mallows and Sloane); irregular triangle T, read by rows (n >= 0 and 0 <= k <= n*(n-1)/2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A243253 Number of graphs with n nodes that are chordal and Eulerian.

Views

Author

Keywords

Links

Crossrefs

Extensions

A243272 Number of unlabeled simple graphs with n nodes that are Hamiltonian and Eulerian.

Views

Author

Keywords

Links

Crossrefs

Extensions

A243320 Number of simple connected graphs with n nodes that are bipartite and Eulerian.

Views

Author

Keywords

Links

Crossrefs

Extensions

A243322 Number of simple connected graphs with n nodes that are distance regular and Eulerian.