Antti Karttunen
An Introduction to Gatomorphisms
(This is a paper in preparation, please don't redistribute this
document or its URL without my permission. Last edited 31. Mar 2003.)
Abstract
In this paper we adopt the programming language Scheme (a dialect of Lisp)
as an unambiguous and elegant notation,
with which to define arbitrarily complex automorphisms
that act on the combinatorial structures found
in the Catalan family: on planar binary trees, planar general trees,
parenthesizations, polygon triangulations and non-crossing
chord arrangements, among others.
We start our survey of these gatomorphisms from the
simple cases, and then play with some simple methods for
inductively generating infinite, countable subsets of them,
which still are wide enough to encompass the most
obvious symmetry operations (reflections & rotations) one
can imagine to occur in the Catalan family.
On the other hand we also show that certain well-defined
gatomorphisms are outside of these sets.
We summarize the formulae of long-established EIS-sequences
which we will meet when counting the orbits and fixpoints
to which such gatomorphisms partition each subset of
Catalan structures of a certain size, and derive also formulae
for two new such sequences, via the orbit-counting ("Burnside's") lemma.
We also observe few specific properties the gatomorphisms may
have, what are their implications and how various
gatomorphisms are related to each other.
Introduction to Scheme and S-expressions
The functional programming language Lisp (including its dialect Scheme)
has its roots in Church's Lambda calculus, and differs
in substantial ways from many of the more traditional
programming languages like Algol, Pascal, C or Java.
The inventor of Lisp, John McCarthy lists fifteen distinct features
[McCarthy, 1980, -99]
that make it special, but for the purpose of this paper, we need to concentrate only on one:
its S-expressions.
Definition.
There are various definitions for S-expressions in the
literature [...], however in this paper we adopt a convention that an
internal, "dotted" representation of an S-expression can be any
of the following:
- a symbol. For example, define, pair?, else and + are symbols.
- an integer. For example, 144 and -1 are integers.
- an empty list ( )
or
- an ordered pair of the form (X . Y)
where the element X (traditionally called car) can be any
of the cases (a-d), while the element Y (traditionally called cdr)
can be either the case (c) (an empty list) or the case (d), other such
pair.
This definition is isomorphic with the external, "dotless" representation,
in which an S-expression can be any of the following:
- a symbol.
- an integer.
or
- (<dotfree-sexpr>*)
The last case says that a parenthesis-delimited list of zero or more
other such external representations is also an external, dot-free representation.
From now on, when it's not the question of a single symbol or integer, we shall refer
to these dotless representations of S-expressions as lists.
The isomorphism between these two representations is realized
by the function f which maps from the "internal" to "external"
representation as follows:
| symbol | --> | symbol |
|---|
| integer | --> | integer |
|---|
| ( ) | --> | ( ) |
|---|
| (X . ( )) |
--> |
( f(X) ) |
| (X . Y) |
--> |
a list obtained by inserting f(X) as the first element
to a front of a list obtained with f(Y) |
For example, the function f would map the internal, dotted S-expression
(a . ((( ) . (2 . ( ))) . (b . ( ))))
to external, dotless list
(a (( ) 2) b)
This definition is sufficient for explaining how to define
functions in our minimal subset of Scheme.
Furthermore, we define a subset of content-free S-expressions. Their
internal, dotted representation is defined that they are either:
- an empty list ( )
or
- an ordered pair of the form (X . Y)
where either element, X or Y can be either an empty list
or other such pair.
When we apply the above map f to this subset, we realize
we have a missing link connecting our two sub-families
of the Catalan clan, represented in the previous section.
Namely, the former definition is equivalent (*) to the
definition of planar binary trees and binary bracketings,
and the corresponding external, dot-free representations are lists
composed of parentheses only, i.e. parenthesizations
surrounded by an extra pair of parentheses.
We will define our gatomorphisms as Scheme-functions
that manipulate such content-free S-expressions.
Definitions
- Gatomorphism
- Gatomorphism is any bijection from a set of parenthesizations
of the size n to the same set (of size n), which is well-defined for
all the sizes n>=0 (for sizes n=0 and 1 we must always have an identity mapping).
By parenthesization of size n we mean a S-expression
where only ( ) can occur as a terminal (atomic, non-pair) node,
and whose ordinary printed manifestation consists of n+1
left (or right) parentheses, which thus is composed of
n cons cells (pairs).
Instead of taking the approach of
R. Donaghey in his Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
where he defines a separate variant
of his Map M for each of the various
incarnations of the Catalan family,
i.e. binary trees, binary bracketings,
general trees, general bracketings (= parenthesizations),
etc., we let our gatomorphisms be uniquely
defined by any Scheme-function which satisfies
the above condition of bijectivity on such
content-free S-expressions.
Then on we can talk about the gatomorphism's effect on the other
incarnations of the Catalan family by using
the obvious, "canonical" mappings between
these forms. For now I don't explain formally
these mappings here, but refer the reader
just to the programmatically generated drawings of the first 626
such incarnations given here,
from which he can get an intuitive grasp
for the correspondences involved.
Also, we let the Scheme function car to
refer the left hand subtree of a S-expression
viewed as a binary tree, and the Scheme function cdr
to respectively refer the right hand subtree.
(I will explain this later in more detail.)
- A057163-conjugation
- We say that the gatomorphism g is the
A057163-conjugate of the gatomorphism f
if g = gmA057163 o f o gmA057163,
that is, we reflect the argument as a binary tree before feeding
it to f, and then reflect again its result (as a binary tree).
Embeddability
Definition. We say that
gatomorphism f embeds into gatomorphism g in scale n:m
if there is an injection:
e: Catn (parenthesizations/trees/etc. of size n) --> Catm (parenthesizations/trees/etc. of size m)
that for all the elements a of the former set, and for all integer values of the superscript r in Z
(which stands for the repeated applications of f or g (if the exponent is positive) or their inverse (if the exponent is negative))
it holds that
(gr (e a)) = (e (fr a))
Examples.
Definition. We say that
gatomorphism g is Lukasiewicz-word permuting
if the Lukasiewicz-word of (g s) is always a permutation of the Lukasiewicz-word
of s for all trees/parenthesizations s of any size.
This implies that the subset of the planar binary trees (of the general trees)
is closed under the action of g, and thus its restriction to that
subset induces another gatomorphism f.
Rephrasing this in above terms, we can say that gatomorphism f embeds
into gatomorphism g in scale n:2n.
Definition. We say that
gatomorphism g is self-embeddable
if g embeds into itself in scale n:m, where n ranges through
all values in N, and m is a function of n, with m > n.
Two special cases of self-embeddability deserve special attention:
Definition. We say that
gatomorphism g is "horizontally telescoping"
if for all the parenthesizations s it holds that
(g (cons '( ) s)) = (cons '( ) (g s))
where the injection e required by our general definition of embeddability is now defined as
(define (e s) (cons '( ) s))
which maps the parenthesizations/trees of size n to the parenthesizations/trees
of size n+1 by simply concatenating empty parentheses to the front
of the corresponding parenthesization, or in terms of binary trees, by
grafting an old tree of size n as a right-hand-side subtree
of a new tree of size n+1 whose left-hand-side subtree
is just a single edge \.
Remark.
This is equivalent to saying that each sub-permutation of the length A000108(n) induced by g's action on
the standard sequence of lexicographically ordered parenthesizations
A014486 (A063171)
starts with the same cycle-structure as the previous sub-permutation.
In this case we can form yet another permutation of the natural numbers
by conceptually taking the "infiniteth" of such sub-permutations
and by "normalizing" it to begin from 0 or 1.
For example, Meeussen's breadth-first <-> depth-first conversion for binary trees
A057117
satisfies the above condition, and by thus "contracting the telescope" we get another
permutation of natural numbers,
A038776.
Definition. We say that
gatomorphism g is "vertically telescoping"
if for all parenthesizations s it holds that
(g (cons s '( ))) is equal to (cons (g s) '( ))
where the injection e is now defined as
(define (e s) (cons s '( )))
which maps the parenthesizations/trees of size n to the parenthesizations/trees
of size n+1 by surrounding the corresponding parenthesization with one extra
parentheses ( and ), or in terms of binary trees, by
grafting an old tree of size n as a left-hand-side subtree
of a new tree of size n+1 whose right-hand-side subtree
is just a single edge /.
Remark.
For example, it is easy to see that this holds for the gatomorphism A057164 (Deep Reverse),
and similarly for A057511/A057512 (Deep Rotates), and
as A069787 = A057163 o A057164 o A057163,
we can contract A069787 (a horizontally telescoping gatomorphism)
to get A072799.
Remark.
The A057163-conjugate of any "horizontally telescoping" gatomorphism is "vertically telescoping"
and vice versa. Like with all self-embeddable gatomorphisms of the scale n:n+1
we can be sure that the corresponding cycle/orbit count sequences of these gatomorphisms
are genuinely monotone (growing) after size n>0.
This is because one can find the same cycles/orbits from the set of Catn+1
parenthesizations/trees/whatever of size n+1 as what one finds in the set of
Catn parenthesizations/trees/whatever of size n
and the remaining Catn+1 - Catn
parenthesizations/trees/whatever must form at least one extra orbit.
Remark.
The allusions "horizontal" and "vertical" should be obvious
if one thinks in the terms of Dyck paths (Catalan Mountain Ranges),
and also the plane general trees in the latter case.
Construction process
We would like to define our gatomorphisms
with as primitive building blocks as possible.
Our first building block is naturally swap which
just swaps the contents of car and cdr
in one cons-cell, i.e.
if the A and B are any subtrees,
including the empty tree, i.e. ( ), then this
has the following effect, i.e. it just flips
the tree sides at its root:
 | <--SWAP--> |  |
|---|
Here we have implemented it as a constructive Scheme-function:
(define (swap s) (cons (cdr s) (car s)))
and here as a destructive one:
(define (swap! s)
(let ((ex-car (car s)))
(set-car! s (cdr s))
(set-cdr! s ex-car)
s
)
)
Then the next primitive we need is
"rotation of binary trees", with two
variants that are inverses of each
other: robl
(rotate binary tree left) and robr
(rotate binary tree right).
They have the following effect on
binary trees, when applied at the
root:
 | --ROBR-->
<--ROBL-- |  |
|---|
As destructively modifying Scheme functions these are implemented
here as:
;; robl! -- Rotate Binary tree Left. Inverse of robr!
;; Convert (a . (b . rest)) to ((a . b) . rest) destructively
;; (with no cons cells wasted).
;; Like cons2top! but keeps the "point(er) of reference" same:
(define (robl! s)
(let ((ex-car (car s))) ;; <- a
(set-car! s (cddr s)) ;; (a . (b . rest)) -> (rest . (b . rest))
(set-cdr! (cdr s) ex-car) ;; -> (rest . (b . a))
(swap! (cdr s)) ;; -> (rest . (a . b))
(swap! s) ;; -> ((a . b) . rest)
s
)
)
;; robr! -- Rotate Binary tree Right. Inverse of robl!
;; Convert ((a . b) . rest) to (a . (b . rest)) destructively
;; (with no cons cells wasted).
(define (robr! s)
(let ((ex-cdr (cdr s))) ;; <- rest
(set-cdr! s (caar s)) ;; ((a . b) . rest) -> ((a . b) . a)
(set-car! (car s) ex-cdr) ;; -> ((rest . b) . a)
(swap! (car s)) ;; -> ((b . rest) . a)
(swap! s) ;; -> (a . (b . rest))
s
)
)
Note that the primitive swap can be made
a genuine gatomorphism (A069770) just by adding an
additional condition that ( )
maps to itself, i.e. we have a definition:
(define (gmA069770 s)
(cond ((not (pair? s)) s)
(else (cons (cdr s) (car s)))
)
)
However, that trick is not enough to make robl
or robr a true bijection.
Instead, we have to build a slightly
more complicated primitive, called exch2first
(A072796), which effects the following transformation
of binary trees that correspond to general
trees of length at least two:
| <--EXCH2FIRST--> |  |
|---|
and otherwise fixes (leaves intact) the tree,
i.e. if its either empty tree ( )
or is of degree 1 when viewed as a general
tree (that is, the binary subtree at the right
side is empty).
This is well defined gatomorphism, which like
swap (A069770) is self-inverse
(an involution).
Here we have implemented it as a constructive Scheme-function:
(define (gmA072796 s)
(cond ((not (pair? s)) s)
((not (pair? (cdr s))) s)
(else (cons (cadr s) (cons (car s) (cddr s))))
)
)
and here as a destructive one:
(define (gmA072796! s)
(cond ((not (pair? s)) s) ;; ( ) --> ( )
((not (pair? (cdr s))) s) ;; Fixes the general trees of degree one.
(else (swap! s) ;; Otherwise, first swap!,
(robr! s) ;; then rotate binary tree right,
(swap! (cdr s)) ;; and swap! the right subtree of the produced binary tree.
s
)
)
)
Definition:
A gatomorphism is called a simple gatomorphism of
type B, if it is inductively constructed
starting from these two involutions (swap and exch2first)
and using only simple composition, and/or one of the
five cases of recursive construction as explained in
the sequence A073200 of [OEIS].
In the following list, all others, except
A071655/A071656
and the last four cases are known to be
constructible by such means.
A brief survey on some gatomorphisms.
We survey the following gatomorphisms in this document:
- A069770 - Swap binary tree sides
- A072796 - Exchange the two leftmost branches of general trees if the degree of root > 1, otherwise keep the tree intact
- A057163 - Reflect binary trees and polygon triangulations
- A069767/A069768 - Swap recursively the other side of binary tree
- A057511/A057512 - Deep Rotate general trees and parenthesizations
- A057509/A057510 - Shallow Rotate general trees and parenthesizations
- A057164 - Deep Reverse general trees and parenthesizations
- A057508 - Shallow Reverse general trees and parenthesizations
- A057501/A057502 - Rotate non-crossing chords (handshake) arrangements; Rotate root position of the general trees
- A057161/A057162 - Rotate polygon triangulations
- A074679/A074680 - Rotate binary tree, if possible, otherwise swap its sides
- A057503/A057504 - Gatomorphism A057503/A057504
- A057505/A057506 - Donaghey's M
- A071655/A071656 - Rotate binary tree if possible and recurse down both branches, otherwise apply swap and terminate
- A074681/A074682 - Gatomorphism A074681/A074682
- A074683/A074684 - Gatomorphism A074683/A074684
- A069773/A069774 - The car/cdr-flipped conjugate of handshake rotate
- A069787 - The car/cdr-flipped conjugate of deep reverse
- A069769 - The car/cdr-flipped conjugate of shallow reverse
- A069888 - Reflect non-crossing chords by the axis through corners (WM)
- A069771 - Rotate non-crossing chords by 180 degrees
- A069772 - Reflect non-crossing chords by X-axis
- A072088/A072089 - Meeussen's breadth-first <-> depth-first conversion for general trees
- A057117/A057118 - Meeussen's breadth-first <-> depth-first conversion for binary trees
- 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.
- 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.
- 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.
- 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 2n-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.
- 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))))))))
- Destructive, recursive variants for both, using exch2first (A072796):
(define (gmA057511! s)
(cond ((pair? s)
(gmA072796! s)
(gmA057511! (car s))
(gmA057511! (cdr s))
)
)
s
)
(define (gmA057512! s)
(cond ((pair? s)
(gmA057512! (car s))
(gmA057512! (cdr s))
(gmA072796! s)
)
)
s
)
- The effect of this gatomorphism on the forest Cat[4] viewed as general trees, Dyck paths (mountain ranges), parenthesizations and Lukasiewicz-words.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
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.
- Description:
- Reflect non-crossing chords by X-axis.
- Fixes:
- Counted by A0?????: = 1,1,2,1,6,2,20,5,...
- Cycles correspond to:
- Counted by A0?????: = 1,1,2,3,10,22,76,217,...
- 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:
- A069772: no?
- Composed of:
- A069772 = A057164 o A069771
- Scheme functions implementing this gatomorphism on S-expressions:
- Constructive variant, composed of gatomorphisms RotateHandshakes 180 degrees (gmA069771) & DeepReverse (gmA057164):
(define (gma069772 s)
(gma057164 (gma069771 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.
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.
- Description:
- Meeussen's breadth-first <-> depth-first conversion for general trees.
- Fixes:
- Counted by A0?????: = 1,1,2,5,12,27,60,127,...
- Cycles correspond to:
- Counted by A0?????: = 1,1,2,5,13,33,84,204,...
- Max. cycle lengths given by:
- A0????? =
1,1,1,1,2,3,8,12,...
- L.C.M.s of cycle lengths given by:
- A0????? =
1,1,1,1,2,6,24,2520,...
- L-word permuting:
- Yes, the restriction to binary trees induces the gatomorphism A057117.
- Telescoping:
- Yes, contraction gives the permutation A072619.
- Occurs in A073200:
- A072088: no!?
- A072089: no!?
- Scheme functions implementing this gatomorphism on S-expressions:
- Lazily evaluating variant for A072808:
(define (gma072088 s)
(cond ((null? s) s)
(else (lw-bf->p! (p->lw s)))))
(define (p->Lw p)
(reverse! (cdr (reverse
(let recurse ((p p))
(cond ((null? p) (list 0))
(else ;; it is a list.
(append! (list (length p))
(apply append! (map recurse p))
)
)
)
)
)))
)
(define (lw-bf->p! l)
(letrec ((lazy-liz
(lambda (n)
(cond ((zero? n) (list))
(else
(let ((d (pop-with-trailing-zeros! l)))
(cons (delay (lazy-liz d)) (lazy-liz (- n 1)))))))))
(force-bf-wise! (lazy-liz (pop-with-trailing-zeros! l)))))
(define (force-bf-wise! s)
(letrec ((clear? #t)
(force-next-level!
(lambda (s)
(cond ((not (null? s))
(cond ((promise? (car s))
(set-car! s (force (car s)))
(cond ((not (null? (car s))) (set! clear? ()))))
((pair? (car s)) (force-next-level! (car s))))
(force-next-level! (cdr s)))))))
(let loop ()
(set! clear? #t)
(force-next-level! s)
(if (not clear?)
(loop)))
s))
(define (pop-with-trailing-zeros! lista)
(let ((topmost (car lista)))
(cond ((pair? (cdr lista)) (set-car! lista (cadr lista))
(set-cdr! lista (cddr lista)))
(else (set-car! lista 0)))
topmost))
- Continuation-passing variant for A072809:
(define (gma072089 p)
(let ((conts (list car)))
(let recurse ((p p) (depth 0))
(let* ((plp (nthcdr depth conts))
(pass-left (and (pair? plp) (car plp)))
(newcont
(lambda (stack)
((or pass-left
(list-ref conts (-1+ depth)))
(list-n-from-top (length p) stack)))))
(if pass-left
(set-car! plp newcont)
(append! conts (list newcont)))
(for-each (lambda (branch) (recurse branch (1+ depth))) p)))
((car (last-pair conts)) (list))))
(define (list-n-from-top n stack)
(cons (list-head stack n) (nthcdr n stack)))
(define (nthcdr n lista)
(if (or (zero? n)
(null? lista))
lista
(nthcdr (- n 1) (cdr lista))))
- 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.
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.
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.
- Description:
- Meeussen's breadth-first <-> depth-first conversion for binary trees.
- Fixes:
- Counted by A0?????: = 1,1,2,2,2,2,2,2,...
- Cycles correspond to:
- Counted by A038775: = 1,1,2,3,6,10,12,17,...
- Max. cycle lengths given by:
- A057542 =
1,1,1,3,4,16,87,202,...
- L.C.M.s of cycle lengths given by:
- A060113 =
1,1,1,3,12,48,1392,214402800,...
- L-word permuting:
- No.
- Telescoping:
- Yes, contraction gives the permutation A038776.
- Occurs in A073200:
- A057117: no!?
- A057118: no!?
- Scheme functions implementing this gatomorphism on S-expressions:
- Continuation-passing variant for A057118:
(define (gma057118 bt)
(let ((conts (list car)))
(let recurse ((bt bt) (depth 0))
(let* ((plp (nthcdr depth conts))
(pass-left (and (pair? plp) (car plp)))
(newcont
(lambda (stack)
((or pass-left
(list-ref conts (-1+ depth)))
(if (pair? bt)
(cons2top! stack)
(cons bt stack))))))
(if pass-left
(set-car! plp newcont)
(append! conts (list newcont)))
(cond ((pair? bt) (recurse (car bt) (1+ depth))
(recurse (cdr bt) (1+ depth))))))
((car (last-pair conts)) (list))))
(define (nthcdr n lista)
(if (or (zero? n)
(null? lista))
lista
(nthcdr (- n 1) (cdr lista))))
(define (cons2top! stack)
(let ((ex-cdr (cdr stack)))
(set-cdr! stack (car ex-cdr))
(set-car! ex-cdr stack)
ex-cdr))
- 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.
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.
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.
This HTML-document generated with http://www.iki.fi/~kartturi/matikka/Nekomorphisms/gato-out.scm.
For other needed sources, see http://www.iki.fi/~kartturi/matikka/Nekomorphisms/gatomorf.htm
