|
%I #64 Apr 20 2020 10:54:39
%S 1,1,1,4,29,311,4447,79745,1722681,43578820,1264185051,41381702275,
%T 1509114454597,60681141052273,2667370764248023,127258109992533616,
%U 6549338612837162225,361680134713529977507,21333858798449021030515,1338681172839439064846881
%N Number of labeled spanning trees in the complete hypergraph on n vertices (all hyperedges having cardinality 2 or greater).
%C 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.
%C Also number of labeled connected graphs where every block is a complete graph (cf. A035053).
%C 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.
%D Warren D. Smith and David Warme, Paper in preparation, 2002.
%H Alois P. Heinz, <a href="/A030019/b030019.txt">Table of n, a(n) for n = 0..370</a> (first 101 terms from T. D. Noe)
%H Ayomikun Adeniran and Catherine Yan, <a href="https://arxiv.org/abs/1907.07814">Gončarov Polynomials in Partition Lattices and Exponential Families</a>, arXiv:1907.07814 [math.CO], 2019.
%H Ronald Bacher, <a href="http://arxiv.org/abs/1102.2708">On the enumeration of labelled hypertrees and of labelled bipartite trees</a>, arXiv:1102.2708v1 [math.CO], 2011.
%H Maryam Bahrani and Jérémie Lumbroso, <a href="http://arxiv.org/abs/1608.01465">Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition</a>, arXiv:1608.01465 [math.CO], 2016.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=810">Encyclopedia of Combinatorial Structures 810</a>.
%H Louis H. Kalikow, <a href="http://people.brandeis.edu/~gessel/homepage/students/kalikowthesis.pdf">Enumeration of parking functions, allowable permutation pairs, and labeled trees</a>, PhD thesis, Brandeis University, 1999.
%H R. Lorentz, S. Tringali, and C.H. Yan, <a href="http://arxiv.org/abs/1511.04039">Generalized Goncarov polynomials</a>, arXiv preprint arXiv:1511.04039, 2015.
%H Adam Piggott, <a href="https://web.archive.org/web/20171109082007/http://www.facstaff.bucknell.edu/ap030/researchfiles/TheSymmetriesOfMMSpace.pdf">The symmetries of Mccullough-Miller space</a>, 2011, preprint.
%H Adam Piggott, <a href="http://admjournal.luguniv.edu.ua/index.php/adm/article/view/724">The symmetries of Mccullough-Miller space</a>, Algebra and Discrete Mathematics 14(2) (2012), 239-266.
%H D. M. Warme, <a href="https://doi.org/10.18130/V3ZG4B">Spanning Trees in Hypergraphs with Applications to Steiner Trees</a>, PhD thesis, University of Virginia, 1998, Table 5.1.
%H D. M. Warme, <a href="https://pdfs.semanticscholar.org/664b/7dc1691cc43a1a650eb9dec4e3c621024ed9.pdf">Spanning Trees in Hypergraphs with Applications to Steiner Trees</a>, PhD thesis, University of Virginia, 1998, Table 5.1.
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F a(n) = A035051(n)/n for n > 0.
%F a(n) = Sum_{i=0...n-1} Stirling2(n-1, i) n^(i-1), n >= 1. (Warme, Corollary 3.15.1, p. 59)
%F a(n) = E[X_n^{n-1}] / n, n >= 1, where X_n is a Poisson random variable with mean n.
%F 1 = Sum_{n>=0} a(n+1) * x^n/n! * exp( -(n+1)*(exp(x)-1) ). - _Paul D. Hanna_, Jun 11 2011
%F 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
%F 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
%F a(n) ~ n^(n-2) / (sqrt(1+LambertW(1)) * (LambertW(1))^(n-1) * exp((2-1/LambertW(1))*n)). - _Vaclav Kotesovec_, Jul 26 2014
%t 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 *)
%o (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_ */
%o (PARI) /* E.g.f. of sequence shifted left one place: */
%o {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_ */
%Y Cf. A030438, A035051, A035053, A134954, A134956, A134958. A052888, A210587.
%K nonn,nice
%O 0,4
%A David Warme (warme(AT)s3i.com)
%E More terms, formula and comment from _Christian G. Bower_ Dec 15 1999
| 