cp's OEIS Frontend

A085161 Involution of natural numbers induced by Catalan Automorphism *A085161 acting on symbolless S-expressions encoded by A014486/A063171.

%I A085161 #11 Mar 31 2012 13:21:09
%S A085161 0,1,2,3,4,7,6,5,8,9,17,14,12,21,11,20,16,10,18,19,15,13,22,23,45,37,
%T A085161 31,58,28,54,42,26,49,51,40,35,63,25,48,39,34,62,30,57,44,24,46,56,38,
%U A085161 32,59,33,61,53,29,55,47,43,27,50,60,52,41,36,64,65,129,107,87,170
%N A085161 Involution of natural numbers induced by Catalan Automorphism *A085161 acting on symbolless S-expressions encoded by A014486/A063171.
%C A085161 This automorphism reflects the interpretations (pp)-(rr) of Stanley, obtained from the Dyck paths with the "rising slope mapping" illustrated on the example lines.
%H A085161 A. Karttunen, <a href="http://oeis.org/wiki/Catalan_Automorphisms">Catalan Automorphisms</a>
%H A085161 R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/ec/catalan.pdf">Exercises on Catalan and Related Numbers</a> (including 66 combinatorial interpretations)
%H A085161 <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations induced by Catalan automorphisms</a>
%e A085161 Map the Dyck paths (Stanley's interpretation (i)) to noncrossing Murasaki-diagrams (Stanley's interpretation (rr)) by drawing a vertical line above each rising slope / and connect those vertical lines that originate from the same height without any lower valleys between, as in illustration below:
%e A085161 ..................................................
%e A085161 ...._____..___....................................
%e A085161 ...|.|...||...|...................................
%e A085161 ...|.||..|||..|...................._.___...___....
%e A085161 ...|.||..|||..|...................|.|...|.|...|...
%e A085161 ...|.||..||/\.|....i.e..equal.to..|.|.|.|.|.|.|...
%e A085161 ...|.|/\.|/..\/\..................|.|.|.|.|.|.|...
%e A085161 .../\/..\/......\.................|.|.|.|.|.|.|...
%e A085161 ...10110011100100=11492=A014486(250)..............
%e A085161 ...()(())((())()).................................
%e A085161 Now this automorphism gives the parenthesization such that the corresponding Murasaki-diagram is a reflection of the original one:
%e A085161 ....___.._____....................................
%e A085161 ...|...||...|.|...................................
%e A085161 ...||..|||..|.|....................___..._____....
%e A085161 ...||..|||..|.|...................|...|.|...|.|...
%e A085161 ...||..||/\.|.|....i.e..equal.to..|.|.|.|.|.|.|...
%e A085161 ...|/\.|/..\/\/\..................|.|.|.|.|.|.|...
%e A085161 .../..\/........\.................|.|.|.|.|.|.|...
%e A085161 ...11001110010100=13204=A014486(360)..............
%e A085161 ...(())((())()()).................................
%e A085161 So we have A085161(250)=360 and A085161(360)=250.
%o A085161 (Scheme function implementing this automorphism on list-structures:)
%o A085161 (define (*A085161 s) (cond ((null? s) s) (else (let ((u (reverse s))) (app-to-xrt (*A085161 (car u)) (append (map *A085161 (cdr u)) (list (list))))))))
%o A085161 (define (app-to-xrt a b) (cond ((null? a) b) ((pair? (cdr a)) (cons (car a) (app-to-xrt (cdr a) b))) (else (cons (app-to-xrt (car a) b) (cdr a)))))
%Y A085161 a(n) = A085163(A057508(n)) = A074684(A057164(A074683(n))). Occurs in A073200. Cf. also A085159, A085160, A085162, A085175. Alternative mappings illustrated in A086431 & A085169.
%Y A085161 Number of cycles: A007123. Number of fixed points: A001405 (in each range limited by A014137 and A014138).
%K A085161 nonn
%O A085161 0,3
%A A085161 _Antti Karttunen_, Jun 23 2003