0,4

Number of spanning trees in complete graph K_n on n labeled nodes.

Robert Castelo (rcastelo(AT)imim.es), Jan 06 2001, observes that n^(n-2) is also the number of transitive subtree acyclic digraphs on n-1 vertices.

a(n) is also the number of ways of expressing an n-cycle in the symmetric group S_n as a product of n-1 transpositions. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 12 2001

Also counts parking functions, noncrossing partitions, critical configurations of the chip firing game, allowable pairs sorted by a priority queue [Hamel].

a(n+1) = sum( i * n^(n-1-i) * binomial(n, i), i=1..n) - Yong Kong (ykong(AT)curagen.com), Dec 28 2000

a(n+1) = number of endofunctions with no cycles of length > 1; number of forests of rooted labeled trees on n vertices. - Mitch Harris (Harris.Mitchell(AT)mgh.harvard.edu), Jul 06 2006

a(n) is also the number of nilpotent partial bijections (of an n-element set). Equivalently, the number of nilpotents in the partial symmetric semigroup, P sub n. [From A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008]

a(n) is also the number of edge-labeled rooted trees on n nodes. [From Nikos Apostolakis (nikos.ap(AT)gmail.com), Nov 30 2008]

a(n+1) is the number of length n sequences on an alphabet of {1,2,...,n} that have a partial sum equal to n. For example a(4)=16 because there are 16 length 3 sequences on {1,2,3} in which the terms (beginning with the first term and proceeding sequentialy) sum to 3 at some point in the sequence. {1, 1, 1}, {1, 2, 1}, {1, 2, 2}, {1, 2, 3}, {2, 1, 1}, {2, 1, 2}, {2, 1, 3}, {3, 1, 1}, {3, 1, 2}, {3, 1, 3}, {3, 2, 1}, {3, 2, 2}, {3, 2, 3}, {3, 3, 1}, {3, 3, 2}, {3, 3, 3}} [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Jul 20 2009]

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 1999; see p. 142.

M. D. Atkinson and R. Beals, Priority queues and permutations, SIAM J. Comput. 23 (1994), 1225-1230.

N. L. Biggs, Chip-firing and the critical group of a graph, J. Algeb. Combin., 9 (1999), 25-45.

N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 51.

R. Castelo and A. Siebes, A characterization of moral transitive acyclic directed graph Markov models as labeled trees, J. Statist. Planning Inference, 115(1):235-259, 2003.

J. Denes, The representation of a permutation as the product of a minimal number of transpositions ..., Pub. Math. Inst. Hung. Acad. Sci., 4 (1959), 63-70.

J. Gilbey and L. Kalikow, Parking functions, valet functions and priority queues, Discrete Math., 197 (1999), 351-375.

M. Golin and S. Zaks, Labeled trees and pairs of input-output permutations in priority queues, Theoret. Comput. Sci., 205 (1998), 99-114.

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 3.3.33.

I. P. Goulden and S. Pepper, Labeled trees and factorizations of a cycle into transpositions, Discrete Math., 113 (1993), 263-268.

I. P. Goulden and A. Yong, Tree-like properties of cycle factorizations, J. Combin. Theory, A 98 (2002), 106-117.

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 524.

A. M. Hamel, Priority queue sorting and labeled trees, Annals Combin., 7 (2003), 49-54.

D. M. Jackson - Some Combinatorial Problems Associated with Products of Conjugacy Classes of the Symmetric Group, Journal of Combinatorial Theory, Seies A, 49 363-369(1988).

S. Janson, D. E. Knuth, T. Luczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.

L. Kalikow, Symmetries in trees and parking functions, Discrete Math., 256 (2002), 719-741.

J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge Univ. Press, 1992.

G. Martens, On Algebraic Solutions of Polynomial Equations of Degree n in one Variable, GH Consulting EPI-01-06 preprint, 2006

F. McMorris and F. Harary (1992), Subtree acyclic digraphs, Ars Comb., vol. 34.

A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992, Eq. (4.2.2.37)

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 128.

M. P. Schutenberger, On an Enumeration Problem, Journal of Combinatorial Theory 4, 219-221 (1968). [A 1-1 correspondence between maps under permutations and acyclics maps.]

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see page 25, Prop. 5.3.2.

R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68.

Zvonkine, D., An algebra of power series arising in the intersection theory of moduli spaces of curves and in the enumeration of ramified coverings of the sphere. Preprint 2004.

Laradji, A. and Umar, A. On the number of nilpotents in the partial symmetric semigroup, Comm. Algebra 32 (2004), 3017-3023. [From A. Umar (aumarh(AT)squ.edu.om), Aug 25 2008]

N. J. A. Sloane, Table of n, a(n) for n = 0..100

David Callan, A Combinatorial Derivation of the Number of Labeled Forests, J. Integer Seqs., Vol. 6, 2003.

