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

A125976 Signature-permutation of Kreweras' 1970 involution on Dyck paths.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jan 02 2007

nonn

Lalanne shows in the 1992 paper that this automorphism preserves the sum of peak heights, i.e., that A126302(a(n)) = A126302(n) for all n. Furthermore, he also shows that A126306(a(n)) = A057514(n)-1 and likewise, that A057514(a(n)) = A126306(n)+1, for all n >= 1.
Like A069772, this involution keeps symmetric Dyck paths symmetric, but not necessarily same.
The number of cycles and fixed points in range [A014137(n-1)..A014138(n-1)] of this involution seem to be given by A007595 and the "aerated" Catalan numbers [1, 1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, ...], thus this is probably a conjugate of A069770 (as well as of A057163).

A. Karttunen, Table of n, a(n) for n = 0..2055
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41.
J.-C. Lalanne, Une Involution sur les Chemins de Dyck, European J. Combin. 13 (1992), no. 6, 477-487.
Index entries for signature-permutations of Catalan automorphisms

Cf. A080300, A125974, A014486.
Cf. A057163, A069770, A007595, A014137, A014138.
Compositions and conjugations with other automorphisms: A125977-A125979, A125980, A126290.

a(n) = A080300(A125974(A014486(n))).

A127284 a(n) = number of valleys (DU-steps) in the Dyck path encoded by A014486(n).

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 1, 1, 0, 3, 2, 2, 2, 1, 2, 1, 2, 2, 1, 1, 1, 1, 0, 4, 3, 3, 3, 2, 3, 2, 3, 3, 2, 2, 2, 2, 1, 3, 2, 2, 2, 1, 3, 2, 3, 3, 2, 2, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 2, 1, 1, 1, 1, 1, 0, 5, 4, 4, 4, 3, 4, 3, 4, 4, 3, 3, 3, 3, 2, 4, 3, 3, 3, 2, 4, 3, 4, 4, 3, 3, 3, 3, 2, 3, 2, 3, 3, 2, 3, 3, 3, 2

Offset: 0

Antti Karttunen, Jan 16 2007

nonn

			A014486(2) = 10 (1010 in binary) which encodes Dyck path /\/\ with two peaks and one valley, thus a(2)=1.
A014486(12) = 180 (10110100 in binary) which encodes Dyck path:
..../\/\...
./\/....\..
which has two valleys, thus a(12) = 2.

a(A057163(n)) = A126306(n), a(n) = A126306(A057163(n)) for all n. Cf. A057516.

(define (A127284 n) (if (zero? n) 0 (- (A057514 n) 1)))

a(0)=0, a(n) = A057514(n)-1.

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

A125976 Signature-permutation of Kreweras' 1970 involution on Dyck paths.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A127284 a(n) = number of valleys (DU-steps) in the Dyck path encoded by A014486(n).

Views

Author

Keywords

Examples

Crossrefs

Programs

Scheme

Formula