cp's OEIS Frontend

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

%I A057163 #36 Jan 14 2024 08:58:50
%S A057163 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,
%T A057163 59,58,61,57,55,50,49,54,48,46,45,60,56,53,47,44,52,43,41,36,35,40,34,
%U A057163 32,31,51,42,39,33,30,38,29,27,26,37,28,25,24,23,196,195,194,190,189
%N A057163 Signature-permutation of a Catalan automorphism: Reflect a rooted plane binary tree; Deutsch's 1998 involution on Dyck paths.
%C A057163 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.
%C A057163 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.
%C 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.
%H A057163 JungHwan Min, <a href="/A057163/b057163.txt">Table of n, a(n) for n = 0..10000</a>
%H A057163 Emeric Deutsch, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00370-7">An involution on Dyck paths and its consequences</a>, Discrete Math., 204 (1999), no. 1-3, 163-166.
%H A057163 Indranil Ghosh, <a href="/A057163/a057163.txt">Python program for computing this sequence, translated from Maple code</a>.
%H A057163 Antti Karttunen, <a href="/A089408/a089408.c.txt">C program which computes this sequence</a>.
%H A057163 Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, <a href="https://arxiv.org/abs/2012.04625">Finding structure in sequences of real numbers via graph theory: a problem list</a>, arXiv:2012.04625, Dec 08, 2020.
%H A057163 <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations induced by Catalan automorphisms</a>
%F A057163 a(n) = A083927(A057164(A057123(n))).
%e A057163 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:
%e A057163     0   0             0   0
%e A057163      \ /               \ /
%e A057163       1   0         0   1
%e A057163        \ /           \ /
%e A057163     0   1             1   0
%e A057163      \ /               \ /
%e A057163       1                 1
%e A057163 thus a(5)=7 and a(7)=5.
%p A057163 a(n) = A080300(ReflectBinTree(A014486(n)))
%p A057163 ReflectBinTree := n -> ReflectBinTree2(n)/2; ReflectBinTree2 := n -> (`if`((0 = n),n,ReflectBinTreeAux(A030101(n))));
%p A057163 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;
%p A057163 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;
%p A057163 BinTreeLeftBranch := n -> NextSubBinTree(floor(n/2));
%p A057163 BinTreeRightBranch := n -> NextSubBinTree(floor(n/(2^(1+A070939(BinTreeLeftBranch(n))))));
%t A057163 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 *)
%o A057163 (Scheme implementations of this automorphism that acts on S-expressions, i.e., list-structures:)
%o A057163 (CONSTRUCTIVE IMPLEMENTATION:) (define (*A057163 s) (cond ((not (pair? s)) s) (else (cons (*A057163 (cdr s)) (*A057163 (car s))))))
%o A057163 (DESTRUCTIVE IMPLEMENTATION:) (define (*A057163! s) (cond ((pair? s) (*A069770! s) (*A057163! (car s)) (*A057163! (cdr s)))) s)
%Y A057163 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))).
%Y A057163 Row 1 of tables A122201 and A122202, that is, obtained with FORK (and KROF) transformation from even simpler automorphism *A069770. Cf. A122351.
%K A057163 nonn
%O A057163 0,3
%A A057163 _Antti Karttunen_, Aug 18 2000
%E A057163 Equivalence with Deutsch's 1998 involution realized Dec 15 2006 and entry edited accordingly by _Antti Karttunen_, Jan 16 2007