A030019 -id:A030019 - cp's OEIS frontend

A317634 Number of caps (also clutter partitions) of clutters (connected antichains) spanning n vertices.

1, 0, 1, 9, 315, 64880

Offset: 0

Gus Wiseman, Aug 02 2018

A kernel of a clutter is the restriction of the edge set to all edges contained within some connected vertex set. A clutter partition is a set partition of the edge set using kernels.

			The a(3) = 9 clutter partitions:
  {{{1,2,3}}}
  {{{1,3},{2,3}}}
  {{{1,2},{2,3}}}
  {{{1,2},{1,3}}}
  {{{1,3}},{{2,3}}}
  {{{1,2}},{{2,3}}}
  {{{1,2}},{{1,3}}}
  {{{1,2},{1,3},{2,3}}}
  {{{1,2}},{{1,3}},{{2,3}}}

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.
Gus Wiseman, All clutter partitions of non-isomorphic clutters on 4 vertices.

Cf. A001187, A030019, A048143, A275307, A286520,, A293510, A304717, A317631, A317632, A317635.

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

A317635 Number of connected vertex sets of clutters (connected antichains) spanning n vertices.

Original entry on oeis.org

1, 0, 1, 14, 486, 71428

Offset: 0

Gus Wiseman, Aug 02 2018

A connected vertex set in a clutter is any union of a connected subset of the edges.

			There are four connected vertex sets of {{1,2},{1,3},{2,3}}, namely {1,2,3}, {1,2}, {1,3}, {2,3}; there are three connected vertex sets of {{1,2},{1,3}}, {{1,2},{2,3}}, and {{1,3},{2,3}} each; and there is one connected vertex set of {{1,2,3}}. So we have a total of a(3) = 4 + 3 * 3 + 1 = 14 connected vertex sets.

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Cf. A001187, A006126, A030019, A048143, A134954, A275307, A286520, A293510, A304717, A317631, A317632, A317634.

