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

 

Logo


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

%I M3027 N1227

%S 1,1,1,3,16,125,1296,16807,262144,4782969,100000000,2357947691,

%T 61917364224,1792160394037,56693912375296,1946195068359375,

%U 72057594037927936,2862423051509815793,121439531096594251776,5480386857784802185939

%N Number of trees on n labeled nodes: n^(n-2) with a(0)=1.

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

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

%C 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

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

%C 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

%C 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

%C 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

%C a(n) is also the number of edge-labeled rooted trees on n nodes. - _Nikos Apostolakis_, Nov 30 2008

%C 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

%C 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

%C 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

%C 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

%C The tree formula a(n) = n^(n-2) is due to Cayley (see the first comment). - _Jonathan Sondow_, Jan 11 2018

%C a(n) is the number of topologically distinct lines of play for the game Planted Brussels Sprouts on n vertices. See Ji and Propp link. - _Caleb Ji_, May 11 2018

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

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

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

%D A. Cayley, A theorem on trees, Quart. J. Pure and Applied Math., 23 (1889), 376-378.

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

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

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

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

%D 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)

%D H. Pruefer, Neuer Beweis eines Satzes ueber Permutationen, Archiv der Mathematik und Physik, (3) 27 (1918), 142-144.

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

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

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

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

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

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

%H Seiichi Manyama, <a href="/A000272/b000272.txt">Table of n, a(n) for n = 0..388</a> (terms 0..100 from N. J. A. Sloane)

%H M. D. Atkinson and R. Beals, <a href="http://dx.doi.org/10.1137/S0097539792240893">Priority queues and permutations</a>, SIAM J. Comput. 23 (1994), 1225-1230.

%H M. Beck et al., <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.122.7.660">Parking functions, Shi arrangements, and mixed graphs</a>, Amer. Math. Monthly, 122 (2015), 660-673.

%H N. L. Biggs, <a href="https://doi.org/10.1023/A:1018611014097">Chip-firing and the critical group of a graph</a>, J. Algeb. Combin., 9 (1999), 25-45.

%H David Callan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Callan/callan10.html">A Combinatorial Derivation of the Number of Labeled Forests</a>, J. Integer Seqs., Vol. 6, 2003.

%H Saverio Caminiti and Emanuele G. Fusco, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Caminiti/caminiti.html">On the Number of Labeled k-arch Graphs</a>, Journal of Integer Sequences, Vol 10 (2007), Article 07.7.5

%H Peter Cameron's Blog, <a href="https://cameroncounts.wordpress.com/2015/12/17/cycles-and-trees/">Cycles and trees</a>, Posted 17/12/2015.

%H Huantian Cao, <a href="http://www.cs.uga.edu/~rwr/STUDENTS/hcao.html">AutoGF</a>: An Automated System to Calculate Coefficients of Generating Functions.

%H R. Castelo and A. Siebes, <a href="http://ftp.cs.uu.nl:/pub/RUU/CS/techreps/CS-2000/2000-44.ps.gz">A characterization of moral transitive directed acyclic graph ...</a>, Report CS-2000-44, Department of Computer Science, Univ. Utrecht.

%H R. Castelo and A. Siebes, <a href="http://dx.doi.org/10.1016/S0378-3758(02)00143-X">A characterization of moral transitive acyclic directed graph Markov models as labeled trees</a>, J. Statist. Planning Inference, 115(1):235-259, 2003.

%H S. Coulomb and M. Bauer, <a href="http://arXiv.org/abs/math.CO/0407456">On vertex covers, matchings and random trees</a>, arXiv:math/0407456 [math.CO], 2004.

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/ParkingFunctions">Parking functions</a>

%H J. Gilbey and L. Kalikow, <a href="http://dx.doi.org/10.1016/S0012-365X(99)90085-7">Parking functions, valet functions and priority queues</a>, Discrete Math., 197 (1999), 351-375.

%H M. Golin and S. Zaks, <a href="http://dx.doi.org/10.1016/S0304-3975(97)00037-6">Labeled trees and pairs of input-output permutations in priority queues</a>, Theoret. Comput. Sci., 205 (1998), 99-114.

