login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000272 Number of trees on n labeled nodes: n^(n-2) with a(0)=1.
(Formerly M3027 N1227)
161
1, 1, 1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000, 2357947691, 61917364224, 1792160394037, 56693912375296, 1946195068359375, 72057594037927936, 2862423051509815793, 121439531096594251776, 5480386857784802185939 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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

For n>2, a(n+2) is the number of nodes in the canonical automaton for the affine Weyl group of type A_n. - Tom Edgar, May 12 2016

REFERENCES

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

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

Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups. Graduate Texts in Mathematics, 231. Springer, New York, 2005.

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.

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

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

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.

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.

LINKS

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

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.

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

Peter Cameron's Blog, Cycles and trees, Posted 17/12/2015.

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.

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.

S. Coulomb and M. Bauer, On vertex covers, matchings and random trees, arXiv:math/0407456 [math.CO], 2004.

FindStat - Combinatorial Statistic Finder, Parking functions

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

Suresh Govindarajan, Notes on higher-dimensional partitions, arXiv preprint arXiv:1203.4419 [math.CO], 2012.

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

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 78

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.

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

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

C. J. Liu and Yutze Chow, 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, Polynomial Equations of Degree n, arXiv:math/0605183 [math.GM], 2006.

G. Martens, On Algebraic Solutions of Polynomial Equations of Degree n in one Variable, GH Consulting EPI-01-06 preprint, arXiv:math/0605183 [math.GM], 2006.

Mustafa Obaid et al., The number of complete exceptional sequences for a Dynkin algebra, arXiv preprint arXiv:1307.7573 [math.RT], 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 [math.CO], 2014.

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

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

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

Dennis Walsh, Notes on acyclic functions and their directed graphs

Eric Weisstein's World of Mathematics, Complete Graph, Labeled Tree, and 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..., arXiv:math/0403092 [math.AG], 2004.

D. Zvonkine, Home Page

Index entries for sequences related to trees

Index entries for "core" sequences

FORMULA

E.g.f.: 1 + T - (1/2)T^2; where T=T(x) is Euler's tree function (see A000169, also A001858). - Len Smiley, 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=1..n} i * n^(n-1-i) * binomial(n, i). - Yong Kong (ykong(AT)curagen.com), Dec 28 2000

For n>=1, a(n+1)= Sum_{i=1..n} n^(n-i)*binomial(n-1,i-1). - 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).

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

Related to A000254 by Sum_{n >= 1} a(n+1)*x^n/n! = series reversion( 1/(1 + x)*log(1 + x) ) = series reversion(x - 3*x^2/2! + 11*x^3/3! - 50*x^4/4! + ...). Cf. A052750. - Peter Bala, Jun 15 2016

EXAMPLE

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

MAPLE

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

MATHEMATICA

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

PROG

(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

CROSSREFS

Cf. A000055, A000169, A000254, A000312, A007778, A007830, A008785-A008791, A052750, A081048, A083483, A097170, A239910.

a(n)= A033842(n-1, 0) (first column of triangle).

a(n)= A058127(n-1, n) (right edge 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).

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

Sequence in context: A000950 A245012 A000951 * A246527 A159594 A246525

Adjacent sequences:  A000269 A000270 A000271 * A000273 A000274 A000275

KEYWORD

easy,nonn,core,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified December 9 14:38 EST 2016. Contains 278971 sequences.