A Brief Survey on Gatomorphisms.

1. A069770 - Swap binary tree sides
2. A072796 - Exchange the two leftmost branches of general trees if the degree of root > 1, otherwise keep the tree intact
3. A057163 - Reflect binary trees and polygon triangulations
4. A069767/A069768 - Swap recursively the other side of binary tree
5. A057511/A057512 - Deep Rotate general trees and parenthesizations
6. A057509/A057510 - Shallow Rotate general trees and parenthesizations
7. A057164 - Deep Reverse general trees and parenthesizations
8. A057508 - Shallow Reverse general trees and parenthesizations
9. A057501/A057502 - Rotate non-crossing chords (handshake) arrangements; Rotate root position of the general trees
10. A057161/A057162 - Rotate polygon triangulations
11. A074679/A074680 - Rotate binary tree, if possible, otherwise swap its sides
12. A057503/A057504 - Gatomorphism A057503/A057504
13. A057505/A057506 - Donaghey's M
14. A071655/A071656 - Rotate binary tree if possible and recurse down both branches, otherwise apply swap and terminate
15. A074681/A074682 - Gatomorphism A074681/A074682
16. A074683/A074684 - Gatomorphism A074683/A074684
17. A069773/A069774 - The car/cdr-flipped conjugate of handshake rotate
18. A069787 - The car/cdr-flipped conjugate of deep reverse
19. A069769 - The car/cdr-flipped conjugate of shallow reverse
20. A069888 - Reflect non-crossing chords by the axis through corners (WM)
21. A069771 - Rotate non-crossing chords by 180 degrees
22. A069772 - Reflect non-crossing chords by X-axis
23. A072088/A072089 - Meeussen's breadth-first <-> depth-first conversion for general trees
24. A057117/A057118 - Meeussen's breadth-first <-> depth-first conversion for binary trees

A069770

Description:

Swap binary tree sides.

Fixes:

binary trees whose both sides are identical.

Counted by A000108: = 1,1,0,1,0,2,0,5,...

Cycles correspond to:

rooted planar binary trees upto left-right swap.

