A000665 -id:A000665 - cp's OEIS frontend

A058882 Erroneous version of A000665.

Original entry on oeis.org

1, 1, 2, 5, 34, 2136, 7013488

Offset: 1

dead

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 231.

A241586 Erroneous version of A000665.

Original entry on oeis.org

1, 1, 2, 5, 34, 2135, 7013320, 1788782616656, 53304527811667897248, 366299663432194332594005123072

Offset: 1

dead

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

a(6) is incorrect. Should be 2136.

Jianguo Qian, Enumeration of unlabeled uniform hypergraphs, Discrete Math. 326 (2014), 66--74. MR3188989. See Table 1, p. 71.

A000088 Number of simple graphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864, 165091172592, 50502031367952, 29054155657235488, 31426485969804308768, 64001015704527557894928, 245935864153532932683719776, 1787577725145611700547878190848, 24637809253125004524383007491432768

Offset: 0

N. J. A. Sloane

Euler transform of the sequence A001349.

Also, number of equivalence classes of sign patterns of totally nonzero symmetric n X n matrices.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 430.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
Thomas Boyer-Kassem, Conor Mayo-Wilson, Scientific Collaboration and Collective Knowledge: New Essays, New York, Oxford University Press, 2018, see page 47.
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 54.
Lupanov, O. B. Asymptotic estimates of the number of graphs with n edges. (Russian) Dokl. Akad. Nauk SSSR 126 1959 498--500. MR0109796 (22 #681).
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.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
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).

