A057506 -id:A057506 - cp's OEIS frontend

A081158 Number of even cycles in range [A014137(2n-1)..A014138(2n-1)] of permutation A057505/A057506, with no fixed points of A057164.

Original entry on oeis.org

0, 0, 0, 8, 60, 402, 2474, 14496, 84282, 492048

Offset: 0

Wouter Meeussen and Antti Karttunen, Mar 10 2003

Cf. A081157, A081151, A001700.

Cf. A014137, A014138, A057505, A057506, A057164.

a(n) = A081157(2n) = A081151(n) - A001700(n-1) [where A001700(-1) is taken as 0 here].

A081159 Number of even cycles in range [A014137(2n)..A014138(2n)] of permutation A057505/A057506, with no fixed points of either A057163 or A057164.

Original entry on oeis.org

0, 0, 2, 20, 148, 986, 5918, 34708, 202664

Offset: 0

Wouter Meeussen and Antti Karttunen, Mar 10 2003

Cf. A081157, A014137, A014138, A057505, A057506, A057163, A057164.

a(n) = A081157(2n+1).

A081161 Number of even cycles in range [A014137(2n)..A014138(2n)] of permutation A057505/A057506, with two fixed-points of A057164.

Original entry on oeis.org

0, 1, 4, 16, 60, 225, 848, 3188, 12095

Offset: 0

Wouter Meeussen and Antti Karttunen, Mar 10 2003

Cf. A081160, A014137, A014138, A057505, A057506, A057164.

a(n) = A081160(2n+1).

A081149 Number of odd cycles in range [A014137(2n)..A014138(2n)] of permutation A057505/A057506.

Original entry on oeis.org

1, 1, 4, 9, 24, 62, 162, 447, 1234

Offset: 0

Wouter Meeussen and Antti Karttunen, Mar 10 2003

Cf. A014137, A014138, A057505, A057506, A081148.

a(n) = A081148(2n+1).

A081154 Number of odd cycles in range [A014137(2n)..A014138(2n)] of permutation A057505/A057506, with no fixed points of either A057163 or A057164.

Original entry on oeis.org

0, 0, 2, 6, 18, 50, 142, 388, 1114

Offset: 0

Wouter Meeussen and Antti Karttunen, Mar 10 2003

Cf. A081153, A014137, A014138, A057505, A057506, A057163, A057164.

a(n) = A081153(2n+1).

A081167 Number of cycles in range [A014137(2n)..A014138(2n)] of permutation A057505/A057506.

Original entry on oeis.org

1, 2, 10, 46, 236, 1288, 6984, 38528, 216648, 1240818

Offset: 0

Wouter Meeussen and Antti Karttunen, Mar 10 2003

Cf. A057507, A081151, A014137, A014138, A057505, A057506.

a(n) = A057507(2n+1).

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

Original entry on oeis.org

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".

A057164 Self-inverse permutation of natural numbers induced by reflections of the rooted plane trees and mountain ranges encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Aug 18 2000

nonn

CatalanRankGlobal given in A057117 and the other Maple procedures in A056539.

Composition with A057163 gives Donaghey's Map M (A057505/A057506).

			a(10)=14 and a(14)=10, A014486[10] = 172 (10101100 in binary), A014486[14] = 202 (11001010 in binary) and these encode the following mountain ranges (and the corresponding rooted plane trees), which are reflections of each other:
...../\___________/\
/\/\/__\_________/__\/\/\
...
...../...........\
..\|/.............\|/

Rémy Sigrist, Table of n, a(n) for n = 0..6917 (first 197 terms from Indranil Ghosh)
Antti Karttunen, Gatomorphisms (includes the complete Scheme program for computing this sequence).
Antti Karttunen, C program which implements this Catalan bijection.
Indranil Ghosh, Python program for computing the sequence.
Rémy Sigrist, PARI program.
Index entries for signature-permutations induced by Catalan automorphisms

A057123(A057163(n)) = A057164(A057123(n)) for all n. Also the car/cdr-flipped conjugate of A069787, i.e., A057164(n) = A057163(A069787(A057163(n))). Fixed terms are given by A061856. Cf. also A057508, A069772.

Row 2 of tables A122287 and A122288.