Saverio Caminiti and Emanuele G. Fusco, On the Number of Labeled k-arch Graphs, Journal of Integer Sequences, Vol 10 (2007), Article 07.7.5

Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions.

R. Castelo and A. Siebes, A characterization of moral transitive directed acyclic graph ..., Report CS-2000-44, Department of Computer Science, Univ. Utrecht.

S. Coulomb and M. Bauer, On vertex covers, matchings and random trees

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 78

C. Lamathe, The Number of Labeled k-Arch Graphs, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.1.

G. Martens, Polynomial Equations of Degree n.

J. Pitman, Coalescent Random Forests, J. Combin. Theory, A85 (1999), 165-193.

S. Ramanujan, Question 738, J. Ind. Math. Soc.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

D. Zeilberger, The n^(n-2)-th Proof Of The Formula For The Number Of Labeled Trees

D. Zeilberger, Yet Another Proof For The Enumeration Of Labeled Trees

D. Zvonkine, An algebra of power series...

D. Zvonkine, Home Page

Index entries for sequences related to trees

Index entries for "core" sequences

E.g.f.: T - (1/2)T^2; where T=T(x) is Euler's tree function (see A000169, also A001858). - Len Smiley (smiley(AT)math.uaa.alaska.edu), Nov 19 2001

E.g.f.: ((W(-x)/x)^2)/(1+W(-x)), W(x): Lambert's function (principal branch).

Number of labeled k-trees on n nodes is binomial(n, k) * (k(n-k)+1)^(n-k-2).

Determinant of the symmetric matrix H generated for a polynomial of degree n by: for(i=1,n-1, for(j=1,i, H[i,j]=(n*i^3-3*n*(n+1)*i^2/2+n*(3*n+1)*i/2+(n^4-n^2)/2)/6-(i^2-(2*n+1)*i+n*(n+1))*(j-1)*j/4; H[j,i]=H[i,j]; ); ); - Gerry Martens (GerryMrt(AT)aol.com), May 04 2007

For n>=1, a(n+1)= Sum(n^(n-i)*Binomial(n-1,i-1),i=1...n) [From Geoffrey Critzer (critzer.geoffrey(AT)usd443.org), Jul 20 2009]

a(7)=matdet([196, 175, 140, 98, 56, 21; 175, 160, 130, 92, 53, 20; 140, 130, 110, 80, 47, 18; 98, 92, 80, 62, 38, 15; 56, 53, 47, 38, 26, 11; 21, 20, 18, 15, 11, 6])=16807

A000272 := n->n^(n-2); [ seq(n^(n-2), n=1..20) ];

seq(mul((n), k=3..n), n=1..19); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Sep 14 2007

a:=n->mul(denom (1/(n+3)), k=0..n): seq(a(n), n=-3..16); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Apr 26 2008

a:=n->mul(1+add(1, j=0..n), j=1..n):seq(a(n), n=-2..18); # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 06 2008]

with(finance):seq(futurevalue( 1, n+1, n), n=0..17); # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Mar 24 2009]

<< DiscreteMath`Combinatorica` Table[NumberOfSpanningTrees[CompleteGraph[n]], {n, 1, 20}] - Artur Jasinski (grafix(AT)csl.pl), Dec 06 2007

(PARI) a(n)=if(n<1, 0, n^(n-2))

(MAGMA) [ n^(n-2) : n in [1..10]]; - from Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006

(PARI) \ GP Function for Determinant of Hermitian (square symmetric) matrix for univariate polynomial of degree n by G. Martens: Hn(n=2)= {local(H=matrix(n-1, n-1), i, j); for(i=1, n-1, for(j=1, i, H[i, j]=(n*i^3-3*n*(n+1)*i^2/2+n*(3*n+1)*i/2+(n^4-n^2)/2)/6-(i^2-(2*n+1)*i+n*(n+1))*(\ j-1)*j/4; H[j, i]=H[i, j]; ); ); print("a(", n, ")=matdet(", H, ")"); print("Determinant H =", matdet(H)); return(matdet(H)); } { print(Hn(7)); } - Gerry Martens (GerryMrt(AT)aol.com), May 04 2007

Cf. A000055, A000169, A000312, A007778, A007830, A008785-A008791. a(n)= A033842(n-1, 0) (first column of triangle).

Cf. A000272 (labeled trees), A036361 (labeled 2-trees), A036362 (labeled 3-trees), A036506 (labeled 4-trees), A000055 (unlabeled trees), A054581 (unlabeled 2-trees).

Cf. A097170.

Sequence in context: A157457 A000950 A000951 this_sequence A159594 A088358 A082161

Adjacent sequences: A000269 A000270 A000271 this_sequence A000273 A000274 A000275

easy,nonn,core,nice

N. J. A. Sloane (njas(AT)research.att.com).