Keith M. Briggs, Table of n, a(n) for n = 0..87 (From link below)
R. Absil and H. Mélot, Digenes: genetic algorithms to discover conjectures about directed and undirected graphs, arXiv preprint arXiv:1304.7993 [cs.DM], 2013.
Natalie Arkus, Vinothan N. Manoharan and Michael P. Brenner. Deriving Finite Sphere Packings, arXiv:1011.5412 [cond-mat.soft], Nov 24, 2010. (See Table 1.)
Leonid Bedratyuk and Anna Bedratyuk, A new formula for the generating function of the numbers of simple graphs, Comptes rendus de l'Académie Bulgare des Sciences, Tome 69, No 3, 2016, p.259-268.
Benjamin A. Blumer, Michael S. Underwood and David L. Feder, Single-qubit unitary gates by graph scattering, arXiv:1111.5032 [quant-ph], 2011.
Keith M. Briggs, Combinatorial Graph Theory [Gives first 140 terms]
Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur and Hadrien Melot, House of Graphs: a database of interesting graphs, arXiv preprint arXiv:1204.3549 [math.CO], 2012.
P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp. [Annotated scanned copy]
P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102.
P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 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.
Gi-Sang Cheon, Jinha Kim, Minki Kim and Sergey Kitaev, On k-11-representable graphs, arXiv:1803.01055 [math.CO], 2018.
CombOS - Combinatorial Object Server, Generate graphs
Karen M. Daehli, Sarah A Obead, Hsuan-Yin Lin, and Eirik Rosnes, Improved Capacity Outer Bound for Private Quadratic Monomial Computation, arXiv:2401.06125 [cs.IR], 2024.
R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271. (Annotated scanned copy of 3 pages)
Peter Dukes, Notes for Math 422: Enumeration and Ramsey Theory, University of Victoria BC Canada (2019). See page 36.
D. S. Dummit, E. P. Dummit and H. Kisilevsky, Characterizations of quadratic, cubic, and quartic residue matrices, arXiv preprint arXiv:1512.06480 [math.NT], 2015.
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
Mareike Fischer, Michelle Galla, Lina Herbst, Yangjing Long, and Kristina Wicke, Non-binary treebased unrooted phylogenetic networks and their relations to binary and rooted ones, arXiv:1810.06853 [q-bio.PE], 2018.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 105.
E. Friedman, Illustration of small graphs
Harald Fripertinger, Graphs
Scott Garrabrant and Igor Pak, Pattern Avoidance is Not P-Recursive, preprint, 2015.
Lee M. Gunderson and Gecia Bravo-Hermsdorff, Introducing Graph Cumulants: What is the Variance of Your Social Network?, arXiv:2002.03959 [math.ST], 2020.
P. Hegarty, On the notion of balance in social network analysis, arXiv preprint arXiv:1212.4303 [cs.SI], 2012.
S. Hougardy, Home Page
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
Richard Hua and Michael J. Dinneen, Improved QUBO Formulation of the Graph Isomorphism Problem, SN Computer Science (2020) Vol. 1, No. 19.
A. Itzhakov and M. Codish, Breaking Symmetries in Graph Search with Canonizing Sets, arXiv preprint arXiv:1511.08205 [cs.AI], 2015-2016.
Dan-Marian Joiţa and Lorentz Jäntschi, Extending the Characteristic Polynomial for Characterization of C_20 Fullerene Congeners, Mathematics (2017), 5(4), 84.
Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes
Maksim Karev, The space of framed chord diagrams as a Hopf module, arXiv preprint arXiv:1404.0026 [math.GT], 2014.
J. M. Larson, Cheating Because They Can: Social Networks and Norm Violators, 2014. See Footnote 11.
Steffen Lauritzen, Alessandro Rinaldo and Kayvan Sadeghi, On Exchangeability in Network Models, arXiv:1709.03885 [math.ST], 2017.
O. B. Lupanov, On asymptotic estimates of the number of graphs and networks with n edges, Problems of Cybernetics [in Russian], Moscow 4 (1960): 5-21.
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]
B. D. McKay, Maple program (used to redirect to here).
B. D. McKay, Maple program [Cached copy, with permission]
B. D. McKay, Simple graphs
A. Milicevic and N. Trinajstic, Combinatorial Enumeration in Chemistry, Chem. Modell., Vol. 4, (2006), pp. 405-469.
Angelo Monti and Blerina Sinaimeri, Effects of graph operations on star pairwise compatibility graphs, arXiv:2410.16023 [cs.DM], 2024. See p. 16.
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
M. Petkovsek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes, I-graphs and others, Croatica Chem. Acta, 78 (2005), 563-567.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
E. M. Palmer, Letter to N. J. A. Sloane, no date
Marko Riedel, Nonisomorphic graphs.
Marko Riedel, Compact Maple code for cycle index, sequence values and ordinary generating function by the number of edges.
R. W. Robinson, Enumeration of non-separable graphs, J. Combin. Theory 9 (1970), 327-356.
Sage, Common Graphs (Graph Generators)
S. S. Skiena, Generating graphs
N. J. A. Sloane, Illustration of initial terms
Quico Spaen, Christopher Thraves Caro and Mark Velednitsky, The Dimension of Valid Distance Drawings of Signed Graphs, Discrete & Computational Geometry (2019), 1-11.
P. R. Stein, On the number of graphical partitions, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978). [Annotated scanned copy]
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Overview of the 17 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 1
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 2
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 3
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 4
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 5
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 6
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 7
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 8
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 9
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 10
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 11
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 12
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 13
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 14
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 15
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 16
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17
J. M. Tangen and N. J. A. Sloane, Correspondence, 1976-1976
James Turner and William H. Kautz, A survey of progress in graph theory in the Soviet Union SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 18.
S. Uijlen and B. Westerbaan, A Kochen-Specker system has at least 22 vectors, arXiv preprint arXiv:1412.8544 [cs.DM], 2014.
Mark Velednitsky, New Algorithms for Three Combinatorial Optimization Problems on Graphs, Ph. D. Dissertation, University of California, Berkeley (2020).
Eric Weisstein's World of Mathematics, Simple Graph
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Degree Sequence
E. M. Wright, The number of graphs on many unlabelled nodes, Mathematische Annalen, December 1969, Volume 183, Issue 4, 250-253
E. M. Wright, The number of unlabelled graphs with many nodes and edges Bull. Amer. Math. Soc. Volume 78, Number 6 (1972), 1032-1034.
Chris Ying, Enumerating Unique Computational Graphs via an Iterative Graph Invariant, arXiv:1902.06192 [cs.DM], 2019.
Index entries for "core" sequences

Partial sums of A002494.
Cf. A000666 (graphs with loops), A001349 (connected graphs), A002218, A006290, A003083.
Column k=1 of A063841.
Column k=2 of A309858.
Row sums of A008406.
Cf. also A000055, A000664.
Partial sums are A006897.

