This site is supported by donations to The OEIS Foundation.

 Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS". Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A061356 Triangle T(n,k) = labeled trees on n nodes with maximal node degree k (0 < k < n). 12
 1, 2, 1, 9, 6, 1, 64, 48, 12, 1, 625, 500, 150, 20, 1, 7776, 6480, 2160, 360, 30, 1, 117649, 100842, 36015, 6860, 735, 42, 1, 2097152, 1835008, 688128, 143360, 17920, 1344, 56, 1, 43046721, 38263752, 14880348, 3306744, 459270, 40824, 2268, 72, 1 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 2,2 COMMENTS This is a formula from Theorem F, vol. I, p. 81 (French edition) used in proving Theorem D. If we let N = n+1, binomial(N-2, k-1)*(N-1)^(N-k-1) = binomial(n-1, k-1)*n^(n-k), so this sequence with offset 1,1 also gives the number of rooted forests of k trees over [n]. - Washington Bomfim, Jan 09 2008 Let S(n,k) be the signed triangle, S(n,k) = (-1)^(n-k)T(n,k), which starts 1, -2, 1, 9, -6, 1,..., then the inverse of S is the triangle of idempotent numbers A059298. - Peter Luschny, Mar 13 2009 With offset 1 also number of labeled multigraphs of k components, n nodes, and no cycles except one loop in each component. See link below to have a picture showing the bijection between rooted forests and multigraphs of this kind. (Note that there are no labels in the picture, but the bijection remains true if we label the nodes.) - Washington Bomfim, Sep 04 2010 With offset 1, T(n,k) is the number of forests of rooted trees on n nodes with exactly k (rooted) trees. - Geoffrey Critzer, Feb 10 2012 Also the Bell transform of the sequence (n+1)^n (A000169(n+1)) without column 0. For the definition of the Bell transform see A264428.  - Peter Luschny, Jan 21 2016 REFERENCES L. Comtet, Analyse Combinatoire, P.U.F., Paris 1970. Volume 1, p 81. L. Comtet, Advanced Combinatorics, Reidel, 1974. LINKS G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened A. Avron, N. Dershowitz, Cayley's Formula, A Page From The Book, Amer. Math. Monthly, Vol. 123, No. 7, Aug.-Sep. 2016, 699-700 (2) W. Bomfim, Bijection between rooted forests and multigraphs without cycles except one loop in each connected component. [From Washington Bomfim, Sep 04 2010] J. W. Moon, Another proof of Cayley's formula for counting trees, Amer. Math. Monthly, Vol. 70, No. 8, Oct. 1963, 846-847 Jim Pitman, Coalescent Random Forests . E. W. Weisstein, Abel Polynomial, From MathWorld - A Wolfram Web Resource. Wikipedia, Lambert W function J. Zeng, A Ramanujan sequence that refines the Cayley formula for trees, Ramanujan J., 3(1999) 1, 45-54. FORMULA T(n, k) = binomial(n-2, k-1)*(n-1)^(n-k-1). E.g.f.: (-LambertW(-y)/y)^(x+1)/(1+LambertW(-y)). - Vladeta Jovovic From Peter Bala, Sep 21 2012: (Start) Let T(x) = Sum_{n >= 0} n^(n-1)*x^n/n! denote the tree function of A000169. E.g.f.: F(x,t) := exp(t*T(x)) - 1 = -1 + {T(x)/x}^t = t*x + t*(2 + t)*x^2/2! + t*(9 + 6*t + t^2)*x^3/3! + .... The compositional inverse with respect to x of (1/t)*F(x,t) is the e.g.f. for a signed version of the row reverse of A028421. The row generating polynomials are the Abel polynomials A(n,x) = x*(x+n)^(n-1) for n >= 1. Define B(n,x) = x^n/(1+n*x)^(n+1) = (-1)^n*A(-n,-1/x) for n >= 1. The k-th column entries are the coefficients in the formal series expansion of x^k in terms of B(n,x). For example, Col. 1: x = B(1,x) + 2*B(2,x) + 9*B(3,x) + 64*B(4,x) + ..., Col. 2: x^2 = B(2,x) + 6*B(3,x) + 48*B(4,x) + 500*B(5,x) + ... Compare with A059297. n-th row sum = A000272(n+1). Row reverse triangle is A139526. The o.g.f.'s for the diagonals of the triangle are the rational functions R(n,x)/(1-x)^(2*n+1), where R(n,x) are the row polynomials of A155163. See below for examples. (End) T(n,m) = C(n,m)*Sum_{k=1..n-m} m^k*T(n-m,k), T(n,n) = 1. - Vladimir Kruchinin, Mar 31 2015 EXAMPLE :    1; :    2,     1; :    9,     6,     1; :   64,    48,    12,    1; :  625,   500,   150,   20,    1; : 7776,  6480,  2160,  360,   30,    1; ... From Peter Bala, Sep 21 2012: (Start) O.g.f.'s for the diagonals begin: 1/(1-x) = 1 + x + x^2 + x^3 + ... 2*x/(1-x)^3 = 2 + 6*x + 12*x^3 + ... (9+3*x)/(1-x)^5 = 9 + 48*x + 150*x^2 + ... The numerator polynomials are the row polynomials of A155163. (End) MAPLE # The function BellMatrix is defined in A264428. # Adds (1, 0, 0, 0, ...) as column 0 to the triangle. BellMatrix(n -> (n+1)^n, 12); # Peter Luschny, Jan 21 2016 MATHEMATICA nn = 7; t = Sum[n^(n - 1)  x^n/n!, {n, 1, nn}]; f[list_] := Select[list, # > 0 &]; Map[f, Drop[Range[0, nn]! CoefficientList[Series[Exp[y t], {x, 0, nn}], {x, y}], 1]] // Flatten  (* Geoffrey Critzer, Feb 10 2012 *) T[n_, m_] := T[n, m] = Binomial[n, m]*Sum[m^k*T[n-m, k], {k, 1, n-m}]; T[n_, n_] = 1; Table[T[n, m], {n, 1, 9}, {m, 1, n}] // Flatten (* Jean-François Alcover, Mar 31 2015, after Vladimir Kruchinin *) Table[Binomial[n - 2, k - 1]*(n - 1)^(n - k - 1), {n, 2, 12}, {k, 1, n - 1}] // Flatten (* G. C. Greubel, Nov 12 2017 *) PROG (Maxima) create_list(binomial(n, k)*(n+1)^(n-k), n, 0, 20, k, 0, n); /* Emanuele Munarini, Apr 01 2014 */ (Sage) # The function bell_matrix is defined in A264428. # Adds (1, 0, 0, 0, ...) as column 0 to the triangle. bell_matrix(lambda n: (n+1)^n, 12) # Peter Luschny, Jan 21 2016 (PARI) for(n=2, 11, for(k=1, n-1, print1(binomial(n-2, k-1)*(n-1)^(n-k-1), ", "))) \\ G. C. Greubel, Nov 12 2017 CROSSREFS Columns are A000169, A053506, A053507, A053508, A053509. First diagonal is A002378. Sum of lines gives A000272. Cf. A028421, A059297, A139526 (row reverse), A155163, A202017. Sequence in context: A141618 A061691 A235595 * A141028 A246323 A201685 Adjacent sequences:  A061353 A061354 A061355 * A061357 A061358 A061359 KEYWORD easy,nonn,tabl AUTHOR Olivier Gérard, Jun 07 2001 STATUS approved

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.

Last modified December 18 03:54 EST 2017. Contains 296128 sequences.