|
| |
|
|
A030019
|
|
Number of labeled spanning trees in the complete hypergraph on n vertices (all hyperedges having cardinality 2 or greater).
|
|
9
| |
|
|
1, 1, 1, 4, 29, 311, 4447, 79745, 1722681, 43578820, 1264185051, 41381702275, 1509114454597, 60681141052273, 2667370764248023, 127258109992533616, 6549338612837162225, 361680134713529977507, 21333858798449021030515
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,4
|
|
|
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. - D. E. 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
| A. Piggott, THE SYMMETRIES OF MCCULLOUGH-MILLER SPACE, 2011; http://www.facstaff.bucknell.edu/ap030/researchfiles/TheSymmetriesOfMMSpace.pdf
Warren D. Smith and David Warme, Paper in preparation, 2002.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..100
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 810
Index entries for sequences related to trees
|
|
|
FORMULA
| a(n) = A035051(n)/n, n>0.
a(n) = sum_{i=0...n-1} Stirling2(n-1, i) n^{i-1}, n >= 1.
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) ). [From 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!. [From Paul D. Hanna, Sep 25 2011]
|
|
|
PROG
| (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 */
|
|
|
CROSSREFS
| Cf. A030438, A035051, A035053, A134954, A134956, A134958.
Sequence in context: A089470 A014622 A067146 * A201627 A195194 A028853
Adjacent sequences: A030016 A030017 A030018 * A030020 A030021 A030022
|
|
|
KEYWORD
| nonn,nice,changed
|
|
|
AUTHOR
| David Warme (warme(AT)s3i.com)
|
|
|
EXTENSIONS
| More terms, formula and comment from Christian G. Bower (bowerc(AT)usa.net) Dec 15 1999
|
| |
|
|
