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

Author

David Warme (warme(AT)s3i.com)

Keywords

• nonn
• nice

Comments

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.

References

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

Links

• 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

Crossrefs

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

Programs

Mathematica

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 *)

PARI

{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 */

PARI

/* 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 */

Formula

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

Extensions

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