A134958 -id:A134958 - cp's OEIS frontend

A030019 Number of labeled spanning trees in the complete hypergraph on n vertices (all hyperedges having cardinality 2 or greater).

1, 1, 1, 4, 29, 311, 4447, 79745, 1722681, 43578820, 1264185051, 41381702275, 1509114454597, 60681141052273, 2667370764248023, 127258109992533616, 6549338612837162225, 361680134713529977507, 21333858798449021030515, 1338681172839439064846881

Offset: 0

David Warme (warme(AT)s3i.com)

Equivalently, this is the number of "hypertrees" on n labeled nodes, i.e. connected hypergraphs that have no cycles, assuming that each edge contains at least two vertices. - Don Knuth, Jan 26 2008. See A134954 for hyperforests.
Also number of labeled connected graphs where every block is a complete graph (cf. A035053).
Let H = (V,E) be the complete hypergraph on N labeled vertices (all edges having cardinality 2 or greater). Let e in E and K = |e|. Then the number of distinct spanning trees of H that contain edge e is g(N,K) = K * E[X_N^{N-K}] / N and the K=1 case gives this sequence. Clearly there is some deep structural connection between spanning trees in hypergraphs and Poisson moments.

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

Alois P. Heinz, Table of n, a(n) for n = 0..370 (first 101 terms from T. D. Noe)
Ayomikun Adeniran and Catherine Yan, Gončarov Polynomials in Partition Lattices and Exponential Families, arXiv:1907.07814 [math.CO], 2019.
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 [math.CO], 2016.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 810.
Louis H. Kalikow, Enumeration of parking functions, allowable permutation pairs, and labeled trees, PhD thesis, Brandeis University, 1999.
R. Lorentz, S. Tringali, and C.H. Yan, Generalized Goncarov polynomials, arXiv preprint arXiv:1511.04039, 2015.
Adam Piggott, The symmetries of Mccullough-Miller space, 2011, preprint.
Adam Piggott, The symmetries of Mccullough-Miller space, Algebra and Discrete Mathematics 14(2) (2012), 239-266.
D. M. Warme, Spanning Trees in Hypergraphs with Applications to Steiner Trees, PhD thesis, University of Virginia, 1998, Table 5.1.
D. M. Warme, Spanning Trees in Hypergraphs with Applications to Steiner Trees, PhD thesis, University of Virginia, 1998, Table 5.1.
Index entries for sequences related to trees

Cf. A030438, A035051, A035053, A134954, A134956, A134958. A052888, A210587.

a[n_] := Sum[ StirlingS2[n-1, i]*n^(i-1), {i, 0, n-1}]; a[0] = 1; Table[a[n], {n, 0, 18}](* Jean-François Alcover, Sep 12 2012, from 2nd formula *)

{a(n)=if(n==0,1,(n-1)!*polcoeff(1-sum(k=0, n-2, a(k+1)*x^k/k!*exp(-(k+1)*(exp(x+O(x^n))-1))), n-1))} /* Paul D. Hanna */

/* E.g.f. of sequence shifted left one place: */
{a(n)=local(A=1+x); for(i=1, n, A=exp(-1)*sum(m=0, 2*n+10, exp(m*x*A+x*O(x^n))/m!)); round(n!*polcoeff(A, n))} /* Paul D. Hanna */

a(n) = A035051(n)/n for n > 0.
a(n) = Sum_{i=0...n-1} Stirling2(n-1, i) n^(i-1), n >= 1. (Warme, Corollary 3.15.1, p. 59)
a(n) = E[X_n^{n-1}] / n, n >= 1, where X_n is a Poisson random variable with mean n.
1 = Sum_{n>=0} a(n+1) * x^n/n! * exp( -(n+1)*(exp(x)-1) ). - Paul D. Hanna, Jun 11 2011
E.g.f. satisfies: A(x) = Sum_{n>=0} exp(n*x*A(x)-1)/n! = Sum_{n>=0} a(n+1)*x^n/n!. - Paul D. Hanna, Sep 25 2011
Dobinski-type formula: a(n) = 1/e^n*sum {k = 0..inf} n^(k-1)*k^(n-1)/k!. Cf. A052888. For a refinement of this sequence see A210587. - Peter Bala, Apr 05 2012
a(n) ~ n^(n-2) / (sqrt(1+LambertW(1)) * (LambertW(1))^(n-1) * exp((2-1/LambertW(1))*n)). - Vaclav Kotesovec, Jul 26 2014