necklaces of n+1 white beads and n-1 black beads. [Correspondence with above requires Raney's lemma.].

Counted by A007595: = 1,1,1,3,7,22,66,217,...

Max. cycle lengths given by:

A0????? = 1,1,2,2,2,2,2,2,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,2,2,2,2,2,2,...

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A069770: as the row 0.

Scheme functions implementing this gatomorphism on S-expressions:

Constructive variant:

(define (gma069770 s)
  (cond ((not (pair? s)) s)
        (else (cons (cdr s) (car s)))))

Destructive variant:

(define (gma069770! s)
  (if (pair? s)
      (swap! s))
  s)

The effect of this gatomorphism on the forest Cat[3] viewed as binary trees, polygon triangulations, parenthesizations and Lukasiewicz-words.

(()()())	((()()))		(()(()))	(((())))		((())())
3000	1200		2010	1110		2100

A072796

Description:

Exchange the two leftmost branches of general trees if the degree of root > 1, otherwise keep the tree intact.

Fixes:

general plane trees whose root degree is either 1, or the two leftmost branches of the root are identical.

Counted by A073190: = 1,1,2,3,8,20,60,181,...

Cycles correspond to:

Counted by A073191: = 1,1,2,4,11,31,96,305,...

Max. cycle lengths given by:

A0????? = 1,1,1,2,2,2,2,2,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,1,2,2,2,2,2,...

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A072796: as the row 1.

Scheme functions implementing this gatomorphism on S-expressions:

Constructive variant:

(define (gma072796 s)
  (cond ((not (pair? s)) s)
        ((not (pair? (cdr s))) s)
        (else (cons (cadr s) (cons (car s) (cddr s))))))

Destructive variant:

(define (gma072796! s)
  (cond ((not (pair? s)) s)
        ((not (pair? (cdr s))) s)
        (else (swap! s) (robr! s) (swap! (cdr s)) s)))

The effect of this gatomorphism on the forest Cat[4] viewed as general trees, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\ /\/ \/\	/\ / \/\/\		/\/\ /\/ \	/\/\ / \/\		/\ / \ /\/ \	/\ / \ / \/\
(()(())())	((())()())		(()(()()))	((()())())		(()((())))	(((()))())
30100	31000		20200	22000		20110	21100
/\/\/\/\		/\ /\/\/ \		/\ /\ / \/ \		/\/\/\ / \
(()()()())		(()()(()))		((())(()))		((()()()))
40000		30010		21010		13000
/\ /\/ \ / \		/\ / \/\ / \		/\/\ / \ / \		/\ / \ / \ / \
((()(())))		(((())()))		(((()())))		((((()))))
12010		12100		11200		11110

A057163

Description:

Reflect binary trees and polygon triangulations.

Fixes:

binary trees whose left and right side are mirror images of each other.

Counted by A000108: = 1,1,0,1,0,2,0,5,...

Cycles correspond to:

rooted planar binary trees upto reflection.

necklaces of n+1 white beads and n-1 black beads. [Correspondence with above requires Raney's lemma.].

Counted by A007595: = 1,1,1,3,7,22,66,217,...

Max. cycle lengths given by:

A0????? = 1,1,2,2,2,2,2,2,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,2,2,2,2,2,2,...

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A057163: as the row 2.

Scheme functions implementing this gatomorphism on S-expressions:

Constructive variant:

(define (gma057163 s)
  (cond ((not (pair? s)) s)
        (else (cons (gma057163 (cdr s)) (gma057163 (car s))))))

Destructive variant:

(define (gma057163! s)
  (cond ((pair? s) (swap! s) (gma057163! (car s)) (gma057163! (cdr s))))
  s)

The effect of this gatomorphism on the forest Cat[3] viewed as binary trees, polygon triangulations, parenthesizations and Lukasiewicz-words.

(()()())	(((())))		(()(()))	((()()))		((())())
3000	1110		2010	1200		2100

A069767/A069768

Description:

Swap recursively the other side of binary tree.

Fixes:

complete binary trees [with leaves all on the same level].

Counted by A036987: = 1,1,0,1,0,0,0,1,...

Cycles correspond to:

Counted by A073431: = 1,1,1,2,3,6,12,28,...

Max. cycle lengths and L.C.M.s of all cycle lengths given by:

A011782 =

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A069767: as the row 6.

A069768: as the row 8.

Notes:

In each forest of Cat[n] binary trees of n internal (branching nodes), there is a subset of 2^n-1 binary trees whose height (i.e. max depth) is equal to their size. This gatomorphism keeps that subset closed, and furthermore, it acts transitively on it, i.e. those trees form a single cycle of their own, as can be seen below. If we let the root node stand for the least significant bit, and the next-to-top node on those trees stand the most significant bit, and mark 0 when the next node upwards is at the right, and 1 when it is at left, we get the sequence of binary words (in this case, of three bits) shown below on the top of the eight binary trees belonging to that closed cycle.
It is easy to see that this gatomorphism induces the well-known binary wrap-around ("odometer") increment/decrement algorithm on the binary strings that are in bijective correspondence with such binary trees.

Scheme functions implementing this gatomorphism on S-expressions:

Destructive variants:

(define (gma069767! s)
  (cond ((pair? s) (swap! s) (gma069767! (cdr s))))
  s)

(define (gma069768! s)
  (cond ((pair? s) (gma069768! (cdr s)) (swap! s)))
  s)

The effect of this gatomorphism on the forest Cat[4] viewed as binary trees, polygon triangulations, parenthesizations and Lukasiewicz-words.

(()()()())	((()()()))	(()(()()))	(((()())))	(()()(()))	((()(())))	(()((())))	((((()))))
40000	13000	20200	11200	30010	12010	20110	11110
((())()())	((()())())	((())(()))	(((()))())		(()(())())	(((())()))
31000	22000	21010	21100		30100	12100

A057511/A057512

Description:

Deep Rotate general trees and parenthesizations.

Fixes:

[I'm working on this].

Counted by A057546: = 1,1,2,3,5,6,10,11,...

Cycles correspond to:

Counted by A057513: = 1,1,2,4,9,21,56,153,...

Max. cycle lengths given by:

A000793 = 1,1,1,2,3,4,6,6,...

L.C.M.s of cycle lengths given by:

A003418 = 1,1,1,2,6,12,60,60,...

L-word permuting:

Yes, the restriction to binary trees induces the gatomorphism A057163.

Telescoping:

No.

Occurs in A073200:

A057511: as the row 12.

A057512: as the row 14.

Scheme functions implementing this gatomorphism on S-expressions:

Constructive, recursive variant for deep rotate left:

(define (gma057511 s)
  (cond ((not (pair? s)) s)
        ((null? (cdr s)) (list (gma057511 (car s))))
        (else
         (cons (gma057511 (car (cdr s)))
               (gma057511 (cons (car s) (cdr (cdr s))))))))

The effect of this gatomorphism on the forest Cat[4] viewed as general trees, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\ /\/\/ \	/\ /\/ \/\	/\ / \/\/\		/\/\ /\/ \	/\/\ / \/\		/\/\/\/\
(()()(()))	(()(())())	((())()())		(()(()()))	((()())())		(()()()())
30010	30100	31000		20200	22000		40000
/\ / \ /\/ \	/\ / \ / \/\		/\ /\/ \ / \	/\ / \/\ / \		/\ /\ / \/ \
(()((())))	(((()))())		((()(())))	(((())()))		((())(()))
20110	21100		12010	12100		21010
/\/\/\ / \		/\/\ / \ / \		/\ / \ / \ / \
((()()()))		(((()())))		((((()))))
13000		11200		11110

A057509/A057510

Description:

Shallow Rotate general trees and parenthesizations.

Fixes:

general trees where all sub-branches of the root are identical.

Counted by A034731: = 1,1,2,3,7,15,46,133,...

Cycles correspond to:

rooted planar trees with n non-root nodes (???).

necklaces with n black beads and n white beads.

Counted by A003239: = 1,1,2,4,10,26,80,246,...

Max. cycle lengths given by:

A028310 = 1,1,1,2,3,4,5,6,...

L.C.M.s of cycle lengths given by:

A003418 = 1,1,1,2,6,12,60,60,...

L-word permuting:

Yes, the restriction to binary trees induces the gatomorphism A069770.

Telescoping:

No.

Occurs in A073200:

A057509: as the row 16.

A057510: as the row 18.

Composed of:

A057509 = A057501 o A069770

A057510 = A069770 o A057502

Scheme functions implementing this gatomorphism on S-expressions:

Constructive variant for rotate left using Lisp/Scheme built-in function append:

(define (gma057509 s)
  (cond ((not (pair? s)) s)
        (else (append (cdr s) (list (car s))))))

Constructive, recursive variant for rotate left:

(define (gma057509v2 s)
  (cond ((not (pair? s)) s)
        ((null? (cdr s)) s)
        (else
         (cons (car (cdr s)) (gma057509v2 (cons (car s) (cdr (cdr s))))))))

Destructive variants, for both rotate left and right, composed of swap! and handshake rotates:

(define (gma057509! s)
  (cond ((pair? s) (swap! s) (gma057501! s)))
  s)

(define (gma057510! s)
  (cond ((pair? s) (gma057502! s) (swap! s)))
  s)

The effect of this gatomorphism on the forest Cat[4] viewed as general trees, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\ /\/\/ \	/\ /\/ \/\	/\ / \/\/\		/\/\ /\/ \	/\/\ / \/\		/\/\/\/\
(()()(()))	(()(())())	((())()())		(()(()()))	((()())())		(()()()())
30010	30100	31000		20200	22000		40000
/\ / \ /\/ \	/\ / \ / \/\		/\ /\ / \/ \		/\/\/\ / \		/\ /\/ \ / \
(()((())))	(((()))())		((())(()))		((()()()))		((()(())))
20110	21100		21010		13000		12010
/\ / \/\ / \		/\/\ / \ / \		/\ / \ / \ / \
(((())()))		(((()())))		((((()))))
12100		11200		11110

A057164

Description:

Deep Reverse general trees and parenthesizations.

Fixes:

general trees, parenthesizations and Dyck paths which are symmetric.

Counted by A001405: = 1,1,2,3,6,10,20,35,...

Cycles correspond to:

rooted planar general trees upto reflection.

bracelets with n black beads and n-1 white beads [Correspondence with above requires Raney's lemma.].

Counted by A007123: = 1,1,2,4,10,26,76,232,...

Max. cycle lengths given by:

A0????? = 1,1,1,2,2,2,2,2,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,1,2,2,2,2,2,...

L-word permuting:

Yes, the restriction to binary trees induces the gatomorphism A057163.

Telescoping:

No.

Occurs in A073200:

A057164: as the row 164.

Scheme functions implementing this gatomorphism on S-expressions:

Constructive, recursive variant using Lisp/Scheme built-in function append:

(define (gma057164 s)
  (cond ((not (pair? s)) s)
        ((null? (cdr s)) (cons (gma057164 (car s)) (list)))
        (else (append (gma057164 (cdr s)) (gma057164 (cons (car s) (list)))))))

Constructive, deeply recursive variant:

(define (gma057164v2 s)
  (cond ((not (pair? s)) s)
        ((null? (cdr s)) (list (gma057164v2 (car s))))
        (else
         (cons
          (gma057164v2 (car (gma057164v2 (cdr s))))
          (gma057164v2
           (cons (car s) (gma057164v2 (cdr (gma057164v2 (cdr s))))))))))

Destructive variant:

(define (gma057164! s)
  (cond ((pair? s) (gma057164! (car s)) (gma057164! (cdr s)) (gma057509! s)))
  s)

The effect of this gatomorphism on the forest Cat[4] viewed as general trees, non-crossing chord arrangements, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\ /\/\/ \	/\ / \/\/\		/\/\ /\/ \	/\/\ / \/\		/\ / \ /\/ \	/\ / \ / \/\
(()()(()))	((())()())		(()(()()))	((()())())		(()((())))	(((()))())
30010	31000		20200	22000		20110	21100
/\ /\/ \ / \	/\ / \/\ / \		/\/\/\/\		/\ /\/ \/\		/\ /\ / \/ \
((()(())))	(((())()))		(()()()())		(()(())())		((())(()))
12010	12100		40000		30100		21010
/\/\/\ / \		/\/\ / \ / \		/\ / \ / \ / \
((()()()))		(((()())))		((((()))))
13000		11200		11110

A057508

Description:

Shallow Reverse general trees and parenthesizations.

Fixes:

general plane trees whose n-th subtree from the left is equal with the n-th subtree from the right, for all its subtrees (i.e. are palindromic in the shallow sense).

Counted by A073192: = 1,1,2,3,8,18,54,155,...

Cycles correspond to:

rooted planar general trees upto reversal of the order of subtrees.

Counted by A073193: = 1,1,2,4,11,30,93,292,...

Max. cycle lengths given by:

A0????? = 1,1,1,2,2,2,2,2,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,1,2,2,2,2,2,...

L-word permuting:

Yes, the restriction to binary trees induces the gatomorphism A069770.

Telescoping:

No.

Occurs in A073200:

A057508: as the row 168.

Scheme functions implementing this gatomorphism on S-expressions:

Equivalent to Lisp/Scheme built-in function reverse:

(define gma057508
  reverse)

Constructive, recursive variant using Lisp/Scheme built-in function append:

(define (gma057508v2 s)
  (cond ((null? s) (list))
        (else (append (gma057508v2 (cdr s)) (list (car s))))))

Constructive, deeply recursive variant. [See A033538]:

(define (gma057508v3 s)
  (cond ((null? s) s)
        ((null? (cdr s)) s)
        (else
         (cons
          (car (gma057508v3 (cdr s)))
          (gma057508v3
           (cons (car s) (gma057508v3 (cdr (gma057508v3 (cdr s))))))))))

Constructive, tail-recursive variant:

(define (gma057508v4 a)
  (let loop ((a a) (b (list)))
    (cond ((not (pair? a)) b)
          (else (loop (cdr a) (cons (car a) b))))))

Two destructive variants:

(define (gma057508! s)
  (cond ((pair? s) (gma057508! (cdr s)) (gma057509! s)))
  s)

(define (gma057508v2! s)
  (cond ((pair? s) (gma057510! s) (gma057508v2! (cdr s))))
  s)

The effect of this gatomorphism on the forest Cat[4] viewed as general trees, non-crossing chord arrangements, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\ /\/\/ \	/\ / \/\/\		/\/\ /\/ \	/\/\ / \/\		/\ / \ /\/ \	/\ / \ / \/\
(()()(()))	((())()())		(()(()()))	((()())())		(()((())))	(((()))())
30010	31000		20200	22000		20110	21100
/\/\/\/\		/\ /\/ \/\		/\ /\ / \/ \		/\/\/\ / \
(()()()())		(()(())())		((())(()))		((()()()))
40000		30100		21010		13000
/\ /\/ \ / \		/\ / \/\ / \		/\/\ / \ / \		/\ / \ / \ / \
((()(())))		(((())()))		(((()())))		((((()))))
12010		12100		11200		11110

A057501/A057502

Description:

Rotate non-crossing chords (handshake) arrangements; Rotate root position of the general trees.

Fixes:

nothing after size n > 1.

Counted by A019590: = 1,1,0,0,0,0,0,0,...

Cycles correspond to:

non-crossing handshakes upto rotations.

rootless planar trees.

Counted by A002995: = 1,1,1,2,3,6,14,34,...

Max. cycle lengths given by:

A057543 = 1,1,2,3,8,10,12,14,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,2,6,8,10,12,14,...

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A057501: as the row 261.

A057502: as the row 521.

Composed of:

A057501 = A057509 o A069770

A057502 = A069770 o A057510

Scheme functions implementing this gatomorphism on S-expressions:

Constructive variant for A057501 using Lisp/Scheme built-in function append:

(define (gma057501 s)
  (cond ((null? s) (list))
        (else (append (car s) (list (cdr s))))))

Destructive variants using primitives swap! and robl!/robr!:

(define (gma057501! s)
  (cond ((not (pair? s)))
        ((not (pair? (car s))) (swap! s))
        (else (robr! s) (gma057501! (cdr s))))
  s)

(define (gma057502! s)
  (cond ((not (pair? s)))
        ((not (pair? (cdr s))) (swap! s))
        (else (gma057502! (cdr s)) (robl! s)))
  s)

Destructive variants using gatomorphisms A074680 & A074679:

(define (gma057501v2! s)
  (cond ((pair? s) (gma074680! s) (gma057501v2! (cdr s))))
  s)

(define (gma057502v2! s)
  (cond ((pair? s) (gma057502v2! (cdr s)) (gma074679! s)))
  s)

The effect of this gatomorphism on the forest Cat[4] viewed as general trees, non-crossing chord arrangements, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\ /\/\/ \	/\ /\/ \ / \	/\ /\/ \/\	/\ / \/\ / \	/\ / \/\/\	/\/\ /\/ \	/\/\ / \ / \	/\/\ / \/\
(()()(()))	((()(())))	(()(())())	(((())()))	((())()())	(()(()()))	(((()())))	((()())())
30010	12010	30100	12100	31000	20200	11200	22000
/\ / \ /\/ \	/\ / \ / \ / \	/\ / \ / \/\	/\ /\ / \/ \		/\/\/\/\	/\/\/\ / \
(()((())))	((((()))))	(((()))())	((())(()))		(()()()())	((()()()))
20110	11110	21100	21010		40000	13000

A057161/A057162

Description:

Rotate polygon triangulations.

Fixes:

nothing after size n > 1.

Counted by A019590: = 1,1,0,0,0,0,0,0,...

Cycles correspond to:

one-sided triangulations of the polygon (upto rotations), i.e. flexagons of order n.

unlabeled plane boron trees with n leaves, i.e. rootless plane trivalent trees.

Counted by A001683: = 1,1,1,1,4,6,19,49,...

Max. cycle lengths given by:

A057544 = 1,1,2,5,6,7,8,9,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,2,5,6,7,8,9,...

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A057161: as the row 17517.

A057162: as the row 35013.

Composed of:

A057161 = A057508 o A069767 = A069767 o A069769 = A057163 o A057162 o A057163

A057162 = A069768 o A057508 = A069769 o A069768 = A057163 o A057161 o A057163

Scheme functions implementing this gatomorphism on S-expressions:

Constructive, tail-recursive variants:

(define (gma057161 a)
  (let loop ((a a) (b (list)))
    (cond ((not (pair? a)) b)
          (else (loop (car a) (cons (cdr a) b))))))

(define (gma057162 a)
  (let loop ((a a) (b (list)))
    (cond ((not (pair? a)) b)
          (else (loop (cdr a) (cons b (car a)))))))

Constructive, recursive variant for A057161 using Lisp/Scheme built-in function append:

(define (gma057161v2 s)
  (cond ((null? s) s)
        (else (append (gma057161v2 (car s)) (list (cdr s))))))

Destructive variants, composed of other destructively implemented gatomorphisms:

(define (gma057161! s)
  (gma069769! s)
  (gma069767! s)
  s)

(define (gma057162! s)
  (gma057508! s)
  (gma069768! s)
  s)

The effect of this gatomorphism on the forest Cat[4] viewed as binary trees, polygon triangulations, parenthesizations and Lukasiewicz-words.

(()()()())	((()()()))	((()())())	((())(()))	(()((())))	((((()))))
40000	13000	22000	21010	20110	11110
(()()(()))	((()(())))	(((()))())		(()(()()))	(((()())))	((())()())
30010	12010	21100		20200	11200	31000
(()(())())	(((())()))
30100	12100

A074679/A074680

Description:

Rotate binary tree, if possible, otherwise swap its sides.

Fixes:

nothing after size n > 1.

Counted by A019590: = 1,1,0,0,0,0,0,0,...

Cycles correspond to:

Counted by A001683: = 1,1,1,1,1,4,6,19,...

Max. cycle lengths given by:

A0????? = 1,1,2,5,14,18,22,26,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,2,5,14,18,22,26,...

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A074679: as the row 557243.

A074680: yes

Composed of:

A074679 = A057163 o A072796 o A069770 o A057163 o A072796

A074680 = A072796 o A057163 o A069770 o A072796 o A057163

Notes:

The cycle-count sequence seems to be the same as for polygon triangulations (see above), except shifted right by one. [I'm working on this.]

Scheme functions implementing this gatomorphism on S-expressions:

Destructive variants using primitives swap! and robl!/robr!:

(define (gma074679! s)
  (cond ((pair? s) (cond ((pair? (cdr s)) (robl! s)) (else (swap! s)))))
  s)

(define (gma074680! s)
  (cond ((pair? s) (cond ((pair? (car s)) (robr! s)) (else (swap! s)))))
  s)

The effect of this gatomorphism on the forest Cat[4] viewed as polygon triangulations, binary trees, general trees, non-crossing chord arrangements, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\/\/\/\	/\ / \/\/\	/\ / \ / \/\	/\ / \ / \ / \	/\ / \ /\/ \	/\ /\/ \ / \	/\ /\/\/ \	/\ /\ / \/ \
(()()()())	((())()())	(((()))())	((((()))))	(()((())))	((()(())))	(()()(()))	((())(()))
40000	31000	21100	11110	20110	12010	30010	21010
--------->
--------->
--------->
--------->
--------->	/\ / \/\ / \	/\ /\/ \/\	/\/\ / \/\	/\/\ / \ / \	/\/\ /\/ \	/\/\/\ / \
--------->	(((())()))	(()(())())	((()())())	(((()())))	(()(()()))	((()()()))
--------->	12100	30100	22000	11200	20200	13000

The effect of this gatomorphism on the forest Cat[5] viewed as polygon triangulations, binary trees, general trees, non-crossing chord arrangements, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\/\/\/\/\	/\ / \/\/\/\	/\ / \ / \/\/\	/\ / \ / \ / \/\	/\ / \ / \ / \ / \	/\ / \ / \ /\/ \	/\ / \ /\/ \ / \	/\ / \ /\/\/ \
(()()()()())	((())()()())	(((()))()())	((((())))())	(((((())))))	(()(((()))))	((()((()))))	(()()((())))
500000	410000	311000	211100	111110	201110	120110	300110
----------->
----------->
----------->
----------->
----------->	/\ /\ / \ / \/ \	/\ /\ / \/ \ / \	/\ /\ /\/ \/ \	/\/\ /\ / \/ \	/\/\ / \/\ / \	/\/\ /\/ \/\	/\/\/\ / \/\
----------->	((())((())))	(((())(())))	(()(())(()))	((()())(()))	(((()())()))	(()(()())())	((()()())())
----------->	210110	121010	301010	220010	122000	302000	230000
----------->
----------->
----------->
----------->
----------->	/\/\/\ / \ / \	/\/\/\ /\/ \	/\/\/\/\ / \
----------->	(((()()())))	(()(()()()))	((()()()()))
----------->	113000	203000	140000
/\ /\/\/\/ \	/\ /\ / \/\/ \	/\ / \ /\ / \/ \	/\ / \ / \/\ / \	/\ / \ /\/ \/\	/\ /\/ \ / \/\	/\ /\/ \ / \ / \	/\ /\/ \ /\/ \
(()()()(()))	((())()(()))	(((()))(()))	((((()))()))	(()((()))())	((()(()))())	(((()(()))))	(()(()(())))
400010	310010	211010	121100	301100	220100	112010	202010
----------->
----------->
----------->
----------->
----------->	/\ /\/\/ \ / \
----------->	((()()(())))
----------->	130010
/\/\ /\/\/ \	/\ /\/\ / \/ \	/\ / \/\/\ / \	/\ /\/ \/\/\	/\/\ / \/\/\	/\/\ / \ / \/\	/\/\ / \ / \ / \	/\/\ / \ /\/ \
(()()(()()))	((())(()()))	(((())()()))	(()(())()())	((()())()())	(((()()))())	((((()()))))	(()((()())))
300200	210200	131000	401000	320000	212000	111200	201200
----------->
----------->
----------->
----------->
----------->	/\/\ /\/ \ / \
----------->	((()(()())))
----------->	120200
/\ /\/\/ \/\	/\ /\ / \/ \/\	/\ / \/\ / \/\	/\ / \/\ / \ / \	/\ / \/\ /\/ \	/\ /\/ \/\ / \
(()()(())())	((())(())())	(((())())())	((((())())))	(()((())()))	((()(())()))
400100	310100	221000	112100	202100	130100

A057503/A057504

Description:

Gatomorphism A057503/A057504.

Fixes:

Counted by A019590: = 1,1,0,0,0,0,0,0,...

Cycles correspond to:

Counted by A001683: = 1,1,1,1,4,6,19,49,...

Max. cycle lengths given by:

A057544 = 1,1,2,5,6,7,8,9,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,2,5,6,7,8,9,...

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A057503: as the row 2618.

A057504: as the row 5216.

Notes:

The count sequences seem to be the same as for polygon triangulations. [I'm working on this.]

Scheme functions implementing this gatomorphism on S-expressions:

Constructive, recursive variant for A057503 using Lisp/Scheme built-in function append:

(define (gma057503 s)
  (cond ((null? s) s)
        (else (append (car s) (list (gma057503 (cdr s)))))))

Destructive variants, built on handshake rotates:

(define (gma057503! s)
  (cond ((pair? s) (gma057503! (cdr s)) (gma057501! s)))
  s)

(define (gma057504! s)
  (cond ((pair? s) (gma057502! s) (gma057504! (cdr s))))
  s)

The effect of this gatomorphism on the forest Cat[4] viewed as polygon triangulations, binary trees, general trees, non-crossing chord arrangements, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\/\/\/\	/\ / \ / \ / \	/\ / \ / \/\	/\ /\ / \/ \	/\/\ /\/ \	/\/\/\ / \
(()()()())	((((()))))	(((()))())	((())(()))	(()(()()))	((()()()))
40000	11110	21100	21010	20200	13000
/\ /\/\/ \	/\/\ / \ / \	/\/\ / \/\		/\ / \ /\/ \	/\ / \/\ / \	/\ / \/\/\
(()()(()))	(((()())))	((()())())		(()((())))	(((())()))	((())()())
30010	11200	22000		20110	12100	31000
/\ /\/ \/\	/\ /\/ \ / \
(()(())())	((()(())))
30100	12010

A057505/A057506

Description:

Donaghey's M.

Fixes:

nothing after size n > 1.

Counted by A019590: = 1,1,0,0,0,0,0,0,...

Cycles correspond to:

Counted by A057507: = 1,1,1,2,3,10,18,46,...

Max. cycle lengths given by:

A057545 = 1,1,2,3,6,6,24,72,...

L.C.M.s of cycle lengths given by:

A060114 = 1,1,2,6,6,30,120,720,...

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A057505: as the row 2614.

A057506: as the row 5212.

Composed of:

A057505 = A057164 o A057163

A057506 = A057163 o A057164

Notes:

See: R. Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.

Scheme functions implementing this gatomorphism on S-expressions:

Constructive, tail-recursive variants:

(define (gma057505 a)
  (let loop ((a a) (b (list)))
    (cond ((not (pair? a)) b)
          (else (loop (car a) (cons (gma057505 (cdr a)) b))))))

(define (gma057506 a)
  (let loop ((a a) (b (list)))
    (cond ((not (pair? a)) b)
          (else (loop (cdr a) (cons b (gma057506 (car a))))))))

Constructive, recursive variant for gmA057505 using Lisp/Scheme built-in function append:

(define (gma057505v2 s)
  (cond ((null? s) s)
        (else (append (gma057505v2 (car s)) (list (gma057505v2 (cdr s)))))))

The variant based on the transformation explained in Donaghey's paper:

(define (gma057505v3 s)
  (with-input-from-string (list->string-strange s) read))

(define (list->string-strange s)
  (string-append
   "("
   (with-output-to-string
    (lambda ()
      (let recurse ((s s))
        (cond ((pair? s) (recurse (car s))
                         (write-string "(")
                         (recurse (cdr s))
                         (write-string ")"))))))
   ")"))

Destructive variants, built on handshake rotates:

(define (gma057505! s)
  (cond ((pair? s) (gma057505! (car s)) (gma057505! (cdr s)) (gma057501! s)))
  s)

(define (gma057506! s)
  (cond ((pair? s) (gma057502! s) (gma057506! (car s)) (gma057506! (cdr s))))
  s)

The effect of this gatomorphism on the forest Cat[4] viewed as polygon triangulations, binary trees, general trees, non-crossing chord arrangements, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\ /\/\/ \	/\/\ / \ / \	/\ / \/\/\	/\ / \ /\/ \	/\/\/\ / \	/\ / \ / \/\
(()()(()))	(((()())))	((())()())	(()((())))	((()()()))	(((()))())
30010	11200	31000	20110	13000	21100
/\ /\/ \/\	/\ /\/ \ / \	/\/\ / \/\	/\ /\ / \/ \	/\/\ /\/ \	/\ / \/\ / \
(()(())())	((()(())))	((()())())	((())(()))	(()(()()))	(((())()))
30100	12010	22000	21010	20200	12100
/\/\/\/\	/\ / \ / \ / \
(()()()())	((((()))))
40000	11110

A071655/A071656

Description:

Rotate binary tree if possible and recurse down both branches, otherwise apply swap and terminate.

Fixes:

Counted by A0?????: = 1,1,0,0,0,0,0,0,...

Cycles correspond to:

Counted by A0?????: = 1,1,1,2,2,4,4,5,...

Max. cycle lengths given by:

A0????? = 1,1,2,3,12,29,97,378,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,2,6,12,870,13580,10962,...

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A071655: ???

A071656: ???

Scheme functions implementing this gatomorphism on S-expressions:

Destructive variants:

(define (gma071655! s)
  (cond ((not (pair? s)))
        ((not (pair? (car s))) (swap! s))
        (else (robr! s) (gma071655! (car s)) (gma071655! (cdr s))))
  s)

(define (gma071656! s)
  (cond ((not (pair? s)))
        ((not (pair? (cdr s))) (swap! s))
        (else (gma071656! (car s)) (gma071656! (cdr s)) (robl! s)))
  s)

The effect of this gatomorphism on the forest Cat[4] viewed as polygon triangulations, binary trees, general trees, non-crossing chord arrangements, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\ /\/\/ \	/\ /\/ \ / \	/\ /\/ \/\	/\ / \/\ / \	/\ / \/\/\	/\/\ /\/ \	/\/\ / \ / \	/\ / \ / \/\
(()()(()))	((()(())))	(()(())())	(((())()))	((())()())	(()(()()))	(((()())))	(((()))())
30010	12010	30100	12100	31000	20200	11200	21100
--------->
--------->
--------->
--------->
--------->	/\ /\ / \/ \	/\ / \ /\/ \	/\ / \ / \ / \	/\/\ / \/\
--------->	((())(()))	(()((())))	((((()))))	((()())())
--------->	21010	20110	11110	22000
/\/\/\/\	/\/\/\ / \
(()()()())	((()()()))
40000	13000

A074681/A074682

Description:

Gatomorphism A074681/A074682.

Fixes:

Counted by A0?????: = 1,1,0,0,0,0,0,0,...

Cycles correspond to:

Counted by A0?????: = 1,1,1,1,3,4,4,11,...

Max. cycle lengths given by:

A0????? = 1,1,2,5,9,28,57,253,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,2,5,18,84,2793,211123440,...

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A074681: as the row 5572432.

A074682: yes

Notes:

The count sequence is not monotone

Scheme functions implementing this gatomorphism on S-expressions:

Destructive variants:

(define (gma074681! s)
  (cond ((pair? s) (gma074679! s) (gma074681! (car s)) (gma074681! (cdr s))))
  s)

(define (gma074682! s)
  (cond ((pair? s) (gma074682! (car s)) (gma074682! (cdr s)) (gma074680! s)))
  s)

The effect of this gatomorphism on the forest Cat[4] viewed as polygon triangulations, binary trees, general trees, non-crossing chord arrangements, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\/\/\/\	/\ /\ / \/ \	/\/\ / \ / \	/\ /\/\/ \	/\ / \/\/\	/\/\ / \/\	/\ /\/ \ / \	/\ / \ /\/ \
(()()()())	((())(()))	(((()())))	(()()(()))	((())()())	((()())())	((()(())))	(()((())))
40000	21010	11200	30010	31000	22000	12010	20110
--------->
--------->
--------->
--------->
--------->	/\ / \ / \ / \
--------->	((((()))))
--------->	11110
/\ /\/ \/\	/\ / \ / \/\	/\/\/\ / \		/\/\ /\/ \	/\ / \/\ / \
(()(())())	(((()))())	((()()()))		(()(()()))	(((())()))
30100	21100	13000		20200	12100

A074683/A074684

Description:

Gatomorphism A074683/A074684.

Fixes:

Counted by A0?????: = 1,1,0,0,0,0,0,0,...

Cycles correspond to:

Counted by A0?????: = 1,1,1,1,3,4,4,11,...

Max. cycle lengths given by:

A0????? = 1,1,2,5,9,28,57,253,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,2,5,18,84,2793,211123440,...

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A074683: as the row 5572434.

A074684: yes

Notes:

The count sequence is not monotone

Scheme functions implementing this gatomorphism on S-expressions:

Destructive variants:

(define (gma074683! s)
  (cond ((pair? s) (gma074683! (car s)) (gma074683! (cdr s)) (gma074679! s)))
  s)

(define (gma074684! s)
  (cond ((pair? s) (gma074680! s) (gma074684! (car s)) (gma074684! (cdr s))))
  s)

The effect of this gatomorphism on the forest Cat[4] viewed as polygon triangulations, binary trees, general trees, non-crossing chord arrangements, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\/\/\/\	/\/\/\ / \	/\/\ /\/ \	/\ /\ / \/ \	/\ / \ / \/\	/\/\ / \ / \	/\ /\/\/ \	/\/\ / \/\
(()()()())	((()()()))	(()(()()))	((())(()))	(((()))())	(((()())))	(()()(()))	((()())())
40000	13000	20200	21010	21100	11200	30010	22000
--------->
--------->
--------->
--------->
--------->	/\ / \ / \ / \
--------->	((((()))))
--------->	11110
/\ / \ /\/ \	/\ / \/\/\	/\ / \/\ / \		/\ /\/ \/\	/\ /\/ \ / \
(()((())))	((())()())	(((())()))		(()(())())	((()(())))
20110	31000	12100		30100	12010

A069773/A069774

Description:

The car/cdr-flipped conjugate of handshake rotate.

Fixes:

nothing after size n > 1.

Counted by A019590: = 1,1,0,0,0,0,0,0,...

Cycles correspond to:

Counted by A002995: = 1,1,1,2,3,6,14,34,...

Max. cycle lengths given by:

A057543 = 1,1,2,3,8,10,12,14,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,2,6,8,10,12,14,...

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A069773: as the row 163899.

A069774: as the row 164379.

Composed of:

A069773 = A057163 o A057501 o A057163

A069774 = A057163 o A057502 o A057163

Scheme functions implementing this gatomorphism on S-expressions:

Destructive variants using primitives swap! and robl!/robr!:

(define (gma069773! s)
  (cond ((not (pair? s)))
        ((not (pair? (cdr s))) (swap! s))
        (else (robl! s) (gma069773! (car s))))
  s)

(define (gma069774! s)
  (cond ((not (pair? s)))
        ((not (pair? (car s))) (swap! s))
        (else (gma069774! (car s)) (robr! s)))
  s)

Destructive variants using gatomorphisms A074680 & A074679:

(define (gma069773v2! s)
  (cond ((pair? s) (gma074679! s) (gma069773v2! (car s))))
  s)

(define (gma069774v2! s)
  (cond ((pair? s) (gma069774v2! (car s)) (gma074680! s)))
  s)

The effect of this gatomorphism on the forest Cat[4] viewed as polygon triangulations, binary trees, general trees, non-crossing chord arrangements, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\ /\/\/ \	/\ /\ / \/ \	/\/\ / \ / \	/\/\ /\/ \	/\ / \/\ / \	/\ /\/ \/\	/\ / \ / \/\	/\ /\/ \ / \
(()()(()))	((())(()))	(((()())))	(()(()()))	(((())()))	(()(())())	(((()))())	((()(())))
30010	21010	11200	20200	12100	30100	21100	12010
/\/\/\/\	/\ / \/\/\	/\/\ / \/\	/\/\/\ / \		/\ / \ /\/ \	/\ / \ / \ / \
(()()()())	((())()())	((()())())	((()()()))		(()((())))	((((()))))
40000	31000	22000	13000		20110	11110

A069787

Description:

The car/cdr-flipped conjugate of deep reverse.

Fixes:

Counted by A001405: = 1,1,2,3,6,10,20,35,...

Cycles correspond to:

Counted by A007123: = 1,1,2,4,10,26,76,232,...

Max. cycle lengths given by:

A0????? = 1,1,1,2,2,2,2,2,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,1,2,2,2,2,2,...

L-word permuting:

No.

Telescoping:

Yes, contraction gives the permutation A072799.

Occurs in A073200:

A069787: as the row 538968755.

Composed of:

A069787 = A057163 o A057164 o A057163

The effect of this gatomorphism on the forest Cat[4] viewed as polygon triangulations, binary trees, general trees, non-crossing chord arrangements, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\ /\/ \/\	/\/\ /\/ \		/\ / \/\/\	/\/\/\ / \		/\ /\ / \/ \	/\ /\/ \ / \
(()(())())	(()(()()))		((())()())	((()()()))		((())(()))	((()(())))
30100	20200		31000	13000		21010	12010
/\ / \ / \/\	/\/\ / \ / \		/\/\/\/\		/\ /\/\/ \		/\ / \ /\/ \
(((()))())	(((()())))		(()()()())		(()()(()))		(()((())))
21100	11200		40000		30010		20110
/\/\ / \/\		/\ / \/\ / \		/\ / \ / \ / \
((()())())		(((())()))		((((()))))
22000		12100		11110

A069769

Description:

The car/cdr-flipped conjugate of shallow reverse.

Fixes:

Counted by A073192: = 1,1,2,3,8,18,54,155,...

Cycles correspond to:

Counted by A073193: = 1,1,2,4,11,30,93,292,...

Max. cycle lengths given by:

A0????? = 1,1,1,2,2,2,2,2,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,1,2,2,2,2,2,...

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A069769: as the row 538976435.

Composed of:

A069769 = A057163 o A057508 o A057163

The effect of this gatomorphism on the forest Cat[4] viewed as polygon triangulations, binary trees, general trees, non-crossing chord arrangements, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\ / \/\/\	/\/\/\ / \		/\ /\ / \/ \	/\ /\/ \ / \		/\ / \ / \/\	/\/\ / \ / \
((())()())	((()()()))		((())(()))	((()(())))		(((()))())	(((()())))
31000	13000		21010	12010		21100	11200
/\/\/\/\		/\ /\/\/ \		/\ /\/ \/\		/\/\ /\/ \
(()()()())		(()()(()))		(()(())())		(()(()()))
40000		30010		30100		20200
/\ / \ /\/ \		/\/\ / \/\		/\ / \/\ / \		/\ / \ / \ / \
(()((())))		((()())())		(((())()))		((((()))))
20110		22000		12100		11110

A069888

Description:

Reflect non-crossing chords by the axis through corners (WM).

Fixes:

Counted by A000108: = 1,1,0,1,0,2,0,5,...

Cycles correspond to:

Counted by A007595: = 1,1,1,3,7,22,66,217,...

Max. cycle lengths given by:

A0????? = 1,1,2,2,2,2,2,2,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,2,2,2,2,2,2,...

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A069888: as the row 2155874567.

Composed of:

A069888 = A057501 o A057164

Scheme functions implementing this gatomorphism on S-expressions:

Constructive variant, composed of gatomorphisms DeepReverse (gmA057164) & RotateHandshakes (gmA057501):

(define (gma069888 s)
  (gma057501 (gma057164 s)))

Destructive variant, composed of gatomorphisms DeepReverse (gmA057164) & RotateHandshakes (gmA057501):

(define (gma069888! s)
  (gma057164! s)
  (gma057501! s)
  s)

The effect of this gatomorphism on the forest Cat[4] viewed as polygon triangulations, binary trees, general trees, non-crossing chord arrangements, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\/\/\/\	/\/\/\ / \		/\ /\/\/ \	/\/\ /\/ \		/\ /\/ \/\	/\ / \/\ / \
(()()()())	((()()()))		(()()(()))	(()(()()))		(()(())())	(((())()))
40000	13000		30010	20200		30100	12100
/\ / \ /\/ \	/\ /\ / \/ \		/\ / \/\/\	/\ /\/ \ / \		/\/\ / \/\	/\/\ / \ / \
(()((())))	((())(()))		((())()())	((()(())))		((()())())	(((()())))
20110	21010		31000	12010		22000	11200
/\ / \ / \/\	/\ / \ / \ / \
(((()))())	((((()))))
21100	11110

A069771

Description:

Rotate non-crossing chords by 180 degrees.

Fixes:

Counted by A001405: = 1,1,2,3,6,10,20,35,...

Cycles correspond to:

Counted by A007123: = 1,1,2,4,10,26,76,232,...

Max. cycle lengths given by:

A0????? = 1,1,1,2,2,2,2,2,...

L.C.M.s of cycle lengths given by:

A0????? = 1,1,1,2,2,2,2,2,...

L-word permuting:

No.

Telescoping:

No.

Occurs in A073200:

A069771: no?

Composed of:

A069771 = A057164 o A069772

Scheme functions implementing this gatomorphism on S-expressions:

Constructive variant, which calls RotateHandshakes (gmA057501) as many times as there are left or right parentheses in the S-expression:

(define (gma069771 s)
  (rotatehandshakes_n_steps s (count-pars s)))

(define (rotatehandshakes_n_steps s n)
  (cond ((zero? n) s)
        (else (rotatehandshakes_n_steps (gma057501 s) (- n 1)))))

(define (count-pars s)
  (cond ((not (pair? s)) 0)
        (else (+ 1 (count-pars (car s)) (count-pars (cdr s))))))

The effect of this gatomorphism on the forest Cat[3] viewed as polygon triangulations, binary trees, general trees, non-crossing chord arrangements, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.

/\/\/\	/\/\ / \		/\ /\/ \		/\ / \/\		/\ / \ / \
(()()())	((()()))		(()(()))		((())())		(((())))
3000	1200		2010		2100		1110