

A007334


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 (for n>=2).
(Formerly M1883)


4



1, 2, 8, 50, 432, 4802, 65536, 1062882, 20000000, 428717762, 10319560704, 275716983698, 8099130339328, 259492675781250, 9007199254740992, 336755653118801858, 13493281232954916864, 576882827135242335362, 26214400000000000000000
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,2


COMMENTS

The old name (referring to the ChenGoyal article) was "[Number of] essential complementary partitions of [an] nset."
This sequence was obtained using the deletioncontraction 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 (n2)*(n^{n3}). Since the number of spanning trees in K_{n} is n^{n2}, we see that (n2)*(n^{n3})+f(n)=n^{n2} by the deletioncontraction recursion. Hence it follows that f(n)=2*n^{n3}.  N. Eaton, W. Kook and L. Thoma (andrewk(AT)math.uri.edu), Jan 17 2004
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

J. Oxley, Matroid Theory, Oxford University Press, 1992.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

Table of n, a(n) for n=2..20.
W.K. Chen and I. C. Goyal, Tables of essential complementary partitions, IEEE Trans. Circuit Theory, 18 (1971), 562563.
W.K. Chen and I. C. Goyal, Tables of essential complementary partitions, IEEE Trans. Circuit Theory, 18 (1971), 562563. (Annotated scanned copy)
N. Eaton, W. Kook and L. Thoma, Monotonicity for complete graphs, preprint, 2003.
J.B. Priez, A. Virmaux, Noncommutative Frobenius characteristic of generalized parking functions: Application to enumeration, arXiv:1411.4161 [math.CO], 20142015.
Dennis Walsh, Notes on acyclic functions


FORMULA

a(n) = 2*n^{n3} (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/(1x).  Paul D. Hanna, Jan 17 2013


EXAMPLE

a(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, 1polcoeff(sum(k=2, n1, a(k)*x^k/(1+(k1)*x+x*O(x^n))^(k1)), n))} /* Paul D. Hanna, Jan 17 2013 */


CROSSREFS

The sequence is A058127(n, n2) for n >= 2.  Peter Luschny, Apr 22 2009
Cf. A007830.
Sequence in context: A225052 A295759 A089104 * A050398 A135081 A296366
Adjacent sequences: A007331 A007332 A007333 * A007335 A007336 A007337


KEYWORD

nonn


AUTHOR

N. J. A. Sloane


EXTENSIONS

a(6) corrected and more terms from Sean A. Irvine, Dec 19 2017
After correction, this became identical (except for the offset) with A089104, contributed by N. Eaton, W. Kook and L. Thoma (andrewk(AT)math.uri.edu), Jan 17 2004. The two entries have been merged using the older Anumber.  N. J. A. Sloane, Dec 19 2017


STATUS

approved