More terms, formula and comment from Christian G. Bower Dec 15 1999

A305843 Number of labeled spanning intersecting set-systems on n vertices.

Original entry on oeis.org

1, 1, 3, 27, 1245, 1308285, 912811093455, 291201248260060977862887, 14704022144627161780742038728709819246535634969, 12553242487940503914363982718112298267975272588471811456164576678961759219689708372356843289

Offset: 0

Gus Wiseman, Jun 11 2018

nonn

An intersecting set-system S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection. S is spanning if every vertex is contained in some edge.

			The a(3) = 27 spanning intersecting set-systems:
{{1,2,3}}
{{1},{1,2,3}}
{{2},{1,2,3}}
{{3},{1,2,3}}
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1,2},{1,2,3}}
{{1,3},{2,3}}
{{1,3},{1,2,3}}
{{2,3},{1,2,3}}
{{1},{1,2},{1,3}}
{{1},{1,2},{1,2,3}}
{{1},{1,3},{1,2,3}}
{{2},{1,2},{2,3}}
{{2},{1,2},{1,2,3}}
{{2},{2,3},{1,2,3}}
{{3},{1,3},{2,3}}
{{3},{1,3},{1,2,3}}
{{3},{2,3},{1,2,3}}
{{1,2},{1,3},{2,3}}
{{1,2},{1,3},{1,2,3}}
{{1,2},{2,3},{1,2,3}}
{{1,3},{2,3},{1,2,3}}
{{1},{1,2},{1,3},{1,2,3}}
{{2},{1,2},{2,3},{1,2,3}}
{{3},{1,3},{2,3},{1,2,3}}
{{1,2},{1,3},{2,3},{1,2,3}}

Cf. A001206, A006126, A048143, A051185, A134958, A030019, A304985, A305844.

