A000272 Number of trees on n labeled nodes: n^(n-2) with a(0)=1.
1, 1, 1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000, 2357947691, 61917364224, 1792160394037, 56693912375296, 1946195068359375, 72057594037927936, 2862423051509815793, 121439531096594251776, 5480386857784802185939, 262144000000000000000000, 13248496640331026125580781
Offset: 0
Examples
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 + ...
References
- M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 1999; see p. 142.
- Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups. Graduate Texts in Mathematics, 231. Springer, New York, 2005.
- Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 311.
- J. Dénes, The representation of a permutation as the product of a minimal number of transpositions and its connection with the theory of graphs, 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. Harary, J. A. Kabell, and F. R. McMorris (1992), Subtree acyclic digraphs, Ars Comb., vol. 34:93-95.
- 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)
- H. Prüfer, Neuer Beweis eines Satzes über Permutationen, Archiv der Mathematik und Physik, (3) 27 (1918), 142-144.
- 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.
- J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge Univ. Press, 1992.
Links
- Seiichi Manyama, Table of n, a(n) for n = 0..388 (terms 0..100 from N. J. A. Sloane)
- Federico Ardila, Matthias Beck, and Jodi McWhirter, The Arithmetic of Coxeter Permutahedra, arXiv:2004.02952 [math.CO], 2020.
- M. D. Atkinson and R. Beals, Priority queues and permutations, SIAM J. Comput. 23 (1994), 1225-1230.
- M. Beck, A. Berrizbeitia, M. Dairyko, C. Rodriguez, A. Ruiz, and S. Veeneman., Parking functions, Shi arrangements, and mixed graphs, Amer. Math. Monthly, 122 (2015), 660-673.
- Norman L. Biggs, Chip-firing and the critical group of a graph, J. Algeb. Combin., 9 (1999), 25-45.
- Norman L. Biggs, E. Keith Lloyd, and Robin J. Wilson, Graph Theory 1736-1936, Oxford, 1976, p. 51.
- Richard P. Brent, M. L. Glasser, and Anthony J. Guttmann, A Conjectured Integer Sequence Arising From the Exponential Integral, arXiv:1812.00316 [math.NT], 2018.
- Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
- 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 Dec 17 2015.
- Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002. [Archived copy]
- Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.
- Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002 [Local copy, with permission]
- Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions. [Broken link]
- R. Castelo and A. Siebes, A characterization of moral transitive directed acyclic graph Markov models as labeled trees, 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.
- A. Cayley, A theorem on trees, Quart. J. Pure and Applied Math., 23 (1889), 376-378.
- Jacob W. Cooper, Adam Kabela, Daniel Král', and Théo Pierron, Hadwiger meets Cayley, arXiv:2005.05989 [math.CO], 2020.
- 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, Labelled 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.
- Vsevolod Gubarev, Rota-Baxter operators on a sum of fields, arXiv:1811.08219 [math.RA], 2018.
- F. A. Haight, Overflow at a traffic light, Biometrika, 46 (1959), 420-424. (Annotated scanned copy)
- F. A. Haight, Letter to N. J. A. Sloane, n.d.
- A. M. Hamel, Priority queue sorting and labeled trees, Annals Combin., 7 (2003), 49-54.
- Angela Hicks, Combinatorics of the Diagonal Harmonics, in Recent Trends in Algebraic Combinatorics, part of the Association for Women in Mathematics Series (2019) Vol 16. Springer, Cham, 159-188.
- INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 78 [Dead link]
- D. M. Jackson, Some Combinatorial Problems Associated with Products of Conjugacy Classes of the Symmetric Group, Journal of Combinatorial Theory, Series A, 49 363-369(1988).
- S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.
- C. Ji and J. Propp, Brussels Sprouts, Noncrossing Trees, and Parking Functions, arXiv preprint arXiv:1805.03608 [math.CO], 2018.
- L. Kalikow, Symmetries in trees and parking functions, Discrete Math., 256 (2002), 719-741.
- C. Lamathe, The Number of Labelled 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 A. A. Obaid, S. Khalid Nauman, Wafa S. Al Shammakh, Wafaa M. Fakieh, and Claus Michael Ringel, 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 and 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 acyclic maps.]
- Alok Shukla, A short proof of Cayley's tree formula, Amer. Math. Monthly, 125 (2018), 65-68.
- Stefano Spezia, A determinantal formula for the number of trees on n labeled nodes, 2023.
- R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68.
- Dennis Walsh, Notes on acyclic functions and their directed graphs [Archived copy]
- 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, The n^(n-2)-th Proof Of The Formula For The Number Of Labeled Trees [Local copy]
- D. Zeilberger, Yet Another Proof For The Enumeration Of Labeled Trees
- D. Zeilberger, Yet Another Proof For The Enumeration Of Labeled Trees [Local copy]
- D. Zvonkine, 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, arXiv:math/0403092 [math.AG], 2004.
- D. Zvonkine, Home Page [Dead link]
- Index entries for sequences related to trees
- Index entries for "core" sequences
Crossrefs
Cf. 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
Programs
-
Haskell
a000272 0 = 1; a000272 1 = 1 a000272 n = n ^ (n - 2) -- Reinhard Zumkeller, Jul 07 2013
-
Magma
[ n^(n-2) : n in [1..10]]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
-
Maple
A000272 := n -> ifelse(n=0, 1, n^(n-2)): seq(A000272(n), n = 0..20); # Peter Luschny, Jun 12 2022
-
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 *) -
Maxima
A000272[n]:=if n=0 then 1 else n^(n-2)$ makelist(A000272[n],n,0,30); /* Martin Ettl, Oct 29 2012 */
-
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 */ -
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 */
-
Python
def A000272(n): return 1 if n <= 1 else n**(n-2) # Chai Wah Wu, Feb 03 2022
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). [Equals d/dx (W(-x)/(-x)). - Wolfdieter Lang, Oct 25 2022]
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
For n >= 3 and 2 <= k <= n-1, the number of trees on n vertices with exactly k leaves is binomial(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} binomial(n,k)*S(n-2,n-k)(n-k)! for n >= 3. - Jonathan Noel, May 05 2017
Comments