|
| |
|
|
A089104
|
|
Number of spanning trees in the graph K_{n}/e, which results from contracting an edge e in the complete graph K_{n} on n vertices (n>=2).
|
|
1
|
|
|
|
1, 2, 8, 50, 432, 4802, 65536, 1062882, 20000000, 428717762, 10319560704, 275716983698, 8099130339328, 259492675781250, 9007199254740992, 336755653118801858, 13493281232954916864, 576882827135242335362
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,2
|
|
|
COMMENTS
|
This sequence was obtained using the deletion-contraction recursions satisfied by the number of spanning trees for graphs. It is readily seen that the number of spanning trees in K_{n}-e (the complete graph K_{n} with an edge e deleted) is (n-2)*(n^{n-3}). Since the number of spanning trees in K_{n} is n^{n-2}, we see that (n-2)*(n^{n-3})+f(n)=n^{n-2} by the deletion-contraction recursion. Hence it follows that f(n)=2*n^{n-3}.
With offset 0, the number of acyclic functions from {1,...,n} to {1,...,n+2}. See link below. [Dennis P. Walsh, Nov 27 2011]
With offset 0, a(n) is the number of forests of rooted labeled trees on n nodes in which some (possibly all or none) of the trees have been specially designated. a(n) = Sum_{k=1..n} A061356(n,k)*2^k. E.g.f. is exp(T(x))^2 where T(x) is the e.g.f for A000169. The expected number of trees in each forest approaches 3 as n gets large. Cf. A225497. - Geoffrey Critzer, May 10 2013
|
|
|
REFERENCES
|
N. Eaton, W. Kook and L. Thoma, Monotonicity for complete graphs, preprint, 2003
J. Oxley, Matroid Theory, Oxford University Press, 1992.
|
|
|
LINKS
|
Table of n, a(n) for n=2..19.
Dennis Walsh, Notes on acyclic functions
|
|
|
FORMULA
|
f(n)=2*n^{n-3} (n>=2)
E.g.f.: (-W(-x)/x)*exp(-W(-x)). [Paul Barry, Nov 19 2010]
G.f.: Sum_{n>=1} a(n+1) * x^n / (1 + n*x)^n = x/(1-x). - Paul D. Hanna, Jan 17 2013
|
|
|
EXAMPLE
|
f(3)=2 because K_{3}/e consists of two veritices and two parallel edges, where each edge is a spanning tree.
|
|
|
MATHEMATICA
|
nn = 17; tx = Sum[n^(n - 1) x^n/n!, {n, 1, nn}];
Range[0, nn]! CoefficientList[Series[Exp[ tx]^2, {x, 0, nn}], x] (* Geoffrey Critzer, May 10 2013 *)
|
|
|
PROG
|
(PARI) {a(n)=if(n==2, 1, 1-polcoeff(sum(k=2, n-1, a(k)*x^k/(1+(k-1)*x+x*O(x^n))^(k-1)), n))} /* Paul D. Hanna, Jan 17 2013 */
|
|
|
CROSSREFS
|
The sequence is A058127(n, n-2) for n >= 2. [From Peter Luschny, Apr 22 2009]
Sequence in context: A193352 A002801 A225052 * A050398 A135081 A007334
Adjacent sequences: A089101 A089102 A089103 * A089105 A089106 A089107
|
|
|
KEYWORD
|
nonn,changed
|
|
|
AUTHOR
|
N. Eaton, W. Kook and L. Thoma (andrewk(AT)math.uri.edu), Jan 17 2004
|
|
|
STATUS
|
approved
|
| |
|
|
