A057513 Number of separate orbits to which permutations given in A057511/A057512 (induced by deep rotation of general parenthesizations/plane trees) partition each A000108(n) objects encoded by A014486 between (A014138(n-1)+1)-th and (A014138(n))-th terms.

1, 1, 2, 4, 9, 21, 56, 153, 451, 1357, 4212, 13308, 42898, 140276, 465324, 1561955, 5300285, 18156813, 62732842, 218405402, 765657940

Offset: 0

Author

Antti Karttunen Sep 03 2000

Keywords

• nonn
• more

Comments

It is much faster to compute this sequence empirically with the given C-program than to calculate the terms with the formula in its present form.

Links

• A. Karttunen, Gatomorphisms (with the complete Scheme source)
• Index entries for sequences related to rooted trees
• A. Karttunen, C-program for computing empirically the initial terms of this sequence

Crossrefs

CountCycles given in A057502, for other procedures, follow A057511 and A057501.

Similarly generated sequences: A001683, A002995, A003239, A038775, A057507. Cf. also A000081.

Occurs for first time in A073201 as row 12. Cf. A057546 and also A000081.

Programs

Maple

A057513 := proc(n) local i; `if`((0=n),1,(1/A003418(n-1))*add(A079216bi(n,i),i=1..A003418(n-1))); end;
# Or empirically:
DeepRotatePermutationCycleCounts := proc(upto_n) local u,n,a,r,b; a := []; for n from 0 to upto_n do b := []; u := (binomial(2*n,n)/(n+1)); for r from 0 to u-1 do b := [op(b),1+CatalanRank(n,DeepRotateL(CatalanUnrank(n,r)))]; od; a := [op(a),CountCycles(b)]; od; RETURN(a); end;

Formula

a(0)=1, a(n) = (1/A003418(n-1))*Sum_{i=1..A003418(n-1)} A079216(n, i) [Needs improvement.] - Antti Karttunen, Jan 03 2003