a(n) = CatalanRankGlobal(runcounts2binexp(reverse(binexp2runcounts(A014486[n])))) # i.e., reverse and complement the totally balanced binary sequences

PARI
```
See Links section.
```

a(n) = A080300(A036044(A014486(n))) = A080300(A056539(A014486(n))).

A057505 Signature-permutation of a Catalan Automorphism: Donaghey's map M acting on the parenthesizations encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

This is equivalent to map M given by Donaghey on page 81 of his paper "Automorphisms on ..." and also equivalent to the transformation procedure depicted in the picture (23) of Donaghey-Shapiro paper.

This can be also considered as a "more recursive" variant of A057501 or A057503 or A057161.

D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees--History of Combinatorial Generation, vi+120pp. ISBN 0-321-33570-8 Addison-Wesley Professional; 1ST edition (Feb 06, 2006).

Antti Karttunen, Table of n, a(n) for n = 0..2055
Robert Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
Robert Donaghey and Louis W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, Vol. 23, No. 3 (1977), pp. 291-301.
Indranil Ghosh, Python program for computing this sequence (after the functions mentioned in the OEIS wiki).
Antti Karttunen, Illustration of symmetric general trees whose A057163-reflection is also symmetric (ones that occur in 2-cycles of A057505/A057506)
Antti Karttunen, On the fixed points of A071661 (Notes in OEIS Wiki regarding the 2-cycles of this automorphism)
D. E. Knuth, Pre-Fascicle 4a: Generating All Trees, Exercise 17, 7.2.1.6.
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057506.
The 2nd, 3rd, 4th, 5th and 6th "power": A071661, A071663, A071665, A071667, A071669.
Other related permutations: A057501, A057503, A057161.
Cycle counts: A057507. Maximum cycle lengths: A057545. LCM's of all cycles: A060114. See A057501 for other Maple procedures.
Row 17 of table A122288.
Cf. A080981 (the "primitive elements" of this automorphism), A079438, A079440, A079442, A079444, A080967, A080968, A080972, A080272, A080292, A083929, A080973, A081164, A123050, A125977, A126312.

map(CatalanRankGlobal,map(DonagheysM, A014486)); or map(CatalanRankGlobal,map(DeepRotateTriangularization, A014486));
DonagheysM := n -> pars2binexp(DonagheysMP(binexp2pars(n)));
DonagheysMP := h -> `if`((0 = nops(h)),h,[op(DonagheysMP(car(h))),DonagheysMP(cdr(h))]);
DeepRotateTriangularization := proc(nn) local n,s,z,w; n := binrev(nn); z := 0; w := 0; while(1 = (n mod 2)) do s := DeepRotateTriangularization(BinTreeRightBranch(n))*2; 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(a(A072772(n)))). [This recurrence 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) = A057164(A057163(n)).
a(n) = A057163(A057506(A057163(n))).

cp's OEIS Frontend

A081158 Number of even cycles in range [A014137(2n-1)..A014138(2n-1)] of permutation A057505/A057506, with no fixed points of A057164.

Views

Author

Keywords

Crossrefs

Formula

A081159 Number of even cycles in range [A014137(2n)..A014138(2n)] of permutation A057505/A057506, with no fixed points of either A057163 or A057164.

Views

Author

Keywords

Crossrefs

Formula

A081161 Number of even cycles in range [A014137(2n)..A014138(2n)] of permutation A057505/A057506, with two fixed-points of A057164.

Views

Author

Keywords

Crossrefs

Formula

A081149 Number of odd cycles in range [A014137(2n)..A014138(2n)] of permutation A057505/A057506.

Views

Author

Keywords

Crossrefs

Formula

A081154 Number of odd cycles in range [A014137(2n)..A014138(2n)] of permutation A057505/A057506, with no fixed points of either A057163 or A057164.

Views

Author

Keywords

Crossrefs

Formula

A081167 Number of cycles in range [A014137(2n)..A014138(2n)] of permutation A057505/A057506.

Views

Author

Keywords

Crossrefs

Formula

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

A057164 Self-inverse permutation of natural numbers induced by reflections of the rooted plane trees and mountain ranges encoded by A014486.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A057505 Signature-permutation of a Catalan Automorphism: Donaghey's map M acting on the parenthesizations encoded by A014486.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Formula