A057162 -id:A057162 - cp's OEIS frontend

A057163 Signature-permutation of a Catalan automorphism: Reflect a rooted plane binary tree; Deutsch's 1998 involution on Dyck paths.

0, 1, 3, 2, 8, 7, 6, 5, 4, 22, 21, 20, 18, 17, 19, 16, 15, 13, 12, 14, 11, 10, 9, 64, 63, 62, 59, 58, 61, 57, 55, 50, 49, 54, 48, 46, 45, 60, 56, 53, 47, 44, 52, 43, 41, 36, 35, 40, 34, 32, 31, 51, 42, 39, 33, 30, 38, 29, 27, 26, 37, 28, 25, 24, 23, 196, 195, 194, 190, 189

Offset: 0

Antti Karttunen, Aug 18 2000

nonn

Deutsch shows in his 1999 paper that this automorphism maps the number of doublerises of Dyck paths to number of valleys and height of the first peak to the number of returns, i.e., that A126306(n) = A127284(a(n)) and A126307(n) = A057515(a(n)) hold for all n.
The A000108(n-2) n-gon triangularizations can be reflected over n axes of symmetry, which all can be generated by appropriate compositions of the permutations A057161/A057162 and A057163.
Composition with A057164 gives signature permutation for Donaghey's Map M (A057505/A057506). Embeds into itself in scale n:2n+1 as a(n) = A083928(a(A080298(n))). A127302(a(n)) = A127302(n) and A057123(A057163(n)) = A057164(A057123(n)) hold for all n.

			This involution (self-inverse permutation) of natural numbers is induced when we reflect the rooted plane binary trees encoded by A014486. E.g., we have A014486(5) = 44 (101100 in binary), A014486(7) = 52 (110100 in binary) and these encode the following rooted plane binary trees, which are reflections of each other:
    0   0             0   0
     \ /               \ /
      1   0         0   1
       \ /           \ /
    0   1             1   0
     \ /               \ /
      1                 1
thus a(5)=7 and a(7)=5.

JungHwan Min, Table of n, a(n) for n = 0..10000
Emeric Deutsch, An involution on Dyck paths and its consequences, Discrete Math., 204 (1999), no. 1-3, 163-166.
Indranil Ghosh, Python program for computing this sequence, translated from Maple code.
Antti Karttunen, C program which computes this sequence.
Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625, Dec 08, 2020.
Index entries for signature-permutations induced by Catalan automorphisms

This automorphism conjugates between the car/cdr-flipped variants of other automorphisms, e.g., A057162(n) = a(A057161(a(n))), A069768(n) = a(A069767(a(n))), A069769(n) = a(A057508(a(n))), A069773(n) = a(A057501(a(n))), A069774(n) = a(A057502(a(n))), A069775(n) = a(A057509(a(n))), A069776(n) = a(A057510(a(n))), A069787(n) = a(A057164(a(n))).

Row 1 of tables A122201 and A122202, that is, obtained with FORK (and KROF) transformation from even simpler automorphism *A069770. Cf. A122351.

a(n) = A080300(ReflectBinTree(A014486(n)))
ReflectBinTree := n -> ReflectBinTree2(n)/2; ReflectBinTree2 := n -> (`if`((0 = n),n,ReflectBinTreeAux(A030101(n))));
ReflectBinTreeAux := proc(n) local a,b; a := ReflectBinTree2(BinTreeLeftBranch(n)); b := ReflectBinTree2(BinTreeRightBranch(n)); RETURN((2^(A070939(b)+A070939(a))) + (b * (2^(A070939(a)))) + a); end;
NextSubBinTree := proc(nn) local n,z,c; n := nn; c := 0; z := 0; while(c < 1) do z := 2*z + (n mod 2); c := c + (-1)^n; n := floor(n/2); od; RETURN(z); end;
BinTreeLeftBranch := n -> NextSubBinTree(floor(n/2));
BinTreeRightBranch := n -> NextSubBinTree(floor(n/(2^(1+A070939(BinTreeLeftBranch(n))))));