# To produce all graphs on 4 nodes, for example:
with(GraphTheory):
L:=[NonIsomorphicGraphs](4,output=graphs,outputform=adjacency): # N. J. A. Sloane, Oct 07 2013
seq(GraphTheory[NonIsomorphicGraphs](n,output=count),n=1..10); # Juergen Will, Jan 02 2018
# alternative Maple program:
b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(ceil((p[j]-1)/2)
      +add(igcd(p[k], p[j]), k=1..j-1), j=1..nops(p)))([l[], 1$n])),
       add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
    end:
a:= n-> b(n$2, []):
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 14 2019

Needs["Combinatorica`"]
Table[NumberOfGraphs[n], {n, 0, 19}] (* Geoffrey Critzer, Mar 12 2011 *)
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[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 05 2018, after Andrew Howroyd *)
b[n_, i_, l_] := If[n==0 || i==1, 1/n!*2^(Function[p, Sum[Ceiling[(p[[j]]-1 )/2]+Sum[GCD[p[[k]], p[[j]]], {k, 1, j-1}], {j, 1, Length[p]}]][Join[l, Table[1, {n}]]]), Sum[b[n-i*j, i-1, Join[l, Table[i, {j}]]]/j!/i^j, {j, 0, n/i}]];
a[n_] := b[n, n, {}];
a /@ Range[0, 20] (* Jean-François Alcover, Dec 03 2019, after Alois P. Heinz *)

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)}
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 A000088(n): return int(sum(Fraction(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

def a(n):
    return len(list(graphs(n)))
# Ralf Stephan, May 30 2014

a(n) = 2^binomial(n, 2)/n!*(1+(n^2-n)/2^(n-1)+8*n!/(n-4)!*(3*n-7)*(3*n-9)/2^(2*n)+O(n^5/2^(5*n/2))) (see Harary, Palmer reference). - Vladeta Jovovic and Benoit Cloitre, Feb 01 2003
a(n) = 2^binomial(n, 2)/n!*[1+2*n$2*2^{-n}+8/3*n$3*(3n-7)*2^{-2n}+64/3*n$4*(4n^2-34n+75)*2^{-3n}+O(n^8*2^{-4*n})] where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1). - Keith Briggs, Oct 24 2005
From David Pasino (davepasino(AT)yahoo.com), Jan 31 2009: (Start)
a(n) = a(n, 2), where a(n, t) is the number of t-uniform hypergraphs on n unlabeled nodes (cf. A000665 for t = 3 and A051240 for t = 4).
a(n, t) = Sum_{c : 1*c_1+2*c_2+...+n*c_n=n} per(c)*2^f(c), where:
..per(c) = 1/(Product_{i=1..n} c_i!*i^c_i);
..f(c) = (1/ord(c)) * Sum_{r=1..ord(c)} Sum_{x : 1*x_1+2*x_2+...+t*x_t=t} Product_{k=1..t} binomial(y(r, k; c), x_k);
..ord(c) = lcm{i : c_i>0};
..y(r, k; c) = Sum_{s|r : gcd(k, r/s)=1} s*c_(k*s) is the number of k-cycles of the r-th power of a permutation of type c. (End)
a(n) ~ 2^binomial(n,2)/n! [see Flajolet and Sedgewick p. 106, Gross and Yellen, p. 519, etc.]. - N. J. A. Sloane, Nov 11 2013
For asymptotics see also Lupanov 1959, 1960, also Turner and Kautz, p. 18. - N. J. A. Sloane, Apr 08 2014
a(n) = G(1) where G(z) = (1/n!) Sum_g det(I-g z^2)/det(I-g z) and g runs through the natural matrix n X n representation of the pair group A^2_n (for A^2_n see F. Harary and E. M. Palmer, Graphical Enumeration, page 83). - Leonid Bedratyuk, May 02 2015
From Keith Briggs, Jun 24 2016: (Start)
a(n) = 2^binomial(n,2)/n!*(
   1+
   2^(  -n +  1)*n$2+
   2^(-2*n +  3)*n$3*(n-7/3)+
   2^(-3*n +  6)*n$4*(4*n^2/3 - 34*n/3 + 25) +
   2^(-4*n + 10)*n$5*(8*n^3/3 - 142*n^2/3 + 2528*n/9 - 24914/45) +
   2^(-5*n + 15)*n$6*(128*n^4/15 - 2296*n^3/9 + 25604*n^2/9 - 630554*n/45 + 25704) +
   2^(-6*n + 21)*n$7*(2048*n^5/45 - 18416*n^4/9 + 329288*n^3/9 - 131680816*n^2/405 + 193822388*n/135 - 7143499196/2835) + ...),
where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1), using the method of Wright 1969.
(End)
a(n) = 1/n*Sum_{k=1..n} a(n-k)*A003083(k). - Andrey Zabolotskiy, Aug 11 2020

Harary gives an incorrect value for a(8); compare A007149

A309858 Number A(n,k) of k-uniform hypergraphs on n unlabeled nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

2, 1, 2, 1, 2, 2, 1, 1, 3, 2, 1, 1, 2, 4, 2, 1, 1, 1, 4, 5, 2, 1, 1, 1, 2, 11, 6, 2, 1, 1, 1, 1, 5, 34, 7, 2, 1, 1, 1, 1, 2, 34, 156, 8, 2, 1, 1, 1, 1, 1, 6, 2136, 1044, 9, 2, 1, 1, 1, 1, 1, 2, 156, 7013320, 12346, 10, 2, 1, 1, 1, 1, 1, 1, 7, 7013320, 1788782616656, 274668, 11, 2

Offset: 0

Alois P. Heinz, Aug 20 2019

See A000088 and A000665 for more references.

			Square array A(n,k) begins:
  2, 1,    1,       1,       1,    1, 1, 1, ...
  2, 2,    1,       1,       1,    1, 1, 1, ...
  2, 3,    2,       1,       1,    1, 1, 1, ...
  2, 4,    4,       2,       1,    1, 1, 1, ...
  2, 5,   11,       5,       2,    1, 1, 1, ...
  2, 6,   34,      34,       6,    2, 1, 1, ...
  2, 7,  156,    2136,     156,    7, 2, 1, ...
  2, 8, 1044, 7013320, 7013320, 1044, 8, 2, ...

Alois P. Heinz, Antidiagonals n = 0..20, flattened
Jianguo Qian, Enumeration of unlabeled uniform hypergraphs, Discrete Math. 326 (2014), 66--74. MR3188989.
Wikipedia, Hypergraph

Columns k=0..10 give: A007395, A000027, A000088, A000665, A051240, A051249, A309860, A309861, A309862, A309863, A309864.

Cf. A301922, A309865 (the same as triangle).

g:= (l, i, n)-> `if`(i=0, `if`(n=0, [[]], []), [seq(map(x->
     [x[], j], g(l, i-1, n-j))[], j=0..min(l[i], n))]):
h:= (p, v)-> (q-> add((s-> add(`if`(andmap(i-> irem(k[i], p[i]
     /igcd(t, p[i]))=0, [$1..q]), mul((m-> binomial(m, k[i]*m
     /p[i]))(igcd(t, p[i])), i=1..q), 0), t=1..s)/s)(ilcm(seq(
    `if`(k[i]=0, 1, p[i]), i=1..q))), k=g(p, q, v)))(nops(p)):
b:= (n, i, l, v)-> `if`(n=0 or i=1, 2^((p-> h(p, v))([l[], 1$n]))
     /n!, add(b(n-i*j, i-1, [l[], i$j], v)/j!/i^j, j=0..n/i)):
A:= proc(n, k) option remember; `if`(k>n, 1,
     `if`(k>n-k, A(n, n-k), b(n$2, [], k)))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);

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}
rep(typ)={my(L=List(), k=0); for(i=1, #typ, k+=typ[i]; listput(L, k); while(#L0, u=vecsort(apply(f, u)); d=lex(u, v)); !d}
Q(n, k, perm)={my(t=0); forsubset([n, k], v, t += can(Vec(v), t->perm[t])); t}
T(n, k)={my(s=0); forpart(p=n, s += permcount(p)*2^Q(n, k, rep(p))); s/n!} \\ Andrew Howroyd, Aug 22 2019

A(n,k) = A(n,n-k) for 0 <= k <= n.

A(n,k) - A(n-1,k) = A301922(n,k) for n,k >= 1.

A322451 Number of unlabeled 3-uniform hypergraphs spanning n vertices.

Original entry on oeis.org

1, 0, 0, 1, 3, 29, 2102, 7011184, 1788775603336, 53304526022885280592, 366299663378889804782337225824, 1171638318502622784366970315264281830913536, 3517726593606524901243694560022510194223171115509135178240

Offset: 0

Gus Wiseman, Dec 09 2018

nonn

3-uniform means that every edge consists of 3 vertices. - Brendan McKay, Sep 03 2023

			Non-isomorphic representatives of the a(5) = 29 hypergraphs:
  {{125}{345}}
  {{123}{245}{345}}
  {{135}{245}{345}}
  {{145}{245}{345}}
  {{123}{145}{245}{345}}
  {{124}{135}{245}{345}}
  {{125}{135}{245}{345}}
  {{134}{235}{245}{345}}
  {{145}{235}{245}{345}}
  {{123}{124}{135}{245}{345}}
  {{123}{145}{235}{245}{345}}
  {{124}{134}{235}{245}{345}}
  {{134}{145}{235}{245}{345}}
  {{135}{145}{235}{245}{345}}
  {{145}{234}{235}{245}{345}}
  {{123}{124}{134}{235}{245}{345}}
  {{123}{134}{145}{235}{245}{345}}
  {{123}{145}{234}{235}{245}{345}}
  {{124}{135}{145}{235}{245}{345}}
  {{125}{135}{145}{235}{245}{345}}
  {{135}{145}{234}{235}{245}{345}}
  {{123}{124}{135}{145}{235}{245}{345}}
  {{124}{135}{145}{234}{235}{245}{345}}
  {{125}{135}{145}{234}{235}{245}{345}}
  {{134}{135}{145}{234}{235}{245}{345}}
  {{123}{124}{135}{145}{234}{235}{245}{345}}
  {{125}{134}{135}{145}{234}{235}{245}{345}}
  {{124}{125}{134}{135}{145}{234}{235}{245}{345}}
  {{123}{124}{125}{134}{135}{145}{234}{235}{245}{345}}

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

First differences of A000665.

Cf. A006126, A006129, A038041, A299471, A301922, A302374, A302394, A306017, A306021.

a(12) from Andrew Howroyd, Dec 15 2018

Name corrected by Brendan McKay, Sep 03 2023

A034941 Number of labeled triangular cacti with 2n+1 nodes (n triangles).

Original entry on oeis.org

1, 1, 15, 735, 76545, 13835745, 3859590735, 1539272109375, 831766748637825, 585243816844111425, 520038240188935042575, 569585968715180280038175, 753960950911045074462890625, 1186626209895384011075327630625, 2190213762744801162239116550679375

Offset: 0

Christian G. Bower, Oct 15 1998

nonn

Also the number of 3-uniform hypertrees spanning 2n + 1 labeled vertices. - Gus Wiseman, Jan 12 2019

Number of rank n+1 simple series-parallel matroids on [2n+1]. - Matt Larson, Mar 06 2023

			a(3) = 5!! * 7^2 = (1*3*5) * 49 = 735.
From _Gus Wiseman_, Jan 12 2019: (Start)
The a(2) = 15 3-uniform hypertrees:
  {{1,2,3},{1,4,5}}
  {{1,2,3},{2,4,5}}
  {{1,2,3},{3,4,5}}
  {{1,2,4},{1,3,5}}
  {{1,2,4},{2,3,5}}
  {{1,2,4},{3,4,5}}
  {{1,2,5},{1,3,4}}
  {{1,2,5},{2,3,4}}
  {{1,2,5},{3,4,5}}
  {{1,3,4},{2,3,5}}
  {{1,3,4},{2,4,5}}
  {{1,3,5},{2,3,4}}
  {{1,3,5},{2,4,5}}
  {{1,4,5},{2,3,4}}
  {{1,4,5},{2,3,5}}
The following are non-isomorphic representatives of the 2 unlabeled 3-uniform hypertrees spanning 7 vertices, and their multiplicities in the labeled case, which add up to a(3) = 735:
  105 X {{1,2,7},{3,4,7},{5,6,7}}
  630 X {{1,2,6},{3,4,7},{5,6,7}}
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..200
Maryam Bahrani and Jérémie Lumbroso, Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition, arXiv:1608.01465 [math.CO], 2016.
Luis Ferroni and Matt Larson, Kazhdan-Lusztig polynomials of braid matroids, arXiv:2303.02253 [math.CO], 2023.
Katie Gedeon, N. Proudfoot, and B. Young, Kazhdan-Lusztig polynomials of matroids: a survey of results and conjectures, arXiv preprint arXiv:1611.07474 [math.CO], 2016-2017.
Nicholas Proudfoot and Ben Young, Configuration spaces, FS^op-modules, and Kazhdan-Lusztig polynomials of braid matroids, arXiv:1704.04510 [math.RT], 2017.
Eric Weisstein's World of Mathematics, Cactus Graph
Index entries for sequences related to cacti

Cf. A000272, A000665, A003081, A030019, A035053, A125791, A302374, A320444, A323292, A323298.

[(2*n+1)^(n-1)*Factorial(2*n)/(2^n*Factorial(n)): n in [0..15]]; // Vincenzo Librandi, Feb 19 2020

Table[(2n+1)^(n-1)(2n)!/(2^n n!), {n, 0, 14}] (* Jean-François Alcover, Nov 06 2018 *)

a(n) = A034940(n)/(2n+1).

The closed form a(n) = (2n-1)!! (2n+1)^(n-1) can be obtained from the generating function in A034940. - Noam D. Elkies, Dec 16 2002

Typo in a(10) corrected and more terms from Alois P. Heinz, Jun 23 2017

A289837 Number of cliques in the n-tetrahedral graph.

Original entry on oeis.org

1, 1, 2, 16, 76, 261, 757, 2003, 5035, 12286, 29426, 69554, 162670, 376923, 865971, 1973941, 4466853, 10040524, 22430584, 49829116, 110127536, 242254321, 530619937, 1157676711, 2516640751, 5452664426, 11777687182, 25367246038, 54492508610, 116769551831

Offset: 1

Eric W. Weisstein, Jul 13 2017

Here, "cliques" means complete subgraphs (not necessarily the largest).
Sequence extended to a(1) using formula. - Andrew Howroyd, Jul 18 2017
From Gus Wiseman, Jan 11 2019: (Start)
The n-tetrahedral graph has all 3-subsets of {1,...,n} as vertices, and two are connected iff they share two elements. So a(n) is the number of 3-uniform hypergraphs on n labeled vertices where every two edges have two vertices in common. For example, the a(4) = 16 hypergraphs are:
  {}
  {{1,2,3}}
  {{1,2,4}}
  {{1,3,4}}
  {{2,3,4}}
  {{1,2,3},{1,2,4}}
  {{1,2,3},{1,3,4}}
  {{1,2,3},{2,3,4}}
  {{1,2,4},{1,3,4}}
  {{1,2,4},{2,3,4}}
  {{1,3,4},{2,3,4}}
  {{1,2,3},{1,2,4},{1,3,4}}
  {{1,2,3},{1,2,4},{2,3,4}}
  {{1,2,3},{1,3,4},{2,3,4}}
  {{1,2,4},{1,3,4},{2,3,4}}
  {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}
The following are non-isomorphic representatives of the 7 unlabeled 3-uniform cliques on 6 vertices, and their multiplicities in the labeled case, which add up to a(6) = 261.
   1 X {}
  20 X {{1,2,3}}
  90 X {{1,3,4},{2,3,4}}
  60 X {{1,4,5},{2,4,5},{3,4,5}}
  60 X {{1,2,4},{1,3,4},{2,3,4}}
  15 X {{1,5,6},{2,5,6},{3,5,6},{4,5,6}}
  15 X {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Clique
Eric Weisstein's World of Mathematics, Tetrahedral Graph
Index entries for linear recurrences with constant coefficients, signature (11,-52,138,-225,231,-146,52,-8).

Cf. A055795 (maximal cliques), A287232 (independent vertex sets), A290056 (triangular graph).

Cf. A000665, A125791, A299471, A302374, A302394, A322451, A323293, A323296, A323298.

Table[(2^(n - 2) - n + 1) Binomial[n, 2] + Binomial[n, 3] +
  5 Binomial[n, 4] + 1, {n, 20}] (* Eric W. Weisstein, Jul 21 2017 *)
LinearRecurrence[{11, -52, 138, -225, 231, -146, 52, -8}, {1, 1, 2, 16, 76, 261, 757, 2003}, 20] (* Eric W. Weisstein, Jul 21 2017 *)
CoefficientList[Series[(1 - 10 x + 43 x^2 - 92 x^3 + 91 x^4 - 25 x^5 - 5 x^6 - 8 x^7)/((-1 + x)^5 (-1 + 2 x)^3), {x, 0, 20}], x] (* Eric W. Weisstein, Jul 21 2017 *)
stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];
Table[Length[stableSets[Subsets[Range[n],{3}],Length[Intersection[#1,#2]]<=1&]],{n,6}] (* Gus Wiseman, Jan 11 2019 *)

a(n) = 1 + binomial(n,3) + (2^(n-2)-n+1)*binomial(n,2) + 5*binomial(n,4); \\ Andrew Howroyd, Jul 18 2017

Vec(x*(1 - 10*x + 43*x^2 - 92*x^3 + 91*x^4 - 25*x^5 - 5*x^6 - 8*x^7) / ((1 - x)^5*(1 - 2*x)^3) + O(x^40)) \\ Colin Barker, Jul 19 2017

a(n) = 1 + binomial(n,3) + (2^(n-2)-n+1)*binomial(n,2) + 5*binomial(n,4). - Andrew Howroyd, Jul 18 2017
a(n) = 11*a(n-1)-52*a(n-2)+138*a(n-3)-225*a(n-4)+231*a(n-5)-146*a(n-6)+52*a(n-7)-8*a(n-8). - Eric W. Weisstein, Jul 21 2017
From Colin Barker, Jul 19 2017: (Start)
G.f.: x*(1 - 10*x + 43*x^2 - 92*x^3 + 91*x^4 - 25*x^5 - 5*x^6 - 8*x^7) / ((1 - x)^5*(1 - 2*x)^3).
a(n) = (24 - (34+3*2^n)*n + (67+3*2^n)*n^2 - 38*n^3 + 5*n^4) / 24.
(End)
Binomial transform of A323294. - Gus Wiseman, Jan 11 2019

a(1)-a(5) and a(21)-a(30) from Andrew Howroyd, Jul 18 2017

A320395 Number of non-isomorphic 3-uniform multiset systems over {1,...,n}.

Original entry on oeis.org

1, 2, 10, 208, 45960, 287800704, 100103176111616, 3837878984050795692032, 32966965900633495618246298767360, 128880214965936601447070466061615999984402432, 464339910355487357558396669850788946402420533504952464572416

Offset: 0

Gus Wiseman, Dec 12 2018

nonn

			Non-isomorphic representatives of the a(2) = 10 multiset systems:
  {}
  {{111}}
  {{122}}
  {{111}{222}}
  {{112}{122}}
  {{112}{222}}
  {{122}{222}}
  {{111}{122}{222}}
  {{112}{122}{222}}
  {{111}{112}{122}{222}}

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

The 2-uniform case is A000666. The case of sets (as opposed to multisets) is A000665. The case of labeled spanning sets is A302374, with unlabeled case A322451.

Cf. A000088, A000612, A003180, A070166, A301922, A317795, A319876.

Table[Sum[2^PermutationCycles[Ordering[Map[Sort,Select[Tuples[Range[n],3],OrderedQ]/.Rule@@@Table[{i,prm[[i]]},{i,n}],{1}]],Length],{prm,Permutations[Range[n]]}]/n!,{n,6}]

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}
rep(typ)={my(L=List(), k=0); for(i=1, #typ, k+=typ[i]; listput(L, k); while(#L0, u=vecsort(apply(f, u)); d=lex(u, v)); !d}
Q(perm)={my(t=0); forsubset([#perm+2, 3], v, t += can([v[1],v[2]-1,v[3]-2], t->perm[t])); t}
a(n)={my(s=0); forpart(p=n, s += permcount(p)*2^Q(rep(p))); s/n!} \\ Andrew Howroyd, Aug 26 2019

Terms a(9) and beyond from Andrew Howroyd, Aug 26 2019

A051240 Number of 4-uniform hypergraphs on n unlabeled nodes, or equivalently pure 3-dimensional simplicial complexes on n unlabeled nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 6, 156, 7013320, 29281354514767168, 234431745534048922731115555415680, 453456943706240925312368435237969462391555337386758635520

Offset: 0

Vladeta Jovovic

V. Jovovic, On the number of m-place relations (in Russian), Logiko-algebraicheskie konstruktsii, Tver, 1992, 59-66.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..18 (terms n=1..16 from Andrew Howroyd)
E. M. Palmer, On the number of n-plexes, Discrete Math., 6 (1973), 377-390. [The numbers are incorrect]

Cf. A000665, A092337, A301922.

Column k=4 of A309858.

a(n) = 1 + Sum_{i=1..n} A301922(i, 4). - Andrew Howroyd, Aug 09 2019

a(0)=1 prepended by Alois P. Heinz, Aug 20 2019

A323293 Number of 3-uniform hypergraphs on n labeled vertices where no two edges have two vertices in common.

Original entry on oeis.org

1, 1, 1, 2, 5, 26, 271, 5596, 231577, 21286940, 4392750641, 2100400533176

Offset: 0

Gus Wiseman, Jan 10 2019

			The a(5) = 26 hypergraphs:
  {}
  {{1,2,3}}
  {{1,2,4}}
  {{1,2,5}}
  {{1,3,4}}
  {{1,3,5}}
  {{1,4,5}}
  {{2,3,4}}
  {{2,3,5}}
  {{2,4,5}}
  {{3,4,5}}
  {{1,2,3},{1,4,5}}
  {{1,2,3},{2,4,5}}
  {{1,2,3},{3,4,5}}
  {{1,2,4},{1,3,5}}
  {{1,2,4},{2,3,5}}
  {{1,2,4},{3,4,5}}
  {{1,2,5},{1,3,4}}
  {{1,2,5},{2,3,4}}
  {{1,2,5},{3,4,5}}
  {{1,3,4},{2,3,5}}
  {{1,3,4},{2,4,5}}
  {{1,3,5},{2,3,4}}
  {{1,3,5},{2,4,5}}
  {{1,4,5},{2,3,4}}
  {{1,4,5},{2,3,5}}
Non-isomorphic representatives of the 6 unlabeled 3-uniform hypertrees spanning 6 vertices where no two edges have two vertices in common, and their multiplicities in the labeled case which add up to a(6) = 271:
    1 X {}
   20 X {{1,2,3}}
   90 X {{1,2,5},{3,4,5}}
   10 X {{1,2,3},{4,5,6}}
  120 X {{1,3,5},{2,3,6},{4,5,6}}
   30 X {{1,2,4},{1,3,5},{2,3,6},{4,5,6}}

Essentially the same as A287232.

Cf. A000665, A025035, A125791, A190865, A289837, A302374, A302394, A319540, A320395, A322451, A323292-A323299.

stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];
Table[Length[stableSets[Subsets[Range[n],{3}],Length[Intersection[#1,#2]]>1&]],{n,8}]

a(9) from Andrew Howroyd, Aug 14 2019

a(10) and a(11) (using A287232) from Joerg Arndt, Oct 12 2023

cp's OEIS Frontend

A058882 Erroneous version of A000665.

Views

Author

Keywords

References

A241586 Erroneous version of A000665.

Views

Author

Keywords

Comments

Links

A000088 Number of simple graphs on n unlabeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A309858 Number A(n,k) of k-uniform hypergraphs on n unlabeled nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A322451 Number of unlabeled 3-uniform hypergraphs spanning n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A034941 Number of labeled triangular cacti with 2n+1 nodes (n triangles).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A289837 Number of cliques in the n-tetrahedral graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A320395 Number of non-isomorphic 3-uniform multiset systems over {1,...,n}.

Views

Author

Keywords

Examples