%H I. P. Goulden and S. Pepper, <a href="http://dx.doi.org/10.1016/0012-365X(93)90522-U">Labeled trees and factorizations of a cycle into transpositions</a>, Discrete Math., 113 (1993), 263-268.

%H I. P. Goulden and A. Yong, <a href="http://dx.doi.org/10.1006/jcta.2001.3230">Tree-like properties of cycle factorizations</a>, J. Combin. Theory, A 98 (2002), 106-117.

%H Suresh Govindarajan, <a href="http://arxiv.org/abs/1203.4419">Notes on higher-dimensional partitions</a>, arXiv preprint arXiv:1203.4419 [math.CO], 2012.

%H F. A. Haight, <a href="/A001787/a001787_3.pdf">Overflow at a traffic light</a>, Biometrika, 46 (1959), 420-424. (Annotated scanned copy)

%H F. A. Haight, <a href="/A001787/a001787_2.pdf">Letter to N. J. A. Sloane, n.d.</a>

%H A. M. Hamel, <a href="http://dx.doi.org/10.1007/s000260300004">Priority queue sorting and labeled trees</a>, Annals Combin., 7 (2003), 49-54.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=78">Encyclopedia of Combinatorial Structures 78</a>

%H D. M. Jackson, <a href="http://dx.doi.org/10.1016/0097-3165(88)90062-3">Some Combinatorial Problems Associated with Products of Conjugacy Classes of the Symmetric Group</a>, Journal of Combinatorial Theory, Seies A, 49 363-369(1988).

%H S. Janson, D. E. Knuth, T. Luczak and B. Pittel, <a href="http://dx.doi.org/10.1002/rsa.3240040303">The Birth of the Giant Component</a>, Random Structures and Algorithms Vol. 4 (1993), 233-358.

%H C. Ji, J. Propp, <a href="https://arxiv.org/abs/1805.03608">Brussels Sprouts, Noncrossing Trees, and Parking Functions</a>, arXiv preprint arXiv:1805.03608 [math.CO], 2018.

%H L. Kalikow, <a href="http://dx.doi.org/10.1016/S0012-365X(02)00344-8">Symmetries in trees and parking functions</a>, Discrete Math., 256 (2002), 719-741.

%H C. Lamathe, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Lamathe/lamathe2.html">The Number of Labeled k-Arch Graphs</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.1.

%H A. Laradji and A. Umar, <a href="http://dx.doi.org/10.1081/AGB-120038637">On the number of nilpotents in the partial symmetric semigroup</a>, Comm. Algebra 32 (2004), 3017-3023. From _Abdullahi Umar_, Aug 25 2008

%H C. J. Liu and Yutze Chow, <a href="http://dx.doi.org/10.1137/0605038">On operator and formal sum methods for graph enumeration problems</a>, 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

%H G. Martens, <a href="http://arXiv.org/abs/math/0605183">Polynomial Equations of Degree n</a>, arXiv:math/0605183 [math.GM], 2006.

%H G. Martens, <a href="https://arxiv.org/abs/math/0605183">On Algebraic Solutions of Polynomial Equations of Degree n in one Variable</a>, GH Consulting EPI-01-06 preprint, arXiv:math/0605183 [math.GM], 2006.

%H Mustafa Obaid et al., <a href="http://arxiv.org/abs/1307.7573">The number of complete exceptional sequences for a Dynkin algebra</a>, arXiv preprint arXiv:1307.7573 [math.RT], 2013.

%H J. Pitman, <a href="http://www.stat.berkeley.edu/users/pitman/457.pdf">Coalescent Random Forests</a>, J. Combin. Theory, A85 (1999), 165-193.

%H J.-B. Priez, A. Virmaux, <a href="http://arxiv.org/abs/1411.4161">Non-commutative Frobenius characteristic of generalized parking functions: Application to enumeration</a>, arXiv preprint arXiv:1411.4161 [math.CO], 2014.

%H S. Ramanujan, <a href="http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/question/q738.htm">Question 738</a>, J. Ind. Math. Soc.

