cp's OEIS Frontend

A061356 Triangle read by rows: T(n, k) is the number of labeled trees on n nodes with maximal node degree k (0 < k < n).

%I A061356 #125 Aug 23 2025 16:41:29
%S A061356 1,2,1,9,6,1,64,48,12,1,625,500,150,20,1,7776,6480,2160,360,30,1,
%T A061356 117649,100842,36015,6860,735,42,1,2097152,1835008,688128,143360,
%U A061356 17920,1344,56,1,43046721,38263752,14880348,3306744,459270,40824,2268,72,1
%N A061356 Triangle read by rows: T(n, k) is the number of labeled trees on n nodes with maximal node degree k (0 < k < n).
%C A061356 Essentially the coefficients of the Abel polynomials (A137452). - _Peter Luschny_, Jun 12 2022
%C A061356 This is a formula from Comtet, Theorem F, vol. I, p. 81 (French edition) used in proving Theorem D.
%C A061356 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
%C A061356 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
%C A061356 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
%C A061356 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
%C A061356 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
%C A061356 Abel polynomials A(n,x) = x*(x+n)^(n-1) satisfy d/dx A(n,x) = n*A(n-1,x+1). - _Michael Somos_, May 10 2024
%C A061356 Also, T(n,k) is the number of parking functions with k ties. - _Kyle Celano_, Aug 18 2025
%D A061356 L. Comtet, Analyse Combinatoire, P.U.F., Paris 1970. Volume 1, p 81.
%D A061356 L. Comtet, Advanced Combinatorics, Reidel, 1974.
%H A061356 G. C. Greubel, <a href="/A061356/b061356.txt">Table of n, a(n) for the first 50 rows, flattened</a>
%H A061356 A. Avron and N. Dershowitz, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.123.7.699">Cayley's Formula, A Page From The Book</a>, Amer. Math. Monthly, Vol. 123, No. 7, Aug.-Sep. 2016, 699-700 (2).
%H A061356 Peter Bala, <a href="/A112007/a112007_Bala.txt">Diagonals of triangles with generating function exp(t*F(x))</a>
%H A061356 W. Bomfim, <a href="http://en.wikipedia.org/wiki/File:Bijecao.gif">Bijection between rooted forests and multigraphs without cycles except one loop in each connected component.</a> [From _Washington Bomfim_, Sep 04 2010]
%H A061356 J. W. Moon, <a href="http://www.jstor.org/stable/2312668">Another proof of Cayley's formula for counting trees</a>, Amer. Math. Monthly, Vol. 70, No. 8, Oct. 1963, 846-847.
%H A061356 Jim Pitman, <a href="http://www.stat.berkeley.edu/tech-reports/457.pdf">Coalescent Random Forests</a>, Technical Report No. 457, Department of Statistics, University of California.
%H A061356 Jim Pitman, <a href="https://doi.org/10.1006/jcta.1998.2919">Coalescent Random Forests</a>, Journal of Combinatorial Theory, Series A, Volume 85, Issue 2, February 1999, Pages 165-193.
%H A061356 Paul R. F. Schumacher, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Schumacher/schu5.pdf">Descents in parking functions</a>, J. Integer Seq., Vol. 21 (2018), Article 18.2.3.
%H A061356 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/AbelPolynomial.html">Abel Polynomial</a>.
%H A061356 Wikipedia, <a href="http://en.wikipedia.org/wiki/Lambert_W_function">Lambert W function</a>
%H A061356 J. Zeng, <a href="http://dx.doi.org/10.1023/A:1009809224933">A Ramanujan sequence that refines the Cayley formula for trees</a>, Ramanujan J., 3(1999) 1, 45-54.
%F A061356 T(n, k) = binomial(n-2, k-1)*(n-1)^(n-k-1).
%F A061356 E.g.f.: (-LambertW(-y)/y)^(x+1)/(1+LambertW(-y)). - _Vladeta Jovovic_
%F A061356 From _Peter Bala_, Sep 21 2012: (Start)
%F A061356 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! + ....
%F A061356 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.
%F A061356 The row generating polynomials are the Abel polynomials A(n,x) = x*(x+n)^(n-1) for n >= 1.
%F A061356 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.
%F A061356 n-th row sum = A000272(n+1).
%F A061356 Row reverse triangle is A139526.
%F A061356 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.
%F A061356 (End)
%F A061356 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
%e A061356 Triangle begins
%e A061356     1;
%e A061356     2,     1;
%e A061356     9,     6,     1;
%e A061356    64,    48,    12,    1;
%e A061356   625,   500,   150,   20,    1;
%e A061356  7776,  6480,  2160,  360,   30,    1;
%e A061356  ...
%e A061356 From _Peter Bala_, Sep 21 2012: (Start)
%e A061356 O.g.f.'s for the diagonals begin:
%e A061356 1/(1-x) = 1 + x + x^2 + x^3 + ...
%e A061356 2*x/(1-x)^3 = 2 + 6*x + 12*x^3 + ... A002378(n+1)
%e A061356 (9+3*x)/(1-x)^5 = 9 + 48*x + 150*x^2 + ... 3*A004320(n+1)
%e A061356 The numerator polynomials are the row polynomials of A155163.
%e A061356 (End)
%p A061356 # The function BellMatrix is defined in A264428.
%p A061356 # Adds (1,0,0,0,...) as column 0 to the triangle.
%p A061356 BellMatrix(n -> (n+1)^n, 12); # _Peter Luschny_, Jan 21 2016
%t A061356 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 A061356 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_ *)
%t A061356 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 *)
%t A061356 BellMatrix[f_Function, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len-1}, {k, 0, len-1}]];
%t A061356 rows = 10;
%t A061356 M = BellMatrix[(# + 1)^#&, rows];
%t A061356 Table[M[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* _Jean-François Alcover_, Jun 23 2018, after _Peter Luschny_ *)
%o A061356 (Maxima) create_list(binomial(n,k)*(n+1)^(n-k),n,0,20,k,0,n); /* _Emanuele Munarini_, Apr 01 2014 */
%o A061356 (Sage) # uses[bell_matrix from A264428]
%o A061356 # Adds (1,0,0,0,...) as column 0 to the triangle.
%o A061356 bell_matrix(lambda n: (n+1)^n, 12) # _Peter Luschny_, Jan 21 2016
%o A061356 (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
%Y A061356 Variant of A137452.
%Y A061356 Columns are A000169, A053506, A053507, A053508, A053509.
%Y A061356 First diagonal is A002378.
%Y A061356 Row sums give A000272.
%Y A061356 Cf. A028421, A059297, A139526 (row reverse), A155163, A202017.
%K A061356 easy,nonn,tabl,changed
%O A061356 2,2
%A A061356 _Olivier Gérard_, Jun 07 2001