A000568 -id:A000568 - cp's OEIS frontend

A334335 Inverse Euler transform of A000568.

1, 0, 1, 2, 8, 43, 398, 6413, 184596, 9540998, 894012628, 153204356304, 48387996396590, 28352880689501075, 30992600581556641380, 63499394791445838416399, 244849247994227524521679624, 1783153933475289754036309451798, 24603857772350530383609071261316942

Offset: 1

Pontus von Brömssen, Apr 23 2020

nonn

It appears that a(n) is the number of connected even graphs with n vertices, as defined in the Andersson paper (verified for n <= 10): a graph G is even if, for a given orientation of its edges, all automorphisms of G reverse the orientation of an even number of edges. If this is true, it means that A000568(n) is the number of even graphs (not necessarily connected) with n vertices. [This has been proved by Royle et al. 2023. - Pontus von Brömssen, Apr 06 2022]

Pontus von Brömssen, Table of n, a(n) for n = 1..76
Pontus Andersson (von Brömssen), On the asymptotic distributions of subgraph counts in a random tournament, Random Structures & Algorithms 13 (1998), 249-260.
Gordon F. Royle, Cheryl E. Praeger, S. P. Glasby, Saul D. Freedman, and Alice Devillers, Tournaments and even graphs are equinumerous, Journal of Algebraic Combinatorics 57 (2023), 515-524; arXiv version, arXiv:2204.01947 [math.CO], 2022.

Cf. A000568.

from functools import lru_cache
from itertools import product
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A334335(n):
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<<(sum(p[r]*p[s]*gcd(r,s) for r,s in product(p.keys(),repeat=2))-sum(p.values())>>1),prod(q**p[q]*factorial(p[q]) for q in p)) for p in partitions(n) if all(q&1 for q in p)))
    @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

A151879 Produced by same formula that gives A000568 (unlabeled tournaments), but with LCM instead of GCD in the exponent.

Original entry on oeis.org

1, 1, 1, 2, 8, 52, 528, 8632, 252928, 15494032, 2050181376, 525675623520, 239430803636224, 189133678584246592, 260786292437892272128, 638374284463941710477184, 2842966981002836533300953088, 23866119110542723640161098330368, 394851495657676102988098496313229312

Offset: 0

