A038775 -id:A038775 - cp's OEIS frontend

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

Antti Karttunen Sep 03 2000

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.

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

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.

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;

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

A038776 The sequence a[1] to a[ cat[n] ] is the permutation that converts forest[n] of depth-first planar planted binary trees into breadth-first representation.

Original entry on oeis.org

1, 2, 4, 5, 3, 9, 10, 13, 14, 12, 6, 7, 8, 11, 23, 24, 27, 28, 26, 36, 37, 41, 42, 40, 32, 33, 35, 39, 15, 16, 18, 19, 17, 22, 25, 20, 21, 34, 38, 29, 30, 31, 65, 66, 69, 70, 68, 78, 79, 83, 84, 82, 74, 75, 77, 81, 106, 107, 111, 112, 110, 125, 126, 131, 132, 130

Offset: 1

Wouter Meeussen, May 04 2000

nonn

			tree ( 1 (100) (10 ) ) becomes (1) (11)(00 0 ) thus (1 (1(100) 0) ) and is permuted from position 3 in forest[3] to position 5 by permutation {1,2,4,5,3}={{1},{2},{4,5,3}}

Antti Karttunen, Table of n, a(n) for n = 1..1430
Antti Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence).
Index entries for sequences that are permutations of the natural numbers

Compare to the plot of A082364 and A072619.

Inverse of A070041. Cf. also A038774, A038775. If "expanded" produces A057117. Max cycle lengths: A057542.

[seq(CatalanRank(inf,(btbf2df(binrev(CatalanUnrank(inf,j)),0,1)/2))+1,j=0..(binomial(2*inf,inf)/(inf+1))-1)]; (In practice, use a value like 6 instead of infinity).
btbf2df := proc(nn,i,r) local n,j,c,x,y,w; n := nn; if(0 = (n mod 2)) then RETURN(0); fi; c := i; for j from 1 to r do c := c + (n mod 2); n := floor(n/2); od; w := 2*c; c := 0; for j from 1 to (2*i) do c := c + (n mod 2); n := floor(n/2); od; x := btbf2df(n,c,(w-(j-1))); y := btbf2df(floor(n/2),c+(n mod 2),(w-(j))); RETURN((2^(binwidth(x)+binwidth(y))) + (x * (2^(binwidth(y)))) + y); end;
floor_log_2 := proc(n) local nn,i: nn := n; for i from -1 to n do if(0 = nn) then RETURN(i); fi: nn := floor(nn/2); od: end:
binwidth := n -> (`if`((0 = n),1,floor_log_2(n)+1));
binrev := proc(nn) local n,z; n := nn; z := 0; while(n <> 0) do z := 2*z + (n mod 2); n := floor(n/2); od; RETURN(z); end;

bracket[ tree_ ] := (Flatten[ {tree, 0} ]/. 0->{0})//.{1, z___, 1, a_List, b_List, y___}:>{1, z, {1, a, b}, y}; widthfirst[ dectree_ ] := b2d[ Drop[ Flatten[ {Table[ Cases[ Level[ #, {k}, z ], A014486%20*)%20Ordering%5BReverse%5Bwidthfirst%20/@%20b2d%20/@%20wood%5B6%5D%5D%5D%20(*%20_Wouter%20Meeussen">Integer ], {k, Depth[ # ]-1} ] }/.z->List ], -1 ] ] & @(bracket@d2b[ dectree ]); (* uses functions in A014486 *) Ordering[Reverse[widthfirst /@ b2d /@ wood[6]]] (* _Wouter Meeussen, Aug 19 2025 *)

Additional comments from Antti Karttunen, Aug 11 2000

A038774 Cycle lengths of the permutation that converts the forest of depth-first planar planted binary trees into breadth-first representation.

Original entry on oeis.org

1, 1, 3, 4, 3, 2, 16, 8, 2, 2, 87, 3, 202, 25, 5, 4, 61, 607, 63, 165, 127, 12, 8, 10, 4, 5, 927, 1441, 283, 625, 91, 52, 8, 5, 4708, 592, 1890, 86, 3505, 482, 471, 34, 84, 17, 22, 25, 5, 9, 3, 1

Offset: 1

Wouter Meeussen, May 04 2000

nonn

			The first 6 terms add up to 14=cat[4], so the cycle lengths of the permutation for forest[4] are {1, 1, 3, 4, 3, 2}. The sequence as given (50 terms) was generated on forest[10].

Cf. A038775, A038776. Max cycle lengths: A057542.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A038776 The sequence a[1] to a[ cat[n] ] is the permutation that converts forest[n] of depth-first planar planted binary trees into breadth-first representation.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A038774 Cycle lengths of the permutation that converts the forest of depth-first planar planted binary trees into breadth-first representation.

Views

Author

Keywords

Examples

Crossrefs