cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

Original entry on oeis.org

1, 1, 1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000, 2357947691, 61917364224, 1792160394037, 56693912375296, 1946195068359375, 72057594037927936, 2862423051509815793, 121439531096594251776, 5480386857784802185939, 262144000000000000000000, 13248496640331026125580781
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of spanning trees in complete graph K_n on n labeled nodes.
Robert Castelo, 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) 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
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(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
The tree formula a(n) = n^(n-2) is due to Cayley (see the first comment). - Jonathan Sondow, Jan 11 2018
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
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
Cooper et al. show that every connected k-chromatic graph contains at least k^(k-2) spanning trees. - Michel Marcus, May 14 2020

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

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.