N. J. A. Sloane, Jul 21 2009

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[Sum[LCM[v[[i]], v[[j]]], {j, 1, i - 1}], {i, 2, Length[v]} ] + Sum[Quotient[v[[i]], 2], {i, 1, Length[v]}];
oddp[v_] := (For[i = 1, i <= Length[v], i++, If[BitAnd[v[[i]], 1] == 0, Return[0]]]; 1);
a[n_] := a[n] = (s = 0; Do[If[oddp[p] == 1, s += permcount[p]*2^edges[p]], {p, IntegerPartitions[n]}]; s/n!); (* Jean-François Alcover, Nov 13 2017, after Andrew Howroyd *)

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, lcm(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
oddp(v) = {for(i=1, #v, if(bitand(v[i], 1)==0, return(0))); 1}
a(n) = {my(s=0); forpart(p=n, if(oddp(p), s+=permcount(p)*2^(edges(p)))); s/n!} \\ Andrew Howroyd, Feb 29 2020

from math import prod, lcm, factorial
from fractions import Fraction
from itertools import product
from sympy.utilities.iterables import partitions
def A151879(n): return int(sum(Fraction(1<<(sum(p[r]*p[s]*lcm(r,s) for r,s in product(p.keys(),repeat=2))-sum(p.values())>>1),prod(q**p[q]*factorial(p[q]) for q in p)) for p in partitions(n) if all(q&1 for q in p))) # Chai Wah Wu, Jul 01 2024

a(n) = Sum_{j} (1/(Product (k^(j_k) (j_k)!))) * 2^{t_j}, where j runs through all partitions of n into odd parts, say with j_1 parts of size 1, j_3 parts of size 3, etc., and t_j = (1/2)*[ Sum_{r=1..n, s=1..n} j_r j_s lcm(r,s) - Sum_{r} j_r ].

A006125 a(n) = 2^(n*(n-1)/2).

Original entry on oeis.org

1, 1, 2, 8, 64, 1024, 32768, 2097152, 268435456, 68719476736, 35184372088832, 36028797018963968, 73786976294838206464, 302231454903657293676544, 2475880078570760549798248448, 40564819207303340847894502572032, 1329227995784915872903807060280344576

Offset: 0

N. J. A. Sloane

Number of graphs on n labeled nodes; also number of outcomes of labeled n-team round-robin tournaments.
Number of perfect matchings of order n Aztec diamond. [see Speyer]
Number of Gelfand-Zeitlin patterns with bottom row [1,2,3,...,n]. [Zeilberger]
For n >= 1 a(n) is the size of the Sylow 2-subgroup of the Chevalley group A_n(2) (sequence A002884). - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 30 2001
From James Propp: (Start)
a(n) is the number of ways to tile the region
           o-----o
           |.....|
        o--o.....o--o
        |...........|
     o--o...........o--o
     |.................|
  o--o.................o--o
  |.......................|
  |.......................|
  |.......................|
  o--o.................o--o
     |.................|
     o--o...........o--o
        |...........|
        o--o.....o--o
           |.....|
           o-----o
(top-to-bottom distance = 2n) with dominoes like either of
  o--o      o-----o
  |..|  or  |.....|
  |..|      o-----o
  |..|
  o--o
(End)
The number of domino tilings in A006253, A004003, A006125 is the number of perfect matchings in the relevant graphs. There are results of Jockusch and Ciucu that if a planar graph has a rotational symmetry then the number of perfect matchings is a square or twice a square - this applies to these 3 sequences. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 12 2001
Let M_n denotes the n X n matrix with M_n(i,j)=binomial(2i,j); then det(M_n)=a(n+1). - Benoit Cloitre, Apr 21 2002
Smallest power of 2 which can be expressed as the product of n distinct numbers (powers of 2), e.g., a(4) = 1024 = 2*4*8*16. Also smallest number which can be expressed as the product of n distinct powers. - Amarnath Murthy, Nov 10 2002
The number of binary relations that are both reflexive and symmetric on an n-element set. - Justin Witt (justinmwitt(AT)gmail.com), Jul 12 2005
The number of symmetric binary relations on an (n-1)-element set. - Peter Kagey, Feb 13 2021
To win a game, you must flip n+1 heads in a row, where n is the total number of tails flipped so far. Then the probability of winning for the first time after n tails is A005329 / A006125. The probability of having won before n+1 tails is A114604 / A006125. - Joshua Zucker, Dec 14 2005
a(n) = A126883(n-1)+1. - Zerinvary Lajos, Jun 12 2007
Equals right border of triangle A158474 (unsigned). - Gary W. Adamson, Mar 20 2009
a(n-1) is the number of simple labeled graphs on n nodes such that every node has even degree. - Geoffrey Critzer, Oct 21 2011
a(n+1) is the number of symmetric binary matrices of size n X n. - Nathan J. Russell, Aug 30 2014
Let T_n be the n X n matrix with T_n(i,j) = binomial(2i + j - 3, j-1); then det(T_n) = a(n). - Tony Foster III, Aug 30 2018
k^(n*(n-1)/2) is the determinant of n X n matrix T_(i,j) = binomial(k*i + j - 3, j-1), in this case k=2. - Tony Foster III, May 12 2019
Let B_n be the n+1 X n+1 matrix with B_n(i, j) = Sum_{m=max(0, j-i)..min(j, n-i)} (binomial(i, j-m) * binomial(n-i, m) * (-1)^m), 0<=i,j<=n. Then det B_n = a(n+1). Also, deleting the first row and any column from B_n results in a matrix with determinant a(n). The matrices B_n have the following property: B_n * [x^n, x^(n-1) * y, x^(n-2) * y^2, ..., y^n]^T = [(x-y)^n, (x-y)^(n-1) * (x+y), (x-y)^(n-2) * (x+y)^2, ..., (x+y)^n]^T. - Nicolas Nagel, Jul 02 2019
a(n) is the number of positive definite (-1,1)-matrices of size n X n. - Eric W. Weisstein, Jan 03 2021
a(n) is the number of binary relations on a labeled n-set that are both total and antisymmetric. - José E. Solsona, Feb 05 2023

			From _Gus Wiseman_, Feb 11 2021: (Start)
This sequence counts labeled graphs on n vertices. For example, the a(0) = 1 through a(2) = 8 graph edge sets are:
  {}  {}  {}    {}
          {12}  {12}
                {13}
                {23}
                {12,13}
                {12,23}
                {13,23}
                {12,13,23}
This sequence also counts labeled graphs with loops on n - 1 vertices. For example, the a(1) = 1 through a(3) = 8 edge sets are the following. A loop is represented as an edge with two equal vertices.
  {}  {}    {}
      {11}  {11}
            {12}
            {22}
            {11,12}
            {11,22}
            {12,22}
            {11,12,22}
(End)

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 547 (Fig. 9.7), 573.
G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; p. 178.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 517.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 178.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 3, Eq. (1.1.2).
J. Propp, Enumeration of matchings: problems and progress, in: New perspectives in geometric combinatorics, L. Billera et al., eds., Mathematical Sciences Research Institute series, vol. 38, Cambridge University Press, 1999.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 0..50
F. Ardila and R. P. Stanley, Tilings, arXiv:math/0501170 [math.CO], 2005.
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #12.4.8. - From _N. J. A. Sloane_, Oct 08 2012
Anders Björner and Richard P. Stanley, A combinatorial miscellany, 2010.
Tobias Boege and Thomas Kahle, Construction Methods for Gaussoids, arXiv:1902.11260 [math.CO], 2019.
Taylor Brysiewicz and Fulvio Gesmundo, The Degree of Stiefel Manifolds, arXiv:1909.10085 [math.AG], 2019.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Mihai Ciucu, Perfect matchings of cellular graphs, J. Algebraic Combin., 5 (1996) 87-103.
Mihai Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, J. Combin. Theory Ser. A 77 (1997), no. 1, 67-97.
Thierry de la Rue and Élise Janvresse, Pavages aléatoires par touillage de dominos, Images des Mathématiques, CNRS, 2023. In French.
Noam Elkies, Greg Kuperberg, Michael Larsen, and James Propp, Alternating sign matrices and domino tilings. Part I, Journal of Algebraic Combinatorics 1-2, 111-132 (1992).
Noam Elkies, Greg Kuperberg, Michael Larsen, and James Propp, Alternating sign matrices and domino tilings. Part II, Journal of Algebraic Combinatorics 1-3, 219-234 (1992).
Sen-Peng Eu and Tung-Shan Fu, A simple proof of the Aztec diamond theorem, arXiv:math/0412041 [math.CO], 2004.
D. Grensing, I. Carlsen, and H.-Chr. Zapp, Some exact results for the dimer problem on plane lattices with non-standard boundaries, Phil. Mag. A, 41:5 (1980), 777-781.
Harald Helfgott and Ira M. Gessel, Enumeration of tilings of diamonds and hexagons with defects, arXiv:math/9810143 [math.CO], 1998.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
Pakawut Jiradilok, Some Combinatorial Formulas Related to Diagonal Ramsey Numbers, arXiv:2404.02714 [math.CO], 2024. See p. 19.
William Jockusch, Perfect matchings and perfect squares J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.
Eric H. Kuo, Applications of graphical condensation for enumerating matchings and tilings, Theoretical Computer Science, Vol. 319, No. 1-3 (2004), pp. 29-57, arXiv preprint, arXiv:math/0304090 [math.CO], 2003.
C. L. Mallows & N. J. A. Sloane, Emails, May 1991
W. H. Mills, David P. Robbins, and Howard Rumsey, Jr., Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (1983), 340-359.
Götz Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
James Propp, Enumeration of matchings: problems and progress, in L. J. Billera et al. (eds.), New Perspectives in Algebraic Combinatorics
James Propp, Enumeration of matchings: problems and progress, arXiv:math/9904150 [math.CO], 1999.
James Propp, Lessons I learned from Richard Stanley, arXiv preprint [math.CO], 2015.
James Propp and R. P. Stanley, Domino tilings with barriers, arXiv:math/9801067 [math.CO], 1998.
Steven S. Skiena, Generating graphs.
David E. Speyer, Perfect matchings and the octahedron recurrence, Journal of Algebraic Combinatorics, Vol. 25, No. 3 (2007), pp. 309-348, arXiv preprint, arXiv:math/0402452 [math.CO], 2004.
Jan Tóth and Ondřej Kuželka, Complexity of Weighted First-Order Model Counting in the Two-Variable Fragment with Counting Quantifiers: A Bound to Beat, arXiv:2404.12905 [cs.LO], 2024. See p. 24.
Herman Tulleken, Polyominoes 2.2: How they fit together, (2019).
Eric Weisstein's World of Mathematics, Connected Graph.
Eric Weisstein's World of Mathematics, Labeled Graph.
Eric Weisstein's World of Mathematics, Symmetric Matrix.
Doron Zeilberger, Dave Robbins's Art of Guessing, Adv. in Appl. Math. 34 (2005), 939-954.
Index entries for sequences related to dominoes

Cf. A000568 for the unlabeled analog, A053763, A006253, A004003.
Cf. A001187 (connected labeled graphs).
Cf. A095340, A103904, A005329, A114604, A299998.
Cf. A158474. - Gary W. Adamson, Mar 20 2009
Cf. A136652 (log). - Paul D. Hanna, Dec 04 2009
The unlabeled version is A000088, or A002494 without isolated vertices.
The directed version is A002416.
The covering case is A006129.
The version for hypergraphs is A058891, or A016031 without singletons.
Row sums of A143543.
The case of connected edge set is A287689.
Cf. A000169, A000295, A036442, A059167, A100743, A136284, A327078.

[2^(n*(n-1) `div` 2) | n <- [0..20]] -- José E. Solsona, Feb 05 2023

[2^(n*(n-1) div 2): n in [0..20]]; // Vincenzo Librandi, Jul 03 2019

Join[{1}, 2^Accumulate[Range[0, 20]]] (* Harvey P. Dale, May 09 2013 *)
Table[2^(n (n - 1) / 2), {n, 0, 20}] (* Vincenzo Librandi, Jul 03 2019 *)
Table[2^Binomial[n, 2], {n, 0, 15}] (* Eric W. Weisstein, Jan 03 2021 *)
2^Binomial[Range[0, 15], 2] (* Eric W. Weisstein, Jan 03 2021 *)
Prepend[Table[Count[Tuples[{0, 1}, {n, n}], ?SymmetricMatrixQ], {n, 5}], 1] (* _Eric W. Weisstein, Jan 03 2021 *)
Prepend[Table[Count[Tuples[{-1, 1}, {n, n}], ?PositiveDefiniteMatrixQ], 1], {n, 4}] (* _Eric W. Weisstein, Jan 03 2021 *)

A006125(n):=2^(n*(n-1)/2)$ makelist(A006125(n), n, 0, 30); /* Martin Ettl, Oct 24 2012 */

a(n)=1<Charles R Greathouse IV, Jun 15 2011

def A006125(n): return 1<<(n*(n-1)>>1) # Chai Wah Wu, Nov 09 2023

Sequence is given by the Hankel transform of A001003 (Schroeder's numbers) = 1, 1, 3, 11, 45, 197, 903, ...; example: det([1, 1, 3, 11; 1, 3, 11, 45; 3, 11, 45, 197; 11, 45, 197, 903]) = 2^6 = 64. - Philippe Deléham, Mar 02 2004
a(n) = 2^floor(n^2/2)/2^floor(n/2). - Paul Barry, Oct 04 2004
G.f. satisfies: A(x) = 1 + x*A(2x). - Paul D. Hanna, Dec 04 2009
a(n) = 2 * a(n-1)^2 / a(n-2). - Michael Somos, Dec 30 2012
G.f.: G(0)/x - 1/x, where G(k) = 1 + 2^(k-1)*x/(1 - 1/(1 + 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 26 2013
E.g.f. satisfies A'(x) = A(2x). - Geoffrey Critzer, Sep 07 2013
Sum_{n>=1} 1/a(n) = A299998. - Amiram Eldar, Oct 27 2020
a(n) = s_lambda(1,1,...,1) where s is the Schur polynomial in n variables and lambda is the partition (n,n-1,n-2,...,1). - Leonid Bedratyuk, Feb 06 2022
a(n) = Product_{1 <= j <= i <= n-1}  (i + j)/(2*i - 2*j + 1). Cf. A007685.  - Peter Bala, Oct 25 2024

More terms from Vladeta Jovovic, Apr 09 2000

A000666 Number of symmetric relations on n nodes.

Original entry on oeis.org

1, 2, 6, 20, 90, 544, 5096, 79264, 2208612, 113743760, 10926227136, 1956363435360, 652335084592096, 405402273420996800, 470568642161119963904, 1023063423471189431054720, 4178849203082023236058229792, 32168008290073542372004082199424

Offset: 0

N. J. A. Sloane

Each node may or may not be related to itself.
Also the number of rooted graphs on n+1 nodes.
The 1-to-1 correspondence is as follows: Given a rooted graph on n+1 nodes, replace each edge joining the root node to another node with a self-loop at that node and erase the root node. The result is an undirected graph on n nodes which is the graph of the symmetric relation.
Also the number of the graphs with n nodes whereby each node is colored or not colored. A loop can be interpreted as a colored node. - Juergen Will, Oct 31 2011

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 101, 241.
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sept. 15, 1955, pp. 14-22.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
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).

David Applegate, Table of n, a(n) for n = 0..80 [Shortened file because terms grow rapidly: see Applegate link below for additional terms]
David Applegate, Table of n, a(n) for n = 0..100
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
R. L. Davis, Structure of dominance relations, Bull. Math. Biophys., 16 (1954), 131-140. [Annotated scanned copy]
F. Harary, The number of linear, directed, rooted, and connected graphs, Trans. Am. Math. Soc. 78 (1955) 445-463, eq. (24).
Frank Harary, Edgar M. Palmer, Robert W. Robinson and Allen J. Schwenk, Enumeration of graphs with signed points and lines, J. Graph Theory 1 (1977), no. 4, 295-308.
Adib Hassan, Po-Chien Chung and Wayne B. Hayes, Graphettes: Constant-time determination of graphlet and orbit identity including (possibly disconnected) graphlets up to size 8, arXiv:1708.04341 [cs.DS], 2017.
Mathematics Stack Exchange, Enumerating Graphs with Self-Loops, Jan 23 2014.
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22. [Annotated scanned copy]
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
W. Oberschelp, The number of non-isomorphic m-graphs, Presented at Mathematical Institute Oberwolfach, July 3 1967 [Scanned copy of manuscript]
W. Oberschelp, Strukturzahlen in endlichen Relationssystemen, in Contributions to Mathematical Logic (Proceedings 1966 Hanover Colloquium), pp. 199-213, North-Holland Publ., Amsterdam, 1968. [Annotated scanned copy]
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Marko Riedel, Maple code for sequence.
Marko Riedel et al., Enumerating Graphs with Self-Loops
R. W. Robinson, Notes - "A Present for Neil Sloane"
R. W. Robinson, Notes - computer printout
Sage, Common Graphs (Graph Generators)
Lorenzo Sauras-Altuzarra, Graphs
J. M. Tangen and N. J. A. Sloane, Correspondence, 1976-1976
Eric Weisstein's World of Mathematics, Rooted Graph

Cf. A000595, A001172, A001174, A006905, A000250, A054921 (connected relations).

Maple
```
# see Riedel link above
```

Join[{1,2}, Table[CycleIndex[Join[PairGroup[SymmetricGroup[n]], Permutations[Range[n*(n-1)/2+1, n*(n+1)/2]], 2],s] /. Table[s[i]->2, {i,1,n^2-n}], {n,2,8}]] (* Geoffrey Critzer, Nov 04 2011 *)
Table[Module[{eds,pms,leq},
eds=Select[Tuples[Range[n],2],OrderedQ];
pms=Map[Sort,eds/.Table[i->Part[#,i],{i,n}]]&/@Permutations[Range[n]];
leq=Function[seq,PermutationCycles[Ordering[seq],Length]]/@pms;
Total[Thread[Power[2,leq]]]/n!
],{n,0,8}] (* This is after Geoffrey Critzer's program but does not use the (deprecated) Combinatorica package. - Gus Wiseman, Jul 21 2016 *)
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i-1}], {i, 2, Length[v]}] + Sum[Quotient[v[[i]], 2] + 1, {i, 1, Length[v]}];
a[n_] := a[n] = (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 17}] (* Jean-François Alcover, Nov 13 2017, after Andrew Howroyd *)

permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2 + 1)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

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

Euler transform of A054921. - N. J. A. Sloane, Oct 25 2018
Let G_{n+1,k} be the number of rooted graphs on n+1 nodes with k edges and let G_{n+1}(x) = Sum_{k=0..n(n+1)/2} G_{n+1,k} x^k. Thus a(n) = G_{n+1}(1). Let S_n(x_1, ..., x_n) denote the cycle index for Sym_n. (cf. the link in A000142).
Compute x_1*S_n and regard it as the cycle index of a set of permutations on n+1 points and find the corresponding cycle index for the action on the n(n+1)/2 edges joining those points (the corresponding "pair group"). Finally, by replacing each x_i by 1+x^i gives G_{n+1}(x). [Harary]
Example, n=2. S_2 = (1/2)*(x_1^2+x_2), x_1*S_2 = (1/2)*(x_1^3+x_1*x_2). The pair group is (1/2)*(x_1^2+x_1*x_2) and so G_3(x) = (1/2)*((1+x)^3+(1+x)*(1+x^2)) = 1+2*x+2*x^2+x^3; set x=1 to get a(2) = 6.
a(n) ~ 2^(n*(n+1)/2)/n! [McIlroy, 1955]. - Vaclav Kotesovec, Dec 19 2016

Description corrected by Christian G. Bower
More terms from Vladeta Jovovic, Apr 18 2000
Entry revised by N. J. A. Sloane, Mar 06 2007

A096368 Number of unlabeled regular tournaments with 2n+1 nodes.

Original entry on oeis.org

1, 1, 1, 3, 15, 1223, 1495297, 18400989629, 2406183070160597, 3511056114693589781331, 59423289286172717542785192911, 12034362241475984037791303316068785847, 29921426689289629541982244885554389482859734381

Offset: 0

David J. Haglin (david.haglin(AT)mnsu.edu), Jul 02 2004

Terms may be computed without generating each tournament by enumerating the number of tournaments by degree sequence. A PARI program showing this technique for labeled tournaments is given in A007079. Burnside's lemma as applied in A000568 can be used to extend this method to the unlabeled case. - Andrew Howroyd, Mar 13 2020

Gunnar Brinkmann, Generating regular directed graphs, Discrete Math., 313 (2012), 1-7. [_N. J. A. Sloane_, Nov 26 2012]
Marc Chamberland and Eugene A. Herman, Rock-paper-scissors meets Borromean rings, The Mathematical Intelligencer, 37(2), 20--25.
Marc Chamberland, What's Better than Rock Paper Scissors? (2014).
B. D. McKay, Catalogues of directed graphs.
B. D. McKay, The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs, Combinatorica 10 (1990), 367-377.

Cf. A000568, A007079.

Offset and count for 15 vertices corrected by Brendan McKay, Dec 09 2008
a(0) from Álvar Ibeas, Nov 18 2017
a(8)-a(12) from Andrew Howroyd, Mar 13 2020

A054946 Number of strongly connected labeled tournaments on n nodes.

Original entry on oeis.org

1, 0, 2, 24, 544, 22320, 1677488, 236522496, 64026088576, 33832910196480, 35262092417856512, 72926863133112198144, 300318571786159783496704, 2467430973323656141183549440, 40490606137578335674252914280448

Offset: 1

N. J. A. Sloane, May 24 2000

For n>=3, a(n) is equal to the number of minimal idempotent generating sets of the semigroup of all singular mappings on {1,2,...,n}. (In the reference below, Howie gave a correspondence between such generating sets and strongly connected labeled tournaments, but stated an incorrect formula for a(n).) - James East, Jan 08 2013

			For n=3, there are two minimal idempotent generating sets for the semigroup of singular mappings on {1,2,3}.  Writing (a,b,c) to indicate the map for which 1->a, etc, the relevant generating sets are: {(1,1,3),(1,2,2),(3,2,3)} and {(2,2,3),(1,3,3),(1,2,1)}.

Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.

N. J. A. Sloane, Table of n, a(n) for n = 1..80 [Shortened file because terms grow rapidly: see Sloane link below for additional terms]
James East and Robert D. Gray, Idempotent generators in finite partition monoids and related semigroups, arXiv preprint arXiv:1404.2359, 2014
J. M. Howie, Idempotent generators in finite full transformation semigroups, Proc. Roy. Soc. Edinburgh Sect. A, 81 (1978), no. 3-4, 317-323.
Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See p. 33.
Valery A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.
Thierry Monteil and Khaydar Nurligareev, Asymptotic probability for connectedness, arXiv:2401.00818 [math.CO], 2024. See p. 12.
N. J. A. Sloane, Table of n, a(n) for n = 1..100
E. M. Wright, The number of irreducible tournaments, Glasgow Math. J., 11 (1970), 97-101.

Cf. A000568 (unlabeled tournaments), A051337 (strongly connected unlabeled tournaments).

with(powseries): powcreate(t(n)=2^(n*(n-1)/2)/n!): s := evalpow(1-1/t): a := tpsform(s, x, 21): for n from 0 to 20 do printf(`%d,`,n!*coeff(a,x,n)) od:
f:=array(0..500); F:=array(0..500); M:=100; f[1]:=1; F[1]:=1; lprint(1,f[1]); for n from 2 to M do F[n]:=2^(n*(n-1)/2); f[n]:=F[n]-add( binomial(n,s)*f[s]*F[n-s], s=1..n-1); lprint(n,f[n]); od:

F[n_] := 2^(n*(n - 1)/2);
a[1] = 1; a[n_] := a[n] = F[n] - Sum[Binomial[n, s]*a[s]*F[n-s], {s, 1, n-1 }];
Array[a, 15] (* Jean-François Alcover, Nov 13 2017, from first formula *)

seq(n)={my(a=vector(n)); for(n=1, n, a[n] = 2^(n*(n-1)/2) - sum(k=1, n-1, binomial(n,k)*2^((n-k)*(n-k-1)/2)*a[k])); a} \\ Andrew Howroyd, Jan 10 2022

Let F(n) = 2^(n*(n-1)/2). Then a(n) is defined by the recurrence a(1)=1, F(n) = a(n) + Sum_{s=1..n-1} binomial(n,s)*a(s)*F(n-s). [Wright]
E.g.f.: 1-1/(1+f(x)) where f(x) = Sum_{m>=1} 2^(m(m-1)/2) x^m / m!.
Wright also gives an asymptotic expansion for a(n).

A129584 Number of unlabeled bi-point-determining graphs: graphs in which no two vertices have the same neighborhoods or the same augmented neighborhoods (the augmented neighborhood of a vertex is the neighborhood of the vertex union the vertex itself).

Original entry on oeis.org

1, 0, 0, 1, 6, 36, 324, 5280, 156088, 8415760

Offset: 1

Ji Li (vieplivee(AT)hotmail.com), May 07 2007

This is the unlabeled case of bi-point-determining graphs, which are basically graphs that are both point-determining (no two vertices have the same neighborhoods) and co-point-determining (graphs whose complements are point-determining)

Ira M. Gessel and Ji Li, Enumeration of point-determining Graphs, Journal of Combinatorial Theory, Series A 118 (2011) 591-612.

Cf. graphs: labeled A006125, unlabeled A000568; connected graphs: labeled A001187, unlabeled A001349; point-determining graphs: labeled A006024, unlabeled A004110; connected point-determining graphs: labeled A092430, unlabeled A004108; connected co-point-determining graphs: labeled A079306, unlabeled A004108; bi-point-determining graphs: labeled A129583, unlabeled A129584; connected bi-point-determining graphs: labeled A129585, unlabeled A129586; phylogenetic trees: labeled A000311, unlabeled A000669.

A129583 Number of labeled bi-point-determining graphs with n vertices.

Original entry on oeis.org

1, 1, 0, 0, 12, 312, 13824, 1147488, 178672128, 52666091712, 29715982846848, 32452221242518272, 69259424722321036032, 291060255757818125657088, 2421848956937579216663491584, 40050322614433939228627991906304, 1319551659023608317386779165849208832

Offset: 0

Ji Li (vieplivee(AT)hotmail.com), May 07 2007

A bi-point determining graph is a graph in which no two vertices have the same neighborhoods or the same augmented neighborhoods (the augmented neighborhood of a vertex is the neighborhood of the vertex union the vertex itself).

R. C. Read, The Enumeration of Mating-Type Graphs. Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.

Andrew Howroyd, Table of n, a(n) for n = 0..50
Ira M. Gessel and Ji Li, Enumeration of point-determining Graphs, Journal of Combinatorial Theory, Series A 118 (2011) 591-612.

seq(n)={my(g=sum(k=0, n, 2^binomial(k,2)*x^k/k!) + O(x*x^n)); Vec(serlaplace(subst(g, x, 2*log(1+x+O(x*x^n))-x)))} \\ Andrew Howroyd, May 06 2021

E.g.f.: G(2*log(1+x)-x) where G(x) is the e.g.f. of A006125.

a(0)=1 prepended and terms a(13) and beyond from Andrew Howroyd, May 06 2021

A129585 Number of labeled connected bi-point-determining graphs with n vertices (see A129583).

Original entry on oeis.org

1, 1, 0, 0, 12, 252, 12312, 1061304, 170176656, 51134075424, 29204599254624, 32130964585236096, 68873851786953047040, 290164895151435531345024, 2417786648013402212500060416, 40014055814155246577685250570752, 1318911434129029730677931158374449664

Offset: 0

Ji Li (vieplivee(AT)hotmail.com), May 07 2007

The calculation of connected bi-point-determining graphs is carried out by examining the connected components of bi-point-determining graphs. For more details, see reference.

Andrew Howroyd, Table of n, a(n) for n = 0..50
Ira M. Gessel and Ji Li, Enumeration of point-determining Graphs, Journal of Combinatorial Theory, Series A 118 (2011) 591-612.

max = 15; f[x_] := x + Log[ Sum[ 2^Binomial[n, 2]*((2*Log[1 + x] - x)^n/n!), {n, 0, max}]/(1 + x)]; A129585 = Drop[ CoefficientList[ Series[ f[x], {x, 0, max}], x]*Range[0, max]!, 1](* Jean-François Alcover, Jan 13 2012, after e.g.f. *)

seq(n)={my(g=sum(k=0, n, 2^binomial(k,2)*x^k/k!) + O(x*x^n)); Vec(serlaplace(1+x+log(subst(g, x, 2*log(1+x+O(x*x^n))-x)/(1+x))))} \\ Andrew Howroyd, May 06 2021

E.g.f.: 1 + x + log((Sum_{n>=0} 2^binomial(n,2)*(2*log(1+x)-x)^n/n!)/(1+x)). - Goran Kilibarda, Vladeta Jovovic, May 09 2007

E.g.f.: 1 + x + log(B(x)/(1+x)) where B(x) is the e.g.f. of A129583. - Andrew Howroyd, May 06 2021

More terms from Goran Kilibarda, Vladeta Jovovic, May 09 2007

a(0)=1 prepended and terms a(16) and beyond from Andrew Howroyd, May 06 2021

A129586 Number of unlabeled connected bi-point-determining graphs (see A129583).

Original entry on oeis.org

1, 0, 0, 1, 5, 31, 293, 4986, 151096, 8264613, 812528493, 144251345591, 46649058611515, 27744159658789435, 30603223477819571330, 63039669933956074333128, 243839768084859914114367906, 1779006737976575676931317142360, 24571827603944282248499044846893618

Offset: 1

Ji Li (vieplivee(AT)hotmail.com), May 07 2007

The calculation of the number of connected bi-point-determining graphs is carried out by examining the connected components of bi-point-determining graphs. For more details, see linked paper "Enumeration of point-determining Graphs".

Martin Rubey, Table of n, a(n) for n = 1..29
Florian Fürnsinn, Moritz Gangl, and Martin Rubey, Unexpectedly, a symmetry on unlabeled graphs, arXiv:2505.03665 [math.CO], 2025. See p. 18.
Ira M. Gessel and Ji Li, Enumeration of point-determining Graphs, Journal of Combinatorial Theory, Series A 118 (2011) 591-612.

151096 and 8264613 from Vladeta Jovovic, May 10 2007

a(n) for n >= 11 from Martin Rubey, May 08 2025

cp's OEIS Frontend

A334335 Inverse Euler transform of A000568.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

A151879 Produced by same formula that gives A000568 (unlabeled tournaments), but with LCM instead of GCD in the exponent.

Views

Author

Keywords

Links

Programs

Mathematica

PARI

Python

Formula

A006125 a(n) = 2^(n*(n-1)/2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

Maxima

PARI

Python

Formula

Extensions

A000666 Number of symmetric relations on n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A096368 Number of unlabeled regular tournaments with 2n+1 nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A054946 Number of strongly connected labeled tournaments on n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A129584 Number of unlabeled bi-point-determining graphs: graphs in which no two vertices have the same neighborhoods or the same augmented neighborhoods (the augmented neighborhood of a vertex is the neighborhood of the vertex union the vertex itself).

Views

Author

Keywords

Comments