A239910 -id:A239910 - cp's OEIS frontend

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

N. J. A. Sloane

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

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

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.

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

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

a000272 0 = 1; a000272 1 = 1
a000272 n = n ^ (n - 2)  -- Reinhard Zumkeller, Jul 07 2013

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

A000272 := n -> ifelse(n=0, 1, n^(n-2)): seq(A000272(n), n = 0..20); # Peter Luschny, Jun 12 2022

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

A000272[n]:=if n=0 then 1 else n^(n-2)$
makelist(A000272[n],n,0,30); /* Martin Ettl, Oct 29 2012 */

{a(n) = if( n<1, n==0, n^(n-2))}; /* Michael Somos, Feb 16 2002 */

{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 */

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

def A000272(n): return 1 if n <= 1 else n**(n-2) # Chai Wah Wu, Feb 03 2022

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

A105599 Triangle read by rows: T(n, m) = number of forests with n nodes and m labeled trees. Also number of forests with exactly n - m edges on n labeled nodes.

Original entry on oeis.org

1, 1, 1, 3, 3, 1, 16, 15, 6, 1, 125, 110, 45, 10, 1, 1296, 1080, 435, 105, 15, 1, 16807, 13377, 5250, 1295, 210, 21, 1, 262144, 200704, 76608, 18865, 3220, 378, 28, 1, 4782969, 3542940, 1316574, 320544, 55755, 7056, 630, 36, 1, 100000000, 72000000, 26100000, 6258000, 1092105, 143325, 14070, 990, 45, 1

Offset: 1

Washington Bomfim, Apr 14 2005; revised May 19 2005

Row sums equal A001858 (number of forests of labeled trees with n nodes).
Also the Bell transform of A000272(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016
The permutohedron (convex hull of permutations on 1,...,n in R^n) has Ehrhart polynomial Sum_{k=0..n-1} T(n,n-k) t^k. - Matthieu Josuat-Vergès, Mar 31 2018

			T(3, 2) = 3 because there are 3 such forests with 3 nodes and 2 trees.
Triangle begins:
      1;
      1,     1;
      3,     3,    1;
     16,    15,    6,    1;
    125,   110,   45,   10,   1;
   1296,  1080,  435,  105,  15,  1;
  16807, 13377, 5250, 1295, 210, 21, 1;

B. Bollobas, Graph Theory - An Introductory Course (Springer-Verlag, New York, 1979)

Alois P. Heinz, Rows n = 1..141, flattened
E. Britikov, Asymptotic number of forests from unrooted trees, Mat. Zametki (1988).
Mathoverflow, Is there a formula for the number of labeled forests with k components on n vertices?

Cf. A033185, A106240.
Rows reflected give A138464. - Alois P. Heinz, Sep 10 2008
Columns k=1-10 give: A000272, A083483, A239910, A240681, A240682, A240683, A240684, A240685, A240686, A240687.
T(2n,n) gives A302112.

Flat(List([1..11],n->List([1..n],m->(1/Factorial(m)*Sum([0..m],j->(-1/2)^j*Binomial(m,j)*Binomial(n-1,m+j-1)*n^(n-m-j)*Factorial(m+j)))))); # Muniru A Asiru, Apr 01 2018

T:= proc(n,m) option remember;
      if n<0 then 0
    elif n=m then 1
    elif m<1 or m>n then 0
    else add(binomial(n-1,j-1)*j^(j-2)*T(n-j,m-1), j=1..n-m+1)
      fi
    end:
seq(seq(T(n, m), m=1..n), n=1..12); # Alois P. Heinz, Sep 10 2008
# The function BellMatrix is defined in A264428.
# Adds (1,0,0,0, ..) as column 0.
BellMatrix(n -> (n+1)^(n-1), 9); # Peter Luschny, Jan 27 2016

f[list_]:=Select[list,#>0&];Flatten[Map[f, Transpose[Table[t = Sum[n^(n - 2) x^n/n!, {n, 1, 20}];Drop[Range[0, 8]! CoefficientList[Series[t^k/k!, {x, 0, 8}], x],1], {k, 1, 8}]]]] (* Geoffrey Critzer, Nov 22 2011 *)
T[n_, m_] := Sum[(-1/2)^j*Binomial[m, j]*Binomial[n-1, m+j-1]*n^(n-m-j)*(m + j)!, {j, 0, m}]/m!; Table[T[n, m], {n, 1, 10}, {m, 1, n}] // Flatten (* Jean-François Alcover, Jan 09 2016, after Max Alekseyev *)
rows = 10;
t = Table[(n+1)^(n-1), {n, 0, rows}];
T[n_, k_] := BellY[n, k, t];
Table[T[n, k], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 22 2018, after Peter Luschny *)

{ T(n,m) = sum(j=0,m, (-1/2)^j * binomial(m,j) * binomial(n-1,m+j-1) * n^(n-m-j)* (m+j)! )/m! } /* Max Alekseyev, Oct 08 2014 */

T(n,m) = Sum_{k=1..n-m+1} binomial(n-1,k-1)*k^(k-2)*T(n-k,m-1), T(n,0) = 0 if n > 0, T(0,0) = 1. - Vladeta Jovovic and Washington Bomfim
The value of T(n, m) can be calculated by the formula in Bollobas, pp. 172, exercise 44. Also T(n, m) = sum N/D over the partitions of n, 1*K(1) + 2*K(2) + ... + n*K(n), with exactly m parts, where N = n! * Product_{i = 1..n} i^( (i-2) * K(i) ) and D = Product_{i = 1..n} ( K(i)! * (i!)^K(i) ).
From Peter Bala, Aug 14 2012: (Start)
E.g.f.: A(x,t) := exp(t*F(x)) = 1 + t*x + (t + t^2)*x^2/2! + (3*t + 3*t^2 + t^3)*x^3/3! + ..., where F(x) = sum {n >= 1} n^(n-2)*x^n/n! is the e.g.f. for labeled trees (see A000272). The row polynomials R(n,t) are thus a sequence of binomial type polynomials.
Differentiating A(x,t) w.r.t. x yields A'(x,t) = t*A(x,t)*F'(x) leading to the recurrence equation for the row polynomials R(n,t) = t*sum {k = 0..n-1} (k+1)^(k-1)*binomial(n-1,k)*R(n-k-1,t) with R(0,t) = 1 and R(1,t) = t: the above recurrence for the table entries follows from this.
(End)
T(n,m) = (1/m!) * Sum_{j=0..m} (-1/2)^j * binomial(m,j) * binomial(n-1,m+j-1) * n^(n-m-j)* (m+j)!. Due to A. Renyi. - Max Alekseyev, Oct 08 2014
T(n,m) = (n!/m!)*Sum_{k_1+...+k_m=n, k_i>=1} Product_{j=1..m} k_j^(k_j-2)/k_j!. See Britikov reference. - Roland Vincze, Apr 18 2020

A138464 Triangle read by rows: T(n, k) is the number of forests on n labeled nodes with k edges. T(n, k) for n >= 1 and 0 <= k <= n-1.

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 1, 6, 15, 16, 1, 10, 45, 110, 125, 1, 15, 105, 435, 1080, 1296, 1, 21, 210, 1295, 5250, 13377, 16807, 1, 28, 378, 3220, 18865, 76608, 200704, 262144, 1, 36, 630, 7056, 55755, 320544, 1316574, 3542940, 4782969, 1, 45, 990, 14070, 143325, 1092105, 6258000, 26100000, 72000000, 100000000

Offset: 1

N. J. A. Sloane, May 09 2008

The rows of the triangle give the coefficients of the Ehrhart polynomials of integral Coxeter permutahedra of type A. These polynomials count lattice points in a dilated lattice polytope. For a definition see Ardila et al. (p. 1158), the generating functions of these polynomials for the classical root systems are given in theorem 5.2 (p. 1163). - Peter Luschny, May 01 2021

			Triangle begins:
[1]  1;
[2]  1,  1;
[3]  1,  3,   3;
[4]  1,  6,  15,   16;
[5]  1, 10,  45,  110,  125;
[6]  1, 15, 105,  435, 1080,  1296;
[7]  1, 21, 210, 1295, 5250, 13377, 16807;

Alois P. Heinz, Rows n = 1..141, flattened
Federico Ardila, Matthias Beck, and Jodi McWhirter, The arithmetic of Coxeter permutahedra, Rev. Acad. Colomb. Cienc. Ex. Fis. Nat. 44(173):1152-1166, 2020.
John Riordan and N. J. A. Sloane, Correspondence, 1974

Row sums give A001858. Rightmost diagonal gives A000272. Cf. A136605.
Rows reflected give A105599. - Alois P. Heinz, Oct 28 2011
Cf. A088956.
Lower diagonals give: A083483, A239910, A240681, A240682, A240683, A240684, A240685, A240686, A240687. - Alois P. Heinz, Apr 11 2014
T(2n,n) gives A302112.
For Ehrhart polynomials of integral Coxeter permutahedra of classical type cf. this sequence (type A), A343805 (type B), A343806 (type C), A343807 (type D).

T:= proc(n) option remember; if n=0 then 0 else T(n-1) +n^(n-1) *x^n/n! fi end: TT:= proc(n) option remember; expand(T(n) -T(n)^2/2) end: f:= proc(k) option remember; if k=0 then 1 else unapply(f(k-1)(x) +x^k/k!, x) fi end: A:= proc(n,k) option remember; series(f(k)(TT(n)), x,n+1) end: aa:= (n,k)-> coeff(A(n,k), x,n) *n!: a:= (n,k)-> aa(n,n-k) -aa(n,n-k-1): seq(seq(a(n,k), k=0..n-1), n=1..10);  # Alois P. Heinz, Sep 02 2008
alias(W = LambertW): EhrA := exp(-W(-t*x)/t - W(-t*x)^2/(2*t)):
ser := series(EhrA, x, 12): cx := n -> n!*coeff(ser, x, n):
T := n -> seq(coeff(cx(n), t, k), k=0..n-1):
seq(T(n), n = 1..10); # Peter Luschny, Apr 30 2021

t[0, 0] = 1; t[n_ /; n >= 1, k_] /; (0 <= k <= n-1) := t[n, k] = Sum[(i+1)^(i-1)*Binomial[n-1, i]*t[n-i-1, k-i], {i, 0, k}]; t[, ] = 0; Table[t[n, k], {n, 1, 10}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Jan 14 2014, after Peter Bala *)
gf := E^(-(ProductLog[-(t x)] (2 + ProductLog[-(t x)]))/(2 t));
ser := Series[gf, {x, 0, 12}]; cx[n_] := n! Coefficient[ser, x, n];
Table[CoefficientList[cx[n], t], {n, 1, 10}] // Flatten  (* Peter Luschny, May 01 2021 *)

From Peter Bala, Aug 14 2012: (Start)
T(n+1,k) = Sum_{i=0..k} (i+1)^(i-1)*binomial(n,i)*T(n-i,k-i) with T(0,0)=1.
Recurrence equation for row polynomials R(n,t): R(n,t) = Sum_{k=0..n-1} (k+1)^(k-1)*binomial(n-1,k)*t^k*R(n-k-1,t) with R(0,t) = R(1,t) = 1.
The production matrix for the row polynomials of the triangle is obtained from A088956 and starts:
    1    t
    1    1    t
    3    2    1    t
   16    9    3    1    t
  125   64   18    4    1   t
(End)
E.g.f.: exp( Sum_{n >= 1} n^(n-2)*t^(n-1)*x^n/n! ). - Peter Bala, Nov 08 2015
T(n, k) = [t^k] n! [x^n] exp(-W(-t*x)/t - W(-t*x)^2/(2*t)), where W denotes the Lambert function. - Peter Luschny, Apr 30 2021 [Typo corrected after note from Andrew Howroyd, Peter Luschny, Jun 20 2021]

More terms from Alois P. Heinz, Sep 02 2008

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI

PARI

Python

Formula

A105599 Triangle read by rows: T(n, m) = number of forests with n nodes and m labeled trees. Also number of forests with exactly n - m edges on n labeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Formula

A138464 Triangle read by rows: T(n, k) is the number of forests on n labeled nodes with k edges. T(n, k) for n >= 1 and 0 <= k <= n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A083483 Number of forests with two connected components in the complete graph K_{n}.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions