A002854 -id:A002854 - cp's OEIS frontend

A182055 Bisection of A002854.

1, 2, 7, 54, 2038, 1182004, 12886193064, 1944000150734320, 3768516017219786199856, 94109042015724412679233018144, 30739974599837035594494908346443726272, 133517867425328719965824261177376949378463724928, 7828241053490735575604692213976871639067242060743800973568

Offset: 1

N. J. A. Sloane, Apr 08 2012

nonn

Cf. A002854, A182012.

A036356 Erroneous version of A002854.

Original entry on oeis.org

1, 1, 2, 3, 7, 16, 54, 283

Offset: 0

dead

A282320 Erroneous version of A002854.

Original entry on oeis.org

1, 1, 2, 3, 7, 16, 54, 241, 2038, 33120

Offset: 1

dead

Included in accordance with the OEIS policy of including erroneous published sequences to serve as pointers to the correct versions.

Hofmeister, Michael. "Counting double covers of graphs." Journal of graph theory 12.3 (1988): 437-444.

A003049 Number of connected Eulerian graphs with n unlabeled nodes.

Original entry on oeis.org

1, 0, 1, 1, 4, 8, 37, 184, 1782, 31026, 1148626, 86539128, 12798435868, 3620169692289, 1940367005824561, 1965937435288738165, 3766548132138130650270, 13666503289976224080346733

Offset: 1

N. J. A. Sloane

These are connected graphs with every node of even degree (cf. A002854).

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 117.
Valery A. Liskovets, Enumeration of Euler graphs. (Russian), Vesci Akad. Navuk BSSR, Ser. Fiz.-Mat. Navuk 1970, No.6, 38-46 (1970). Math. Rev., Vol. 44, 1972, p. 1195, #6557.
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, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1979.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Chai Wah Wu, Table of n, a(n) for n = 1..88 (terms 1..60 from Max Alekseyev)
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Erich Friedman, Illustration of initial terms
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.
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 on N. J. A. Sloane's Home Page]
Brendan McKay, Combinatorial Data (Eulerian graphs).
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)
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Eulerian Graph.

Cf. A002854, A008683.

A002854 = Import["https://oeis.org/A002854/b002854.txt", "Table"][[All, 2]];
(* EulerInvTransform is defined in A022562 *)
EulerInvTransform[A002854] (* Jean-François Alcover, Aug 27 2019, updated Mar 17 2020 *)

from functools import lru_cache
from itertools import combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A003049(n):
    @lru_cache(maxsize=None)
    def b(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)))
    @lru_cache(maxsize=None)
    def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
    return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n # Chai Wah Wu, Jul 03 2024

Let B(x) = g.f. for A002854. Then g.f. A(x) for A003049 satisfies 1 + B(x) = exp(Sum_{n>=1} A(x^n)/n). - Robinson (1969).
Inverse Euler transform of A002854. (This is equivalent to the Robinson formula.) - Franklin T. Adams-Watters, Jul 24 2006
Let B(x) = g.f. for A002854. Then A(x) = Sum_{m >= 1} (mu(m)/m) * log(1 + B(x^m)), where mu(m) = A008683(m). (This is essentially a re-statement of the equation on p. 151 in Robinson (1969).) - Petros Hadjicostas, Feb 24 2021

a(1)-a(26) were computed by R. W. Robinson

More terms from Vladeta Jovovic, Apr 18 2000

A007869 Number of complementary pairs of graphs on n nodes. Also number of unlabeled graphs with n nodes and an even number of edges.

Original entry on oeis.org

1, 1, 2, 6, 18, 78, 522, 6178, 137352, 6002584, 509498932, 82545586656, 25251015686776, 14527077828617744, 15713242984902154384, 32000507852263779299344, 122967932076766466347469888, 893788862572805850273939095424, 12318904626562502262191503745716384

Offset: 1

Peter J. Cameron

