This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .