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, see example. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 12 2001

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

The parking functions of length n can be described as all permutations of all words [d(1),d(2), ..., d(n)] where 1 <= d(k) <= k; see example. There are (n+1)^(n-1) = a(n+1) parking functions of length n. - Joerg Arndt, Jul 15 2014

a(n+1) = number of endofunctions with no cycles of length > 1; number of forests of rooted labeled trees on n vertices. - Mitch Harris, 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. - Abdullahi Umar, Aug 25 2008

a(n) is also the number of edge-labeled rooted trees on n nodes. - Nikos Apostolakis, 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 sequentially) 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}. - Geoffrey Critzer, Jul 20 2009

a(3) = 3 is the only prime value in the sequence. There are no semiprime values. Generally, the number of distinct primes dividing a(n) = omega(a(n)) = A001221(a(n)) = omega(n). Similarly, the number of prime divisors of a(n) (counted with multiplicity) = bigomega(a(n)) = A001222(a(n)) = Product (p_j^k_j) = Sum (k_j) where a(n) = Product (p_j^k_j), which is an obvious function of n and n-2. - Jonathan Vos Post, May 27 2010

a(n) is the number of acyclic functions from {1,2,...,n-1} to {1,2,...,n}. An acyclic function f satisfies the following property: for any x in the domain, there exists a positive integer k  such that (f^k)(x) is not in the domain. Note that f^k denotes the k-fold composition of f with itself, e.g., (f^2)(x)=f(f(x)). - Dennis P. Walsh, Mar 02 2011

a(n) is the absolute value of the discriminant of the polynomial x^{n-1}+...+x+1. More precisely, a(n) = (-1)^{(n-1)(n-2)/2} times the discriminant. - Zach Teitler, Jan 28 2014

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.

M. Beck et al., Parking functions, Shi arrangements, and mixed graphs. Amer. Math. Monthly, 122 (2015), 660-673.

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.

Laradji, A. and Umar, A. On the number of nilpotents in the partial symmetric semigroup, Comm. Algebra 32 (2004), 3017-3023. - From Abdullahi Umar, Aug 25 2008

Liu, C. J.; Chow, Yutze. On operator and formal sum methods for graph enumeration problems. SIAM J. Algebraic Discrete Methods, 5 (1984), no. 3, 384--406. MR0752043 (86d:05059). See Eq. (47). - From N. J. A. Sloane, Apr 09 2014

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.

J. Riordan, Forests of labeled trees, J. Combin. Theory, 5 (1968), 90-103. See Table 1.

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

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

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

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.

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

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.

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

Suresh Govindarajan, Notes on higher-dimensional partitions, arXiv preprint arXiv:1203.4419, 2012.

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.

Mustafa Obaid et al., The number of complete exceptional sequences for a Dynkin algebra, arXiv preprint arXiv:1307.7573, 2013

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

J.-B. Priez, A. Virmaux, Non-commutative Frobenius characteristic of generalized parking functions: Application to enumeration, arXiv preprint arXiv:1411.4161, 2014

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

Dennis Walsh, Notes on acyclic functions and their directed graphs

Eric Weisstein's World of Mathematics, Complete Graph

Eric Weisstein's World of Mathematics, Labeled Tree

Eric Weisstein's World of Mathematics, Spanning Tree

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.: 1 + 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

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

E.g.f. for b(n)=a(n+2): ((W(-x)/x)^2)/(1+W(-x)), where W is Lambert's function (principal branch).

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, May 04 2007

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

For n>=1, a(n+1)= Sum(n^(n-i)*Binomial(n-1,i-1),i=1...n). - Geoffrey Critzer, Jul 20 2009

E.g.f. for b(n)=a(n+1): exp(-W(-x)), where W is Lambert's function satisfying W(x)exp(W(x))=x. Proof is contained in link "Notes on acyclic functions..." - Dennis P. Walsh, Mar 02 2011

From Sergei N. Gladkovskii, Sep 18 2012: (Start)

E.g.f.: 1+x+x^2/(U(0)-x) where U(k)= x*(k+1)*(k+2)^k + (k+1)^k*(k+2) - x*(k+2)^2*(k+3)*((k+1)*(k+3))^k/U(k+1); (continued fraction, Euler's 1st kind, 1-step).

G.f.: 1+x+x^2/(U(0)-x) where U(k)= x*(k+1)*(k+2)^k + (k+1)^k - x*(k+2)*(k+3)*((k+1)*(k+3))^k/E(k+1); (continued fraction, Euler's 1st kind, 1-step). (End)

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

a(3)=3 since there are 3 acyclic functions f:[2]->[3], namely, {(1,2),(2,3)}, {(1,3),(2,1)}, and {(1,3),(2,3)}.

From Joerg Arndt and Greg Stevenson, Jul 11 2011: (Start)

The following products of 3 transpositions lead to a 4-cycle in S_4:

(1,2)*(1,3)*(1,4);

(1,2)*(1,4)*(3,4);

(1,2)*(3,4)*(1,3);

(1,3)*(1,4)*(2,3);

(1,3)*(2,3)*(1,4);

(1,4)*(2,3)*(2,4);

(1,4)*(2,4)*(3,4);

(1,4)*(3,4)*(2,3);

(2,3)*(1,2)*(1,4);

(2,3)*(1,4)*(2,4);

(2,3)*(2,4)*(1,2);

(2,4)*(1,2)*(3,4);

(2,4)*(3,4)*(1,2);

(3,4)*(1,2)*(1,3);

(3,4)*(1,3)*(2,3);

(3,4)*(2,3)*(1,2).  (End)

The 16 parking functions of length 3 are 111, 112, 121, 211, 113, 131, 311, 221, 212, 122, 123, 132, 213, 231, 312, 321. - Joerg Arndt, Jul 15 2014

G.f. = 1 + x + x^2 + 3*x^3 + 16*x^4 + 125*x^5 + 1296*x^6 + 16807*x^7 + ...

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

for n to 7 do ST := [seq(seq(i, j = 1 .. n+1), i = 1 .. n)]; PST := powerset(ST);

Result[n] := nops(PST) end do; seq(Result[n], n = 1 .. 7)

# Thomas Wieder, Feb 07 2010

<< DiscreteMath`Combinatorica` Table[NumberOfSpanningTrees[CompleteGraph[n]], {n, 1, 20}] - Artur Jasinski, Dec 06 2007

Join[{1}, Table[n^(n-2), {n, 20}]] (* Harvey P. Dale, Nov 28 2012 *)

a[ n_] := If[ n < 1, Boole[n == 0], n^(n - 2)]; (* Michael Somos, May 25 2014 *)

a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ 1 - LambertW[-x] - LambertW[-x]^2 / 2, {x, 0, n}]]; (* Michael Somos, May 25 2014 *)

a[ n_] := If[ n < 1, Boole[n == 0], With[ {m = n - 1}, m! SeriesCoefficient[ Exp[ -LambertW[-x]], {x, 0, m}]]]; (* Michael Somos, May 25 2014 *)

a[ n_] := If[ n < 2, Boole[n >= 0], With[ {m = n - 1}, m! SeriesCoefficient[ InverseSeries[ Series[ Log[1 + x] / (1 + x), {x, 0, m}]], m]]]; (* Michael Somos, May 25 2014 *)

a[ n_] := If[ n < 1, Boole[n == 0], With[ {m = n - 1}, m! SeriesCoefficient[ Nest[ 1 + Integrate[ #^2 / (1 - x #), x] &, 1 + O[x], m], {x, 0, m}]]]; (* Michael Somos, May 25 2014 *)

(PARI) {a(n) = if( n<1, n==0, n^(n-2))}; /* Michael Somos, Feb 16 2002 */

(PARI) {a(n) = my(A); if( n<1, n==0, n--; A = 1 + O(x); for(k=1, n, A = 1 + intformal( A^2 / (1 - x * A))); n! * polcoeff( A, n))}; /* Michael Somos, May 25 2014 */

(MAGMA) [ n^(n-2) : n in [1..10]]; - 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 Gerry 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, May 04 2007 */

(Maxima) A000272[n]:=if n=0 then 1 else n^(n-2)$

makelist(A000272[n], n, 0, 30); /*Martin Ettl, Oct 29 2012*/

(Haskell)

a000272 0 = 1; a000272 1 = 1

a000272 n = n ^ (n - 2)  -- Reinhard Zumkeller, Jul 07 2013

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. also A097170, A083483, A239910.

Cf. A058127 where a(n)= A058127(n-1,n) (right edge of triangle).

Column m=1 of A105599. - Alois P. Heinz, Apr 10 2014

Cf. A081048.

Sequence in context: A000950 A245012 A000951 * A246527 A159594 A246525

Adjacent sequences:  A000269 A000270 A000271 * A000273 A000274 A000275

easy,nonn,core,nice

N. J. A. Sloane

approved