A014486Q[0] = True; A014486Q[n_] := Catch[Fold[If[# < 0, Throw[False], If[#2 == 0, # - 1, # + 1]] &, 0, IntegerDigits[n, 2]] == 0]; tree[n_] := Block[{func, num = Append[IntegerDigits[n, 2], 0]}, func := If[num[[1]] == 0, num = Drop[num, 1]; 0, num = Drop[num, 1]; 1[func, func]]; func]; A057163L[n_] := Function[x, FirstPosition[x, FromDigits[Most@Cases[tree[#] /. 1 -> Reverse@*1, 0 | 1, All, Heads -> True], 2]][[1]] - 1 & /@ x][Select[Range[0, 2^n], A014486Q]]; A057163L[11] (* JungHwan Min, Dec 11 2016 *)

a(n) = A083927(A057164(A057123(n))).

Equivalence with Deutsch's 1998 involution realized Dec 15 2006 and entry edited accordingly by Antti Karttunen, Jan 16 2007

A073200 Number of simple Catalan bijections of type B.

Original entry on oeis.org

0, 1, 0, 3, 1, 0, 2, 2, 1, 0, 7, 3, 3, 1, 0, 8, 4, 2, 3, 1, 0, 6, 6, 8, 2, 3, 1, 0, 4, 5, 7, 7, 2, 3, 1, 0, 5, 7, 6, 6, 8, 2, 3, 1, 0, 17, 8, 5, 8, 7, 7, 2, 2, 1, 0, 18, 9, 4, 4, 6, 8, 7, 3, 3, 1, 0, 20, 10, 22, 5, 5, 5, 8, 4, 2, 2, 1, 0, 21, 14, 21, 17, 4, 4, 6, 5, 8, 3, 3, 1, 0

Offset: 0

Antti Karttunen, Jun 25 2002

Each row is a permutation of nonnegative integers induced by a Catalan bijection (constructed as explained below) acting on the parenthesizations/plane binary trees as encoded and ordered by A014486/A063171.
The construction process is akin to the constructive mapping of primitive recursive functions to N: we have two basic primitives, A069770 (row 0) and A072796 (row 1), of which the former swaps the left and the right subtree of a binary tree and the latter exchanges the positions of the two leftmost subtrees of plane general trees, unless the tree's degree is less than 2, in which case it just fixes it. From then on, the even rows are constructed recursively from any other Catalan bijection in this table, using one of the five allowed recursion types:
0 - Apply the given Catalan bijection and then recurse down to both subtrees of the new binary tree obtained. (last decimal digit of row number = 2)
1 - First recurse down to both subtrees of the old binary tree and only after that apply the given Catalan bijection. (last digit = 4)
2 - Apply the given Catalan bijection and then recurse down to the right subtree of the new binary tree obtained. (last digit = 6)
3 - First recurse down to the right subtree of old binary tree and only after that apply the given Catalan bijection. (last digit = 8)
4 - First recurse down to the left subtree of old binary tree, after that apply the given Catalan bijection and then recurse down to the right subtree of the new binary tree. (last digit = 0)
The odd rows > 2 are compositions of the rows 0, 1, 2, 4, 6, 8, ... (i.e. either one of the primitives A069770 or A072796, or one of the recursive compositions) at the left hand side and any Catalan bijection from the same array at the right hand side. See the scheme-functions index-for-recursive-sgtb and index-for-composed-sgtb how to compute the positions of the recursive and ordinary compositions in this table.

A. Karttunen, Gatomorphisms (With the complete source and explanation)

Four other tables giving the corresponding cycle-counts: A073201, counts of the fixed elements: A073202, the lengths of the largest cycles: A073203, the LCM's of all the cycles: A073204. The ordinary compositions are encoded using the N X N -> N bijection A054238 (which in turn uses the bit-interleaving function A000695).
The first 21 rows of this table:.
Row 0: A069770. Row 1: A072796. Row 2: A057163. Row 3: A073269, Row 4: A057163 (duplicate), Row 5: A073270, Row 6: A069767, Row 7: A001477 (identity perm.), Row 8: A069768, Row 9: A073280.
Row 10: A069770 (dupl.), Row 11: A072796 (dupl.), Row 12: A057511, Row 13: A073282, Row 14: A057512, Row 15: A073281, Row 16: A057509, Row 17: A073280 (dupl.), Row 18: A057510, Row 19: A073283, Row 20: A073284.
Other Catalan bijection-induced EIS-permutations which occur in this table. Only the first known occurrence is given. Involutions are marked with *, others paired with their inverse:.
Row 164: A057164*, Row 168: A057508*, Row 179: A072797*.
Row 41: A073286 - Row 69: A073287. Row 105: A073290 - Row 197: A073291. Row 416: A073288 - Row 696: A073289.
Row 261: A057501 - Row 521: A057502. Row 2618: A057503 - Row 5216: A057504. Row 2614: A057505 - Row 5212: A057506.
Row 10435: A073292 - Row ...: A073293. Row 17517: A057161 - Row ...: A057162.
For a more practical enumeration system of (some) Catalan automorphisms see table A089840 and its various "recursive derivations".

A057506 Signature-permutation of a Catalan Automorphism: (inverse of) "Donaghey's map M", acting on the parenthesizations encoded by A014486.

Original entry on oeis.org

0, 1, 3, 2, 8, 6, 7, 5, 4, 22, 19, 20, 15, 14, 21, 16, 18, 13, 11, 17, 12, 10, 9, 64, 60, 61, 52, 51, 62, 53, 55, 41, 39, 54, 40, 38, 37, 63, 56, 57, 43, 42, 59, 47, 50, 36, 33, 48, 34, 29, 28, 58, 44, 49, 35, 30, 46, 32, 27, 25, 45, 31, 26, 24, 23, 196, 191, 192, 178, 177

Offset: 0

Antti Karttunen, Sep 03 2000

This is inverse of A057505, which is a signature permutation of Catalan automorphism (bijection) known as "Donaghey's map M". See A057505 for more comments, links and references.

Antti Karttunen, Table of n, a(n) for n = 0..23713
A. Karttunen (et al) at OEIS Wiki, Maple implementations of CatalanRankGlobal, CatalanSequences, car, cdr, binexp2pars and pars2binexp functions
A. Karttunen at OEIS WIki, Scheme implementations of CatalanRankSexp and CatalanUnrankSexp
Indranil Ghosh, Python program for computing this sequence (after the functions mentioned in the OEIS wiki)
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057505.
Cf. A057161, A057162, A057163, A057164, A057501, A057502, A057503, A057504 (for similar signature permutations of simple Catalan automorphisms).
Cf. A057507 (cycle counts).
The 2nd, 3rd, 4th, 5th and 6th "powers" of this permutation: A071662, A071664, A071666, A071668, A071670.
Row 12 of table A122287.
Cf. also A014486, A080300, A080069, A080070.

map(CatalanRankGlobal,map(DonagheysA057506,CatalanSequences(196))); # Where CatalanSequences(n) gives the terms A014486(0..n).
DonagheysA057506 := n -> pars2binexp(deepreverse(DonagheysA057505(deepreverse(binexp2pars(n)))));
DonagheysA057505 := h -> `if`((0 = nops(h)), h, [op(DonagheysA057505(car(h))), DonagheysA057505(cdr(h))]);
# The following corresponds to automorphism A057164:
deepreverse := proc(a) if 0 = nops(a) or list <> whattype(a) then (a) else [op(deepreverse(cdr(a))), deepreverse(a[1])]; fi; end;
# The rest of required Maple-functions: see the given OEIS Wiki page.

(define (A057506 n) (CatalanRankSexp (*A057506 (CatalanUnrankSexp n))))
(define (*A057506 bt) (let loop ((lt bt) (nt (list))) (cond ((not (pair? lt)) nt) (else (loop (cdr lt) (cons nt (*A057506 (car lt))))))))
;; Functions CatalanRankSexp and CatalanUnrankSexp can be found at OEIS Wiki page.

a(n) = A057163(A057164(n)).

a(n) = A057163(A057505(A057163(n))) = A057164(A057505(A057164(n))).

Entry revised by Antti Karttunen, May 30 2017

A074679 Signature permutation of a Catalan automorphism: Rotate binary tree left if possible, otherwise swap its sides.

Original entry on oeis.org

0, 1, 3, 2, 6, 7, 8, 4, 5, 14, 15, 16, 17, 18, 19, 20, 21, 9, 10, 22, 11, 12, 13, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 23, 24, 59, 25, 26, 27, 60, 61, 62, 28, 29, 63, 30, 31, 32, 64, 33, 34, 35, 36, 107, 108, 109, 110, 111

Offset: 0

Antti Karttunen, Sep 11 2002

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node.)
...B...C.......A...B
....\./.........\./
.A...x....-->....x...C.................A..().........()..A..
..\./.............\./...................\./....-->....\./...
...x...............x.....................x.............x....
(a . (b . c)) -> ((a . b) . c) ____ (a . ()) --> (() . a)
That is, we rotate the binary tree left, in case it is possible and otherwise (if the right hand side of a tree is a terminal node) swap the left and right subtree (so that the terminal node ends to the left hand side), i.e., apply the automorphism *A069770. Look at the example in A069770 to see how this will produce the given sequence of integers.
This is the first multiclause nonrecursive automorphism in table A089840 and the first one whose order is not finite, i.e., the maximum size of cycles in this permutation is not bounded (see A089842). The cycle counts in range [A014137(n-1)..A014138(n)] of this permutation is given by A001683(n+1), which is otherwise the same sequence as for Catalan automorphisms *A057161/*A057162, but shifted once right. For an explanation, please see the notes in OEIS Wiki.

A. Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Introductory Survey of Catalan Automorphisms and Bijections, (an unfinished draft)
A. Karttunen, Notes on the orbits of this permutation, OEIS Wiki.
A. Karttunen, Prolog-program which illustrates the construction of this and similar nonrecursive bijections of oriented binary trees
Index entries for signature-permutations of Catalan automorphisms

This automorphism has several variants, where the first clause is same (rotate binary tree to the left, if possible), but something else is done (than just swapping sides), in case the right hand side is empty: A082335, A082349, A123499, A123695. The following automorphisms can be derived recursively from this one: A057502, A074681, A074683, A074685, A074687, A074690, A089865, A120706, A122321, A122332. See also somewhat similar ones: A069773, A071660, A071656, A071658, A072091, A072095, A072093.
Inverse: A074680.
Row 12 of A089840.
Occurs also in A073200 as row 557243 because a(n) = A073283(A073280(A072796(n))). a(n) = A083927(A123498(A057123(n))).
Number of cycles: LEFT(A001683). Number of fixed points: LEFT(A019590). Max. cycle size & LCM of all cycle sizes: A089410 (in range [A014137(n-1)..A014138(n)] of this permutation).

Description clarified Oct 10 2006

A069768 Signature-permutation of Catalan bijection "Knack".

Original entry on oeis.org

0, 1, 3, 2, 8, 7, 6, 4, 5, 22, 21, 20, 17, 18, 19, 16, 14, 9, 10, 15, 11, 12, 13, 64, 63, 62, 58, 59, 61, 57, 54, 45, 46, 55, 48, 49, 50, 60, 56, 53, 44, 47, 51, 42, 37, 23, 24, 38, 25, 26, 27, 52, 43, 39, 28, 29, 40, 30, 31, 32, 41, 33, 34, 35, 36, 196, 195, 194, 189, 190

Offset: 0

Antti Karttunen, Apr 16 2002; entry revised Dec 20 2008

nonn

This automorphism of binary trees first swaps the left and right subtree of the root and then proceeds recursively to the (new) left subtree, to do the same operation there. This is one of those Catalan bijections which extend to a unique automorphism of the infinite binary tree, which in this case is A153142. See further comments there and in A153141.
This bijection, Knack, is a ENIPS-transformation of the simple swap: ENIPS(*A069770) (i.e., row 1 of A122204). Furthermore, Knack and Knick (the inverse, A069767) have a special property, that FORK and KROF transforms (explained in A122201 and A122202) transform them to their own inverses, i.e., to each other: FORK(Knick) = KROF(Knick) = Knack and FORK(Knack) = KROF(Knack) = Knick, thus this occurs also as row 1 in A122288 and naturally, the double-fork fixes both, e.g., FORK(FORK(Knack)) = Knack.
Note: the name in Finnish is "Naks".

A. Karttunen, paper in preparation.

Inverse permutation: "Knick", A069767. "n-th powers" (i.e. n-fold applications), from n=2 to 6: A073291, A073293, A073295, A073297, A073299.
In range [A014137(n-1)..A014138(n-1)] of this permutation, the number of cycles is A073431, number of fixed points: A036987 (Fixed points themselves: A084108), Max. cycle size & LCM of all cycle sizes: A011782. See also: A074080.
A127302(a(n)) = A127302(n) for all n. a(n) = A057162(A057508(n)) = A069769(A057162(n))
Row 1 of A122204 and A122288, row 21 of A122285 and A130402, row 8 of A073200.
See also bijections A073287, A082346, A082347, A082350, A130342.

A001683 Number of one-sided triangulations of the disk; or flexagons of order n; or unlabeled plane trivalent trees (n-2 internal vertices, all of degree 3 and hence n leaves).

Original entry on oeis.org

1, 1, 1, 1, 4, 6, 19, 49, 150, 442, 1424, 4522, 14924, 49536, 167367, 570285, 1965058, 6823410, 23884366, 84155478, 298377508, 1063750740, 3811803164, 13722384546, 49611801980, 180072089896, 655977266884, 2397708652276, 8791599732140, 32330394085528

Offset: 2

N. J. A. Sloane

a(n) is the number of triangulations of an n-gon (equivalently, the number of vertices of the (n - 3)-dimensional associahedron) modulo the cyclic action [Bowman and Regev]. - N. J. A. Sloane, Dec 29 2012
a(n) is also the number of non-isomorphic cluster-tilted algebras of type A_(n-3), for n greater than or equal to 5. Equivalently it is the number of non-isomorphic quivers in the mutation class of any quiver with underlying graph A_(n-3) for n greater than or equal to 5. - Hermund A. Torkildsen (hermunda(AT)math.ntnu.no), Aug 06 2008
Number of oriented polyominoes composed of n-2 triangular cells of the hyperbolic regular tiling with Schläfli symbol {3,oo}. A stereographic projection of this tiling on the Poincaré disk can be obtained via the Christensson link. For oriented polyominoes, chiral pairs are counted as two. - Robert A. Russell, Jan 20 2024

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=2..200
Marc J. Beauchamp, On Extremal Punctured Spheres, Dissertation, University of Pittsburgh, 2017.
F. R. Bernhart & N. J. A. Sloane, Correspondence, 1977
Douglas Bowman and Alon Regev, Counting symmetry classes of dissections of a convex regular polygon, arXiv preprint arXiv:1209.6270 [math.CO], 2012. See Th. 29(2).
William G. Brown, Enumeration of Triangulations of the Disk, Proc. Lond. Math. Soc. s3-14 (1964) 746-768.
W. G. Brown, Enumeration of Triangulations of the Disk, Proc. Lond. Math. Soc. s3-14 (1964) 746-768. [Annotated scanned copy]
P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. See p. 163, line 4, but note that the formula given there has many typos (see the correct version given here).
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Malin Christensson, Make hyperbolic tilings of images, web page, 2019.
O. Devillers, Vertex removal in two-dimensional Delauney triangulation: Speed-up by low degrees optimization, Comp. Geom. 44 (2011) 169.
Petr Gregor, Sven Jäger, Torsten Mütze, Joe Sawada, Kaja Wille, Gray codes and symmetric chains, arXiv:1802.06021 [math.CO], 2018.
F. Harary, E. M. Palmer, R. C. Read, On the cell-growth problem for arbitrary polygons, computer printout, circa 1974
F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389.
E. Krasko, A. Omelchenko, Brown's Theorem and its Application for Enumeration of Dissections and Planar Trees, The Electronic Journal of Combinatorics, 22 (2015), #P1.17.
C. O. Oakley and R. J. Wisner, Flexagons, The American Mathematical Monthly, Vol. 64, No. 3 (Mar., 1957), pp. 143-154
R. C. Read, On general dissections of a polygon, Preprint (1974)
Hermund A. Torkildsen, Counting cluster-tilted algebras of type A_n, International Electronic Journal of Algebra, 4, 2008, 149-158. [From Hermund A. Torkildsen (hermunda(AT)math.ntnu.no), Aug 06 2008]
Hermund A. Torkildsen, Colored quivers of type A and the cell-growth problem, J. Algebra and Applications, 12 (2013), #1250133. - From _N. J. A. Sloane_, Jan 22 2013

Column k=3 of A295224.
Cf. A007282, A057162.
A row or column of the array in A262586.
Polyominoes: A000207 (unoriented), A369314 (chiral), A208355(n-1) (achiral), A005034 {4,oo}, A007173 {3,3,oo}.

C := n->binomial(2*n,n)/(n+1); c := x->if whattype(x) = integer then C(x) else 0; fi; A001683 := n->C(n-2)/n + c(n/2-1)/2+(2/3)*c(n/3-1);

p=3; Table[Binomial[(p-1)n, n]/(((p-2)n+1)((p-2)n+2)) +If[OddQ[n], 0, Binomial[(p-1)n/2, n/2]/((p-2)n+2)]+Plus @@ Map[EulerPhi[ # ]Binomial[((p-1)n+1)/#, (n-1)/# ]/((p-1)n+1)&, Complement[Divisors[GCD[p, n-1]], {1}]], {n, 0, 20}] (* Robert A. Russell, Dec 11 2004 *)
Rest[Rest[CoefficientList[Series[(6 + (1 - 4 x)^(3/2) + 6 x - 3(1 - 4 x^2)^(1/2) - 4 (1 - 4 x^3)^(1/2))/12, {x, 0, 33}], x]]] (* Vincenzo Librandi, Nov 25 2015 *)

Cat(n)=if(n==floor(n),return(binomial(2*n,n)/(n+1)));0
for(n=2,100,print1(Cat(n-2)/n+Cat(n/2-1)/2+(2/3)*Cat(n/3-1),", ")) \\ Derek Orr, Feb 26 2017

a(n) = C(n-2)/n + C(n/2-1)/2 + (2/3)*C(n/3-1), where C(n) = Catalan(n) (A000108) and terms are omitted if their subscripts are not integers.
G.f.: (6 + (1 - 4*x)^(3/2) + 6*x - 3*(1 - 4*x^2)^(1/2) - 4*(1 - 4*x^3)^(1/2))/12. - David Callan, Aug 01 2004
a(n) ~ 2^(2*n-4) / (sqrt(Pi) * n^(5/2)). - Vaclav Kotesovec, Mar 13 2016
a(n+2) = A000207(n) + A369314(n) = 2*A000207(n) - A208355(n-1) = 2*A369314(n) + A208355(n-1). - Robert A. Russell, Jan 19 2024
G.f.: z^2 * (4*G(z) - G(z)^2 + 3*G(z^2) + 4*z*G(z^3)) / 6, where G(z) = 1 + z*G(z)^2 is the g.f. for A000108. - Robert A. Russell, Apr 06 2024

A130402 Signature permutations of ENIPS-transformations of A057163-conjugates of Catalan automorphisms in table A122203.

Original entry on oeis.org

0, 1, 0, 2, 1, 0, 3, 3, 1, 0, 4, 2, 2, 1, 0, 5, 7, 3, 2, 1, 0, 6, 8, 4, 3, 2, 1, 0, 7, 6, 5, 4, 3, 2, 1, 0, 8, 4, 7, 5, 4, 3, 2, 1, 0, 9, 5, 6, 6, 5, 4, 3, 2, 1, 0, 10, 17, 8, 8, 8, 5, 4, 3, 2, 1, 0, 11, 18, 9, 7, 6, 8, 5, 5, 3, 2, 1, 0, 12, 20, 10, 9, 7, 7, 7, 4, 4, 3, 2, 1, 0, 13, 22, 12, 10, 9, 6

Offset: 0

Antti Karttunen, Jun 11 2007

Row n is the signature permutation of the Catalan automorphism which is obtained from A057163-conjugate of the n-th automorphism in the table A122203 with the recursion scheme "ENIPS", i.e. row n is obtained as ENIPS(A057163 o SPINE(A089840[n]) o A057163). See A122203 and A122204 for the description of SPINE and ENIPS. Each row occurs only once in this table. Inverses of these permutations can be found in table A130403. This table contains also all the rows of A122204 and A089840.

Cf. The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A082346, 2: A130935, 3: A073289, 4: A130937, 5: A130939, 6: A130941, 7: A130943, 8: A130945, 9: A130947, 10: A130949, 11: A130951, 12: A074687, 13: A130953, 14: A130955, 15: A130957, 16: A130959, 17: A057162, 18: A130961, 19: A130963, 20: A130965, 21: A069768. Other rows: 251: A069770, 3613: A082340, 65352: A057502.
Cf. also tables A089840, A122201-A122204, A122285-A122286, A130400-A130401.
Cf. As a sequence differs from A130403 for the first time at n=92, where a(n)=22, while A130403(n)=21.

A057510 Permutation of natural numbers: rotations of the bottom branches of the rooted plane trees encoded by A014486. (to opposite direction of A057509).

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 5, 7, 8, 9, 14, 10, 16, 19, 11, 15, 12, 17, 18, 13, 20, 21, 22, 23, 37, 24, 42, 51, 25, 38, 26, 44, 47, 27, 53, 56, 60, 28, 39, 29, 43, 52, 30, 40, 31, 45, 46, 32, 48, 49, 50, 33, 41, 34, 54, 55, 35, 57, 58, 59, 36, 61, 62, 63, 64, 65, 107, 66, 121, 149, 67

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

Index entries for sequences that are permutations of the natural numbers
A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)

Inverse of A057509 and the car/cdr-flipped conjugate of A069776 and also composition of A057502 & A069770, i.e. A057510(n) = A057163(A069776(A057163(n))) = A069770(A057502(n)).

Cycle counts given by A003239. Cf. also A057512, A057513.

# reverse given in A057508, for CountCycles, see A057502, for other procedures, follow A057501.
map(CatalanRankGlobal,map(RotateBottomBranchesR, A014486));
RotateBottomBranchesR := n -> pars2binexp(rotateR(binexp2pars(n)));
rotateR := a -> reverse(rotateL(reverse(a)));
RotBBPermutationCycleCounts := 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,RotateBottomBranchesL(CatalanUnrank(n,r)))]; od; a := [op(a),CountCycles(b)]; od; RETURN(a); end;
A003239 := RotBBPermutationCycleCounts(some_value); (e.g. 9. Cf. A057502, A057162)

A057161 Signature-permutation of a Catalan Automorphism: rotate one step counterclockwise the triangulations of polygons encoded by A014486.

Original entry on oeis.org

0, 1, 3, 2, 7, 8, 5, 6, 4, 17, 18, 20, 21, 22, 12, 13, 15, 16, 19, 10, 11, 14, 9, 45, 46, 48, 49, 50, 54, 55, 57, 58, 59, 61, 62, 63, 64, 31, 32, 34, 35, 36, 40, 41, 43, 44, 47, 52, 53, 56, 60, 26, 27, 29, 30, 33, 38, 39, 42, 51, 24, 25, 28, 37, 23, 129, 130, 132, 133, 134

Offset: 0

Antti Karttunen, Aug 18 2000; entry revised Jun 06 2014

nonn

This is a permutation of natural numbers induced when Euler's triangulation of convex polygons, encoded by the sequence A014486 in a straightforward way (via binary trees, cf. the illustration of the rotation of a triangulated pentagon, given in the Links section) are rotated counterclockwise.
The number of cycles in range [A014137(n-1)..A014138(n)] of this permutation is given by A001683(n+2), otherwise the same sequence as for Catalan bijections *A074679/*A074680, but shifted once left (for an explanation, see the related notes in OEIS Wiki).
E.g., in range [A014137(0)..A014138(1)] = [1,1] there is one cycle (as a(1)=1), in range [A014137(1)..A014138(2)] = [2,3] there is one cycle (as a(2)=3 and a(3)=2), in range [A014137(2)..A014138(3)] = [4,8] there is also one cycle (as a(4) = 7, a(7) = 6, a(6) = 5, a(5) = 8 and a(8) = 4), and in range [A014137(3)..A014138(4)] = [9,22] there are A001683(4+2) = 4 cycles.
From the recursive forms of A057161 and A057503 it is seen that both can be viewed as a convergent limits of a process where either the left or right side argument of A085201 in formula for A057501 is "iteratively recursivized", and on the other hand, both of these can then in turn be made to converge towards A057505 by the same method, when the other side of the formula is also "recursivized".

A. Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft), pp. 51-54.
A. Karttunen, Notes on the orbits of the related permutations A074679/A074680, OEIS Wiki.
A. Karttunen, Illustration of how the five triangulations of a pentagon will rotate, and the corresponding changes it induces in the binary trees
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057162.
Also, a "SPINE"-transform of A069774, and thus occurs as row 12 of A130403.
Other related permutations: A057163, A057164, A057501, A057504, A057505.
Cf. A001683 (cycle counts), A057544 (max cycle lengths).

a(n) = CatalanRankGlobal(RotateTriangularization(A014486[n]))
CatalanRankGlobal given in A057117 and the other Maple procedures in A038776.
NextSubBinTree := proc(nn) local n,z,c; n := nn; c := 0; z := 0; while(c < 1) do z := 2*z + (n mod 2); c := c + (-1)^n; n := floor(n/2); od; RETURN(z); end;
BinTreeLeftBranch := n -> NextSubBinTree(floor(n/2));
BinTreeRightBranch := n -> NextSubBinTree(floor(n/(2^(1+binwidth(BinTreeLeftBranch(n))))));
RotateTriangularization := proc(nn) local n,s,z,w; n := binrev(nn); z := 0; w := 0; while(1 = (n mod 2)) do s := BinTreeRightBranch(n); z := z + (2^w)*s; w := w + binwidth(s); z := z + (2^w); w := w + 1; n := floor(n/2); od; RETURN(z); end;

a(0) = 0, and for n>=1, a(n) = A085201(a(A072771(n)), A057548(A072772(n))). [This formula reflects the S-expression implementation given first in the Program section: A085201 is a 2-ary function corresponding to 'append', A072771 and A072772 correspond to 'car' and 'cdr' (known also as first/rest or head/tail in some languages), and A057548 corresponds to unary form of function 'list'.]
As a composition of related permutations:
a(n) = A069767(A069769(n)).
a(n) = A057163(A057162(A057163(n))).
a(n) = A057164(A057504(A057164(n))). [For a proof, see pp. 53-54 in the "Introductory survey ..." draft]

A057503 Signature-permutation of a Catalan Automorphism: Deutsch's 1998 bijection on Dyck paths.

Original entry on oeis.org

0, 1, 3, 2, 8, 7, 5, 4, 6, 22, 21, 18, 17, 20, 13, 12, 10, 9, 11, 15, 14, 16, 19, 64, 63, 59, 58, 62, 50, 49, 46, 45, 48, 55, 54, 57, 61, 36, 35, 32, 31, 34, 27, 26, 24, 23, 25, 29, 28, 30, 33, 41, 40, 38, 37, 39, 43, 42, 44, 47, 52, 51, 53, 56, 60, 196, 195, 190, 189, 194

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

Deutsch shows in his 1998 paper that this automorphism maps the number of returns of Dyck path to the height of the last peak, i.e., that A057515(n) = A080237(A057503(n)) holds for all n, thus the two parameters have the same distribution.

From the recursive forms of A057161 and A057503 it is seen that both can be viewed as a convergent limits of a process where either the left or right side argument of A085201 in formula for A057501 is "iteratively recursivized", and on the other hand, both of these can then in turn be made to converge towards A057505, when the other side of the formula is also "recursivized" in the same way. - Antti Karttunen, Jun 06 2014

Antti Karttunen, Table of n, a(n) for n = 0..2055
Emeric Deutsch, A bijection on Dyck paths and its consequences, Discrete Math., 179 (1998), 253-256.
Antti Karttunen, C program which computes this sequence..
Antti Karttunen, Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft), pp. 53-54.
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057504. Row 17 of A122285. Cf. A057501, A057161, A057505.

The number of cycles, count of the fixed points, maximum cycle sizes and LCM's of all cycle sizes in range [A014137(n-1)..A014138(n)] of this permutation are given by LEFT(LEFT(A001683)), LEFT(A019590), A057544 and A057544, the same sequences as for A057162 because this is a conjugate of it (cf. the Formula section).

a(0) = 0, and for n >= 1, a(n) = A085201(A072771(n), A057548(a(A072772(n)))). [This formula reflects the S-expression implementation given first in the Program section: A085201 is a 2-ary function corresponding to 'append', A072771 and A072772 correspond to 'car' and 'cdr' (known also as first/rest or head/tail in some languages), and A057548 corresponds to the unary form of function 'list'].
a(n) = A057164(A057162(A057164(n))). [For the proof, see pp. 53-54 in the "Introductory survey ..." draft, eq. 144.]
Other identities:
A057515(n) = A080237(a(n)) holds for all n. [See the Comments section.]

Equivalence with Emeric Deutsch's 1998 bijection realized Dec 15 2006 and entry edited accordingly by Antti Karttunen, Jan 16 2007

cp's OEIS Frontend

A057163 Signature-permutation of a Catalan automorphism: Reflect a rooted plane binary tree; Deutsch's 1998 involution on Dyck paths.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A073200 Number of simple Catalan bijections of type B.

Views

Author

Keywords

Comments

Links

Crossrefs

A057506 Signature-permutation of a Catalan Automorphism: (inverse of) "Donaghey's map M", acting on the parenthesizations encoded by A014486.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Scheme

Formula

Extensions

A074679 Signature permutation of a Catalan automorphism: Rotate binary tree left if possible, otherwise swap its sides.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A069768 Signature-permutation of Catalan bijection "Knack".

Views

Author

Keywords

Comments

References

Links

Crossrefs

A001683 Number of one-sided triangulations of the disk; or flexagons of order n; or unlabeled plane trivalent trees (n-2 internal vertices, all of degree 3 and hence n leaves).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A130402 Signature permutations of ENIPS-transformations of A057163-conjugates of Catalan automorphisms in table A122203.

Views

Author

Keywords

Comments

Crossrefs

A057510 Permutation of natural numbers: rotations of the bottom branches of the rooted plane trees encoded by A014486. (to opposite direction of A057509).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A057161 Signature-permutation of a Catalan Automorphism: rotate one step counterclockwise the triangulations of polygons encoded by A014486.

Views

Author

Keywords