Length/@Table[Select[Subsets[Rest[Subsets[Range[n]]]],And[Union@@#==Range[n],FreeQ[Intersection@@@Tuples[#,2],{}]]&],{n,1,4}]

Inverse binomial transform of A051185.

A305844 Number of labeled spanning intersecting antichains on n vertices.

Original entry on oeis.org

1, 1, 1, 5, 50, 2330, 1407712, 229800077244, 423295097236295093695

Offset: 0

Gus Wiseman, Jun 11 2018

nonn

An intersecting antichain S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection, and none of which is a subset of any other. S is spanning if every vertex is contained in some edge.

			The a(3) = 5 spanning intersecting antichains:
{{1,2,3}}
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1,3},{2,3}}
{{1,2},{1,3},{2,3}}

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

Cf. A001206, A006126, A048143, A051185, A134958, A030019, A304985, A305843.

Length/@Table[Select[Subsets[Rest[Subsets[Range[n]]]],And[Union@@#==Range[n],FreeQ[Intersection@@@Tuples[#,2],{},{1}],Select[Tuples[#,2],UnsameQ@@#&&Complement@@#=={}&]=={}]&],{n,1,4}]

Inverse binomial transform of A001206(n + 1).

A134956 Number of hyperforests with n labeled vertices: analog of A134954 when edges of size 1 are allowed (with no two equal edges).

Original entry on oeis.org

1, 2, 8, 64, 880, 17984, 495296, 17255424, 728771584, 36208782336, 2069977144320, 133869415030784, 9664049202221056, 770400218809384960, 67219977066339008512, 6372035504466437079040, 652103070162164448952320, 71656927837957783339925504

Offset: 0

Don Knuth, Jan 26 2008

nonn

			From _Gus Wiseman_, May 21 2018: (Start)
The a(2) = 8 hyperforests are the following:
  {{1},{2},{1,2}}
  {{1},{1,2}}
  {{2},{1,2}}
  {{1,2}}
  {{1},{2}}
  {{1}}
  {{2}}
  {}
(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..335

Cf. A134958. - Washington Bomfim, Sep 25 2008

Cf. A030019, A035053, A048143, A054921, A134954, A134955, A134957, A144959, A304716, A304717, A304867, A304911.

with(combinat): p:= proc(n) option remember; add(stirling2(n-1, i) *n^(i-1), i=0..n-1) end: g:= proc(n) option remember; p(n) +add(binomial(n-1, k-1) *p(k) *g(n-k), k=1..n-1) end: a:= n-> `if`(n=0, 1, 2^n * g(n)): seq(a(n), n=0..30); # Alois P. Heinz, Oct 07 2008

p[n_] := p[n] = Sum[ StirlingS2[n-1, i]*n^(i-1), {i, 0, n-1}]; g[n_] := g[n] = p[n] + Sum[Binomial[n-1, k-1]*p[k]*g[n-k], {k, 1, n-1}]; a[n_] := If[n == 0, 1, 2^n* g[n]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 13 2015, after Alois P. Heinz *)

Equals 2^n*A134954(n).

a(n) = Sum of n!prod_{k=1}^n\{ frac{ A134958(k)^{c_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

A304968 Number of labeled hypertrees spanning some subset of {1,...,n}, with singleton edges allowed.

Original entry on oeis.org

1, 2, 7, 48, 621, 12638, 351987, 12426060, 531225945, 26674100154, 1538781595999, 100292956964456, 7288903575373509, 584454485844541718, 51256293341752583499, 4880654469385955209092, 501471626403154217825457, 55300894427785157597436786

Offset: 0

Gus Wiseman, May 22 2018

nonn

			The a(2) = 7 hypertrees are the following:
{}
{{1}}
{{2}}
{{1,2}}
{{1},{1,2}}
{{2},{1,2}}
{{1},{2},{1,2}}

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

Cf. A030019, A035053, A134954, A134955, A134956, A134957, A134958, A134959, A144959, A304386, A304867, A304911, A304912, A304918, A304968, A304970.

\\ here b(n) is A134958 with b(1)=1.
b(n)=if(n<2, n>=0, 2^n*sum(i=0, n, stirling(n-1, i, 2)*n^(i-1)));
a(n)=sum(k=0, n, binomial(n, k)*b(k)); \\ Andrew Howroyd, Aug 27 2018

Binomial transform of b(1) = 1, b(n) = A134958(n) otherwise.

A304970 Number of unlabeled hypertrees with up to n vertices and without singleton edges.

Original entry on oeis.org

1, 1, 2, 4, 8, 17, 39, 98, 263, 759, 2299, 7259, 23649, 79057, 269629, 935328, 3290260, 11714285, 42139053, 152963037, 559697097, 2062574000, 7649550572, 28534096988, 106994891146, 403119433266, 1525466082179, 5795853930652, 22102635416716, 84579153865570

Offset: 0

Gus Wiseman, May 22 2018

nonn

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

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

Cf. A030019, A035053, A134954, A134955, A134956, A134957, A134958, A134959, A144959, A304386, A304867, A304911, A304912, A304918, A304968, A304970.

\\ here b(n) is A007563 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(v)))); v}
seq(n)={my(u=b(n)); Vec(1 + (x*Ser(EulerT(u))*(1-x*Ser(u)))/(1-x))} \\ Andrew Howroyd, Aug 27 2018

Partial sums of A035053 if we assume A035053(1) = 0.

a(n) = A304937(n) + 1 for n > 0.

A144935 Number of hyperforests with n labeled vertices when edges of size 1 are allowed (with no two equal edges), without isolated nodes nor isolated loops.

Original entry on oeis.org

0, 4, 32, 512, 11232, 323648, 11616768, 500984576, 25275854848, 1461945274368, 95418154739712, 6939291871629312, 556552095965593600, 48807623034247200768, 4646562962112939622400, 477275845583045903777792

Offset: 1

Washington Bomfim, Sep 25 2008

nonn

			a(5) = 11232 since the partitions of 5 with parts > 1 are [5] and [3,2]. The partition [5] corresponds to 9952 hypergraphs and [3,2] corresponds to 5!4/2!32/3! = 1280.

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.

Cf. A134958(hypertrees), A134956(hyperforests).

a(n) = Sum of n!prod_{k=1}^n\{ frac{ A134958(k)^{c_k} }{ k!^{c_k} c_k! } } over all the partitions of n with parts k > 1, c_1 + 2c_2 + ... + nc_n; c_1, c_2, ..., c_n >= 0.

A305004 Number of labeled hypertrees (connected acyclic antichains) spanning some subset of {1,...,n} without singleton edges.

Original entry on oeis.org

1, 1, 2, 8, 52, 507, 6844, 118582, 2504856, 62370530, 1788082154, 57997339633, 2099638691440, 83922479506504, 3670657248913386, 174387350448735878, 8942472292255441104, 492294103555090048459, 28958704109012732921524

Offset: 0

Gus Wiseman, May 23 2018

nonn

			The a(3) = 8 hypertrees:
{}
{{1,2}}
{{1,3}}
{{2,3}}
{{1,2,3}}
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1,3},{2,3}}

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

Cf. A030019, A035053, A134958, A134959, A304386, A304939, A304968, A304970.

\\ here b(n) is A030019 with b(1)=0.
b(n)=if(n<2, n==0, sum(i=0, n, stirling(n-1, i, 2)*n^(i-1)));
a(n)=sum(k=0, n, binomial(n, k)*b(k)); \\ Andrew Howroyd, Aug 27 2018

a(n > 0) = A304939(n) + 1.

Binomial transform of A030019 if we assume A030019(1) = 0.

A304977 Number of unlabeled hyperforests spanning n vertices with singleton edges allowed.

Original entry on oeis.org

1, 1, 4, 14, 55, 235, 1112, 5672, 30783, 175733, 1042812, 6385278, 40093375, 257031667, 1676581863, 11098295287, 74401300872, 504290610004, 3451219615401, 23821766422463, 165684694539918, 1160267446543182, 8175446407807625, 57928670942338011, 412561582740147643

Offset: 0

Gus Wiseman, May 22 2018

nonn

			Non-isomorphic representatives of the a(3) = 14 hyperforests are the following:
  {{1,2,3}}
  {{3},{1,2}}
  {{3},{1,2,3}}
  {{1,3},{2,3}}
  {{1},{2},{3}}
  {{2},{3},{1,3}}
  {{2},{3},{1,2,3}}
  {{3},{1,2},{2,3}}
  {{3},{1,3},{2,3}}
  {{1},{2},{3},{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, A134954, A134955, A134956, A134957, A134958, A134959, A144959, A304867, A304911, A304912, A304918.

\\ 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)); concat([1], EulerT(Vec(Ser(EulerT(u))*(1-x*Ser(u))-1)))} \\ Andrew Howroyd, Aug 27 2018

Euler transform of b(1) = 1, b(n > 1) = A134959(n).

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

cp's OEIS Frontend

A030019 Number of labeled spanning trees in the complete hypergraph on n vertices (all hyperedges having cardinality 2 or greater).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A305843 Number of labeled spanning intersecting set-systems on n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A305844 Number of labeled spanning intersecting antichains on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A134956 Number of hyperforests with n labeled vertices: analog of A134954 when edges of size 1 are allowed (with no two equal edges).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A304968 Number of labeled hypertrees spanning some subset of {1,...,n}, with singleton edges allowed.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A304970 Number of unlabeled hypertrees with up to n vertices and without singleton edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A144935 Number of hyperforests with n labeled vertices when edges of size 1 are allowed (with no two equal edges), without isolated nodes nor isolated loops.

Views

Author

Keywords

Examples

References

Crossrefs

Formula

A305004 Number of labeled hypertrees (connected acyclic antichains) spanning some subset of {1,...,n} without singleton edges.

Views

Author

Keywords