login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A030019 Number of labeled spanning trees in the complete hypergraph on n vertices (all hyperedges having cardinality 2 or greater). 79

%I

%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 L. Kalikow, Enumeration of parking functions, allowable permutation pairs, and labeled trees. PhD thesis, Brandeis University, 1999.

%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, 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 R. 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]

%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, 2016.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=810">Encyclopedia of Combinatorial Structures 810</a>

%H R Lorentz, S Tringali, CH Yan, <a href="http://arxiv.org/abs/1511.04039">Generalized Goncarov polynomials</a>, arXiv preprint arXiv:1511.04039, 2015

%H A. Piggott, <a href="http://www.facstaff.bucknell.edu/ap030/researchfiles/TheSymmetriesOfMMSpace.pdf">The symmetries of Mccullough-Miller space</a>, 2011

%H D. M. Warme, <a href="http://www.citeulike.org/user/veer/article/1236677">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, n>0.

%F a(n) = Sum_{i=0...n-1} Stirling2(n-1, i) n^(i-1), n >= 1. (Warme, corollary 3.15.1)

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 23 19:34 EST 2020. Contains 331175 sequences. (Running on oeis4.)