nn=5;
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],multijoin@@s[[c[[1]]]]]]]]];
clutQ[eds_]:=And[UnsameQ@@eds,!Apply[Or,Outer[#1=!=#2&&Complement[#1,#2]=={}&,eds,eds,1],{0,1}],Length[csm[eds]]==1];
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]]]];
swell[c_]:=Union@@FixedPointList[Union[ReplaceList[#1,{_,a:{_,x_,_},_,b:{_,x_,_},_}:>Union[a,b]]]&,c]
Table[Sum[Length[swell[c]],{c,Select[stableSets[Select[Subsets[Range[n]],Length[#]>1&],Complement[#1,#2]=={}&],And[Union@@#==Range[n],clutQ[#]]&]}],{n,nn}]

A035051 Number of labeled rooted connected graphs where every block is a complete graph.

Original entry on oeis.org

0, 1, 2, 12, 116, 1555, 26682, 558215, 13781448, 392209380, 12641850510, 455198725025, 18109373455164, 788854833679549, 37343190699472322, 1908871649888004240, 104789417805394595600, 6148562290130009617619

Offset: 0

Christian G. Bower, Oct 15 1998

Equivalently, rooted labeled spanning trees in the complete hypergraph on n vertices (all hyperedges having cardinality 2 or greater).

Warren D. Smith and David Warme, Paper in preparation, 2002.

T. D. Noe, Table of n, a(n) for n=0..100
Roland Bacher, On the enumeration of labelled hypertrees and of labelled bipartite trees, arXiv:1102.2708 [math.CO], 2011.
Maryam Bahrani and Jérémie Lumbroso, Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition, arXiv:1608.01465, 2016.
I. M. Gessel and L. H. Kalikow, Hypergraphs and a functional equation...
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 864
D. M. Warme, Spanning Trees in Hypergraphs with Applications to Steiner Trees. PhD thesis, University of Virginia, 1998.

Cf. A007549, A007563, A030019, A038052, A038053, A030438. A052888, A210586.

f[n_] := Sum[ n^i*StirlingS2[n - 1, i], {i, 0, n - 1}]; Array[f, 18, 0] (* Robert G. Wilson v, Apr 05 2012 *)
Table[If[n == 0, 0, BellB[n - 1, n]], {n, 0, 100}] (* Emanuele Munarini, May 23 2014 *)

a(n):=if n=0 then 0 else sum(stirling2(n-1,k)*n^k,k,0,n);
makelist(a(n),n,0,12); /* Emanuele Munarini, May 23 2014 */

for(n=0,30, print1(sum(k=0,n-1, stirling(n-1,k,2)*n^k), ", ")) \\ G. C. Greubel, Nov 17 2017

Recurrence: a(1) = 1, a(n) = Sum_{k=1}^{n-1} Bell(k) / k! Sum_{a_j > 0, Sum_{j=1}^k a_j = n-1} {{n-1} choose {a_1, a_2, ..., a_k }} \prod_{j=1}^k a(a_j) for n > 1, where Bell(k) = A000110(k). - Warren D. Smith, Feb 23 1998
a(n) = Sum_{i=0...n-1} S(n-1, i) n^i, where S(N, M) are Stirling numbers of the second kind - David Warme, Mar 25 1998
E.g.f. satisfies A(x)=x*exp(exp(A(x))-1).
Let X_{mu} be a Poisson random variable with mean mu: P(X_{mu} = K) = e^{-mu} mu^K / K!. The n-th moment of X_{mu} is E[X_{mu}^n] = sum_{i=0}^n S(n, i) mu^i. Therefore a(n) = E[X_n^{n-1}]. - Langworth Withers, May 25 2000
Dobinski-type formula: a(n) = 1/e^n*sum {k = 0..inf} n^k*k^(n-1)/k!. Cf. A030019 and A052888. For a refinement of this sequence see A210586. - Peter Bala, Apr 05 2012
a(n) ~ exp((1/LambertW(1)-2)*n) * n^(n-1) / (sqrt(1+LambertW(1)) * LambertW(1)^(n-1)). - Vaclav Kotesovec, Jan 22 2014

A007549 Number of increasing rooted connected graphs where every block is a complete graph.

Original entry on oeis.org

1, 1, 3, 14, 89, 716, 6967, 79524, 1041541, 15393100, 253377811, 4596600004, 91112351537, 1959073928124, 45414287553455, 1129046241331316, 29965290866974493, 845605519848379436, 25282324544244718411, 798348403914242674980, 26549922456617388029641

Offset: 1

N. J. A. Sloane

In an increasing rooted graph, nodes are numbered and the numbers increase as you move away from the root.

(a(n+1)/a(n))/n tends to 1/A073003 = 1.676875... (same limit as A029768). - Vaclav Kotesovec, Jul 26 2014

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vaclav Kotesovec, Table of n, a(n) for n = 1..410 (first 200 terms from Vincenzo Librandi)
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]

Cf. A007563, A030019, A035051-A035053.
Cf. A029768.
Row sums of A078341. Column k=1 of A264436.

exptr:= proc(p) local g; g:= proc(n) option remember; p(n) +add(binomial(n-1, k-1) *p(k) *g(n-k), k=1..n-1) end: end: b:= exptr(exptr(a)): a:= n-> `if`(n=0, 1, b(n-1)): seq(a(n), n=1..30); # Alois P. Heinz, Oct 07 2008

exptr[p_] := Module[{g}, g[n_] := g[n] = p[n] + Sum[ Binomial[n-1, k-1]*p[k]*g[n-k], {k, 1, n-1}]; g]; b = exptr[ exptr[a] ]; a[n_] := If[n == 0, 1, b[n-1]]; Table[ a[n], {n, 1, 19}] (* Jean-François Alcover, May 10 2012, after Alois P. Heinz *)

Shifts left when exponentiated twice.
Conjecture: a(n) = Sum_{i=0..2^(n-2) - 1} b(i) for n > 1 with a(1) = 1 where b(n) = (L(n) + 2)*b(f(n)) + Sum_{k=0..L(n) - 1} (1 - R(n,k))*b(f(n) + 2^k*(1 - R(n,k))) for n > 0 with b(0) = 1, L(n) = A000523(n), f(n) = A053645(n) and where R(n,k) = floor(n/2^k) mod 2. Here R(n,k) is the (k+1)-th bit from the right side in the binary expansion of n. - Mikhail Kurkov, Jul 21 2024
Conjecture: a(n) = D^(n-1)(exp(x)) evaluated at x = 0, where D denotes the operator exp(x)*(1 + x)*d/dx. - Peter Bala, Feb 24 2025

New description from Christian G. Bower, Oct 15 1998

A317674 Regular triangle where T(n,k) is the number of antichains covering n vertices with k connected components.

Original entry on oeis.org

1, 1, 1, 5, 3, 1, 84, 23, 6, 1, 6348, 470, 65, 10, 1, 7743728, 39598, 1575, 145, 15, 1, 2414572893530, 54354104, 144403, 4095, 280, 21, 1, 56130437190053299918162, 19316801997024, 218033088, 402073, 9100, 490, 28, 1

Offset: 1

Gus Wiseman, Aug 03 2018

			Triangle begins:
        1
        1       1
        5       3       1
       84      23       6       1
     6348     470      65      10       1
  7743728   39598    1575     145      15       1

Gus Wiseman, Sequences enumerating clutters, antichains, hypertrees, and hyperforests, organized by labeling, spanning, and allowance of singletons.

First column is A048143. Row sums are A006126.
Cf. A000272, A001187, A013922, A030019, A134954, A143543, A275307, A293510.
Cf. A317634, A317635, A317671, A317672, A317677.

blg={1,1,5,84,6348,7743728,2414572893530,56130437190053299918162} (*A048143*);
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Sum[Product[blg[[Length[s]]],{s,spn}],{spn,Select[sps[Range[n]],Length[#]==k&]}],{n,Length[blg]},{k,n}]

A304386 Number of unlabeled hypertrees (connected antichains with no cycles) spanning up to n vertices and allowing singleton edges.

Original entry on oeis.org

1, 2, 5, 15, 50, 200, 907, 4607, 25077, 144337, 863678, 5329994, 33697112, 217317986, 1424880997, 9474795661, 63769947778, 433751273356, 2977769238994, 20611559781972, 143720352656500, 1008765712435162, 7122806053951140, 50566532826530292, 360761703055959592

Offset: 0

Gus Wiseman, May 21 2018

nonn

			Non-isomorphic representatives of the a(3) = 15 hypertrees are the following:
  {}
  {{1}}
  {{1,2}}
  {{1,2,3}}
  {{2},{1,2}}
  {{1,3},{2,3}}
  {{3},{1,2,3}}
  {{1},{2},{1,2}}
  {{3},{1,2},{2,3}}
  {{3},{1,3},{2,3}}
  {{2},{3},{1,2,3}}
  {{1},{2},{3},{1,2,3}}
  {{2},{3},{1,2},{1,3}}
  {{2},{3},{1,3},{2,3}}
  {{1},{2},{3},{1,3},{2,3}}

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

Cf. A030019, A035053, A048143, A054921, A134954, A134955, A134957, A134959, A144959, A304386, A304717, A304867, A304911, A304912, A304968, A304970.

\\ here b(n) is A318494 as vector
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
b(n)={my(v=[1]); for(i=2, n, v=concat([1], EulerT(EulerT(2*v)))); v}
seq(n)={my(u=2*b(n)); Vec(1 + x*Ser(EulerT(u))*(1-x*Ser(u))/(1-x))} \\ Andrew Howroyd, Aug 27 2018

Partial sums of b(1) = 1, b(n) = A134959(n) otherwise.

Terms a(7) and beyond from Andrew Howroyd, Aug 27 2018

A318697 Number of ways to partition a hypertree spanning n vertices into hypertrees.

Original entry on oeis.org

1, 1, 7, 93, 1856, 49753, 1679441, 68463769, 3273695758, 179710285011, 11141016392749, 769939840667473, 58695964339179805, 4893452980658819151, 442915168219228586581, 43255083632741702266097, 4533695508041747494704359, 507638249638364368312476913

Offset: 1

Gus Wiseman, Aug 31 2018

nonn

			The a(3) = 7 hypertree partitions:
  {{{1,2,3}}}
  {{{1,2},{1,3}}}
  {{{1,2},{2,3}}}
  {{{1,3},{2,3}}}
  {{{1,2}},{{1,3}}}
  {{{1,2}},{{2,3}}}
  {{{1,3}},{{2,3}}}

Cf. A000272, A030019, A048143, A134954, A275307, A317631, A317632, A317634, A317635, A317677.

trct[n_]:=Sum[StirlingS2[n-1,i]*n^(i-1),{i,0,n-1}];
numSetPtnsOfType[ptn_]:=Total[ptn]!/Times@@Factorial/@ptn/Times@@Factorial/@Length/@Split[ptn];
Table[Sum[n^(Length[ptn]-1)*Product[trct[s+1],{s,ptn}]*numSetPtnsOfType[ptn],{ptn,IntegerPartitions[n-1]}],{n,20}]

A320444 Number of uniform hypertrees spanning n vertices.

Original entry on oeis.org

1, 1, 1, 4, 17, 141, 1297, 17683, 262145, 4861405, 100112001, 2371816701, 61917364225, 1796326510993, 56693912375297, 1947734359001551, 72059082110369793, 2863257607266475419, 121439531096594251777, 5480987217944109919765, 262144000000000000000001

Offset: 0

Gus Wiseman, Jan 09 2019

nonn

The density of a hypergraph is the sum of sizes of its edges minus the number of edges minus the number of vertices. A hypertree is a connected hypergraph of density -1. A hypergraph is uniform if its edges all have the same size. The span of a hypergraph is the union of its edges.

			Non-isomorphic representatives of the 5 unlabeled uniform hypertrees on 5 vertices and their multiplicities in the labeled case, which add up to a(5) = 141:
   5 X {{1,5},{2,5},{3,5},{4,5}}
  60 X {{1,4},{2,5},{3,5},{4,5}}
  60 X {{1,3},{2,4},{3,5},{4,5}}
  15 X {{1,2,5},{3,4,5}}
   1 X {{1,2,3,4,5}}

Robert Israel, Table of n, a(n) for n = 0..387

Row sums of A326374.

Cf. A000272, A030019, A035053, A038041, A052888, A057625, A061095, A121860, A134954, A236696, A262843.

f:= proc(n) local d; add((n-1)!/(d! * ((n-1)/d)!) * (n/d)^((n-1)/d - 1), d = numtheory:-divisors(n-1)); end proc:
f(0):= 1: f(1):= 1:
map(f, [$0..25]); # Robert Israel, Jan 10 2019

Table[Sum[n!/(d!*(n/d)!)*((n+1)/d)^(n/d-1),{d,Divisors[n]}],{n,10}]

a(n) = if (n<2, 1, n--; sumdiv(n, d, n!/(d! * (n/d)!) * ((n + 1)/d)^(n/d - 1))); \\ Michel Marcus, Jan 10 2019

a(n + 1) = Sum_{d|n} n!/(d! * (n/d)!) * ((n + 1)/d)^(n/d - 1).

a(p prime) = 1 + (p + 1)^(p - 1).

A125702 Number of connected categories with n objects and 2n-1 morphisms.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 22, 42, 94, 203, 470, 1082, 2602, 6270, 15482, 38525, 97258, 247448, 635910, 1645411, 4289010, 11245670, 29656148, 78595028, 209273780, 559574414, 1502130920, 4046853091, 10939133170, 29661655793

Offset: 1

Franklin T. Adams-Watters and Christian G. Bower, Jan 05 2007

nonn

Also number of connected antitransitive relations on n objects (antitransitive meaning a R b and b R c implies not a R c); equivalently, number of free oriented bipartite trees, with all arrows going from one part to the other part.

Also the number of non-isomorphic multi-hypertrees of weight n - 1 with singletons allowed. A multi-hypertree with singletons allowed is a connected set multipartition (multiset of sets) with density -1, where the density of a set multipartition is the weight (sum of sizes of the parts) minus the number of parts minus the number of vertices. - Gus Wiseman, Oct 30 2018

			From _Gus Wiseman_, Oct 30 2018: (Start)
Non-isomorphic representatives of the a(1) = 1 through a(6) = 10 multi-hypertrees of weight n - 1 with singletons allowed:
  {}  {{1}}  {{12}}    {{123}}      {{1234}}        {{12345}}
             {{1}{1}}  {{2}{12}}    {{13}{23}}      {{14}{234}}
                       {{1}{1}{1}}  {{3}{123}}      {{4}{1234}}
                                    {{1}{2}{12}}    {{2}{13}{23}}
                                    {{2}{2}{12}}    {{2}{3}{123}}
                                    {{1}{1}{1}{1}}  {{3}{13}{23}}
                                                    {{3}{3}{123}}
                                                    {{1}{2}{2}{12}}
                                                    {{2}{2}{2}{12}}
                                                    {{1}{1}{1}{1}{1}}
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..500

Same as A122086 except for n = 1; see there for formulas. Cf. A125699.

Cf. A000081, A000272, A007716, A007717, A030019, A052888, A134954, A317631, A317632, A318697, A320921, A321155.

\\ TreeGf gives gf of A000081.
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={Vec(2*TreeGf(n) - TreeGf(n)^2 - x)} \\ Andrew Howroyd, Nov 02 2019

a(n) = A122086(n) for n > 1.

G.f.: 2*f(x) - f(x)^2 - x where f(x) is the g.f. of A000081. - Andrew Howroyd, Nov 02 2019

cp's OEIS Frontend

A317634 Number of caps (also clutter partitions) of clutters (connected antichains) spanning n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A317635 Number of connected vertex sets of clutters (connected antichains) spanning n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A035051 Number of labeled rooted connected graphs where every block is a complete graph.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

A007549 Number of increasing rooted connected graphs where every block is a complete graph.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A317674 Regular triangle where T(n,k) is the number of antichains covering n vertices with k connected components.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A304386 Number of unlabeled hypertrees (connected antichains with no cycles) spanning up to n vertices and allowing singleton edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A318697 Number of ways to partition a hypertree spanning n vertices into hypertrees.

Views