This site is supported by donations to The OEIS Foundation.

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 M. Drmota, Recursive Trees. 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 Diagonals give A001710, A006595.  A109822, A130534. Sequence in context: A118435 A115085 A110616 * A092582 A213262 A280512 Adjacent sequences:  A059415 A059416 A059417 * A059419 A059420 A059421 KEYWORD nonn,easy,tabl AUTHOR N. J. A. Sloane, Jan 30 2001 EXTENSIONS More terms from Larry Reeves (larryr(AT)acm.org), Jan 31 2001 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 18 20:57 EST 2019. Contains 319282 sequences. (Running on oeis4.)