A054921 -id:A054921 - cp's OEIS frontend

A000666 Number of symmetric relations on n nodes.

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

A285572 Number of finite sets of pairwise indivisible positive integers with least common multiple n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 9, 1, 1, 2, 2, 2, 6, 1, 2, 2, 4, 1, 9, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 23, 1, 2, 3, 1, 2, 9, 1, 3, 2, 9, 1, 10, 1, 2, 3, 3, 2, 9, 1, 5, 1, 2, 1, 23, 2, 2, 2, 4, 1, 23, 2, 3, 2, 2, 2, 6, 1, 3, 3, 6

Offset: 1

Gus Wiseman, Apr 21 2017

nonn

			The a(72)=10 sets are {72}, {8,9}, {8,18}, {8,36}, {9,24}, {18,24}, {24,36}, {6,8,9}, {8,9,12}, {8,12,18}.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A000666, A006126, A048143, A054921, A076078, A076413, A285573.

nn=50;
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[Select[Rest[stableSets[Divisors[n],Divisible]],LCM@@#===n&]],{n,1,nn}]

A304716 Number of integer partitions of n whose distinct parts are connected.

Original entry on oeis.org

1, 2, 2, 3, 2, 5, 2, 6, 4, 9, 3, 15, 4, 18, 12, 25, 11, 41, 17, 54, 36, 72, 44, 113, 69, 145, 113, 204, 153, 302, 220, 394, 343, 541, 475, 771, 662, 1023, 968, 1398, 1314, 1929, 1822, 2566, 2565, 3440, 3446, 4677, 4688, 6187, 6407, 8216, 8544, 10975, 11436

Offset: 1

Gus Wiseman, May 17 2018

nonn

Given a finite set S of positive integers greater than one, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices with a common divisor. For example, G({6,14,15,35}) is a 4-cycle. A multiset S is said to be connected if G(S) is a connected graph.

			The a(12) = 15 connected integer partitions and their corresponding connected multiset multisystems (see A112798, A302242) are the following.
                     (12): {{1,1,2}}
                    (6 6): {{1,2},{1,2}}
                    (8 4): {{1,1,1},{1,1}}
                    (9 3): {{2,2},{2}}
                   (10 2): {{1,3},{1}}
                  (4 4 4): {{1,1},{1,1},{1,1}}
                  (6 3 3): {{1,2},{2},{2}}
                  (6 4 2): {{1,2},{1,1},{1}}
                  (8 2 2): {{1,1,1},{1},{1}}
                (3 3 3 3): {{2},{2},{2},{2}}
                (4 4 2 2): {{1,1},{1,1},{1},{1}}
                (6 2 2 2): {{1,2},{1},{1},{1}}
              (4 2 2 2 2): {{1,1},{1},{1},{1},{1}}
            (2 2 2 2 2 2): {{1},{1},{1},{1},{1},{1}}
(1 1 1 1 1 1 1 1 1 1 1 1): {{},{},{},{},{},{},{},{},{},{},{},{}}

Cf. A000009, A003963, A048143, A054921, A218970, A285572, A286518, A302242, A304714, A305078, A305079, A322306, A322307.

zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[Less@@#,GCD@@s[[#]]]>1&]},If[c==={},s,zsm[Union[Append[Delete[s,List/@c[[1]]],LCM@@s[[c[[1]]]]]]]]];
Table[Length[Select[IntegerPartitions[n],Length[zsm[Union[#]]]===1&]],{n,30}]

For n > 1, a(n) = A218970(n) + 1. - Gus Wiseman, Dec 04 2018

Name changed to distinguish from A218970 by Gus Wiseman, Dec 04 2018

A322661 Number of graphs with loops spanning n labeled vertices.

Original entry on oeis.org

1, 1, 5, 45, 809, 28217, 1914733, 254409765, 66628946641, 34575388318705, 35680013894626133, 73392583417010454429, 301348381381966079690489, 2471956814761996896091805993, 40530184362443281653842556898237, 1328619783326799871943604598592805525

Offset: 0

Gus Wiseman, Dec 22 2018

nonn

The span of a graph is the union of its edges.

			The a(2) = 5 edge-sets:
  {{1,2}}
  {{1,1},{1,2}}
  {{1,1},{2,2}}
  {{1,2},{2,2}}
  {{1,1},{1,2},{2,2}}

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

Cf. A000666, A006125, A006129 (loops not allowed), A054921, A062740, A116539, A320461, A322635, A048291 (for directed edgs).

Table[Sum[(-1)^(n-k)*Binomial[n,k]*2^Binomial[k+1,2],{k,0,n}],{n,10}]
(* second program *)
Table[Select[Expand[Product[1+x[i]*x[j],{j,n},{i,j}]],And@@Table[!FreeQ[#,x[i]],{i,n}]&]/.x[_]->1,{n,7}]

a(n) = sum(k=0, n, (-1)^(n-k)*binomial(n,k)*2^binomial(k+1,2)) \\ Andrew Howroyd, Jan 06 2024

Exponential transform of A062740, if we assume A062740(1) = 1.

Inverse binomial transform of A006125(n+1) = 2^binomial(n+1,2).

A007297 Number of connected graphs on n labeled nodes on a circle with straight-line edges that don't cross.

Original entry on oeis.org

1, 1, 4, 23, 156, 1162, 9192, 75819, 644908, 5616182, 49826712, 448771622, 4092553752, 37714212564, 350658882768, 3285490743987, 30989950019532, 294031964658430, 2804331954047160, 26870823304476690, 258548658860327880

Offset: 1

N. J. A. Sloane, Mira Bernstein

Apart from the initial 1, reversion of g.f. for A162395 (squares with signs): see A263843.

			G.f. = x*(1 + x + 4*x^2 + 23*x^3 + 156*x^4 + 1162*x^5 + 9192*x^6 + 75819*x^7 + ...).

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 = 1..999 (first 101 terms from T. D. Noe)
M. Aguiar and J.-L. Loday, Quadri-algebras, J. Pure Appl. Algebra, 191 (2004), 205-221.
R. Bacher, On generating series of complementary plane trees arXiv:math/0409050 [math.CO], 2004.
P. Barry and A. Hennessy, Four-term Recurrences, Orthogonal Polynomials and Riordan Arrays, Journal of Integer Sequences, 2012, article 12.4.2. - From _N. J. A. Sloane_, Sep 21 2012
F. R. Bernhart & N. J. A. Sloane, Emails, April-May 1994
F. Cazals, Combinatorics of Non-Crossing Configurations, Studies in Automatic Combinatorics, Volume II (1997).
E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.
C. Domb and A. J. Barrett, Enumeration of ladder graphs, Discrete Math. 9 (1974), 341-358 (column sums in Table 2).
Michael Drmota, Anna de Mier, Marc Noy, Extremal statistics on non-crossing configurations, Discrete Math. 327 (2014), 103--117. MR3192420. See Eq. (3). - N. J. A. Sloane, May 18 2014
Guillermo Esteban, Clemens Huemer, Rodrigo I. Silveira, New production matrices for geometric graphs, arXiv:2003.00524 [math.CO], 2020.
Sen-Peng Eu, Shu-Chung Liu and Yeong-Nan Yeh, On the congruences of some combinatorial numbers, Stud. Appl. Math. vol. 116 (2006) pp. 135-144.
P. Flajolet and M. Noy, Analytic Combinatorics of Non-crossing Configurations
P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 486.
Loïc Foissy, Free quadri-algebras and dual quadri-algebras, arXiv:1504.06056 [math.CO], 2015.
I. M. Gessel, A short proof of the Deutsch-Sagan congruence for connected non crossing graphs, arXiv preprint arXiv:1403.7656 [math.CO], 2014.
Marco Kuhlmann, Tabulation of Noncrossing Acyclic Digraphs, arXiv:1504.04993 [cs.DS], 2015.
M. Kuhlmann, P. Jonsson, Parsing to Noncrossing Dependency Graphs, Transactions of the Association for Computational Linguistics, vol. 3, pp. 559-570, 2015.
Sara Madariaga, Gröbner-Shirshov bases for the non-symmetric operads of dendriform algebras and quadri-algebras, arXiv:1304.5184 [math.RA], 2013.
B. Vallette, Manin products, Koszul duality, Loday algebras and Deligne conjecture, arXiv:math/0609002 [math.QA], 2006-2007; J. Reine Angew. Math. 620 (2008), 105-164.
Gus Wiseman, The a(5) = 156 connected non-crossing graphs.
Gus Wiseman, Constructive Mathematica program for A007297.
Anssi Yli-Jyrä and Carlos Gómez-Rodríguez, Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing, arXiv:1706.03357 [cs.CL], 2017.
Index entries for reversions of series

Cf. A162395, A000290. 4th row of A107111. Row sums of A089434.
See A263843 for a variant.
Cf. A000108 (non-crossing set partitions), A001006, A001187, A054726 (non-crossing graphs), A054921, A099947, A194560, A293510, A323818, A324167, A324169, A324173.

A007297:=proc(n) if n = 1 then 1 else add(binomial(3*n - 3, n + j)*binomial(j - 1, j - n + 1), j = n - 1 .. 2*n - 3)/(n - 1); fi; end;

CoefficientList[ InverseSeries[ Series[(x-x^2)/(1+x)^3, {x, 0, 20}], x], x] // Rest (* From Jean-François Alcover, May 19 2011, after PARI prog. *)
Table[Binomial[3n, 2n+1] Hypergeometric2F1[1-n, n, 2n+2, -1]/n, {n, 1, 20}] (* Vladimir Reshetnikov, Oct 25 2015 *)

a(n)=if(n<0,0,polcoeff(serreverse((x-x^2)/(1+x)^3+O(x^(n+2))),n+1)) /* Ralf Stephan */

Apart from initial term, g.f. is the series reversion of (x-x^2)/(1+x)^3 (A162395). See A263843. - Vladimir Kruchinin, Feb 08 2013
G.f.: (g-z)/z, where g=-1/3+(2/3)*sqrt(1+9z)*sin((1/3)*arcsin((2+27z+54z^2)/2/(1+9*z)^(3/2))). - Emeric Deutsch, Dec 02 2002
a(n) = (1/n)*Sum_{k=0..n} binomial(3n, n-k-1)*binomial(n+k-1, k). - Paul Barry, May 11 2005
a(n) = 4^(n-1)*(Gamma(3*n/2-1)/Gamma(n/2+1)/Gamma(n) -Gamma((3*n-1)/2)/ Gamma( (n+1)/2)/Gamma(n+1)). - Mark van Hoeij, Aug 27 2005, adapted to offset Feb 21 2020 by R. J. Mathar
a(n) = 4^n * binomial(3*n/2, n/2) / (9*n-6) - 4^(n-1) * binomial(3*(n-1)/2, (n-1)/2 ) / n. - Mark van Hoeij, Aug 27 2005, adapted to offset Feb 21 2020 by R. J. Mathar
D-finite with recurrence: n*(n-1)*(3*n-4)*a(n) +36*(n-1)*a(n-1) -12*(3*n-8)*(3*n-1)*(3*n-7)*a(n-2)=0. - Mark van Hoeij, Aug 27 2005, adapted to offset Feb 21 2020 by R. J. Mathar
a(n) = (1/n)*Sum_{k=0..n} C(3n, k)*C(2n-k-2, n-1). - Paul Barry, Sep 27 2005
a(n) ~ (2-sqrt(3)) * 6^n * 3^(n/2) / (sqrt(2*Pi) * n^(3/2)). - Vaclav Kotesovec, Mar 17 2014
a(n) = binomial(3*n,2*n+1)*hypergeom([1-n,n], [2*n+2], -1)/n. - Vladimir Reshetnikov, Oct 25 2015
a(n) = 2*A078531(n) - A085614(n+1). - Vladimir Reshetnikov, Apr 24 2016

Better description from Philippe Flajolet, Apr 20 2000
More terms from James Sellers, Aug 21 2000
Definition revised and initial a(1)=1 added by N. J. A. Sloane, Nov 05 2015 at the suggestion of Axel Boldt. Some of the formulas may now need to be adjusted slightly.

A304714 Number of connected strict integer partitions of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 2, 3, 2, 5, 2, 5, 5, 6, 5, 10, 6, 12, 12, 13, 14, 21, 17, 23, 26, 30, 31, 46, 38, 51, 55, 61, 70, 87, 85, 102, 116, 128, 138, 171, 169, 204, 225, 245, 272, 319, 334, 383, 429, 464, 515, 593, 629, 715, 790, 861, 950, 1082

Offset: 1

Gus Wiseman, May 17 2018

nonn

			The a(19) = 6 strict integer partitions are (19), (9,6,4), (10,5,4), (10,6,3), (12,4,3), (8,6,3,2). Taking the normalized prime factors of each part (see A112798, A302242), we have the following connected multiset multisystems.
       (19): {{8}}
    (9,6,4): {{2,2},{1,2},{1,1}}
   (10,5,4): {{1,3},{3},{1,1}}
   (10,6,3): {{1,3},{1,2},{2}}
   (12,4,3): {{1,1,2},{1,1},{2}}
  (8,6,3,2): {{1,1,1},{1,2},{2},{1}}

The Heinz numbers of these partitions are given by A328513.

Cf. A000009, A003963, A048143, A054921, A076078, A259936, A281116, A285572, A285573, A286518, A286520, A302242.

zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[Less@@#,GCD@@s[[#]]]>1&]},If[c==={},s,zsm[Union[Append[Delete[s,List/@c[[1]]],LCM@@s[[c[[1]]]]]]]]];
Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&Length[zsm[#]]===1&]],{n,60}]

A286520 Number of finite connected sets of pairwise indivisible positive integers greater than one with least common multiple n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 3, 1, 1, 1, 2, 1, 5, 1, 1, 1, 1, 1, 5, 1, 1, 1, 3, 1, 5, 1, 2, 2, 1, 1, 4, 1, 2, 1, 2, 1, 3, 1, 3, 1, 1, 1, 17, 1, 1, 2, 1, 1, 5, 1, 2, 1, 5, 1, 9, 1, 1, 2, 2, 1, 5, 1, 4, 1, 1, 1, 17, 1, 1, 1

Offset: 2

Gus Wiseman, Jul 24 2017

nonn

Given a finite set S of positive integers greater than one, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices that are not relatively prime. For example, G({6,14,15,35}) is a 4-cycle. A set S is said to be connected if G(S) is a connected graph.

			The a(30)=5 sets are: {30}, {6,10}, {6,15}, {10,15}, {6,10,15}.

Cf. A048143, A054921, A076078, A259936, A281116, A285572, A285573, A286518.

zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[Less@@#,GCD@@s[[#]]]>1&]},If[c==={},s,zsm[Union[Append[Delete[s,List/@c[[1]]],LCM@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Rest[Divisors[n]]],And[!MemberQ[Tuples[#,2],{x_,y_}/;And[x

A134954 Number of "hyperforests" on n labeled nodes, i.e., hypergraphs that have no cycles, assuming that each edge contains at least two vertices.

Original entry on oeis.org

1, 1, 2, 8, 55, 562, 7739, 134808, 2846764, 70720278, 2021462055, 65365925308, 2359387012261, 94042995460130, 4102781803365418, 194459091322828280, 9950303194613104995, 546698973373090998382, 32101070021048906407183, 2006125858248695722280564

Offset: 0

Don Knuth, Jan 26 2008

nonn

The part of the name "assuming that each edge contains at least two vertices" is ambiguous. It may mean that not all n vertices have to be covered by some edge of the hypergraph, i.e., it is not necessarily a spanning hyperforest. However it is common to represent uncovered vertices as singleton edges, as in my example. - Gus Wiseman, May 20 2018

			From _Gus Wiseman_, May 20 2018: (Start)
The a(3) = 8 labeled spanning hyperforests are the following:
{{1,2,3}}
{{1,3},{2,3}}
{{1,2},{2,3}}
{{1,2},{1,3}}
{{3},{1,2}}
{{2},{1,3}}
{{1},{2,3}}
{{1},{2},{3}}
(End)

D. E. Knuth: The Art of Computer Programming, Volume 4, Generating All Combinations and Partitions Fascicle 3, Section 7.2.1.4. Generating all partitions. Page 38, Algorithm H. - Washington Bomfim, Sep 25 2008

Alois P. Heinz, Table of n, a(n) for n = 0..370
N. J. A. Sloane, Transforms

Cf. A030019, A035053, A048143, A054921, A134955, A134956, A134957, A144959, A242817, A304716, A304717, A304867, A304911, A304912.

b:= proc(n) option remember; add(Stirling2(n-1,i) *n^(i-1), i=0..n-1) end: B:= proc(n) x-> add(b(k) *x^k/k!, k=0..n) end: a:= n-> coeff(series(exp(B(n)(x)), x, n+1), x,n) *n!: seq(a(n), n=0..30);  # Alois P. Heinz, Sep 09 2008

b[n_] := b[n] = Sum[StirlingS2[n-1, i]*n^(i-1), {i, 0, n-1}]; B[n_][x_] := Sum[b[k] *x^k/k!, {k, 0, n}]; a[0]=1; a[n_] := SeriesCoefficient[ Exp[B[n][x]], {x, 0, n}] *n!; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 13 2015, after Alois P. Heinz *)

Exponential transform of A030019. - N. J. A. Sloane, Jan 30 2008
Binomial transform of A304911. - Gus Wiseman, May 20 2018
a(n) = Sum of n!*Product_{k=1..n} (A030019(k)/k!)^c_k / (c_k)! over all the partitions of n, c_1 + 2c_2 + ... + nc_n; c_1, c_2, ..., c_n >= 0. - Washington Bomfim, Sep 25 2008
a(n) ~ exp((n+1)/LambertW(1)) * n^(n-2) / (sqrt(1+LambertW(1)) * exp(2*n+2) * (LambertW(1))^n). - Vaclav Kotesovec, Jul 26 2014

A286518 Number of finite connected sets of positive integers greater than one with least common multiple n.

Original entry on oeis.org

1, 1, 1, 2, 1, 4, 1, 4, 2, 4, 1, 20, 1, 4, 4, 8, 1, 20, 1, 20, 4, 4, 1, 88, 2, 4, 4, 20, 1, 96, 1, 16, 4, 4, 4, 196, 1, 4, 4, 88, 1, 96, 1, 20, 20, 4, 1, 368, 2, 20, 4, 20, 1, 88, 4, 88, 4, 4, 1, 1824, 1, 4, 20, 32, 4, 96, 1, 20, 4, 96, 1, 1688, 1, 4, 20, 20, 4, 96, 1, 368, 8, 4, 1, 1824, 4, 4, 4, 88, 1, 1824, 4, 20

Offset: 1

Gus Wiseman, Jul 24 2017

nonn

a(n) depends only on prime signature of n (cf. A025487). - Antti Karttunen, Feb 17 2024

			The a(6)=4 sets are: {6}, {2,6}, {3,6}, {2,3,6}.

Antti Karttunen, Table of n, a(n) for n = 1..719
Index entries for sequences computed from exponents in factorization of n

Cf. A048143, A054921, A069626, A076078, A259936, A281116, A285572, A285573, A286520, A305193, A318670.

zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[Less@@#,GCD@@s[[#]]]>1&]},If[c==={},s,zsm[Union[Append[Delete[s,List/@c[[1]]],LCM@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Rest[Divisors[n]]],zsm[#]==={n}&]],{n,2,20}]

isconnected(facs) = { my(siz=length(facs)); if(1==siz,1,my(m=matrix(siz,siz,i,j,(gcd(facs[i],facs[j])!=1))^siz); for(n=1,siz,if(0==vecmin(m[n,]),return(0))); (1)); };
A286518aux(n, parts, from=1, ss=List([])) = { my(k = #parts, s=0, newss); if(lcm(Vec(ss))==n && isconnected(ss), s++); for(i=from, k, newss = List(ss); listput(newss, parts[i]); s += A286518aux(n, parts, i+1, newss)); (s) };
A286518(n) = if(1==n, n, A286518aux(n, divisors(n))); \\ Antti Karttunen, Feb 17 2024

From Antti Karttunen, Feb 17 2024: (Start)
a(n) <= A069626(n).
It seems that a(n) >= A318670(n), for all n > 1.
(End)

Term a(1)=1 prepended and more terms added by Antti Karttunen, Feb 17 2024

cp's OEIS Frontend

A048143 Number of labeled connected simplicial complexes with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A000666 Number of symmetric relations on n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A285572 Number of finite sets of pairwise indivisible positive integers with least common multiple n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A304716 Number of integer partitions of n whose distinct parts are connected.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A322661 Number of graphs with loops spanning n labeled vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A007297 Number of connected graphs on n labeled nodes on a circle with straight-line edges that don't cross.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A304714 Number of connected strict integer partitions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs