|
| |
|
|
A059418
|
|
Triangle T(n,k) arising from enumeration of permutations with ordered orbits, read by rows (1<=k<=n).
|
|
1
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
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)
|
|
|
REFERENCES
|
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 258, #10, F(n,k).
|
|
|
LINKS
|
|
|
|
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)
|
|
|
EXAMPLE
|
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
|
|
|
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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
More terms from Larry Reeves (larryr(AT)acm.org), Jan 31 2001
|
|
|
STATUS
|
approved
|
| |
|
|