Andrew Howroyd, Table of n, a(n) for n = 1..50
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Nevena Francetić, Sarada Herke, and Ian M. Wanless, Parity of Sets of Mutually Orthogonal Latin Squares, arXiv:1703.04764 [math.CO], 2017. See Section 4.1.
Tadeusz Sozański, Enumeration of weak isomorphism classes of signed graphs, J. Graph Theory 4 (1980), no. 2, 127-144. (Zentralblatt 434 #05059)
Ferenc Szöllosi, The two-distance sets in dimension four, arXiv:1806.07861 [math.MG], 2018. See Table 1.

Cf. A000088, A000171.

Cf. A054960 for graphs with an odd number of edges.

Needs["Combinatorica`"]; Table[Total[Table[NumberOfGraphs[n,m],{m,0,Binomial[n,2],2}]],{n,1,15}]  (* Geoffrey Critzer, Oct 20 2012; modified by Harvey P. Dale, Aug 08 2013 *)

a(n)={local(p=vector(n));
my(S=0, J() = sum(j=0, floor((n-1)/2), p[2*j+1]),
    I2() = (sum(i=1, n, sum(j=1, n, p[i]*p[j]*gcd(i, j))) - J())/2,
    M1() = (abs((p[1]-0)*(p[1]-1)) + sum(j=2, n, if(0!=(j%4), p[j], 0))),
inc()=!forstep(i=n, 1, -1, p[i]n, p[i]=n); next(2))); t==n && S+=(if(M1() == 0, 2^I2()/prod(i=1, n, i^p[i]*p[i]!), 0) + 2^I2()/prod(i=1, n, i^p[i]*p[i]!))/2); S} \\ This is a modification of M. F. Hasler's PARI program from A002854. - Petros Hadjicostas, Mar 02 2021

Average of A000088 and A000171.

More terms from Vladeta Jovovic, Jul 19 2000

Terms a(18) and beyond from Andrew Howroyd, Sep 17 2018

A054732 Number of inequivalent n-state 2-input 2-output automata with respect to input and output permutations.

Original entry on oeis.org

2, 44, 2038, 176936, 20943790, 3108818680, 553255960308, 114776687721990, 27196943499525498, 7246997465494260922, 2144966703605620242622, 698192439379511764136358, 247879443355186031710674326, 95324955498172729163827175460, 39473725728022499730768584065928, 17511877093585563126312782917277602

Offset: 1

Vladeta Jovovic, Apr 22 2000

nonn

From Petros Hadjicostas, Mar 08 2021: (Start)
The PARI program below implements the formula in Theorem 6.3 (p. 108) in Harrison (1965) with k = 2 inputs and p = 2 outputs. We use the partitions of 2 twice.
All partitions in the program are written in frequency or multiplicity notation (so, the partitions of 2 are written as 1*2 + 2*0 and 1*0 + 2*1; see the matrices q and qq in the program).
If (s_1, ..., s_n) is a partition of n in frequency notation (with s_i >= 0 for all i and Sum_{i=1..n} i*s_i = n) and we need an element s_j with j > n, we define it to be 0. That is why we use sumdiv(lcm(r, s), d, if(d < n+1, d*p[d], 0)) and sumdiv(lcm(r, s), d, if(d < 3, d*qq[jj, d], 0)) in the program. (End)

F. Harary and E. Palmer, Graphical Enumeration, 1973.

Michael A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, (1965), 100-113. [See Theorem 6.3 (p. 108) with k = p = 2 and Table V (p. 112).]

Cf. A002854.

A054732(n) = {local(p=vector(n)); local(q=matrix(2, 2)); local(qq=matrix(2,2)); q[1, 1] = 2; q[1, 2] = 0; q[2, 1]=0; q[2, 2]=1;
qq[1, 1] = 2; qq[1, 2] = 0; qq[2, 1]=0; qq[2, 2]=1;
my(S=0, A() = sum(jj=1, 2, sum(j=1, 2, prod(r=1, n, prod(s=1, 2, (sumdiv(lcm(r, s), d, if(d < n+1, d*p[d], 0)) * sumdiv(lcm(r, s), d, if(d < 3, d*qq[jj, d], 0)))^(p[r]*q[j, s]*gcd(r, s))))))/4,
inc()=!forstep(i=n, 1, -1, p[i]n, p[i]=n); next(2))); t==n && S+ = A()/prod(i=1, n, i^p[i]*p[i]!)); S} \\ This is a modification of M. F. Hasler's PARI program from A002854. - Petros Hadjicostas, Mar 08 2021

