|
%I M3027 N1227 #302 Aug 12 2023 00:50:38
%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) is the 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
%C a(n+1) is also the number of bases of R^n, that can be made from the n(n+1)/2 vectors of the form [0 ... 0 1 ... 1 0 ... 0]^T, where the initial or final zeros are optional, but at least one 1 has to be included. - _Nicolas Nagel_, Jul 31 2018
%C Cooper et al. show that every connected k-chromatic graph contains at least k^(k-2) spanning trees. - _Michel Marcus_, May 14 2020
%D M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 1999; see p. 142.
%D Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups. Graduate Texts in Mathematics, 231. Springer, New York, 2005.
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 311.
%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. Harary, J. A. Kabell, and F. R. McMorris (1992), Subtree acyclic digraphs, Ars Comb., vol. 34:93-95.
%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 über 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 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 Federico Ardila, Matthias Beck, and Jodi McWhirter, <a href="https://arxiv.org/abs/2004.02952">The Arithmetic of Coxeter Permutahedra</a>, arXiv:2004.02952 [math.CO], 2020.
%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 Norman 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 Norman L. Biggs, E. Keith Lloyd, and Robin J. Wilson, <a href="https://archive.org/details/graphtheory173610000bigg/page/51/mode/1up">Graph Theory 1736-1936</a>, Oxford, 1976, p. 51.
%H Richard P. Brent, M. L. Glasser, and Anthony J. Guttmann, <a href="https://arxiv.org/abs/1812.00316">A Conjectured Integer Sequence Arising From the Exponential Integral</a>, arXiv:1812.00316 [math.NT], 2018.
%H Alexander Burstein and Louis W. Shapiro, <a href="https://arxiv.org/abs/2112.11595">Pseudo-involutions in the Riordan group</a>, arXiv:2112.11595 [math.CO], 2021.
%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="https://web.archive.org/web/20100613201911/http://www.cs.uga.edu/~rwr/STUDENTS/hcao.html">AutoGF: An Automated System to Calculate Coefficients of Generating Functions</a>, thesis, 2002.o
%H Huantian Cao, <a href="http://cobweb.cs.uga.edu/~rwr/STUDENTS/hcao.html">AutoGF: An Automated System to Calculate Coefficients of Generating Functions</a>, thesis, 2002.
%H Huantian Cao, <a href="/A000009/a000009.pdf">AutoGF: An Automated System to Calculate Coefficients of Generating Functions</a>, thesis, 2002 [Local copy, with permission]
%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. [Broken link]
%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 A. Cayley, <a href="https://gdz.sub.uni-goettingen.de/id/PPN600494829_0023?tify={%22pages%22:[396],%22view%22:%22%22}">A theorem on trees</a>, Quart. J. Pure and Applied Math., 23 (1889), 376-378.
%H Jacob W. Cooper, Adam Kabela, Daniel Král', and Théo Pierron, <a href="https://arxiv.org/abs/2005.05989">Hadwiger meets Cayley</a>, arXiv:2005.05989 [math.CO], 2020.
%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 Vsevolod Gubarev, <a href="https://arxiv.org/abs/1811.08219">Rota-Baxter operators on a sum of fields</a>, arXiv:1811.08219 [math.RA], 2018.
%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 Angela Hicks, <a href="https://doi.org/10.1007/978-3-030-05141-9_5">Combinatorics of the Diagonal Harmonics</a>, in Recent Trends in Algebraic Combinatorics, part of the Association for Women in Mathematics Series (2019) Vol 16. Springer, Cham, 159-188.
%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, Series 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 and 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 and 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 Stefano Spezia, <a href="/A362679/a362679.pdf">A determinantal formula for the number of trees on n labeled nodes</a>, 2023.
%H R. P. Stanley, <a href="https://doi.org/10.1090/S0273-0979-02-00966-7">Recent Progress in Algebraic Combinatorics</a>, Bull. Amer. Math. Soc., 40 (2003), 55-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="/A000272/a000272_1.pdf">The n^(n-2)-th Proof Of The Formula For The Number Of Labeled Trees</a> [Local copy]
%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. Zeilberger, <a href="/A000272/a000272.pdf">Yet Another Proof For The Enumeration Of Labeled Trees</a> [Local copy]
%H D. Zvonkine, <a href="https://arxiv.org/abs/math/0403092">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</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). [Equals d/dx (W(-x)/(-x)). - _Wolfdieter Lang_, Oct 25 2022]
%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 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
%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 -> ifelse(n=0, 1, n^(n-2)): seq(A000272(n), n = 0..20); # _Peter Luschny_, Jun 12 2022
%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
%o (Python)
%o def A000272(n): return 1 if n <= 1 else n**(n-2) # _Chai Wah Wu_, Feb 03 2022
%Y Cf. 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
%O 0,4
%A _N. J. A. Sloane_
|
