A067948 Triangle of labeled rooted trees according to the number of increasing edges.

1, 1, 1, 2, 5, 2, 6, 26, 26, 6, 24, 154, 269, 154, 24, 120, 1044, 2724, 2724, 1044, 120, 720, 8028, 28636, 42881, 28636, 8028, 720, 5040, 69264, 319024, 655248, 655248, 319024, 69264, 5040, 40320, 663696, 3793212, 10095228, 13861809, 10095228, 3793212, 663696, 40320

Offset: 1

Author

Cedric Chauve (chauve(AT)lacim.uqam.ca), Mar 19 2002

Keywords

• nonn
• tabl

Comments

Each line is symmetric.

The sum of each line is n^(n-1), A000169.

The outer diagonal is (n-1)!, A000142.

The next-to-last diagonal is A001705.

Examples

			Triangle starts:
   1;
   1,   1;
   2,   5,   2;
   6,  26,  26,   6;
  24, 154, 269, 154,  24;
  ...
From _Bruno Berselli_, Jan 12 2021: (Start)
The rows of the triangle are the coefficients of the following polynomials:
1: 1;
2: 1*x+1;
3: (x+2)*(2*x+1) = 2*x^2 + 5*x + 2;
4: (x+3)*(2*x+2)*(3*x+1) = 6*x^3 + 26*x^2 + 26*x + 6;
5: (x+4)*(2*x+3)*(3*x+2)*(4*x+1) = 24*x^4 + 154*x^3 + 269*x^2 + 154*x + 24, etc.
(End)
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened
• Brian Drake, An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.7.2), A dissertation presented to the Faculty of the Graduate School of Arts and Sciences of Brandeis University.
• Ira M. Gessel and Seunghyun Seo, A refinement of Cayley's formula for trees, Electronic J. Combin. 11, no. 2 (2004-6) (The Stanley Festschrift volume).
• A. M. Khidr and B. S. El-Desouky, A symmetric sum involving the Stirling numbers of the first kind, European J. Combin., 5 (1984), 51-54.

Crossrefs

Cf. A000142, A000169, A001705.

Programs

Maple

b:= proc(n) option remember;
      expand(x*mul(n-k+k*x, k=1..n-1))
    end:
T:= (n, k)-> coeff(b(n), x, k):
seq(seq(T(n,k), k=1..n), n=1..10);  # Alois P. Heinz, Jun 26 2024

Mathematica

L := CoefficientList[InverseSeries[Series[(Exp[-x y] + Sinh[x] - Cosh[x])/(1 - y), {x, 0, 8}]], {x}]; Table[CoefficientList[L, y][[n + 1]] n!, {n, 1, 8}] // Flatten (* Peter Luschny, Jun 23 2018 *)

Formula

G.f. of row n: Sum_{k=0..n-1} T(n, k) x^k = Product_{i=1..n-1} (n - i + i*x).

From Peter Bala, Sep 29 2011: (Start)

E.g.f.: Compositional inverse of (exp(x) - exp(x*t))/((1 - t)*exp(x*(1 + t))) = x + (1 + t)*x^2/2! + (2 + 5*t + 2*t^2)*x^3/3! + ...

Let f(x,t) = (1 - t)/(exp(-x) - t*exp(-x*t)) and let D be the operator f(x,t)*d/dx. Then the (n+1)-th row generating polynomial equals (D^n)(f(x,t)) evaluated at x = 0. See [Drake, example 1.7.2] for the combinatorial interpretation of this table in terms of labeled trees. (End)