Terms a(14)-a(16) from Petros Hadjicostas, Mar 08 2021

A054050 Number of nonisomorphic binary n-state automata.

Original entry on oeis.org

1, 10, 129, 2836, 83061, 3076386, 136647824, 7081061404, 419223006090, 27914819962058, 2064872379041701, 167986348586006675, 14906892578198245332, 1432903480780688968334, 148318150277923875087238, 16447662583606982784243526, 1945436946407977282783367806, 244476687257496605058725664611

Offset: 1

Vladeta Jovovic, Apr 29 2000

nonn

Also, number of isomorphism classes of ordered pairs of endofunctions (i.e., an order pair (f,g) of functions) from {1,...,n} to itself. - Christian G. Bower, Dec 18 2003

			From _Petros Hadjicostas_, Mar 08 2021: (Start)
For n = 2, we have the partitions 1*2 + 2*0 and 1*0 + 2*1 of 2 (in frequency notation). The corresponding denominators in _Christian G. Bower_'s formula are 1^2*2!*2^0*0! = 2 and 1^0*0!*2^1*1! = 2.
Also, fixA[s_1 = 2, s_2 = 0] = (Sum_{d|1} d*s_d)^(2*s_1) * (Sum_{d|2} d*s_d)^(2*s_2) = (1*s_1)^(2*s_1) = 16. In addition, fixA[s_1 = 0, s_2 = 1] = (Sum_{d|1} d*s_d)^(2*s_1) * (Sum_{d|2} d*s_d)^(2*s_2) = (1*s_1 + 2*s_2)^(2*s_2) = (0 + 2)^2 = 4. Hence a(2) = 16/2 + 4/2 = 10. (End)

F. Harary and E. Palmer, Graphical Enumeration, 1973.

M. A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, (1965), 100-113. [See p. 107 (Theorem 6.1 with k = 2 and p = 1) and p. 110 (Table I).]

Cf. A001372, A002854, A054745, A054051.

A054050(n)={local(p=vector(n));
my(S=0, A() = prod(i=1, n, sumdiv(i, d, d*p[d])^(2*p[i])),
inc()=!forstep(i=n, 1, -1, p[i]n, p[i]=n); next(2))); t==n && S+ = A()/prod(i=1, n, i^p[i]*p[i]!)); S} \\ This is a modification of M. F. Hasler's PARI program from A002854. - Petros Hadjicostas, Mar 08 2021

a(n) = Sum_{1*s_1+2*s_2+...=n} fixA[s_1, s_2, ...]/(1^s_1*s_1!*2^s_2*s_2!*...), where fixA[s_1, s_2, ...] = Product_{i>=1} (Sum_{d|i} d*s_d)^(2*s_i). - Christian G. Bower, Dec 18 2003 [Corrected by Petros Hadjicostas, Mar 08 2021 using Theorem 6.1 in Harrison (1965) with k = 2 inputs and p = 1 output.]

a(16)-a(18) from Petros Hadjicostas, Mar 08 2021

A182012 Number of graphs on 2n unlabeled nodes all having odd degree.

Original entry on oeis.org

1, 3, 16, 243, 33120, 87723296, 3633057074584, 1967881448329407496, 13670271807937483065795200, 1232069666043220685614640133362240, 1464616584892951614637834432454928487321792, 23331378450474334173960358458324497256118170821672192, 5051222500253499871627935174024445724071241027782979567759187712

Offset: 1

Georgi Guninski, Apr 06 2012

As usual, "graph" means "simple graph, without self-loops or multiple edges".

The graphs on 2n vertices all having odd degrees are just the complements of those having all even degrees. That's why the property of all odd degrees is seldom mentioned. Therefore this sequence is just every second term of A002854. - Brendan McKay, Apr 08 2012

			The 3 graphs on 4 vertices are [(0, 3), (1, 3), (2, 3)], [(0, 2), (1, 3)], [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]: the tree with root of order 3, the disconnected graph consisting of two complete 2-vertex graphs, and the complete graph.

Sequence Fans Mailing List, Discussion, April 2012.
N. J. A. Sloane, The 16 graphs on 6 nodes

