login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

Table of n, a(n) for n=1..51.

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 25 00:39 EST 2018. Contains 299630 sequences. (Running on oeis4.)