cp's OEIS Frontend

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).

%I A007334 M1883 #58 May 08 2025 10:52:22
%S A007334 1,2,8,50,432,4802,65536,1062882,20000000,428717762,10319560704,
%T A007334 275716983698,8099130339328,259492675781250,9007199254740992,
%U A007334 336755653118801858,13493281232954916864,576882827135242335362,26214400000000000000000
%N 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).
%C A007334 The old name (referring to the Chen-Goyal article) was "[Number of] essential complementary partitions of [an] n-set."
%C A007334 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}. - N. Eaton, W. Kook and L. Thoma (andrewk(AT)math.uri.edu), Jan 17 2004
%C A007334 With offset 0, the number of acyclic functions from {1,...,n} to {1,...,n+2}. See link below. - _Dennis P. Walsh_, Nov 27 2011
%C A007334 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
%D A007334 J. Oxley, Matroid Theory, Oxford University Press, 1992.
%D A007334 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A007334 Alin Bostan, Frédéric Chyzak, Bérénice Delcroix-Oger, Guillaume Laplante-Anfossi, Vincent Pilaud, and Kurt Stoeckl, <a href="https://mathexp.eu/bostan/diagonalsFPSAC25.pdf">Diagonals of permutahedra and associahedra</a>, Sém. Lotharingien Comb., 37th Formal Power Series Alg. Comb. (FPSAC 2025). See p. 7.
%H A007334 W.-K. Chen and I. C. Goyal, <a href="https://doi.org/10.1109/TCT.1971.1083334">Tables of essential complementary partitions</a>, IEEE Trans. Circuit Theory, 18 (1971), 562-563.
%H A007334 W.-K. Chen and I. C. Goyal, <a href="/A007334/a007334.pdf">Tables of essential complementary partitions</a>, IEEE Trans. Circuit Theory, 18 (1971), 562-563. (Annotated scanned copy)
%H A007334 Spencer Daugherty, Pamela E. Harris, Ian Klein, and Matt McClinton, <a href="https://arxiv.org/abs/2406.12941">Metered Parking Functions</a>, arXiv:2406.12941 [math.CO], 2024. See pp. 19, 22.
%H A007334 N. Eaton, W. Kook and L. Thoma, <a href="https://www.researchgate.net/publication/253508155_MONOTONICITY_FOR_COMPLETE_GRAPHS_AND_SYMMETRIC_COMPLETE_BIPARTITE_GRAPHS">Monotonicity for complete graphs</a>, preprint, 2003.
%H A007334 Jean-Baptiste Priez and Aladin Virmaux, <a href="http://arxiv.org/abs/1411.4161">Non-commutative Frobenius characteristic of generalized parking functions: Application to enumeration</a>, arXiv:1411.4161 [math.CO], 2014-2015.
%H A007334 Dennis Walsh, <a href="http://frank.mtsu.edu/~dwalsh/acyclic/ACYCNT3.pdf">Notes on acyclic functions</a>
%F A007334 a(n) = 2*n^{n-3} (n>=2).
%F A007334 E.g.f.: (-W(-x)/x)*exp(-W(-x)). - _Paul Barry_, Nov 19 2010 [With offset 0, and W = LambertW. Equals (W(-x)/(-x))^2 = (exp(-W(-x)))^2 (see a comment above). - _Wolfdieter Lang_, Nov 11 2022]
%F A007334 G.f.: Sum_{n>=1} a(n+1) * x^n / (1 + n*x)^n  =  x/(1-x). - _Paul D. Hanna_, Jan 17 2013
%e A007334 a(3)=2 because K_{3}/e consists of two vertices and two parallel edges, where each edge is a spanning tree.
%t A007334 nn = 17; tx = Sum[n^(n - 1) x^n/n!, {n, 1, nn}];
%t A007334 Range[0, nn]! CoefficientList[Series[Exp[ tx]^2, {x, 0, nn}], x]  (* _Geoffrey Critzer_, May 10 2013 *)
%o A007334 (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 */
%Y A007334 The sequence is A058127(n, n-2) for n >= 2. - _Peter Luschny_, Apr 22 2009
%Y A007334 Cf. A007830.
%K A007334 nonn
%O A007334 2,2
%A A007334 _N. J. A. Sloane_
%E A007334 a(6) corrected and more terms from _Sean A. Irvine_, Dec 19 2017
%E A007334 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 A-number. - _N. J. A. Sloane_, Dec 19 2017