A059418 Triangle T(n,k) arising from enumeration of permutations with ordered orbits, read by rows (1<=k<=n).

1, 1, 1, 3, 2, 1, 12, 7, 4, 1, 60, 33, 19, 7, 1, 360, 192, 109, 47, 11, 1, 2520, 1320, 737, 344, 102, 16, 1, 20160, 10440, 5742, 2801, 956, 198, 22, 1, 181440, 93240, 50634, 25349, 9493, 2342, 352, 29, 1, 1814400, 927360, 498312, 253426, 101293, 28229

Offset: 1

Author

N. J. A. Sloane, Jan 30 2001

Keywords

• nonn
• easy
• tabl

Comments

From Peter Bala, Jul 08 2012: (Start)

A non-plane recursive tree is a rooted labeled plane tree (the children of a node are not ordered) with the property that the labels increase along any path from the root to a leaf. T(n,k) counts the total number of vertices of outdegree k among the set of n! non-plane recursive trees on n+1 vertices. An example is given below.

(End)

Examples

			1; 1,1; 3,2,1; 12,7,4,1; 60,33,19,7,1; ...
Row 3: [12,7,4,1]. There are 6 non-plane recursive trees on 4 nodes.
The total number of nodes of outdegree 0 = 1+2+2+2+2+3 = 12;
The total number of nodes of outdegree 1 = 3+1+1+1+1 = 7;
The total number of nodes of outdegree 2 = 1+1+1+1 = 4;
The total number of nodes of outdegree 3 = 1;
...................................................................
.0o......0o..........0o..........0o.........0o...........0o........
..|.......|........../.\........./.\......../.\........../|\.......
..|.......|........./...\......./...\....../...\......../.|.\......
.1o......1o.......1o.....o3...1o....o2...2o.....o1...../..|..\.....
..|....../.\.......|...........|..........|..........1o..2o...o3...
..|...../...\......|...........|..........|........................
.2o...2o.....o3...2o..........3o.........3o........................
..|................................................................
..|................................................................
.3o................................................................
....................................... - _Peter Bala_, Jul 08 2012
		

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 258, #10, F(n,k).

Links

• M. Drmota, Recursive Trees.

Crossrefs

Diagonals give A001710, A006595. A109822, A130534.

Programs

Mathematica

t[n_, k_] := (n - 2)*t[n - 1, k] + t[n - 1, k - 1]; t[n_, n_] := 1; t[n_, 1] = n!/2; Table[t[n, k], {n, 10}, {k, n}] // Flatten (* Robert G. Wilson v, Jul 08 2012 *)

Formula

T(n, k) = (n-2)*T(n-1, k) + T(n-1, k-1), T(n, 1)=n!/2, T(n, n)=1.

From Peter Bala, Jul 08 2012: (Start)

E.g.f.: A(x,z) = x/(2-x){1/(1-z) - 1/(1-z)^(x-1)} = x*z + (x+x^2)*z^2/2! + (3*x+2*x^2+x^3)*z^3/3! + ....

A(x+1,z) is an e.g.f. for the row reverse of A109822 and A(x+2,z) generates the triangle of unsigned Stirling numbers of the first kind A130534 but with the first column omitted.

E.g.f. for column k: 1/(2^k*(1-x)) + (x-1)*sum {j = 0..k-1} 1/(j!*2^(k-j))*log^j(1/(1-x)) - see Drmota.

The row polynomial R(n,x) satisfies the recurrence equation R(n,x) = (x+n-2)*R(n-1,x) + (n-1)!*x with R(1,x) = x and also the recurrence R(n,x) = (x+2*n-3)*R(n-1,x) - (n-1)*(x+n-3)*R(n-2,x) with R(1,x) = x and R(2,x) = x+x^2. R(n,x) = {(x-1)*x*(x+1)*...*(x+n-2) - n!}/(x-2).

(End)

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Jan 31 2001