%I #11 Mar 31 2012 13:21:09
%S 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 31,58,28,54,42,26,49,51,40,35,63,25,48,39,34,62,30,57,44,24,46,56,38,
%U 32,59,33,61,53,29,55,47,43,27,50,60,52,41,36,64,65,129,107,87,170
%N Involution of natural numbers induced by Catalan Automorphism *A085161 acting on symbolless S-expressions encoded by A014486/A063171.
%C 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 A. Karttunen, <a href="http://oeis.org/wiki/Catalan_Automorphisms">Catalan Automorphisms</a>
%H 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 <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations induced by Catalan automorphisms</a>
%e 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 ..................................................
%e ...._____..___....................................
%e ...|.|...||...|...................................
%e ...|.||..|||..|...................._.___...___....
%e ...|.||..|||..|...................|.|...|.|...|...
%e ...|.||..||/\.|....i.e..equal.to..|.|.|.|.|.|.|...
%e ...|.|/\.|/..\/\..................|.|.|.|.|.|.|...
%e .../\/..\/......\.................|.|.|.|.|.|.|...
%e ...10110011100100=11492=A014486(250)..............
%e ...()(())((())()).................................
%e Now this automorphism gives the parenthesization such that the corresponding Murasaki-diagram is a reflection of the original one:
%e ....___.._____....................................
%e ...|...||...|.|...................................
%e ...||..|||..|.|....................___..._____....
%e ...||..|||..|.|...................|...|.|...|.|...
%e ...||..||/\.|.|....i.e..equal.to..|.|.|.|.|.|.|...
%e ...|/\.|/..\/\/\..................|.|.|.|.|.|.|...
%e .../..\/........\.................|.|.|.|.|.|.|...
%e ...11001110010100=13204=A014486(360)..............
%e ...(())((())()()).................................
%e So we have A085161(250)=360 and A085161(360)=250.
%o (Scheme function implementing this automorphism on list-structures:)
%o (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 (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 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 Number of cycles: A007123. Number of fixed points: A001405 (in each range limited by A014137 and A014138).
%K nonn
%O 0,3
%A _Antti Karttunen_, Jun 23 2003
|