cp's OEIS Frontend

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

%I A059418 #11 Jul 09 2012 07:01:17
%S A059418 1,1,1,3,2,1,12,7,4,1,60,33,19,7,1,360,192,109,47,11,1,2520,1320,737,
%T A059418 344,102,16,1,20160,10440,5742,2801,956,198,22,1,181440,93240,50634,
%U A059418 25349,9493,2342,352,29,1,1814400,927360,498312,253426,101293,28229
%N A059418 Triangle T(n,k) arising from enumeration of permutations with ordered orbits, read by rows (1<=k<=n).
%C A059418 From Peter Bala, Jul 08 2012: (Start)
%C A059418 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.
%C A059418 (End)
%D A059418 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 258, #10, F(n,k).
%H A059418 M. Drmota, <a href="http://www.dmg.tuwien.ac.at/drmota/recursivetrees.pdf">Recursive Trees</a>.
%F A059418 T(n, k) = (n-2)*T(n-1, k) + T(n-1, k-1), T(n, 1)=n!/2, T(n, n)=1.
%F A059418 From Peter Bala, Jul 08 2012: (Start)
%F A059418 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! + ....
%F A059418 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.
%F A059418 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.
%F A059418 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).
%F A059418 (End)
%e A059418 1; 1,1; 3,2,1; 12,7,4,1; 60,33,19,7,1; ...
%e A059418 Row 3: [12,7,4,1]. There are 6 non-plane recursive trees on 4 nodes.
%e A059418 The total number of nodes of outdegree 0 = 1+2+2+2+2+3 = 12;
%e A059418 The total number of nodes of outdegree 1 = 3+1+1+1+1 = 7;
%e A059418 The total number of nodes of outdegree 2 = 1+1+1+1 = 4;
%e A059418 The total number of nodes of outdegree 3 = 1;
%e A059418 ...................................................................
%e A059418 .0o......0o..........0o..........0o.........0o...........0o........
%e A059418 ..|.......|........../.\........./.\......../.\........../|\.......
%e A059418 ..|.......|........./...\......./...\....../...\......../.|.\......
%e A059418 .1o......1o.......1o.....o3...1o....o2...2o.....o1...../..|..\.....
%e A059418 ..|....../.\.......|...........|..........|..........1o..2o...o3...
%e A059418 ..|...../...\......|...........|..........|........................
%e A059418 .2o...2o.....o3...2o..........3o.........3o........................
%e A059418 ..|................................................................
%e A059418 ..|................................................................
%e A059418 .3o................................................................
%e A059418 ....................................... - _Peter Bala_, Jul 08 2012
%t A059418 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 *)
%Y A059418 Diagonals give A001710, A006595.  A109822, A130534.
%K A059418 nonn,easy,tabl
%O A059418 1,4
%A A059418 _N. J. A. Sloane_, Jan 30 2001
%E A059418 More terms from Larry Reeves (larryr(AT)acm.org), Jan 31 2001