Cf. A210345, A210346, A000088. Bisection of A002854.

def graphsodddegree(MAXN=5):
    """
    requires optional package "nauty"
    """
    an=[]
    for n in range(1,MAXN+1):
        gn=graphs.nauty_geng("%s"%(2*n))
        cac={}
        a=0
        for G in gn:
            d = G.degree_sequence()
            if all(i % 2 for i in d):
                a += 1
        print('a(%s)=%s'%(n,a))
        an += [a]
    return an

a(n) = A002854(2n).

Terms from a(6) on added from A002854. - N. J. A. Sloane, Apr 08 2012

A000282 Finite automata.

Original entry on oeis.org

3, 70, 3783, 338475, 40565585, 6061961733, 1083852977811, 225615988054171, 53595807366038234, 14308700593468127485, 4241390625289880226714, 1382214286200071777573643, 491197439886557439295166226, 189044982636675290371386547592, 78334771617452038208125184627931, 34771576300926271400714044414858372

Offset: 1

N. J. A. Sloane

nonn

Given the name of A054747, another name for this sequence can be "Number of inequivalent n-state 2-input 2-output connected automata with respect to an input permutation." - Petros Hadjicostas, Mar 08 2021

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

Christian G. Bower, PARI programs for transforms, 2007.
Michael A. Harrison, A census of finite automata, Canad. J. Math., 17, No. 1, (1965), 100-113. [First apply Theorem 6.2 (p. 107) with k = p = 2 to get A054747. Then apply Theorem 7.2 (p. 110) to get the number of classes of connected automata counted by A054747. - _Petros Hadjicostas_, Mar 08 2021]
N. J. A. Sloane, Maple programs for transforms, 2001-2020.

Cf. A002854, A054732, A054747.

/* This program is a modification of Christian G. Bower's PARI program for the inverse Euler transform from the link above. */
lista(nn) = {local(A=vector(nn+1)); for(n=1, nn+1, A[n]=if(n==1, 1, A054747(n-1))); local(B=vector(#A-1,n,1/n),C); A[1] = 1; C = log(Ser(A)); A=vecextract(A,"2.."); for(i=1, #A, A[i] = polcoeff(C,i)); A = dirdiv(A,B); } \\ Petros Hadjicostas, Mar 08 2021

Inverse Euler transform of A054747. - Petros Hadjicostas, Mar 08 2021

More terms from Vladeta Jovovic, Apr 22 2000

Terms a(14)-a(16) from Petros Hadjicostas, Mar 08 2021

A049313 Switching classes of tournaments on n nodes.

Original entry on oeis.org

1, 1, 1, 2, 2, 6, 12, 79, 792, 19576, 886288, 75369960, 11856006240, 3467430423264, 1893448825054528, 1938818712501985736, 3737086626658278741376, 13606268915761294708760704, 93863103860384959101157737728

Offset: 1

Peter J. Cameron

			a(4)=2: the "local orders" form one switching class and the class containing a 3-cycle dominating a point the other.

L. Babai and P. J. Cameron, Automorphisms and enumeration of switching classes of tournaments, Electron. J. Combin., 7 (2000), no. 1, Research Paper 38, 25 pp.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

Cf. A002854.

Same as for switching classes of graphs but summed only over "level" permutations (same power of 2 divides all cycle lengths)

More terms from Vladeta Jovovic, Mar 01 2000

cp's OEIS Frontend

A182055 Bisection of A002854.

Views

Author

Keywords

Crossrefs

A036356 Erroneous version of A002854.

Views

Author

Keywords

A282320 Erroneous version of A002854.

Views

Author

Keywords

Comments

References

A003049 Number of connected Eulerian graphs with n unlabeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A007869 Number of complementary pairs of graphs on n nodes. Also number of unlabeled graphs with n nodes and an even number of edges.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A054732 Number of inequivalent n-state 2-input 2-output automata with respect to input and output permutations.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A054050 Number of nonisomorphic binary n-state automata.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A182012 Number of graphs on 2n unlabeled nodes all having odd degree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

Formula

Extensions

A000282 Finite automata.

Views

Author

Keywords