%H J. Riordan, <a href="http://dx.doi.org/10.1016/S0021-9800(68)80033-X">Forests of labeled trees</a>, J. Combin. Theory, 5 (1968), 90-103. See Table 1.

%H M. P. Schützenberger, <a href="http://dx.doi.org/10.1016/S0021-9800(68)80003-1">On an Enumeration Problem</a>, Journal of Combinatorial Theory 4, 219-221 (1968). [A 1-1 correspondence between maps under permutations and acyclics maps.]

%H Alok Shukla, <a href="https://doi.org/10.1080/00029890.2018.1392750">A short proof of Cayley's tree formula</a>, Amer. Math. Monthly, 125 (2018), 65-68.

%H Dennis Walsh, <a href="http://frank.mtsu.edu/~dwalsh/acyclic/acycnote.html">Notes on acyclic functions and their directed graphs</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CompleteGraph.html">Complete Graph</a>, <a href="http://mathworld.wolfram.com/LabeledTree.html">Labeled Tree</a>, and <a href="http://mathworld.wolfram.com/SpanningTree.html">Spanning Tree</a>

%H D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/labtree.pdf">The n^(n-2)-th Proof Of The Formula For The Number Of Labeled Trees</a>

%H D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/cayley.pdf">Yet Another Proof For The Enumeration Of Labeled Trees</a>

%H D. Zvonkine, <a href="http://www.arXiv.org/abs/math.AG/0403092">An algebra of power series...</a>, arXiv:math/0403092 [math.AG], 2004.

%H D. Zvonkine, <a href="http://www.math.jussieu.fr/~zvonkine/">Home Page</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%F 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

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

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

%F 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

%F a(n+1) = Sum_{i=1..n} i * n^(n-1-i) * binomial(n, i). - Yong Kong (ykong(AT)curagen.com), Dec 28 2000

%F For n>=1, a(n+1)= Sum_{i=1..n} n^(n-i)*binomial(n-1,i-1). - _Geoffrey Critzer_, Jul 20 2009

%F 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

%F From _Sergei N. Gladkovskii_, Sep 18 2012: (Start)

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

%F 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)

%F 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

%F For n>=3 and 2<=k<=n-1, the number of trees on n vertices with exactly k leaves is binom(n,k)S(n-2,n-k)(n-k)! where S(a,b) is the Stirling number of the second kind. Therefore a(n) = Sum_{k=2}^{n-1}binom(n,k)S(n-2,n-k)(n-k)! for n>=3. - _Jonathan Noel_, May 05 2017

%e 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

%e 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)}.

%e From _Joerg Arndt_ and Greg Stevenson, Jul 11 2011: (Start)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

%e 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

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

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

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

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

%p # _Thomas Wieder_, Feb 07 2010

%t << DiscreteMath`Combinatorica` Table[NumberOfSpanningTrees[CompleteGraph[n]], {n, 1, 20}] (* _Artur Jasinski_, Dec 06 2007 *)

%t Join[{1},Table[n^(n-2),{n,20}]] (* _Harvey P. Dale_, Nov 28 2012 *)

%t a[ n_] := If[ n < 1, Boole[n == 0], n^(n - 2)]; (* _Michael Somos_, May 25 2014 *)

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

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

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

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

%o (PARI) {a(n) = if( n<1, n==0, n^(n-2))}; /* _Michael Somos_, Feb 16 2002 */

%o (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 */

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

%o (PARI) /* GP Function for Determinant of Hermitian (square symmetric) matrix for univariate polynomial of degree n by _Gerry Martens_: */

%o 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 */

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

%o makelist(A000272[n],n,0,30); /*_Martin Ettl_, Oct 29 2012*/

%o (Haskell)

%o a000272 0 = 1; a000272 1 = 1

%o a000272 n = n ^ (n - 2) -- _Reinhard Zumkeller_, Jul 07 2013

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

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

%Y a(n)= A058127(n-1, n) (right edge of triangle).

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

%Y Column m=1 of A105599. - _Alois P. Heinz_, Apr 10 2014

%K easy,nonn,core,nice,changed

%O 0,4

%A _N. J. A. Sloane_

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 May 27 07:28 EDT 2018. Contains 304690 sequences. (Running on oeis4.)