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,4

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.

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.

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)

Example

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)

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

Crossrefs

Cf. A000142, A000169, A001705.

Sequence in context: A179015 A195621 A267090 * A142148 A142583 A327838

Adjacent sequences: A067945 A067946 A067947 * A067949 A067950 A067951

Keyword

nonn,tabl

Author

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

Status

approved