A069775 -id:A069775 - 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

A057509 Permutation of natural numbers: rotations of the bottom branches of the rooted plane trees encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

The number of objects (rooted planar trees, mountain ranges, parenthesizations) fixed by this permutation can be computed with procedure fixedcount, which gives A034731.

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 A057510 and the car/cdr-flipped conjugate of A069775 and also composition of A069770 & A057501, i.e. A057509(n) = A057163(A069775(A057163(n))) = A057501(A069770(n)).

Cycle counts given by A003239. Cf. also A057511.

map(CatalanRankGlobal,map(RotateBottomBranchesL, A014486));
RotateBottomBranchesL := n -> pars2binexp(rotateL(binexp2pars(n)));
rotateL := proc(a) if 0 = nops(a) then (a) else [op(cdr(a)), a[1]]; fi; end;
fixedcount := proc(n) local d,z; z := 0; for d in divisors(n) do z := z+C(d-1); od; RETURN(z); end;

A069773 Permutation of natural numbers induced by the automorphism RoblDownCar_et_Swap! acting on the parenthesizations encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Apr 16 2002

nonn

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

Inverse of A069774, the car/cdr-flipped conjugate of A057501, i.e. A069773(n) = A057163(A057501(A057163(n))). Cf. also A069775.

A069776 Permutation of natural numbers induced by the automorphism gma069776! acting on the parenthesizations encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Apr 16 2002

nonn

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

Inverse of A069775. a(n) = A057163(A057510(A057163(n))) = A069770(A069774(n)). Cf. also A069787, A072797.

Number of cycles: A003239. Number of fixed points: A034731. Max. cycle size: A028310. LCM of cycle sizes: A003418. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A130935 Signature permutation of a Catalan automorphism: row 2 of A130402.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 11 2007

nonn

The signature-permutation of the Catalan automorphism which is derived from *A069775 with recursion schema ENIPS (see A122204 for the definition).

Inverse: A130936. The number of cycles in range [A014137(n-1)..A014138(n-1)] of this permutation are given by A130969. The number of fixed points begins like A003238. Maximum cycle sizes begins like A000792 (shifted once right).

A122313 Row 8 of A122283.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 01 2006

nonn

The signature-permutation of the automorphism which is derived from the eighth non-recursive automorphism *A072797 with recursion schema DEEPEN (see A122283 for the definition).

Index entries for signature-permutations of Catalan automorphisms

Inverse: A122314. A082325(n) = A083927(A122313(A057123(n))). Differs from A069775 for the first time at n=34, where a(n)=35, while A069775(n)=34.

cp's OEIS Frontend

A082337 Duplicate of A069775.

Views

Author

Keywords

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

A057509 Permutation of natural numbers: rotations of the bottom branches of the rooted plane trees encoded by A014486.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A069773 Permutation of natural numbers induced by the automorphism RoblDownCar_et_Swap! acting on the parenthesizations encoded by A014486.

Views

Author

Keywords

Links

Crossrefs

A069776 Permutation of natural numbers induced by the automorphism gma069776! acting on the parenthesizations encoded by A014486.

Views

Author

Keywords

Links

Crossrefs

A130935 Signature permutation of a Catalan automorphism: row 2 of A130402.

Views

Author

Keywords

Comments

Links

Crossrefs

A122313 Row 8 of A122283.

Views

Author

Keywords

Comments

Links

Crossrefs