A057501 Signature-permutation of a Catalan Automorphism: Rotate non-crossing chords (handshake) arrangements; rotate the root position of general trees as encoded by A014486.
0, 1, 3, 2, 7, 8, 5, 4, 6, 17, 18, 20, 21, 22, 12, 13, 10, 9, 11, 15, 14, 16, 19, 45, 46, 48, 49, 50, 54, 55, 57, 58, 59, 61, 62, 63, 64, 31, 32, 34, 35, 36, 26, 27, 24, 23, 25, 29, 28, 30, 33, 40, 41, 38, 37, 39, 43, 42, 44, 47, 52, 51, 53, 56, 60, 129, 130, 132, 133, 134
Offset: 0
Keywords
Links
- Antti Karttunen, Table of n, a(n) for n = 0..2055
- A. Karttunen, Introductory Survey of Catalan Automorphisms and Bijections (an unfinished draft), pp. 56-57.
- A. Karttunen et al, Combinatorial interpretations of Catalan numbers, OEIS Wiki.
- Torsten Mütze, Proof of the middle levels conjecture, arXiv preprint arXiv:1404.4442 [math.CO], 2014 (p. 24).
- R. P. Stanley, Exercises on Catalan and Related Numbers (This sequence is concerned with rotations of the interpretations (e) and (n) in the Exercise 19)
- Index entries for signature-permutations of Catalan automorphisms
Crossrefs
Inverse: A057502.
Also, a "SPINE"-transform of A074680, and thus occurs as row 17 of A122203. (Also as row 65167 of A130403.)
Successive powers of this permutation, a^2(n) - a^6(n): A082315, A082317, A082319, A082321, A082323.
Programs
-
Maple
map(CatalanRankGlobal,map(RotateHandshakes, A014486)); RotateHandshakes := n -> pars2binexp(RotateHandshakesP(binexp2pars(n))); RotateHandshakesP := h -> `if`((0 = nops(h)),h,[op(car(h)),cdr(h)]); # This does the trick! In Lisp: (defun RotateHandshakesP (h) (append (car h) (list (cdr h)))) car := proc(a) if 0 = nops(a) then ([]) else (op(1,a)): fi: end: # The name is from Lisp, takes the first element (head) of the list. cdr := proc(a) if 0 = nops(a) then ([]) else (a[2..nops(a)]): fi: end: # As well. Takes the rest (the tail) of the list. PeelNextBalSubSeq := proc(nn) local n,z,c; if(0 = nn) then RETURN(0); fi; n := nn; c := 0; z := 0; while(1 = 1) do z := 2*z + (n mod 2); c := c + (-1)^n; n := floor(n/2); if(c >= 0) then RETURN((z - 2^(floor_log_2(z)))/2); fi; od; end; RestBalSubSeq := proc(nn) local n,z,c; n := nn; c := 0; while(1 = 1) do c := c + (-1)^n; n := floor(n/2); if(c >= 0) then break; fi; od; z := 0; c := -1; while(1 = 1) do z := 2*z + (n mod 2); c := c + (-1)^n; n := floor(n/2); if(c >= 0) then RETURN(z/2); fi; od; end; pars2binexp := proc(p) local e,s,w,x; if(0 = nops(p)) then RETURN(0); fi; e := 0; for s in p do x := pars2binexp(s); w := floor_log_2(x); e := e * 2^(w+3) + 2^(w+2) + 2*x; od; RETURN(e); end; binexp2pars := proc(n) option remember; `if`((0 = n),[],binexp2parsR(binrev(n))); end; binexp2parsR := n -> [binexp2pars(PeelNextBalSubSeq(n)),op(binexp2pars(RestBalSubSeq(n)))]; # Procedure CatalanRankGlobal given in A057117, other missing ones in A038776.
Formula
a(0) = 0, and for n>=1, a(n) = A085201(A072771(n), A057548(A072772(n))). [This formula reflects directly the given non-destructive Lisp/Scheme function: A085201 is a 2-ary function corresponding to 'append', A072771 and A072772 correspond to 'car' and 'cdr' (known also as first/rest or head/tail in some dialects), and A057548 corresponds to unary form of function 'list'].
As a composition of related permutations:
Invariance-identities:
Comments