\documentclass[11pt]{article} %% Or: {amsart}
\usepackage[usenames]{color}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
%% amsthm
%% \usepackage{amsgen,amssymb,amsmath,epsfig,latexsym,graphicx,here,array,verbatim}
\usepackage{amsgen,amssymb,amsmath,epsfig,latexsym,graphicx,array,verbatim}
\usepackage{pstricks,pstcol,pst-node} % FOR DRAWING.
\usepackage{xspace}
\usepackage[all]{xy}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}
\setlength{\oddsidemargin}{0in}
\setlength{\topmargin}{-0.25in}
\setlength{\headheight}{0in}
\newtheorem{lemma}{Lemma}
\newtheorem{propo}{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{coro}{Corollary}
\newtheorem{conj}{Conjecture}
\def\binom#1#2{{#1}\choose{#2}}
\newcommand{\eqn}[1]{(\ref{#1})}
\newcommand{\Stop}{\mbox{Stop}}
\newcommand{\Prob}{\mbox{Prob}}
\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\ga}{\gamma}
\newcommand{\de}{\delta}
\newcommand{\eps}{\varepsilon}
\newcommand{\Om}{\Omega}
\newcommand{\sset}{\subseteq}
\newcommand{\bsq}{{\vrule height .9ex width .8ex depth -.1ex }}
\newcommand{\hsp}{\hspace*{\parindent}}
\newcommand{\FF}{{\mathbb F}}
\newcommand{\RR}{{\mathbb R}}
\newcommand{\NN}{{\mathbb N}}
\newcommand{\ZZ}{{\mathbb Z}}
\newcommand{\QQ}{{\mathbb Q}}
\newcommand{\sW}{{\mathcal W}}
\newcommand{\sS}{{\mathcal S}}
\newcommand{\sP}{{\mathcal P}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\beql}[1]{\begin{equation}\label{#1}}
\newcommand{\brho}{\mbox{\boldmath $\rho$}}
\newcommand{\btau}{\mbox{\boldmath $\tau$}}
\newcommand{\bzero}{{\mathbf 0}}
\newcommand{\bp}{{\mathbf p}}
\newcommand{\bP}{{\mathbf P}}
\newcommand{\bt}{{\mathbf t}}
\newcommand{\bq}{{\mathbf q}}
\newcommand{\bv}{{\mathbf v}}
\newcommand{\bx}{{\mathbf x}}
\newcommand{\by}{{\mathbf y}}
\newcommand{\bm}{{\mathbf m}}
\newcommand{\leftBra}{\{ \hspace*{-.10in} \{ }
\newcommand{\rightBra}{\} \hspace*{-.10in} \} }
%% AK's additions.
\newcommand{\FoldFunSET}{{\mathbb F}}
\newcommand{\SexprSET}{{\mathbb S}}
\newcommand{\FoldRangeSET}{{\mathbb T}}
\newcommand{\beginautdesc}[1]{\subsection{Automorphism~{\it #1}}\begin{tabular}{p{5.5cm}l}}
\newcommand{\finautdesc}{\end{tabular}}
\def\beginppschemecode{\minipage{30mm}
\begin{verbatim}}
\def\endppschemecode{\endminipage}
\def\defequ{\;{\buildrel\text{\rm def}\over=}\;}
\def\sratio#1#2{{#1/#2}}
\def\oratio#1#2{{#1\over #2}}
%% Use \catint around Stanley-letters for various
%% Catalan interpretations:
\newcommand{\catint}[1]{({\it #1})}
% Calligraphic font doesn't quite work here, because
% the lowercase letters produce something unexpected:
%% \newcommand{\catint}[1]{({\ensuremath{\mathcal{#1}}})}
%% This version has both letters surrounded by parentheses: (4 in total)
%% \def\catintbij#1#2{\catint{#1}~$\leftrightarrow$~\catint{#2}}
%% This version surrounds the whole expression in parenteses: (2 in total)
\def\catintbij#1#2{({\it #1}~$\leftrightarrow$~{\it #2})}
\def\catintmap#1#2{({\it #1}~$\rightarrow$~{\it #2})}
%% Use \autname around the automorphism names:
\newcommand{\autname}[1]{{\it *#1}}
\newcommand{\autletter}[1]{$#1$}
\newcommand{\automorphismlet}[1]{automorphism~\autletter{#1}}
\newcommand{\automorphism}[1]{automorphism~\autname{#1}}
\newcommand{\Automorphism}[1]{Automorphism~\autname{#1}}
\def\automorphisms2#1#2{automorphisms~\autname{#1} and \autname{#2}}
\def\automorphismlets2#1#2{automorphisms~\autletter{#1} and \autletter{#2}}
\newcommand{\EISseq}[1]{{\tt #1}}
\newcommand{\charfun}[1]{\ensuremath{\chi_{{#1}}}}
\newcommand{\charfunforcdrnil}{\charfun{A057548}}
\newcommand{\charfunforcarnil}{\charfun{A072795}}
\newcommand{\proglangname}[1]{{\textsc{#1}}}
\newcommand{\scmsym}[1]{{\tt{#1}}}
\newcommand{\scmnum}[1]{{\textsc{#1}}}
\newcommand{\scmetavar}[1]{\ensuremath{\mathit{#1}}}
\newcommand{\scmcode}[1]{{\tt{#1}}}
\newcommand{\scmcodeintext}[1]{{\tt{#1}}}
\newcommand{\SET}[1]{{\textsc{#1}}}
\newcommand{\GROUP}[1]{{\textsc{#1}}}
\newtheorem{example}[theorem]{Example}
\newtheorem{note}[theorem]{Note}
%% \theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
%% \newenvironment{definition}{{\bf Definition}}
\newenvironment{scmsimplefun}{\item[] \begin{tabular}{l}}{\\
\end{tabular}}
\newenvironment{scmexample}{Examples:\\
\begin{tabular}{l l l p{5cm}}}{\end{tabular}}
\newenvironment{scmdefinefun}{\begin{tabular}{l l l p{5cm}}}{\end{tabular}}
\newenvironment{scmdefinefun5}{\begin{tabular}{l l l l p{7cm}}}{\end{tabular}}
\newenvironment{scmdefinefun7}{\begin{tabular}{l l l l l l l}}{\end{tabular}}
\newcommand{\scmexmcomment}[1]{[\emph{#1}]}
\newenvironment{scmnote}{\item[]}{}
\newcommand{\sexpr}{\ensuremath{\textit{S-expression}}\xspace}
\newcommand{\nsexpr}{\ensuremath{\textit{Nihilistic~S-expression}}\xspace}
\newcommand{\nsexprs}{\ensuremath{\textit{Nihilistic~S-expressions}}\xspace}
\newcommand{\lpair}{\ensuremath{\mathit{PAIR}}\xspace}
\newcommand{\symatom}{\ensuremath{\mathit{SYMBOL}}\xspace}
\newcommand{\numatom}{\ensuremath{\mathit{NUMBER}}\xspace}
\newcommand{\nilatom}{\ensuremath{\mathbf{(~)}}\xspace}
\newcommand{\scmfalse}{\ensuremath{\mathbf{\#f}}\xspace}
\newcommand{\scmtrue}{\ensuremath{\mathbf{\#t}}\xspace}
\newcommand{\ra}{\ensuremath{\rightarrow}\xspace}
\newcommand{\lra}{\ensuremath{\leftrightarrow}\xspace}
%% \newcommand{\Ra}{\ensuremath{\:\Rightarrow\:}}
%% \newcommand{\La}{\ensuremath{\:\Leftarrow\:}}
%% \newcommand{\Lra}{\ensuremath{\:\Leftrightarrow\:}}
%% \newcommand{\notRa}{\ensuremath{\:\not\Rightarrow\:}}
%% \newcommand{\la}{\ensuremath{\:\leftarrow\:}}
%% \newcommand{\ra}{\ensuremath{\:\rightarrow\:}}
%% \newcommand{\tra}{\ensuremath{\:\rightarrow^*\:}}
%% \newcommand{\lra}{\ensuremath{\:\leftrightarrow\:}}
%%
%% \newcommand{\Or}{\ensuremath{\ \vee\ }}
%% \newcommand{\And}{\ensuremath{\ \wedge\ }}
%% \newcommand{\A}{\ensuremath{\ \wedge\ }}
%% \newcommand{\U}{\ensuremath{\:\cup\:}}
%% \newcommand{\I}{\ensuremath{\:\cap\:}}
%% \newcommand{\sse}{\ensuremath{\:\subseteq\:}}
%%
%% \newcommand{\fa}{\ensuremath{\forall}}
%% \newcommand{\te}{\ensuremath{\exists}}
%% \newcommand{\fai}{\ensuremath{\stackrel{\infty}{\forall}}}
%% \newcommand{\tei}{\ensuremath{\stackrel{\infty}{\exists}}}
%%
\newcommand{\funapply}{\ensuremath{\circ}}
\newcommand{\fixarrow}{\ensuremath{\circ}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\makeatletter
\def\@sect#1#2#3#4#5#6[#7]#8{\ifnum #2>\c@secnumdepth
\def\@svsec{}\else
\refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip .75em }\fi
\@tempskipa #5\relax
\ifdim \@tempskipa>\z@
\begingroup #6\relax
\@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par}%
\endgroup
\csname #1mark\endcsname{#7}\addcontentsline
{toc}{#1}{\ifnum #2>\c@secnumdepth \else
\protect\numberline{\csname the#1\endcsname}\fi
#7}\else
\def\@svsechd{#6\hskip #3\@svsec #8\csname #1mark\endcsname
{#7}\addcontentsline
{toc}{#1}{\ifnum #2>\c@secnumdepth \else
\protect\numberline{\csname the#1\endcsname}\fi
#7}}\fi
\@xsect{#5}}
\def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2.}]}
\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus
-.2ex}{2.3ex plus .2ex}{\normalsize\bf}}
\makeatother
\makeatletter
\def\subsection{\@startsection {subsection}{1}{\z@}{-3.5ex plus -1ex minus
-.2ex}{2.3ex plus .2ex}{\normalsize\bf}}
\makeatother
\begin{document}
\begin{center}
{\large\bf Introductory Survey of Catalan Automorphisms} \\
\vspace*{+.2in}
{\em Antti Karttunen} \smallskip \\
Tornipolku 11 A 28, 06400 Porvoo, Finland \\
%% Isn\"{a}s Port,
%% Pernaja, Finland \medskip \\
%% OLD JOKE: Porvoo School of Thought \\
%% No affiliation\footnote{Affiliation might be
%% changed to a more academic one soon...} \\
Email address: \href{mailto:his-firstname.his-surname@gmail.com}{{\tt his-firstname.his-surname@gmail.com}}
\bigskip \\
Oct. 10, 2002; last revised \today \bigskip
\end{center}
{\em XXX - NOTE: This is a draft in very premature stage,
and the layout is still terrible. Lot's of material still missing,
incorrect or deficient proofs, notes to be transferred from old margin notes, etc.
Please do not distribute. To be published officially, when
it is ready.}
\begin{center}
{\bf Abstract} \\
\end{center}
In this paper we adopt the programming language Scheme (a dialect of Lisp)
as an unambiguous and elegant {\em notation},
with which we can 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 {\em Catalan automorphisms}\footnote{
The moniker ``gatomorphism'', which the author previously
used for these automorphisms, has been now laid aside.} from
elementary cases, and then play with some simple methods to
generate inductively 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
automorphisms are outside of these sets.
We summarize the formulae of the long-established OEIS-sequences
which we will meet when counting the orbits and fixpoints
to which such automorphisms partition each subset of
Catalan structures of any finite size, and derive also formulae
for two new such sequences, via the orbit-counting ("Burnside's") lemma.
We also observe few specific properties these automorphisms may
have, what are their implications and how various
Catalan automorphisms are related to each other.
\vspace{0.7\baselineskip}
AMS 2000 Classification: Primary 05A15; Secondary: 05A19, 20B27, 20E08, 68P05 \\
%% 05A05 = Combinatorial choice problems (subsets, representatives, permutations)
%% 05A15 = Exact enumeration problems, generating functions
%% See also 33Cxx, 33Dxx.
%% 05A19 = Combinatorial identities
%% 05C05 = Trees.
%% 11B75 = Other combinatorial number theory
%% 11B99 = None of the above, but in this section
%% (11Bxx = Sequences and sets)
%% 13K05 = Witt vectors and related rings
%% 20-XX = Group theory and generalizations
%% 20-04 = Explicit machine computation and programs
%% (not the theory of computation or programming)
%% 20Bxx = Permutation groups
%% 20B25 = Finite automorphism groups of algebraic,
%% geometric, or combinatorial structures
%% See also 05Bxx, 12F10, 20G40, 20H30, 51-XX
%% 20B27 = Infinite automorphism groups [See also 12F10].
%% (12F10 = Separable extensions, Galois theory)
%% 20B40 = Computational methods
%% 20Exx = Structure and classification of infinite or finite groups
%% 20E08 = Groups acting on trees [See also 20F65].
%% 20E36 = General theorems concerning automorphisms of groups
%% 20Fxx = Special aspects of infinite or finite groups (20F99)
%% 20F28 = Automorphism groups of groups [See also 20E36]
%% 68N15 = Programming languages
%% 68P05 = Data structures
%% 68Rxx = Discrete mathematics in relation to computer science
%% 68R05 = Combinatorics
%*****************************************************
%
%
% Section 1
%
%
%*****************************************************
\section{Introduction}\label{Sec1}
After Fibonacci sequence, Catalan numbers has probably
the most celebrated recurrence in enumerative combinatorics:
$$
C_0 = 1, C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}
$$
giving the famous terms:
$$
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...
$$
Because of the way the sequence is defined as a convolution of
it itself, there are surprisingly many combinatorial structures
which it counts. Stanley gives 66 different interpretations
in his Enumerative Combinatorics, volume 2 [Stanley 1999],
and several dozens more in the sequel [Stanley 2001--].
%% For example, there exists five rooted plane binary trees of three
%% internal nodes, but also five rooted general trees
%% of three edges, and five legal parenthesizations with three
%% opening (or closing) parentheses.
Moreover, in many cases there exists a natural isomorphism
between two interpretations, which is sometimes easy to find,
and sometimes not at all.
In this paper we are concerned with the following interpretations.
\begin{description}
\item{\catint{a}} triangulations of a polygon with n+2 edges.
\item{\catint{c} and \catint{d}} rooted plane binary trees of n (internal) nodes.
\item{\catint{e}} rooted plane general trees of n edges.
\item{\catint{L}} Lukasiewicz-words of those general trees.
\item{\catint{i}} Dyck paths of 2n segments. These are also called "Catalan
Mountain Ranges".
\item{\catint{n}} noncrossing chord arrangements with n chords.
\item{\catint{qq}} noncrossing partitions of n.
\item{\catint{rr}} noncrossing Murasaki-diagrams of n stalks.
\item{\catint{P}} parenthesizations of n opening (closing) parentheses.
\end{description}
The lowercase letters refer to the sections of exercise~19 in
chapter~6 of [Stanley 1999],
while the uppercase letters L and P
are used for those manifestations which are not explicitly present
in Stanley's list.
The table 1 shows each of these interpretations up to the size n=3.
\begin{table}[htbp]
\setlength{\extrarowheight}{0.3in}
\begin{tabular}{c c c c c c c c c}
$n$ & A014486($n$) & \catint{i} & \catint{n} & \catint{e} & \catint{qq} & \catint{rr} & \catint{c/d} & \catint{a} \\
0. \vspace{0.1in} & 0 & \includegraphics{kuvat/i0.eps} & \includegraphics{kuvat/n0.eps}
& \includegraphics[scale=2]{kuvat/e0.eps} & \includegraphics{kuvat/qq0.eps}
& & \includegraphics{kuvat/cd0.eps} & \includegraphics{kuvat/a0.eps}\\ \hline
1. \vspace{0.1in} & 2 & \includegraphics{kuvat/i1.eps} & \includegraphics{kuvat/n1.eps}
& \includegraphics[scale=2]{kuvat/e1.eps} & \includegraphics{kuvat/qq1.eps}
& \includegraphics[scale=1]{kuvat/rr1.eps}
& \includegraphics{kuvat/cd1.eps} & \includegraphics{kuvat/a1.eps}\\ \hline
2. \vspace{0.1in} & 10 & \includegraphics{kuvat/i2.eps} & \includegraphics{kuvat/n2.eps}
& \includegraphics[scale=2]{kuvat/e2.eps} & \includegraphics{kuvat/qq2.eps}
& \includegraphics[scale=1]{kuvat/rr2.eps}
& \includegraphics{kuvat/cd2.eps} & \includegraphics{kuvat/a2.eps}\\
3. \vspace{0.1in} & 12 & \includegraphics{kuvat/i3.eps} & \includegraphics{kuvat/n3.eps}
& \includegraphics[scale=2]{kuvat/e3.eps} & \includegraphics{kuvat/qq3.eps}
& \includegraphics[scale=1]{kuvat/rr3.eps}
& \includegraphics{kuvat/cd3.eps} & \includegraphics{kuvat/a3.eps}\\ \hline
4. \vspace{0.1in} & 42 & \includegraphics{kuvat/i4.eps} & \includegraphics{kuvat/n4.eps}
& \includegraphics[scale=2]{kuvat/e4.eps} & \includegraphics{kuvat/qq4.eps}
& \includegraphics[scale=1]{kuvat/rr4.eps}
& \includegraphics{kuvat/cd4.eps} & \includegraphics{kuvat/a4.eps}\\
5. \vspace{0.1in} & 44 & \includegraphics{kuvat/i5.eps} & \includegraphics{kuvat/n5.eps}
& \includegraphics[scale=2]{kuvat/e5.eps} & \includegraphics{kuvat/qq5.eps}
& \includegraphics[scale=1]{kuvat/rr5.eps}
& \includegraphics{kuvat/cd5.eps} & \includegraphics{kuvat/a5.eps}\\
6. \vspace{0.1in} & 50 & \includegraphics{kuvat/i6.eps} & \includegraphics{kuvat/n6.eps}
& \includegraphics[scale=2]{kuvat/e6.eps} & \includegraphics{kuvat/qq6.eps}
& \includegraphics[scale=1]{kuvat/rr6.eps}
& \includegraphics{kuvat/cd6.eps} & \includegraphics{kuvat/a6.eps}\\
7. \vspace{0.1in} & 52 & \includegraphics{kuvat/i7.eps} & \includegraphics{kuvat/n7.eps}
& \includegraphics[scale=2]{kuvat/e7.eps} & \includegraphics{kuvat/qq7.eps}
& \includegraphics[scale=1]{kuvat/rr7.eps}
& \includegraphics{kuvat/cd7.eps} & \includegraphics{kuvat/a7.eps}\\
8. \vspace{0.1in} & 56 & \includegraphics{kuvat/i8.eps} & \includegraphics{kuvat/n8.eps}
& \includegraphics[scale=2]{kuvat/e8.eps} & \includegraphics{kuvat/qq8.eps}
& \includegraphics[scale=1]{kuvat/rr8.eps}
& \includegraphics{kuvat/cd8.eps} & \includegraphics{kuvat/a8.eps}\\
\end{tabular}
\caption{The interpretations \catint{i}, \catint{n}, \catint{e}, \catint{qq}, \catint{rr}, \catint{c/d} and \catint{a} for the sizes 0, 1, 2 and 3 of the Catalan structures.}
\end{table}
The natural isomorphism between the Dyck paths~\catint{i}
and parenthesizations can be seen immediately, as well as
between parenthesizations and plane general trees~\catint{e}.
Lukasiewicz-word of a rooted plane tree is obtained by
traversing it depth-first-wise from left to right, and
writing down the (out-)degree of each node, leaves
(terminal nodes) producing zero.
Also the interpretation~\catint{n} hides parenthesizations,
which can be easily seen, when one cuts open the
circular tables of noncrossing chord arrangements
from the bottom, and deforms the circle
to an arc. (The starting and ending vertices
of each chord correspond to a pair of balanced opening
and closing parentheses, see~figure~1).
The interpretations \catint{qq} and \catint{rr} are related to each
other in similar simple manner.
However, there are several natural isomorphisms between Dyck paths
\catint{i} and noncrossing Murasaki-diagrams \catint{rr}.
In this paper we will use the "right-hand side slope mapping",
which operates by drawing a vertical line above each right-hand side
slope, and then connecting those vertical lines that originate from
the same height without any lower valleys between. This is
illustrated in the figure~2, and the reader can check that
it is indeed used in the table~1.
\begin{figure}[hbtp]
\includegraphics[scale=0.7, viewport=0 0 275 70, clip]{kuvat/i-rr250.eps}
\caption{``Right-hand side slope mapping'' defines an isomorphism
between the interpretations \catint{i} and \catint{rr}.}
\end{figure}
At the extreme right of the figure 1 we have interpretations \catint{c/d}
and \catint{a}. It is easy to see that each binary tree naturally defines
an unique polygon triangulation, as can be seen from the figure 3
where a binary tree has been drawn inside the corresponding polygon
triangulation.
However, a natural isomorphism between \catint{c/d} and \catint{e} or \catint{i} was not
explicitly described until 1967 in [De Brujn and Morselt 1967]. Between \catint{i} and
\catint{d} it takes the following form. Proceeding from left to right,
replace each upward slope {\bf /} of the Dyck path with 1, and downward
slope {\ensuremath {\bf{\backslash}}} with 0. For example, from
$$
\includegraphics[scale=1]{kuvat/i19.eps}
$$
we get
$$
11100010
$$
from which we build a binary tree in depth-first fashion from left to
right, with 1's in binary expansion standing for internal (branching)
nodes, and 0's for leaves:
%% $$
%% \includegraphics[scale=1]{kuvat/d19.eps}
%% $$
\begin{center}
\psset{xunit=.3cm,yunit=.3cm}
\pspicture*(-8,-2)(8,9)
% \dotnode(+0,+0){root}
% \dotnode(-2,+2){nodeL}
% \dotnode(+2,+2){nodeR}
% \dotnode(-3,+4){nodeLL}
% \dotnode(-1,+4){nodeLR}
% \dotnode(+1,+4){nodeRL}
% \dotnode(+3,+4){nodeRR}
\dotnode(+0,+0){root}
\dotnode(-2.5,2){nodeL}
\dotnode(+2.5,2){nodeR}
\dotnode(-4.5,+4){nodeLL}
\dotnode(-0.5,+4){nodeLR}
\dotnode(+0.5,+4){nodeRL}
\dotnode(+4.5,+4){nodeRR}
\dotnode(-6.5,+6){nodeLLL}
\dotnode(-2.5,+6){nodeLLR}
\ncline{root}{nodeL}
\ncline{root}{nodeR}
\ncline{nodeL}{nodeLL}
\ncline{nodeL}{nodeLR}
\ncline{nodeR}{nodeRL}
\ncline{nodeR}{nodeRR}
\ncline{nodeLL}{nodeLLL}
\ncline{nodeLL}{nodeLLR}
% Subtract 1 from y-coordinate for internals, add 0.8 for leaves
\rput{*0}(+0,-1){{\bf 1}} % root
\rput{*0}(-2.5,+1){{\bf 1}} % nodeL
\rput{*0}(-4.5,+3){{\bf 1}} % nodeLL
\rput{*0}(-6.5,+6.8){{\bf 0}} % nodeLLL
\rput{*0}(-2.5,+6.8){{\bf 0}} % nodeLLR
\rput{*0}(-0.5,+4.8){{\bf 0}} % nodeLR
\rput{*0}(+2.5,+1){{\bf 1}} % nodeR
\rput{*0}(+0.5,+4.8){{\bf 0}} % nodeRL
\rput{*0}(+5.0,+4.8){${\mathbf 0^*}$} % nodeRR
% \rput{*0}(+4.5,+4){${\mathbf 0^*}$} % nodeRR
% \rput{*0}(+4.5,+4.8){{\bf (0)}} % nodeRR
\endpspicture
\end{center}
Note that the last leaf of the binary tree is always implicit, marked here with
{${\mathbf 0^*}$}.
% {\bf (0)}.
We explain the details of the direct mapping between \catint{d} and \catint{e}
in the next section where we
show how that isomorphism is implicitly present in the algorithm
that converts Lisp/Scheme linked list structures from their internal
to external representation.
With these isomorphisms at hand, we can fill the remaining
gaps. E.g. we define an isomorphism \catintbij{a}{qq}
as a composition of isomorphisms \catintbij{a}{d}, \catintbij{d}{e},
\catintbij{e}{i}, \catintbij{i}{rr} and \catintbij{rr}{qq}.
These {\em canonical} isomorphisms define the correspondences used in
the rest of this paper. E.g. if we say that a particular
Catalan automorphism rotates noncrossing partitions~\catint{qq} one step
clockwise, it actually means that when the preimage and image
of any binary tree (with respect to that automorphism) are transformed
through such a chain of isomorphisms to noncrossing partitions,
we will observe that in the interpretation~\catint{qq} the image
is a clockwise rotation of the corresponding preimage.
Table~2 illustrates how a Scheme implementation of the \automorphism{A086429},
although working directly on binary trees (the interpretation \catint{d} on the left),
eventually effects the clockwise rotation of noncrossing partitions
(the interpretation \catint{qq} on the right)
through the natural bijections \catintbij{d}{A063171},
\catintbij{A063171}{i}, \catintbij{i}{rr}
and \catintbij{rr}{qq}.
\begin{table}[htbp]
\setlength{\extrarowheight}{0.3in}
\begin{tabular}{c c c c c c}
index of structure in A014486 & \catint{d} & \catint{A063171}
& \catint{i} & \catint{rr} & \catint{qq} \\
\vspace{0.1in} 29 [= A086429(39)] & \includegraphics{kuvat/d29.eps} & 1011001100
& \includegraphics{kuvat/i29.eps} & \includegraphics{kuvat/rr29.eps}
& \includegraphics{kuvat/qq29.eps} \\
\vspace{0.1in} A086429(29) = 46 & \includegraphics{kuvat/d46.eps} & 1101011000
& \includegraphics{kuvat/i46.eps} & \includegraphics{kuvat/rr46.eps}
& \includegraphics{kuvat/qq46.eps} \\
\vspace{0.1in} A086429(46) = 38 & \includegraphics{kuvat/d38.eps} & 1100101100
& \includegraphics{kuvat/i38.eps} & \includegraphics{kuvat/rr38.eps}
& \includegraphics{kuvat/qq38.eps} \\
\vspace{0.1in} A086429(38) = 48 & \includegraphics{kuvat/d48.eps} & 1101100100
& \includegraphics{kuvat/i48.eps} & \includegraphics{kuvat/rr48.eps}
& \includegraphics{kuvat/qq48.eps} \\
\vspace{0.1in} A086429(48) = 39 & \includegraphics{kuvat/d39.eps} & 1100110010
& \includegraphics{kuvat/i39.eps} & \includegraphics{kuvat/rr39.eps}
& \includegraphics{kuvat/qq39.eps} \\
\end{tabular}
\caption{The effects of \autname{A086429} on the interpretations
\catint{d}, \catint{A063171}, \catint{i}, \catint{rr} and \catint{qq}.}
\end{table}
%% Jonnekin:
There are several mathematical structures that can be naturally
embedded into Catalan structures, e.g. binary strings
which naturally map to that subset of binary trees, which have
no double-branches (we mark 0 when the binary tree branches to left,
and 1 when it branches to the right, or vice versa!),
as well as various Motzkin-structures
that can be embedded into Catalania by various means.
Some Catalan automorphisms keep such subsets of structures
closed, so they induce also an automorphism on those
isomorphic structures. For example, it's easy to construct
a Catalan automorphism that implements a permutation contained in
binary reflected Gray Code, or one that rotates
the non-crossing Mozkin-chords that are embedded
in some Catalan-structure (\automorphism{A085159} and
\autname{A085160}). In some way such
Catalan automorphisms
can then be viewed as {\it extensions} of those
automorphisms.
What's more important, because Catalan structures
can be embedded into themselves,
This topic is further explored in section XXX, ``Embeddability''.
%% Erilaiset rekursiomuodot, INVERT, CONV(A000108,F), ym. muunnokset.
%*****************************************************
%
%
% Section 2
% S-expressions.
%
%
%*****************************************************
\section{S-expressions}\label{Sec2}
In many cases it would be nice to have a concise and unambiguous notation
for symmetry and other operations involving the structures presented in the
previous chapter. Also, when examining their orbit-profiles it's useful
to have some empirical data before trying to derive mathematical conclusions.
Naturally, such data can be obtained with computer, by programming the
rotations, reflections and other operations as procedures that act on
data structures implementing various manifestations presented in Chapter I.
E.g., a simple-minded approach based on the object-oriented programming (OOP)
paradigm might devise a separate class for each such manifestation, with
certain inheritance between the classes, e.g. a class of binary trees might
be a subclass of general trees, and non-crossing handshakes and set-partitions
might diverge from a common class of chord-diagrams.
The objects instantiating the said classes would then each hide
its own set of private elements, for whose manipulation specific
methods would be needed.
Clearly this approach is far too baroque, when in the previous chapter
I have already shown that these various interpretations for
Catalan numbers are just different manifestations of the one and
same combinatorial structure. This means that to effect, say a rotation
of Euler's polygon divisions, it's enough to define a certain
operation on binary trees, as long as we have a commonly agreed
isomorphism from binary trees to polygon triangulations,
for example the one presented in the previous chapter.
So, instead of tailoring multiple custom data types, a single
universal one should suffice.
It turns out that {\em S-expressions}, introduced by John McCarthy
in his programming language \proglangname{Lisp} [McCarthy 1960] naturally fill the bill. %% fit the bill.
Being originally just designed for the manipulation of such
data structures, \proglangname{Lisp} contains a powerful set of primitives
for their manipulation, which have in turn been inherited
by its dialect \proglangname{Scheme} [Sussman and Steele 1975],
and to a lesser extent also by \proglangname{Prolog}, and certain more recent functional
programming languages derived from these.
%% Thus with these languages, having a natural support for such manipulations,
%% we can write the corresponding definitions in totally transparent way,
%% and thus they are much more amenable to mathematical analysis.
%% \label{S-expression}
In this paper we define an {\em S-expression} in two different ways.
Both definitions are given in \textsc{bnf}.
\begin{definition}[{S-expression in its internal, ``dotted'' form.}]
$$
\begin{array}{rll}
\sexpr & \ra & \symatom~~\vert~~\numatom~~\vert~~\nilatom~~\vert~~\lpair \\
\lpair & \ra & (\sexpr~.~\lpair)~~\vert~~(\sexpr~.~\nilatom) \\
\end{array}
$$
\end{definition}\footnote{
Note that our definition of the ``dotted'' S-expression differs from the standard
definition used in \proglangname{Lisp} and \proglangname{Scheme}:
$$
\sexpr \ra \symatom~~\vert~~\numatom~~\vert~~\nilatom~~\vert~~(\sexpr~.~\sexpr)
$$
that it doesn't allow other terminals than the empty list~\nilatom on the right
side of a pair.}
\begin{definition}[{\it S-expression in its external, ``dotless'' list form.}]
$$
\begin{array}{rll}
\sexpr & \ra & \symatom~~\vert~~\numatom~~\vert~~(\sexpr^*) \\
\end{array}
$$
\end{definition}
Here a trailing~``$^{*}$'' denotes zero or more occurrences.
\symatom and \numatom refer to symbolic and numeric
terminals. \scmsym{define}, \scmsym{pair?}, \scmsym{else} and
\scmsym{+} are examples of the former, and
\scmnum{144}, \scmnum{-1} and \scmnum{2.71828}
of the latter class. ``\nilatom'' refers to a special terminal
called either an \emph{empty list} or \emph{NIL}.
The above definitions produce isomorphic structures. The isomorphism
between the two variant syntaxes is realized by the function $f$ which
maps from the ``dotted pair'' to ``list'' syntax as follows:
$$
f(s) = \left\{ \begin{array}{p{5cm}p{7cm}}
s & \textrm{if $s$ is \numatom, \symatom or \nilatom} \\
(\:$f(\sexpr)$\:) & \textrm{if $s$ is of the form
($\sexpr$~.~\nilatom)}\\
\textrm{a list constructed by inserting $f(\sexpr)$ to the front of a list
obtained with $f(\lpair)$}
& \textrm{if $s$ is of the form ($\sexpr$~.~$\lpair$)}\\
\end{array} \right.
$$
%% \begin{tabular}{lll}
%% \numatom & \ra & \numatom \\
%% \symatom & \ra & \symatom \\
%% \nilatom & \ra & \nilatom \\
%% (\sexpr~.~\nilatom) & \ra & ( $f$(\sexpr) ) \\
%% ($X$~.~$Y$) & \ra & a list constructed by inserting
%% $f$($X$) to the front\\
%% & & of a list obtained with $f$($Y$)\\
%% \end{tabular}
\begin{example}
The function $f$ maps the internal, dotted S-expression
``$(\nilatom~.~(\scmnum{1}~.~(\scmsym{two}~.~(\scmnum{2}~.~\nilatom))))$''
to an external, dotless list
``$(\nilatom~\scmnum{1}~\scmsym{two}~\scmnum{2})$''
and likewise, the internal, dotted S-expression
``$(\scmsym{a}~.~((\scmsym{b}~.~\nilatom)~.~\nilatom))$''
to an external, dotless list
``$(\scmsym{a}~(\scmsym{b}))$''
%% $(\scmsym{one}~.~(\scmnum{1}~.~(\scmsym{two}~.~(\scmnum{2}~.~\nilatom))))$
%% to an external, dotless list
%% $(\scmsym{one}~\scmnum{1}~\scmsym{two}~\scmnum{2})$
%% $(\scmsym{a}~.~(((~)~.~(\scmnum{2}~.~(~)))~.~(\scmsym{b}~.~(~))))$
%% to an external, dotless list
%% $(\scmsym{a}~((~)~\scmnum{2})~\scmsym{b})$
\end{example}
If we consider a subset of S-expressions where the only
allowed terminals are \nilatom's (i.e.~\emph{NIL}'s),
we get the following definition:
\begin{definition}[{\it Nihilistic S-expression in its internal, ``dotted'' form.}]
$$
\begin{array}{rll}
\nsexpr & \ra & \nilatom~~\vert~~(\nsexpr~.~\nsexpr) \\
\end{array}
$$
\end{definition}
It is clear that this definition is isomorphic with
rooted plane binary trees introduced in the previous chapter,
one of the most familiar interpretations
\catint{c/d} of Catalan numbers.
When we apply the above function $f$ to this subset,
the result is interpretation \catint{P} (parenthesizations)
surrounded by an extra pair of ``(`` and ``)''. We dub this
interpretation as \catint{Px} (parenthesizations surrounded
by extra parentheses).
\begin{example}
The function $f$ maps the internal, dotted ``nihilistic''
S-expressions to the interpretation \catint{Px} as follows:
$$
\begin{array}{lll}
\nilatom & \ra & \nilatom \\
(\nilatom~.~\nilatom) & \ra & (\nilatom) \\
(\nilatom~.~(\nilatom~.~\nilatom)) & \ra & (\nilatom~\nilatom) \\
((\nilatom~.~\nilatom)~.~\nilatom) & \ra & ((\nilatom)) \\
etc.\\
\end{array}
$$
\end{example}
When we discard the outermost parentheses from the produced
parenthesizations, we see that the above mapping hides
a map \catintmap{c/d}{i}:
\begin{center}
\begin{tabular}{l l l}
\catint{c/d} & & \catint{i} \\
\includegraphics{kuvat/cd0.eps} \vspace{0.1in} & \ra & \includegraphics{kuvat/i0.eps} \\
\includegraphics{kuvat/cd1.eps} \vspace{0.1in} & \ra & \includegraphics{kuvat/i1.eps} \\
\includegraphics{kuvat/cd2.eps} \vspace{0.1in} & \ra & \includegraphics{kuvat/i2.eps} \\
\includegraphics{kuvat/cd3.eps} \vspace{0.1in} & \ra & \includegraphics{kuvat/i3.eps} \\
\ensuremath{\mathit{etc.}}\\
\end{tabular}
\end{center}
We leave it as an excercise to the reader to prove
that the map \catintmap{c/d}{i} produced this way
is the inverse of the map \catintmap{i}{c/d}
presented in the previous chapter.
%
%*****************************************************
%
%
% Section 3
% A brief introduction to the programming language Scheme.
%
%
%*****************************************************
\section{A brief introduction to the programming language
Scheme\protect\footnote{Most
of what is said here applies also to Lisp, with just minor
changes in the names of some primitives and functions.
We might gloss over some details, as our purpose is just to describe
a subset of the language sufficient for implementing Catalan automorphisms.}}\label{Sec3}
All computations in \proglangname{Scheme} are effected by
\emph{evaluating} function calls or so called
special forms. Specifically, a program written in
\proglangname{Scheme} is nothing more than a set of
user-defined functions invoking each other in addition
to built-in functions and special-forms provided by the language.
The syntax of the \proglangname{Scheme} is based
on S-expressions defined in the previous section.
Each invocation of a function (or special form) with arity $n$
is represented as a list of length $n+1$,
where the first element of the list
is the name of the called function (special form).
For example, a function invocation with three arguments,
represented in mathematics usually as $f(a,~b,~c)$
is represented in \proglangname{Scheme} as a list
of four elements: $(f~a~b~c)$.
Similarly, a nested invocation like $LCM(GCD(72,~15),~4)$
is represented by a nested list structure (S-expression):
$(\scmsym{LCM}~(\scmsym{GCD}~72~15)~4)$.
Function calls are evaluated by evaluating
first their arguments.
Symbols and S-expressions prefixed with a single quote~(')
evaluate to themselves, i.e. are supplied
literally to the invoked function.
Numeric arguments also evaluate to themselves,
while unquoted symbols evaluate to the value
they are \emph{bound} to, a concept explained later.
However, if any argument itself is a non-quoted
S-expression, it is considered as an invocation
of another function (or special-form), and
is evaluated before its value can be used
in its place, as an argument to an original
function. Thus, if an S-expression is viewed
as a rooted general plane tree, its evaluation
triggers a depth-first traversal down to
its quoted branches and the symbolic and numeric leaves.
%% in depth-first manner, postorder manner.
Note that the special forms differ from real functions in that
not all of their ``arguments'' are evaluated at all the times.
%% \begin{note}
%% Note that in the following examples the S-expression arguments
%% that are supplied literally to an invoked function, i.e. without evaluation,
%% are prefixed with a single quote~(').
%% \end{note}
%% The user defines new functions with \scmsym{define} special form,
%% which has the following syntax:
The following list gives the built-in functions and special forms
that are sufficient to implement most of the Catalan automorphisms mentioned
in this paper.
\begin{description}
%% cons
\begin{scmsimplefun}
(\scmsym{cons} \scmetavar{Sexpr1} \scmetavar{Sexpr2})
\end{scmsimplefun}
Returns a new S-expression (\scmetavar{Sexpr1}~.~\scmetavar{Sexpr2})
\paragraph{Remark.}
In the context of binary trees~\catint{c/d}, \scmsym{cons} creates
a new binary tree from the left hand side tree \scmetavar{Sexpr1} and
the right hand side tree \scmetavar{Sexpr2}.
In the context of general trees~\catint{e}, \scmsym{cons} creates
a general tree, by grafting tree \scmetavar{Sexpr1} as a scion
to the left of all the branches of tree \scmetavar{Sexpr2}.
In the context of Dyck paths~\catint{i}, \scmsym{cons} creates
a new Dyck path by inserting to ...
\begin{scmexample}
\scmcode{(cons 'a 'b)} & \ra & \scmcode{(a . b)}\\
\scmcode{(cons '()~'(()~.~()))}\\
& \ra & \scmcode{(()~.~(()~.~()))} & \scmexmcomment{Result in internal, dotted-pair format.}\\
& \ra & \scmcode{(()~())} & \scmexmcomment{Result in external format.}\\
\end{scmexample}
%% car
\begin{scmsimplefun}
(\scmsym{car} \scmetavar{Pair})
\end{scmsimplefun}
\scmetavar{Pair} should be of the form (\scmetavar{Sexpr1}~.~\scmetavar{Sexpr2}).
This function returns \scmetavar{Pair}'s left-hand side,
i.e. \scmetavar{Sexpr1}.
\begin{scmexample}
\scmcode{(car '(a b))} & \ra & \scmcode{a}\\
\scmcode{(car '((a b) c d))} & \ra & \scmcode{(a~b)}\\
\end{scmexample}
%% cdr
\begin{scmsimplefun}
(\scmsym{cdr} \scmetavar{Pair})
\end{scmsimplefun}
\scmetavar{Pair} should be of the form (\scmetavar{Sexpr1}~.~\scmetavar{Sexpr2}).
This function returns \scmetavar{Pair}'s right-hand side,
i.e. \scmetavar{Sexpr2}.
\begin{scmexample}
\scmcode{(cdr '(a b))} & \ra & \scmcode{(b)}\\
\scmcode{(cdr '((a b) c d))} & \ra & \scmcode{(c~d)}\\
\end{scmexample}
%% list
\begin{scmsimplefun}
(\scmsym{list} \scmetavar{Sexpr_1} .. \scmetavar{Sexpr_n})
\end{scmsimplefun}
Returns a list constructed from its arguments.
\begin{scmexample}
\scmcode{(list)} & \ra & \nilatom & \scmexmcomment{With no arguments
gives an empty list.}\\
\scmcode{(list '(a b))} & \ra & \scmcode{((a b))} &
\scmexmcomment{Unary form surrounds with extra parentheses.}\\
\scmcode{(list 'a 'b)} & \ra & \scmcode{(a~b)}\\
\end{scmexample}
\paragraph{Remark.}
In the context of binary trees~\catint{c/d}, \scmsym{(list a)} creates
a new binary tree, whose left hand side tree will be \scmetavar{a} and
the right hand side tree an empty leaf. {\em (XXX -- wording)}
In the context of general trees~\catint{e}, \scmsym{(list a)} creates
a new general tree, by {\em ``planting''} the tree \scmetavar{a}
over the trunk of one edge. {\em (XXX -- Draw a nice picture here!)}
In the context of Dyck paths~\catint{i}, \scmsym{list} rises its arguments
on the pedestal /{\dots}{\\}
In the context of parenthesizations~\catint{P}, an unary \scmsym{list} surrounds
its argument with extra parentheses.
%% null?
\begin{scmsimplefun}
(\scmsym{null?} \scmetavar{Sexpr})
\end{scmsimplefun}
Returns \scmtrue~(true) if its argument is an empty list~\nilatom,
otherwise \scmfalse~(false).
\begin{scmexample}
\scmcode{(null? '(a))} & \ra & \scmfalse\\
\scmcode{(null? (list))} & \ra & \scmtrue\\
\end{scmexample}
%% pair?
\begin{scmsimplefun}
(\scmsym{pair?} \scmetavar{Sexpr})
\end{scmsimplefun}
Returns \scmtrue~(true) if its argument is a cons cell,
otherwise \scmfalse~(false).
\begin{scmexample}
\scmcode{(pair? '(a))} & \ra & \scmtrue\\
\scmcode{(pair? (list))} & \ra & \scmfalse\\
\end{scmexample}
%% not
\begin{scmsimplefun}
(\scmsym{not} \scmetavar{Sexpr})
\end{scmsimplefun}
Returns \scmtrue~(true) if its argument is \scmfalse~(false),
and for all other values returns \scmfalse~(false).
\begin{scmexample}
\scmcode{(not (pair? '(a)))} & \ra & \scmfalse\\
\scmcode{(not (pair? (list)))} & \ra & \scmtrue\\
\end{scmexample}
\begin{scmnote}
\textit{Note:} As long we restrict our attention to \nsexprs
(as in the implementations of various Catalan automorphisms
in this paper), then
(\scmsym{null?} \scmetavar{Sexpr}) is equivalent to (\scmsym{not} (\scmsym{pair?} \scmetavar{Sexpr}))
and
(\scmsym{pair?} \scmetavar{Sexpr}) is equivalent to (\scmsym{not} (\scmsym{null?} \scmetavar{Sexpr}))
\end{scmnote}
%% if
\begin{scmsimplefun}
(\scmsym{if} \scmetavar{Sexpr_1} \scmetavar{Sexpr_2} \scmetavar{Sexpr_3})
\end{scmsimplefun}
Returns the value of \scmetavar{Sexpr_2} if \scmetavar{Sexpr_1}
evaluates to a non-false value, otherwise evaluates
\scmetavar{Sexpr_3} and returns its value.
Note that \scmsym{if} always evaluates either \scmetavar{Sexpr_2}
or \scmetavar{Sexpr_3}, but never both.
\begin{scmexample}
\scmcode{(if (null? (list)) (list 'it 'is 'empty) (list 'not 'empty))} & \ra & \scmcode{(it is empty)}\\
\scmcode{(if (pair? (list)) (list 'it 'is 'a 'pair) (list 'not 'pair))} & \ra & \scmcode{(not pair)}\\
\end{scmexample}
%% cond
\item[] \begin{tabular}{l l}
(\scmsym{cond} & (\scmetavar{TestExprA} \scmetavar{ExprA_1} \ldots \scmetavar{ExprA_n})\\
& (\scmetavar{TestExprB} \scmetavar{ExprB_1} \ldots \scmetavar{ExprB_n})\\
& $\cdots$\\
& (\scmsym{else} \scmetavar{ExprElse_1} \ldots \scmetavar{ExprElse_n})\\
)\\
\end{tabular}
If \scmetavar{TestExprA} evaluates to a non-false value, executes
expressions \scmetavar{ExprA_1} \ldots \scmetavar{ExprA_n} listed
after it, returning the value of the last one (\scmetavar{ExprA_n}) as
the value of whole \scmsym{cond}-expression, without evaluating any
other expressions. Otherwise, checks whether \scmetavar{TestExprB}
evaluates to a non-false value, and if so, executes
expressions \scmetavar{ExprB_1} \ldots \scmetavar{ExprB_n} listed
after it, again returning the value of the last one as the value
of the whole \scmsym{cond}-expression.
If none of the test-expressions evaluate to a non-false value before
\scmsym{else}-branch, then the expressions
\scmetavar{ExprElse_1} \ldots \scmetavar{ExprElse_n}
are evaluated, with the value of the last one returned as the value
of the whole cond-expression.
\begin{scmexample}
\scmcode{(cond} & \multicolumn{3}{l}{\scmcode{((null? (list)) (list 'it 'is 'empty))}}\\
& \scmcode{(else (list 'it 'is 'not 'empty))}\\
\scmcode{)}\\
& \ra & \scmcode{(it is empty)}\\
\end{scmexample}
\begin{scmnote}
\textit{Note:}
(\scmsym{if}~\scmetavar{Expr_1}~\scmetavar{Expr_2}~\scmetavar{Expr_3})
is equivalent to
(\scmsym{cond}~(\scmetavar{Expr_1}~\scmetavar{Expr_2})~(\scmsym{else}~\scmetavar{Expr_3}))
\end{scmnote}
%% define
\item[] \begin{tabular}{l l}
(\scmsym{define} & (\scmetavar{funcname} \scmetavar{arg_1} \ldots \scmetavar{arg_n})\\
& \scmetavar{expr_1}\\
& $\cdots$\\
& \scmetavar{expr_n}\\
{)}\\
\end{tabular}
Defines a new function named \scmetavar{funcname} with formal arguments
\scmetavar{arg_1} ... \scmetavar{arg_n}.
When the function \scmetavar{funcname} is invoked, the values of
of the actual arguments will be bound to the formal arguments,
%% which way? c.f. bound to - bound with ?
and each of the expressions \scmetavar{expr_1} \ldots \scmetavar{expr_n} will be executed
in turn, with the value of \scmetavar{expr_n} being returned as the result of the
function invocation.
\begin{scmexample}
\multicolumn{4}{l}{\scmcode{(define (ourlcm a b)} \scmcode{(* a (/ b (gcd a b))))}}\\
& & & \scmexmcomment{We define our version of the LCM-function,
using the built-in functions ``*'' (multiplication),
``/'' (integer division) and ``gcd''.}\\
\scmcode{(ourlcm 12 15)} & \ra & 60 & \scmexmcomment{Works as expected.}\\
%% \scmcode{(define (xcons x y) (cons y x))}
%% \scmcode{(xcons 'a 'b) \ra (b . a)} \emph{[We defined a "crossed" cons.]}
\end{scmexample}
%% let
\item[] \begin{tabular}{l l}
(\scmsym{let} & ((\scmetavar{Sym_1} \scmetavar{InitExpr_1})\\
& $\cdots$\\
& (\scmetavar{Sym_n} \scmetavar{InitExpr_n}))\\
& \scmetavar{Expr_1}\\
& $\cdots$\\
& \scmetavar{Expr_n}\\
{)}\\
\end{tabular}
Evaluates the expressions \scmetavar{InitExpr_1} \ldots
\scmetavar{InitExpr_n} in parallel, and binds the symbols
\scmetavar{Sym_1} \ldots \scmetavar{Sym_n} temporarily
to the resulting values, then executes each of the
expressions \scmetavar{Expr_1} \ldots \scmetavar{Expr_n}
in turn, returning the value of the last one (\scmetavar{Expr_n})
as the result of the whole \scmsym{let}-expression.
Note that in \proglangname{Scheme} \scmsym{let} offers the
standard way to define temporary variables
inside the functions definitions.
%% append
\begin{scmsimplefun}
(\scmsym{append} \scmetavar{Sexpr_1} .. \scmetavar{Sexpr_n})
\end{scmsimplefun}
Returns a list concatenated from its arguments.
\begin{scmexample}
\scmcode{(append)} & \ra & \nilatom & \scmexmcomment{With no arguments
gives an empty list.}\\
\scmcode{(append '(a b) '(c))} & \ra & \scmcode{(a b c)}\\
\scmcode{(append '() '(a b) '() '(c d) '())} & \ra & \scmcode{(a~b~c~d)} &
\scmexmcomment{Empty lists are silently ignored.}\\
\end{scmexample}
\paragraph{Remark.}
In the context of general trees~\catint{e}, \scmsym{append} creates
a new general tree, by ... {\em (XXX -- Draw a nice picture here!)}
In the context of Dyck paths~\catint{i}, parenthesizations~\catint{P} {\em and whatever}
\scmsym{append} just concatenates the structures given as its arguments.
\begin{scmnote}
\textit{Note:} We can implement our own, a strictly 2-ary version of \scmsym{append}
with the following recursive definition:
\end{scmnote}
\begin{scmdefinefun}
\scmcode{(define} & \multicolumn{3}{l}{\scmcode{(append2 a b)}}\\
& \scmcode{(cond} & \scmcode{((null? a) b)}\\
& & \scmcode{(else (cons (car a) (append2 (cdr a) b)))}\\
& \scmcode{)}\\
\scmcode{)}\\
\end{scmdefinefun}
%% set-car!
\begin{scmsimplefun}
(\scmsym{set-car!} \scmetavar{Pair} \scmetavar{SexprNew})
\end{scmsimplefun}
Modifies physically the left-hand side of \scmetavar{Pair} which should
be of the form (\scmetavar{Sexpr1}~.~\scmetavar{Sexpr2}),
and which after the modification is transformed to
(\scmetavar{SexprNew}~.~\scmetavar{Sexpr2}).
An error results if the first argument is not a cons cell.
\begin{scmexample}
%% \scmcode{(set-car! '(a b) 'c)} & \ra & \scmcode{(c~a)}\\
\scmcode{(let} & \multicolumn{2}{l}{\scmcode{((ourpair (list 'a 'b)))}}
& \scmexmcomment{\scmsym{ourpair} is bound to \scmcode{(a~b)}}\\
& \scmcode{(set-car! ourpair 'c)}\\
& \scmcode{ourpair}\\
\scmcode{)}\\
& \ra & \scmcode{(c~a)}\\
\end{scmexample}
%% set-cdr!
\begin{scmsimplefun}
(\scmsym{set-cdr!} \scmetavar{Pair} \scmetavar{SexprNew})
\end{scmsimplefun}
Modifies physically the right-hand side of \scmetavar{Pair} which should
be of the form (\scmetavar{Sexpr1}~.~\scmetavar{Sexpr2}),
and which after the modification is transformed to
(\scmetavar{Sexpr1}~.~\scmetavar{SexprNew}).
An error results if the first argument is not a cons cell.
\begin{scmexample}
%% \scmcode{(set-cdr! '(a b) '(c))} & \ra & \scmcode{(a~c)}\\
\scmcode{(let} & \multicolumn{2}{l}{\scmcode{((ourpair (list 'a 'b)))}}
& \scmexmcomment{\scmsym{ourpair} is bound to \scmcode{(a~b)}}\\
& \scmcode{(set-cdr! ourpair '(c))}\\
& \scmcode{ourpair}\\
\scmcode{)}\\
& \ra & \scmcode{(a~c)}\\
\end{scmexample}
\end{description}
%*****************************************************
%
%
% Section 4
% Constructive and destructive implementations of automorphisms
%
%
%*****************************************************
\section{Constructive and destructive implementations of Catalan automorphisms}\label{Sec4}
\textit{Definition.}
\textrm{We say that a Scheme implementation of Catalan automorphism is}
\textit{destructive}
\textrm{if it invokes either of the primitives} \scmsym{set-car!}
\textrm{or} \scmsym{set-cdr!}
\textrm{shown above, or any function which invokes them explicitly or implicitly.
If a Scheme implementation of a Catalan automorphism is not destructive,
then we say that it is}
\textit{constructive}.
%% Differences between constructive and destructive implementations
If we exclude \scmsym{set-car!} and \scmsym{set-cdr!} from the
set of primitives listed above, we can only define automorphisms
and other functions that leave intact the physical structure of
the S-expression(s) given as their argument(s).
Apart from the trivial identity automorphism,
%% at least for some S-expressions given as its argument
on some values of its argument
every Catalan automorphism must return an S-expression with different
structure than the argument has.
Because by its very definition a Catalan automorphism
is \textit{a~bijection on the set of structures of the same size}
it is impossible to implement this with a function
containing only invocations of the accessor-functions
\scmsym{car} and/or \scmsym{cdr},
as then the result's size (\textit{in cons cell nodes})
would be less than that of the argument.
So to effect changes which return an S-expression of the same size
but of different structure, it must invoke the function \scmsym{cons},
or some other functions like \scmsym{append} or \scmsym{list} which calls
\scmsym{cons} implicitly.
For this reason these are called \textit{constructive} implementations
of Catalan automorphisms.
On the other hand, if an implementation of an automorphism invokes
\scmsym{set-car!} and/or \scmsym{set-cdr!} or any other function
invoking them, it is called \textit{destructive}.
This is because such functions make direct modifications
to their argument's physical structure, and thus destroy
information about their original structure.
Traditionally, use of such destructive functions has been
considered somewhat dangerous, and thus \proglangname{Scheme} has adopted
the convention of suffixing the names of such functions
with an exclamation mark~(!). For example, there is
a function called \scmsym{append!} which is a destructive
version of the function \scmsym{append} described above.
However, it turns out that in our application the use
of strictly destructive implementations of Catalan automorphisms
(\textit{or functions of suspected of being isomorphic})
have certain merits, when they are subjected to mathematical
analysis. Namely, the bijectivity of such a function is much
easier to prove, if we know that it neither does "lose"
any existing cons cells, nor allocate any new ones
with constructive operations. More about this in the last
section of this paper.
For most of the automorphisms represented below we thus
give both constructive and destructive definition. We follow
the Scheme practice of suffixing the names of the latter ones
with~'!'.
For example, here is a destructive version of
\automorphism{A069770} whose constructive version
was defined above. The comments given in brackets
clarify the steps.
\begin{scmdefinefun5}
\multicolumn{2}{l}{\scmcode{(define}} & \multicolumn{2}{l}{\scmcode{(*A069770! s)}}\\
& \scmcode{(if} & \multicolumn{2}{l}{\scmcode{(null? s) s}}
& \scmexmcomment{If \scmsym{s} is \nilatom, then return
it back.}\\
& & \multicolumn{2}{l}{\scmcode{(let ((org-car (car s)))}}
& \scmexmcomment{Otherwise, store its car-side to \scmsym{org-car}}\\
& & & \scmcode{(set-car! s (cdr s))}
& \scmexmcomment{before it is ovewritten with cdr-side of \scmsym{s}.}\\
& & & \scmcode{(set-cdr! s org-car)}
& \scmexmcomment{Then ovewrite the cdr-side with the original
car-side of \scmsym{s},}\\
& & & \scmcode{s}
& \scmexmcomment{and return the modified \scmsym{s} as the value of
the whole function.}\\
& & \scmcode{)}\\
& \scmcode{)}\\
\scmcode{)}\\
\end{scmdefinefun5}
%%
%% (define (gma069770! s)
%% (if (null? s) ; Check whether s is an empty structure ()
%% s ; If so, then return () as the value of automorphism.
%% (let ((org-car (car s))) ; Otherwise, store the car-side to temporary variable org-car
%% (set-car! s (cdr s)) ; before it is overwritten with the cdr-side of s.
%% (set-cdr! s org-car) ; Now overwrite the cdr-side with the original car-side of s.
%% s ; and return the modified s as the value of whole function.
%% )
%% )
%% )
%%
%%
Now the destructive implementation of \automorphism{A057163} can be written
simply as:
\beql{gma057163firstdef}
\begin{scmdefinefun5}
\multicolumn{2}{l}{\scmcode{(define}} & \multicolumn{2}{l}{\scmcode{(*A057163! s)}}\\
& \scmcode{(cond} & \multicolumn{2}{l}{\scmcode{((pair? s)}}\\
& & & \scmcode{(*A069770! s)}\\
& & & \scmcode{(*A057163! (car s))}\\
& & & \scmcode{(*A057163! (cdr s))}\\
& & \scmcode{)}\\
& \scmcode{)}\\
& \scmcode{s}\\
\scmcode{)}\\
\end{scmdefinefun5}
\eeq
that is, we apply \automorphism{A069770} to every cons cell we encounter
(i.e. swap their sides), and recurse down to both car- and cdr-side of
each node, continuing down each branch as long as we encounter \nilatom.
%%
%% (define (*A057163! s)
%% (cond ((pair? s)
%% (*A069770! s)
%% (*A057163! (car s))
%% (*A057163! (cdr s))
%% )
%% )
%% s
%% )
%%
%*****************************************************
%
%
% Section 4
% On Integer-Sequences Associated with Automorphisms
%
%
%*****************************************************
\section{On Integer-Sequences Associated with Catalan Automorphisms}\label{Sec5}
We are interested about several sequences of integers that each
Catalan automorphism naturally produces. Some of these provide merely
fingerprint information about a particular automorphism, suitable for
recording into such online databases as Neil J.A. Sloane's
OEIS ({\em Online Encyclopedia of Integer Sequences}) [Sloane 1995--],
while others may have intrinsic interest of their own.
First we define a few auxiliary functions that turn out useful in
later definitions. As their names we use the A-numbers with which they
have been submitted to OEIS.
\begin{definition}[{A014137 and A014138}]
\normalfont
\EISseq{A014137} gives the partial sums of Catalan numbers (\EISseq{A000108}),
starting the summing from \EISseq{A000108(0)}, yielding
$$
1,2,4,9,23,65,197,626,2056,6918,23714,...
$$
while \EISseq{A014138} starts the summing from \EISseq{A000108(1)}, yielding
$$
1,3,8,22,64,196,625,2055,6917,23713,...
$$
\end{definition}
Note that if we organize all Catalan structures (of some
interpretation) in a sequence ordered by their size, so that we first
have a single empty structure of size 0 at index 0, followed by a
single structure of size 1 at index 1, followed by two structures of
size 2 at indices 2 and 3, followed by five structures of size~$n$=3, etc.
with each subsequence containing C(n) structures of size n, then
[\EISseq{A014137}(n-1)..\EISseq{A014138}(n-1)] gives the inclusive limits for the
structures of size n in such a sequence. (For the convenience we can
assume that \EISseq{A014137(-1)} = \EISseq{A014138(-1)} = 0.)
\begin{definition}[{A014486}]
\normalfont
This is a sequence which contains 0 at index 0 (corresponding to an
empty structure), and thereafter in each subrange
[\EISseq{A014137(n-1)}..\EISseq{A014138(n-1)}]
binary-coded representations of all \EISseq{A000108($n$)}
Dyck-paths/parenthesizations of size $n$ sorted into lexicographic
order. We get a binary-coded representation from a
Dyck-path/parenthesization by mapping each upward-slope/left
parenthesis to 1, and each downward-slope/right parenthesis to 0, and
then reading the resulting number as it were a binary number.
This is illustrated in the table~3.
\end{definition}
The sequence begins as
$$
0,2,10,12,42,44,50,52,56,170,172,178,180,184,202,204,210,212,216,226,228,232,240,...
$$
\begin{table}[htbp]
\setlength{\extrarowheight}{0.3in}
\begin{tabular}{c c c c c c c c c}
$n$ & \catint{i} & A063171($n$) & A014486($n$)\\
1. \vspace{0.1in} & \includegraphics{kuvat/i1.eps} & 10 in binary & 2 in decimal\\
2. \vspace{0.1in} & \includegraphics{kuvat/i2.eps} & 1010 in binary & 10 in decimal\\
3. \vspace{0.1in} & \includegraphics{kuvat/i3.eps} & 1100 in binary & 12 in decimal\\
4. \vspace{0.1in} & \includegraphics{kuvat/i4.eps} & 101010 in binary & 42 in decimal\\
5. \vspace{0.1in} & \includegraphics{kuvat/i5.eps} & 101100 in binary & 44 in decimal\\
\end{tabular}
\caption{Example showing how the first few terms of A014486 are formed.}
\end{table}
\begin{definition}[{A080300}]
\normalfont
This sequence is the inverse function of \EISseq{A014486}.
For those~$n$ which do not occur as values
of \EISseq{A014486} it gives zero, otherwise $n$'s~position
in \EISseq{A014486}.
That is, we have $n$~=~\EISseq{A080300}(\EISseq{A014486}($n$)) for all
$n$. %% \in \N.
The sequence begins as:
$$
0,0,1,0,0,0,0,0,0,0,2,0,3,0,0,0,0,...
$$
\end{definition}
\newcommand{\binexpSexp}{\bf{binexp\ensuremath{\rightarrow}Sexp}}
\newcommand{\Sexpbinexp}{\bf{Sexp\ensuremath{\rightarrow}binexp}}
\newcommand{\CatsetN} {\{\EISseq{A000108}($n$)~structures~of~size~$n$\}}
\newcommand{\CatsetM} {\{\EISseq{A000108}($m$)~structures~of~size~$m$\}}
\newcommand{\MathCatsetN} {\{\EISseq{A000108}(n)~structures~of~size~n\}}
\newcommand{\MathCatsetM} {\{\EISseq{A000108}(m)~structures~of~size~m\}}
\newcommand{\Subrange} {subrange~[\EISseq{A014137}($n$-1)..\EISseq{A014138}($n$-1)]}
\begin{definition}[{{\binexpSexp} and {\Sexpbinexp}}]
\normalfont
These functions convert between the terms of \EISseq{A014486}
(i.e. totally balanced binary sequences) and S-expressions.
They are each other's inverses, i.e.
we have $s$~=~{\binexpSexp}({\Sexpbinexp}($s$)) for all symbolless S-expressions
$s$. %% \in \N.
The \proglangname{Scheme}-code for their implementation is given in the Appendix~P.
\end{definition}
\begin{definition}[{Signature permutation}]
\normalfont
The Signature Permutation $sp_{g}(0),~sp_{g}(1),~sp_{g}(2),~sp_{g}(3),~...$
of \automorphismlet{g} is a sequence
$sp_{g}(n),~n=0..\infty$
where
$$
sp_g~=~\EISseq{A080300} \funapply {\Sexpbinexp} \funapply g \funapply
{\binexpSexp} \funapply \EISseq{A014486}
$$
%% that is
%% $$
%% sp_g(n)~=~\EISseq{A080300}({\Sexpbinexp}(g({\binexpSexp}(\EISseq{A014486}(n)))))
%% $$
\end{definition}
\paragraph{Remark.}
Here it is assumed that \automorphismlet{g} has been specified
as a
%% Scheme-function which acts on symbolless S-expressions,
function whose domain and range are S-expressions,
so we need the functions {\binexpSexp} and {\Sexpbinexp}
to do a round-trip from \EISseq{A014486}-codes and back.
\begin{definition}[{Set \SET{S} of signature permutations}]
\normalfont
In this paper the set of signature-permutations of all possible
Catalan automorphisms
is called the set~\SET{S}.
This set consists of all such permutations of natural numbers where no cycle
resides in more than one
subrange~[\EISseq{A014137($n$)}..\EISseq{A014138($n$)}].
\end{definition}
Clearly this set of permutations is closed with respect to composition
and taking inverses, the former operation corresponding
to the composition of two automorphisms and the latter
with finding the inverse of an automorphism.
Furthermore, the OEIS sequence \EISseq{A001477} (The nonnegative integers)
works as the identity element of this permutation group.
Thus everything regarding automorphisms could be in principle
expressed as group operations of this group~\SET{S}, which itself
is a subgroup of $S_\infty$.
\paragraph{Remark.}
The set~\SET{S} is not enumerable, which can be seen with the help
of standard diagonal argument.
%% for if it were, then
%% we could enumerate its permutations in some order, and with a standard
%% diagonal method find a permutation which would differ from all
%% the other permutations in the set, leading to a contradiction.
However, it turns out that there are important subgroups of
the set~\SET{S} that are enumerable.
\begin{definition}[{Cycle-Count Sequence}]
\normalfont
The Cycle-Count Sequence $cc_{g}(0),~cc_{g}(1),~cc_{g}(2),~cc_{g}(3),~...$
of \automorphismlet{g} is a sequence
$cc_{g}(n),~n=0..\infty$
where $cc_g(n)$ gives the number of orbits into which the set~{\CatsetN}
is partitioned under the action of~$g$.
\end{definition}
That is, $cc_{g}(n)$ is equal to number of cycles
in the {\Subrange}
of the signature permutation of~$g$.
Conceptually, Cycle-Count sequence gives the number of Catalan structures of size~$n$
"up to automorphism"~$g$.
\begin{definition}[{counts of fixed points sequence}]
\normalfont
The counts of fixed points sequence $fcs_{g}(0),~fcs_{g}(1),~fcs_{g}(2),~fcs_{g}(3),~...$
of \automorphismlet{g} is a sequence
$fcs_{g}(n),~n=0..\infty$
where
$$
fcs_{g}(n)~=~\#\{i \in [\EISseq{A014137}(n-1)..\EISseq{A014138}(n-1)]~|~sp_{g}(i)~=~i~\}
$$
\end{definition}
That is, $fcs_{g}(n)$
gives the number of structures in the set~{\CatsetN}
that are fixed (stay same) under the action of~$g$.
Conceptually, counts of fixed points sequence gives the number of Catalan structures of size~$n$
that are ``symmetric'' with respect to automorphism~$g$.
\begin{definition}[{Max-Cycle Sequence}]
\normalfont
The Max-Cycle Sequence $max_{g}(0),~max_{g}(1),~max_{g}(2),~max_{g}(3),~...$
of \automorphismlet{g} is a sequence
$max_{g}(n),~n=0..\infty$
where $max_g(n)$ gives the size of the a largest orbit into which the set
{\CatsetN}
is partitioned under the action of~$g$, that is, the size of a largest
cycle in the in the {\Subrange}
of the signature permutation of~$g$.
\end{definition}
\begin{definition}[{LCM Sequence}]
\normalfont
The LCM Sequence $lcm_{g}(0),~lcm_{g}(1),~lcm_{g}(2),~lcm_{g}(3),~...$
of \automorphismlet{g} is a sequence
$lcm_{g}(n),~n=0..\infty$
where $lcm_g(n)$ gives the {\em least common multiple} of all orbit sizes into which the set
{\CatsetN}
is partitioned under the action of~$g$, that is,
it is equal to the least common multiple of all cycle sizes
present in the {\Subrange}
of the signature permutation of~$g$.
\end{definition}
\paragraph{Remark.}
Of the above five sequence-types, only the signature-permutation
offers a unique fingerprint for each Catalan automorphism,
while the other four, although they might not distinguish
two automorphisms from each other, at least give some hints
about their possible relationships.
Especially with automorphisms that are {\em involutions}
(that is, self-inverse), the counts of fixed points sequence alone
specifies each (such automorphism) up to all of its conjugations.
%% although in some cases the conjugating isomorphism might not be very "natural".
Even if we have two distinct, non-involutive automorphisms, we should
have a strong suspicion that they are conjugates of each other
if their cycle-count, fix-point, max-cycle and lcm sequences
appear to match term by term.
%*****************************************************
%
%
% Subsection ?
% Using "Burnside's~Lemma" to compute Cycle-Count sequence.
%
%
%*****************************************************
\subsection{Using "Burnside's~Lemma" to compute Cycle-Count sequence.}\label{Burnside}
{\em Burnside's lemma}, sometimes also called Cauchy-Frobenius or just Orbit Counting lemma,
states that the number of orbits into which the set~\SET{X} is partitioned by group~\GROUP{G}
(whose members act on \SET{X}'s elements)
is equal to the average number of points fixed by the elements of~\GROUP{G}:
$$
{1\over |\GROUP{G}|} \sum_{g \in \GROUP{G}} \#\{x \in \SET{X}~|~g(x)~=~x\}
$$
In our case, the set~\SET{X} is
the set of~{\CatsetN}
and the group~\GROUP{G} is a cyclic group consisting of \automorphismlet{g}
and its successive powers $g^2$, $g^3$, $g^4$, $\hdots$
%% and the group~\GROUP{G} consists of \automorphismlet{g}
%% and its successive powers $g^2$, $g^3$, $g^4$, ...
%% which makes it a cyclic group.
When acting on any finite sized set~\SET{X},
the group is in practice finite, as there exists an integer $u$ such that
$g^{u}(x)~=~x$ for all $x$ in the set of~{\CatsetN}
thus $g^u$ is equal to an identity element of group~\GROUP{G},
and all higher powers of~\autletter{g} can be taken as modulo $u$.
The integer sequence~\EISseq{A078491}
is defined as the least common multiple of all natural numbers
from 1 to $n$th Catalan number. It grows with a formidable rate:
$$
1, 1, 2, 60, 360360, 219060189739591200,
1749342047920660916901891145781670987072592322134428432000,...
$$
Setting $u$~=~\EISseq{A078491}($n$)
we can be sure that $g^u$ is an identity element (neutral permutation) for
{\em any} \automorphismlet{g} acting on the set of size~$n$.
However, to use Burnside's lemma in practice, we need more down-to-earth
bounds for~$u$. Indeed, for each particular \automorphismlet{g},
it is just the sequence $lcm_{g}(n)$
which offers us the actual lower bound (???) of~$u$ when~$g$
acts on the set of size~$n$.
Applying Burnside's lemma, the Cycle-Count sequence of \automorphismlet{g} can be calculated
with the formula:
\beql{Eq1.1}
cc_{g}(n) = {1\over lcm_{g}(n)} \sum_{i=1}^{lcm_{g}(n)} fcs_{g^i}(n)
\eeq
%% TOISTOA: but to be useful in practice, we should of course
which requires that we also
know how to calculate $fcs_{g^i}(n)$,
i.e. the counts of fixed points sequence for each power $g^i$ of \automorphismlet{g}
up to $i~=~lcm_{g}(n)$,
and also have a method for calculating the lcm-sequence~$lcm_{g}(n)$,
or some sequence $b(n)$, for which it holds that
$$
\forall n, lcm_{g}(n) | b(n)
$$
(EDELLINEN KOHTA PAREMMIN!)
However, in many cases these sequences grow too fast that the
calculation with Burnside's lemma would be any faster
than the explicit counting of the orbits with a computer program,
unless the formula is amenable to further reduction.
%*****************************************************
%
%
% Section E
% Embeddability
%
%
%*****************************************************
\section{Embeddability}\label{Sec_Embeddability}
%% \paragraph{Definition.} We say that
%% $$
%% \automorphismlet{f} {\mathit embeds into} \automorphismlet{g} {\mathit in scale} n:m
%% $$
\begin{definition} %% [{Embeddability of automorphisms}]
\normalfont
We say that \automorphismlet{f} {\em embeds into} \automorphismlet{g} {\em in scale} $n:m$
if there is an injection:
$$
e: {\MathCatsetN} \ra {\MathCatsetM}
$$
so that for all elements $s$ of the domain set, it holds that
\beql{DefEmbeddability}
e(f(s)) = g(e(s)).
%% g(e(s)) = e(f(s)).
\eeq
\end{definition}
%%
\subsection{Examples of embeddability.}
\begin{definition} %% [{Lukasiewicz-word permuting automorphisms}]
\normalfont
We say that \automorphismlet{g} is {\em Lukasiewicz-word permuting},
if for all parenthesizations~$s$, the Lukasiewicz-word of~\autletter{g}($s$)
is always a permutation of the Lukasiewicz-word of $s$ itself.
More formally, \automorphismlet{g} is Lukasiewicz-word permuting
if its signature permutation satisfies
\beql{DefLwordPermuting}
A129593(sp_{g}(n)) = A129593(n)
\eeq
for all $n>=0$.
%% See also A129599.
\end{definition}
%% Consider the subset of those general trees which are isomorphic to
%% binary trees. Clearly these are precisely the trees whose
%% Lukasiewicz-words contain only digits '0' and '2' in some order.
Consider that subset of general trees whose
Lukasiewicz-words contain only digits '0' and '2' in some order.
These trees are isomorphic with binary trees,
and we call them {\em binaryform general trees} in this paper.
%% If a Lukasiewicz-word belongs into such set, then neither does any of its
%% permutations contain any other digits.
Thus, if~\autletter{g} is Lukasiewicz-word
permuting, then that subset is closed under the action of~\autletter{g}, and~\autletter{g}'s
restriction to that subset induces another \automorphismlet{f}. Rephrasing
this in above terms, we obtain:
%% we can say that for
\begin{lemma}~\label{lukaembed}
For any Lukasiewicz-word permuting \automorphismlet{g}
there is
%% an unique (unique, if produced in above fashion!)
an \automorphismlet{f} which {embeds into}
\automorphismlet{g} {in scale} $n:2n$.
\end{lemma}
\begin{definition} %% [{initial nil preserving automorphisms}]
\normalfont
We say that \automorphismlet{g} preserves the {\em initial nil}
if for all
%% parenthesizations~$s$
S-expressions~$s$ it holds that
\beql{EqInitialNils}
\begin{scmdefinefun}
\scmcode{(g (cons '( ) s)) = (cons '( ) (f s))}
\end{scmdefinefun}
\eeq
where the function~$f$ is either the same or different
automorphism than~$g$. In other words, such an automorphism
preserves the second to left~zero in the Lukasiewicz-word of
an S-expression, if present.
%% \automorphismlet{f}
\end{definition}
\begin{definition} %% [{automorphisms preserving planted trees as planted}]
\normalfont
We say that \automorphismlet{g} keeps {\em planted trees as planted}
if for all parenthesizations~$s$ it holds that
\beql{EqInitialOnes}
\begin{scmdefinefun}
\scmcode{(g (cons s '( ))) = (cons (f s) '( ))}
\end{scmdefinefun}
\eeq
where the function~$f$ is either the same or different
automorphism than~$g$. In other words, such an automorphism
preserves the initial~1 in the Lukasiewicz-word of
an S-expression, if present.
%% \automorphismlet{f}
\end{definition}
\begin{definition} %% [{horizontally telescoping automorphisms}]
\normalfont
We say that \automorphismlet{g} is {\em horizontally telescoping}
if for all parenthesizations~$s$ it holds that
\beql{EqHorizontallyTelescoping}
\begin{scmdefinefun}
\scmcode{(g (cons '( ) s)) = (cons '( ) (g s))}
\end{scmdefinefun}
\eeq
that is, the injection $e$ required by the general definition of
embeddability defined in \eqn{DefEmbeddability}
%% given above
is now defined as:
\beql{ConsNil2Front}
\begin{scmdefinefun}
\scmcode{(define (e s) (cons '( ) s))}
\end{scmdefinefun}
\eeq
\end{definition}
We note that this is a special case of a weaker condition
given in \eqn{EqInitialNils}, realized when $f~=~g$,
In this case the injection~$e$ maps the parenthesizations of size~$n$
to the parenthesizations of size~$n+1$ by simply concatenating empty
parentheses {\em to the front}
of the corresponding parenthesization.
This is equivalent to saying that each sub-permutation of the length
\EISseq{A000108}($n$)
induced by \automorphismlet{g}'s action on
the standard sequence of lexicographically ordered parenthesizations
(\EISseq{A014486})
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.
\begin{definition} %% [{vertically telescoping automorphisms}]
\normalfont
We say that \automorphismlet{g} is {\em vertically telescoping}
if for all parenthesizations~$s$ it holds that
\beql{EqVerticallyTelescoping}
\begin{scmdefinefun}
\scmcode{(g (cons s '( ))) = (cons (g s) '( ))}
\end{scmdefinefun}
\eeq
where the injection $e$ required by the general definition of
embeddability %% given above
is now defined as:
\beql{ConsNil2Right}
\begin{scmdefinefun}
\scmcode{(define (e s) (cons s '( )))}
\end{scmdefinefun}
\eeq
\end{definition}
That is, the injection~$e$ is equal to the unary variant of \proglangname{Scheme}-function \scmsym{list},
which maps the parenthesizations of size~$n$
to the parenthesizations of size~$n+1$ by surrounding
them with one extra pair of parentheses.
We note that this is a special case of a weaker condition
given in \eqn{EqInitialOnes}, realized when $f~=~g$,
\begin{definition} %% [{Self-embeddable automorphisms}]
\normalfont
The above two definitions are examples of {\em self-embeddable} automorphisms.
We say that \automorphismlet{g} is {\em self-embeddable}
if~\autletter{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$.
\end{definition}
\paragraph{Notes.}
The allusions {\em "horizontal"} and {\em "vertical"} should
make sense when one thinks in the terms of Dyck paths (Catalan
Mountain Ranges), and also the plane general trees in the latter case.
If a horizontally telescoping automorphism is conjugated with
\automorphism{A057163} we obtain a vertically telescoping
automorphism, and {\em vice versa}.
A Lukasiewicz-word permuting automorphism can also be
a vertically telescoping automorphism, which implies
that it must preserve the initial~1 of the Lukasiewicz-word when present.
(In other words, keeps planted trees as planted.)
%% The Lukasiewicz-word permuting automorphism cannot be
%% a vertically telescoping automorphism, unless it preserves
%% the initial~1 of the Lukasiewicz-word when present.
%% (In other words, keeps planted trees as planted.)
%% BULLSHIT:
%% The intersection of the set of Lukasiewicz-word permuting
%% automorphisms and the set of vertically telescoping automorphisms
%% consists precisely of those automorphisms that preserve
%% the initial~1 of the Lukasiewicz-word if present.
%% (In other words, keep planted trees as planted.)
It should be obvious that all self-embeddable automorphisms of the
scale $n:n+1$ have genuinely monotone (growing) cycle count sequences
and monotone (but not necessarily genuinely) fix point sequences from $n~\ge~1$ onward.
%% \emph{(Lots of text to be transferred from HTML-documents to
%% here... Lots of thinking yet to be done!)}
%*****************************************************
%
%
% Section R - Recursion Schemes
%
%
%*****************************************************
\section{Recursion Schemes}\label{Sec_recschemes}
%% Not in THIS style:
%% If we have just a few automorphisms at hand, how to
%% construct more of them? Clearly a composition of any
%% two automorphisms is itself an automorphism.
%% However, there is another technique, where
%% one can produce a new \automorphism{foo} from
%% an existing \automorphism{bar}, by invoking
%% it recursively ... %% at various points of
We list several recursion schemes by which to construct
new automorphisms from old ones.
%% recursion\_scheme0 = FORK recursion\_scheme1 = KROF
%% recursion\_scheme2 = SPINE recursion\_scheme3 = ENIPS
%% recursion\_schemeM = RIBS
%% recursion\_schemeSD0 = SYVYYS recursion\_schemeSD1 = SYYVYS
%% recursion\_schemeSD0 = DEEP recursion\_schemeSD1 = PEED (c.f. visual symmetry deep / peed)
%% recursion\_schemeSD0 = DEEPER recursion\_schemeSD1 = REPEED
%% recursion\_schemeSD0 = DIVE recursion\_schemeSD1 = EVID
\begin{definition}[{FORK: Apply at root, recurse into both branches.}]
\normalfont
In this recursion scheme, the given automorphism %% \automorphismlet{g}
is applied at the root node, and then the same process
is repeated recursively for both car- and cdr-branch
of the S-expression.
\end{definition}
%% (define (recursion_scheme0 foo!)
%% (letrec ((recurse (lambda (s)
%% (cond ((null? s) s)
%% (else (foo! s)
%% (recurse (car s))
%% (recurse (cdr s)))
%% )
%% s
%% )
%% ))
%% recurse
%% )
%% )
%%
In \proglangname{Scheme} we can define the following {\em higher order function}
that takes as it argument a destructively defined
function~\scmsym{foo!} %% \automorphism{foo!}
and returns back a new function~\scmsym{bar!}, that also acts
on S-expressions:\footnote{In this paper the names of all higher
order functions expecting a destructively implemented automorphism
as their function argument are {\em prefixed} with an exclamation mark~(!).}
%% a new \automorphism{bar!}, which is also destructive:
\beql{definerecscheme0}
\begin{scmdefinefun7}
\multicolumn{7}{l}{\scmcode{(define (!FORK foo!)}}\\
& \scmcode{(letrec} & \scmcode{((bar!} & \multicolumn{4}{l}{\scmcode{(lambda (s)}}\\
& & & & \scmcode{(cond} & \multicolumn{2}{l}{\scmcode{((pair? s)}}\\
& & & & & & \scmcode{(foo! s)}\\
& & & & & & \scmcode{(bar! (car s))}\\
& & & & & & \scmcode{(bar! (cdr s))}\\
& & & & & \scmcode{)}\\ %% pair?
& & & & \scmcode{)}\\ %% cond
& & & & \scmcode{s}\\
& & & \scmcode{)}\\ %% lambda
& & \scmcode{))}\\ %% bar!
& & \scmcode{bar!}\\
& \scmcode{)}\\ %% letrec
\scmcode{)}\\ %% define
\end{scmdefinefun7}
\eeq
Note that this function uses the variant \scmsym{letrec} of
\scmsym{let}, which allows the definition of recursive
lambda-forms ({\em anonymous functions}).
Calling this functional as \scmcode{(!FORK }\autname{A069770!}\scmcode{)}
produces the same destructive definition of \automorphism{A057163!}
that was given at the end of section~4.
\begin{definition}[{KROF: Recurse into both branches, then apply at root.}]
\normalfont
In this recursion scheme, the given automorphism %% \automorphismlet{g}
is applied at the root node, but only {\em after} the same process
has first been repeated recursively for both car- and cdr-branch
of the S-expression.
\end{definition}
This is defined in \proglangname{Scheme} as:
\beql{definerecscheme1}
\begin{scmdefinefun7}
\multicolumn{7}{l}{\scmcode{(define (!KROF foo!)}}\\
& \scmcode{(letrec} & \scmcode{((bar!} & \multicolumn{4}{l}{\scmcode{(lambda (s)}}\\
& & & & \scmcode{(cond} & \multicolumn{2}{l}{\scmcode{((pair? s)}}\\
& & & & & & \scmcode{(bar! (car s))}\\
& & & & & & \scmcode{(bar! (cdr s))}\\
& & & & & & \scmcode{(foo! s)}\\
& & & & & \scmcode{)}\\ %% pair?
& & & & \scmcode{)}\\ %% cond
& & & & \scmcode{s}\\
& & & \scmcode{)}\\ %% lambda
& & \scmcode{))}\\ %% bar!
& & \scmcode{bar!}\\
& \scmcode{)}\\ %% letrec
\scmcode{)}\\ %% define
\end{scmdefinefun7}
\eeq
\begin{definition}[{SPINE: Apply at root, then recurse into cdr branch.}]
\normalfont
In this recursion scheme, the given automorphism %% \automorphismlet{g}
is applied at the root node, and then the same process
is repeated recursively for the cdr-branch of the S-expression.
\end{definition}
This is defined in \proglangname{Scheme} as:
\beql{definerecscheme2}
\begin{scmdefinefun7}
\multicolumn{7}{l}{\scmcode{(define (!SPINE foo!)}}\\
& \scmcode{(letrec} & \scmcode{((bar!} & \multicolumn{4}{l}{\scmcode{(lambda (s)}}\\
& & & & \scmcode{(cond} & \multicolumn{2}{l}{\scmcode{((pair? s)}}\\
& & & & & & \scmcode{(foo! s)}\\
& & & & & & \scmcode{(bar! (cdr s))}\\
& & & & & \scmcode{)}\\ %% pair?
& & & & \scmcode{)}\\ %% cond
& & & & \scmcode{s}\\
& & & \scmcode{)}\\ %% lambda
& & \scmcode{))}\\ %% bar!
& & \scmcode{bar!}\\
& \scmcode{)}\\ %% letrec
\scmcode{)}\\ %% define
\end{scmdefinefun7}
\eeq
\begin{definition}[{ENIPS: Recurse into cdr branch, then apply at root.}]
\normalfont
In this recursion scheme, the given automorphism %% \automorphismlet{g}
is applied at the root node, but only {\em after} the same process
has first been repeated recursively for the cdr-branch
of the S-expression.
\end{definition}
This is defined in \proglangname{Scheme} as:
\beql{definerecscheme3}
\begin{scmdefinefun7}
\multicolumn{7}{l}{\scmcode{(define (!ENIPS foo!)}}\\
& \scmcode{(letrec} & \scmcode{((bar!} & \multicolumn{4}{l}{\scmcode{(lambda (s)}}\\
& & & & \scmcode{(cond} & \multicolumn{2}{l}{\scmcode{((pair? s)}}\\
& & & & & & \scmcode{(bar! (cdr s))}\\
& & & & & & \scmcode{(foo! s)}\\
& & & & & \scmcode{)}\\ %% pair?
& & & & \scmcode{)}\\ %% cond
& & & & \scmcode{s}\\
& & & \scmcode{)}\\ %% lambda
& & \scmcode{))}\\ %% bar!
& & \scmcode{bar!}\\
& \scmcode{)}\\ %% letrec
\scmcode{)}\\ %% define
\end{scmdefinefun7}
\eeq
\begin{definition}[{RIBS: Apply at car branch, then recurse into cdr branch.}]
\normalfont
In this recursion scheme, the given automorphism %% \automorphismlet{g}
is applied at the car branch, and then the same process
is repeated recursively for the cdr-branch of the S-expression.
\end{definition}
This is defined in \proglangname{Scheme} as:
\beql{definerecschemeM}
\begin{scmdefinefun7}
\multicolumn{7}{l}{\scmcode{(define (!RIBS foo!)}}\\
& \scmcode{(letrec} & \scmcode{((bar!} & \multicolumn{4}{l}{\scmcode{(lambda (s)}}\\
& & & & \scmcode{(cond} & \multicolumn{2}{l}{\scmcode{((pair? s)}}\\
& & & & & & \scmcode{(foo! (car s))}\\
& & & & & & \scmcode{(bar! (cdr s))}\\
& & & & & \scmcode{)}\\ %% pair?
& & & & \scmcode{)}\\ %% cond
& & & & \scmcode{s}\\
& & & \scmcode{)}\\ %% lambda
& & \scmcode{))}\\ %% bar!
& & \scmcode{bar!}\\
& \scmcode{)}\\ %% letrec
\scmcode{)}\\ %% define
\end{scmdefinefun7}
\eeq
Alternatively, \scmsym{RIBS} could defined using
the built-in \proglangname{Scheme} primitive \scmsym{(for-each~$f!$~$l$)},
which applies a destructive function~$f!$ to each top-level element
of the list~$l$.
\beql{definerecschemeMalt}
\begin{scmdefinefun5}
\multicolumn{5}{l}{\scmcode{(define} \scmcode{(!RIBS foo!)}}\\
& \scmcode{(letrec} & \scmcode{((bar!} & \multicolumn{2}{l}{\scmcode{(lambda (s)}}\\
& & & & \scmcode{(for-each foo! s)}\\
& & & \scmcode{)}\\ %% lambda
& & \scmcode{))}\\ %% bar!
& & \scmcode{bar!}\\
& \scmcode{)}\\ %% letrec
\scmcode{)}\\ %% define
\end{scmdefinefun5}
\eeq
\begin{definition}[{DEEPEN: Apply at root, then recurse into each car branch.}]
\normalfont
In this recursion scheme, the given automorphism %% \automorphismlet{g}
is applied at the root node, and then the same process
is repeated recursively for each car-branch of the S-expression.
\end{definition}
This is defined in \proglangname{Scheme} as:
\beql{definerecschemeSD0}
\begin{scmdefinefun7}
\multicolumn{7}{l}{\scmcode{(define (!DEEPEN foo!)}}\\
& \scmcode{(letrec} & \scmcode{((bar!} & \multicolumn{4}{l}{\scmcode{(lambda (s)}}\\
& & & & \scmcode{(cond} & \multicolumn{2}{l}{\scmcode{((pair? s)}}\\
& & & & & & \scmcode{(foo! s)}\\
& & & & & & \scmcode{(for-each bar! s)}\\
& & & & & \scmcode{)}\\ %% pair?
& & & & \scmcode{)}\\ %% cond
& & & & \scmcode{s}\\
& & & \scmcode{)}\\ %% lambda
& & \scmcode{))}\\ %% bar!
& & \scmcode{bar!}\\
& \scmcode{)}\\ %% letrec
\scmcode{)}\\ %% define
\end{scmdefinefun7}
\eeq
\begin{definition}[{NEPEED: Recurse into each car branch, then apply at root.}]
\normalfont
In this recursion scheme, the given automorphism %% \automorphismlet{g}
is applied at the root node, but only {\em after} the same process
has first been repeated recursively for each car-branch of the S-expression.
\end{definition}
This is defined in \proglangname{Scheme} as:
\beql{definerecschemeSD1}
\begin{scmdefinefun7}
\multicolumn{7}{l}{\scmcode{(define (!NEPEED foo!)}}\\
& \scmcode{(letrec} & \scmcode{((bar!} & \multicolumn{4}{l}{\scmcode{(lambda (s)}}\\
& & & & \scmcode{(cond} & \multicolumn{2}{l}{\scmcode{((pair? s)}}\\
& & & & & & \scmcode{(for-each bar! s)}\\
& & & & & & \scmcode{(foo! s)}\\
& & & & & \scmcode{)}\\ %% pair?
& & & & \scmcode{)}\\ %% cond
& & & & \scmcode{s}\\
& & & \scmcode{)}\\ %% lambda
& & \scmcode{))}\\ %% bar!
& & \scmcode{bar!}\\
& \scmcode{)}\\ %% letrec
\scmcode{)}\\ %% define
\end{scmdefinefun7}
\eeq
Note that \scmsym{DEEPEN} and \scmsym{NEPEED}
convert certain \textit{shallow} automorphisms to the
corresponding \textit{deep} variants.
%% Explained somewhat later:
%% If a Lukasiewicz-word permuting \automorphismlet{f} preserves the initial~1 of the Lukasiewicz-word when present
%% (in other words, keeps planted trees as planted), then
%% \scmsym{DEEPEN($f$)}
%% produces a vertically telescoping automorphism,
%% which itself belongs to such a subset
%% of Lukasiewicz-word permuting automorphisms.
\begin{propo}~\label{recschemepropo1}
Whenever any of the above recursion schemes is applied to a destructively
defined automorphism, the resulting function is also a destructively
defined automorphism.
\end{propo}
\textit{Proof}. Because no constructive functions are involved, we can be
sure that the resulting function does not map any S-expression
to a larger structure. Thus, to show the bijectivity we just
need to demonstrate that any derivative function defined with
these recursion schemas has an inverse.
Indeed,
\begin{tabular}{l l l l}
\scmcodeintext{(!FORK $g$)} & and & \scmcodeintext{(!KROF $g^{-1}$)}, \\
\scmcodeintext{(!SPINE $g$)} & and & \scmcodeintext{(!ENIPS $g^{-1}$)}, \\
\scmcodeintext{(!RIBS $g$)} & and & \scmcodeintext{(!RIBS $g^{-1}$)} as well as \\
\scmcodeintext{(!DEEPEN $g$)} & and & \scmcodeintext{(!NEPEED $g^{-1}$)} \\
\end{tabular}
are inverses of each other, for all automorphisms~$g$.
We prove only the first case, i.e. that
$bar~\equiv$~\scmcodeintext{(!FORK~$g$)} and
$rab~\equiv$~\scmcodeintext{(!KROF~$g^{-1}$)}
are inverses of each other.
%% This is easily seen to be for the base cases,
%% for the S-expressions \nilatom and (\nilatom~.~\nilatom).
Obviosly this is true when we limit our attention to the set consisting
only of the empty list \nilatom, which provides a base case
for the inductive proof.
For larger S-expressions $bar$~\funapply~$rab$ is equivalent to
\beql{Eq1.1}
(bar(car~side)~.~bar(cdr~side))~\funapply~g~\funapply~g^{-1}~\funapply~(rab(car~side)~.~rab(cdr~side))
%% \begin{array}{l}
%% (bar(car~side~after~g's~action)~.~bar(cdr~side~after~g's~action))~\funapply~g~\funapply~g^{-1} \\
%% ~\funapply~(rab(car~side~before~any~action)~.~rab(cdr~side~before~any~action)) \\
%% \end{array}
\eeq
In the middle $g~\funapply~g^{-1}$ cancels out, and assuming the
induction hypothesis is true, i.e. that $bar(rab(s))~=~s$ for all
smaller S-expressions~$s$,
it can be seen that the above produces an identity function for
all larger S-expressions as well.
The cases involving other recursion schemes are proved similarly.
%% \begin{propo}~\label{lukapreservedness}
%% All recursion schemes mentioned above preserve
%% the Lukasiewicz-word permuting property, that is,
%% if the \automorphismlet{g} is Lukasiewicz-word permuting,
%% then also \scmcodeintext{(FORK~$g$)},
%% \scmcodeintext{(KROF~$g$)},
%% \scmcodeintext{(SPINE~$g$)},
%% \scmcodeintext{(ENIPS~$g$)},
%% \scmcodeintext{(RIBS~$g$)},
%% \scmcodeintext{(DEEPEN~$g$)} and
%% \scmcodeintext{(NEPEED~$g$)}
%% are Lukasiewicz-word permuting automorphisms.
%% \end{propo}
%% \textit{Proof}. This hinges on two facts:
%% \begin{enumerate}
%% \item Also in cases where a Lukasiewicz-word permuting automorphism is applied
%% only to a part of an S-expression,
%% the resulting Lukasiewicz-word of the whole S-expression
%% is a permutation of the original one.
%% \item Composition of two Lukasiewicz-word permuting automorphisms
%% is a Lukasiewicz-word permuting automorphism.
%% \end{enumerate}
%% \begin{enumerate}
%% \item Also in cases where a Lukasiewicz-word permuting automorphism is applied
%% only to a part of an S-expression,
%% the resulting Lukasiewicz-word of the whole S-expression
%% is a permutation of the original one.
%% \item Composition of two Lukasiewicz-word permuting automorphisms
%% is a Lukasiewicz-word permuting automorphism.
%% \end{enumerate}
\subsection{Recursion schemes as folds.}
Of the recursion schemes listed above,
%% \scmsym{KROF}, \scmsym{ENIPS}, \scmsym{RIBS}, \scmsym{DEEPEN} and \scmsym{NEPEED} can all
most of can
be implemented as {\em folds},
%% These are all based on the concept of {\em fold}, described for
%% example in
the concept described for example in
[Hutton 1999] or [Gibbons 2005]:
\begin{definition} %% [{foldr: Right fold for finite lists.}]
\normalfont
Function $fold : \FoldFunSET \times \FoldRangeSET \times \SexprSET \rightarrow \FoldRangeSET$
for $lists$ is defined as
\beql{DefFoldforLists}
fold(m,c,s) = \left\{ \begin{array}{p{5cm}p{7cm}}
$c$ & \textrm{if $s = \nilatom$} \\
$m(x,fold(m,c,y))$ & \textrm{if $s = cons(x,y)$}\\
%% if $s$ is of the form cons($x$,$y$)}\\
\end{array} \right.
\eeq
%% (foldr f c '()) := c
%% (foldr f c (a : x)) := (f a (foldr f c x))
where $c \in \FoldRangeSET$,
%% $\FoldRangeSET$ is the range set
%% the set $\FoldFunSET$ denotes the set of functions~$m : \FoldRangeSET \times \SexprSET \rightarrow \FoldRangeSET$,
the set $\FoldFunSET$ denotes the set of functions
$$
m : \SexprSET \times \FoldRangeSET \rightarrow \FoldRangeSET,
$$
$\SexprSET$ is the set of {\sexpr}'s and $\FoldRangeSET$ is the range
set for both $m$ and $fold$ built upon it.
Similarly, function $foldubt : \FoldFunSET \times \FoldRangeSET \times \SexprSET \rightarrow \FoldRangeSET$
for {\em unlabeled binary trees} is defined as
\beql{DefFoldforBinaryTrees}
foldubt(m,c,s) = \left\{ \begin{array}{p{7cm}p{7cm}}
$c$ & \textrm{if $s~=~$}\includegraphics{kuvat/cd0.eps} \\
%% \textrm{if $s = \nilatom$} \\
$m(foldubt(m,c,a),foldubt(m,c,b))$ & \textrm{if $s~=~$}\includegraphics[scale=0.5]{kuvat/d1ab.eps} \\
%% \includegraphics{kuvat/cd1.eps} \\ %% The bin tree marked with x and y branches.
%% \textrm{if $s = cons(x,y)$}\\
%% if $s$ is of the form cons($x$,$y$)}\\
\end{array} \right.
\eeq
%% However, in the context of this paper, where both {\em lists} and
%% {\em unlabeled binary trees} have been realized in the form of %% / implemented
%% {\nsexpr}'s,
\paragraph{Remark.}
In the context of this paper, where {\em unlabeled binary trees}
are implemented in the form of %% / implemented
{\nsexpr}'s,
and where we restrict our attention to such {\em lists}
which can be also realized as {\nsexpr}'s,
$foldubt$ can always be implemented in terms of $fold$, provided
its argument function $f$ can recursively refer to the function
being defined with $fold$.
We give three important properties of folds.
\begin{lemma}~\label{When_is_a_function_a_fold}
When is a function a fold?
\normalfont
[Gibbons, Hutton and Altenkirch 2001]
If function~$F$ satisfies the implication
\beql{DefHomomorphicFforLists}
F(s) = F(t) \Rightarrow F(cons(a, s)) = F(cons(a, t))
\eeq
then function $F$ can be implemented as {\em fold} for {\em lists}.
If function~$F$ satisfies the implication
\beql{DefHomomorphicFforBinaryTrees}
F(a) = F(b) \wedge F(s) = F(t) \Rightarrow F(cons(a, s)) = F(cons(b, t))
\eeq
then function $F$ can be implemented as {\em foldubt} for {\em unlabeled binary trees}.
\end{lemma}
\paragraph{Remark.}
It should be noted that
any function satisfying
condition~\eqn{DefHomomorphicFforBinaryTrees} satisfies also condition~\eqn{DefHomomorphicFforLists}.
%% the latter condition implies the former one.
%% condition~\eqn{DefHomomorphicFforBinaryTrees} implies condition~\eqn{DefHomomorphicFforLists}.
%% \paragraph{Corollary.} All Catalan automorphisms can be realized as folds.
\begin{lemma}~\label{Universal_Property}
Universal Property.
\normalfont
([Bird 1989], [Meertens 1983] or [Hutton 1999]).
For any such function implementable as {\em fold} or {\em foldubt}
there is a unique solution for function~$m$ in~\eqn{DefFoldforLists}
and in~\eqn{DefFoldforBinaryTrees} and the associated constant~$c$. [XXX -- CHECK!]
\end{lemma}
\begin{lemma}~\label{Fusion_Property}
Fusion Property.
\normalfont
([Bird 1989], [Meertens 1983], [Malcolm 1990], [Hutton 1999]).
This can be stated as an implication
\beql{DefFusionPropertyFold}
h(w(x,y)) = m(x,h(y)) \Rightarrow h \funapply fold(w,c,s) = fold(m,h(c),s)
\eeq
giving the condition which an arbitrary function~$h$ and functions~$m$ and~$w$
must satisfy that the composition of~$h$ and $fold(w,c,s)$
could be implemented as a fold of function~$m$.
\end{lemma}
%% where $v \in \FoldRangeSET$,
%% %% $\FoldRangeSET$ is the range set
%% %% the set $\FoldFunSET$ denotes the set of functions~$f : \FoldRangeSET \times \SexprSET \rightarrow \FoldRangeSET$,
%% the set $\FoldFunSET$ denotes the set of functions
%% $$
%% f : \SexprSET \times \FoldRangeSET \rightarrow \FoldRangeSET,
%% $$
%% $\SexprSET$ is the set of {\sexpr}'s and $\FoldRangeSET$ is the range
%% set for both $f$ and $fold$ built upon it.
\end{definition}
%% \paragraph{Remark.}
In Scheme, $fold(m,c,s)$ is implemented with the function
\scmcode{(fold-right~}{\em m~c~s}\scmcode{)}.
The higher order functions implementing the recursion
schemes \scmsym{KROF}, \scmsym{ENIPS}, \scmsym{RIBS}, \scmsym{DEEPEN} and \scmsym{NEPEED}
for {\em constructively implemented} automorphisms
are implemented in the following way as folds in Scheme:
\beql{KROF_as_fold_right}
\begin{tabular}{l l}
\multicolumn{2}{l}{\scmcode{(define (KROF }{\em g}\scmcode{)}} \\
& \scmcode{(letrec ((}{\em h}\scmcode{ (lambda (s) (fold-right (lambda (x y) (}{\em g}\scmcode{ (cons (}{\em h}\scmcode{ x) y))) '() s)))) }{\em h}\scmcode{))}
\end{tabular}
\eeq
\beql{ENIPS_as_fold_right}
\begin{tabular}{l}
\scmcode{(define (ENIPS }{\em g}\scmcode{) (lambda (s) (fold-right (lambda (x y) (}{\em g}\scmcode{ (cons x y))) '() s)))}
\end{tabular}
\eeq
\beql{RIBS_as_fold_right}
%% \begin{tabular}{l l}
%% \multicolumn{2}{l}{\scmcode{(define (RIBS }{\em g}\scmcode{)}} \\
%% & \scmcode{(lambda (s) (fold-right (lambda (x r) (cons (}{\em g}\scmcode{ x) r)) '() s)))}
\begin{tabular}{l}
\scmcode{(define (RIBS }{\em g}\scmcode{) (lambda (s) (fold-right (lambda (x y) (cons (}{\em g}\scmcode{ x) y)) '() s)))}
\end{tabular}
\eeq
%o A122283 (Scheme:) (define (DEEPEN foo) (letrec ((bar (lambda (s) (map bar (foo s))))) bar))
\beql{DEEPEN_as_fold_right}
\begin{tabular}{l l}
\multicolumn{2}{l}{\scmcode{(define (DEEPEN }{\em g}\scmcode{)}} \\
& \scmcode{(letrec ((}{\em h}\scmcode{ (lambda (s) (fold-right (lambda (x y) (cons (}{\em h}\scmcode{ x) y)) '() (}{\em g}\scmcode{ s))))) }{\em h}\scmcode{))}
\end{tabular}
\eeq
\beql{NEPEED_as_fold_right}
\begin{tabular}{l l}
\multicolumn{2}{l}{\scmcode{(define (NEPEED }{\em g}\scmcode{)}} \\
& \scmcode{(letrec ((}{\em h}\scmcode{ (lambda (s) (}{\em g}\scmcode{ (fold-right (lambda (x y) (cons (}{\em h}\scmcode{ x) y)) '() s))))) }{\em h}\scmcode{))}
\end{tabular}
\eeq
%% \subsection{Invariancy in Catalan automorphisms.}
\subsection{Implications of properties of fold}
\begin{lemma}~\label{AllCatalanAutomorphisms_are_catamorphisms}
\normalfont
All Catalan automorphisms can be realized as folds, i.e. are {\em catamorphisms}.
\textit{Proof}. Follows from the injectivity %% bijectivity
of automorphisms and from %% the
lemma~\ref{When_is_a_function_a_fold}.
\end{lemma}
\begin{lemma}~\label{AboveRecursionSchemes_have_inverses}
\normalfont
Except for \scmcodeintext{RIBS}, all the above mentioned recursion schemes
have well-defined inverse operations.
\textit{Proof}. The inverse operations for each of
\scmcodeintext{(ENIPS~$f$)},
\scmcodeintext{(SPINE~$f$)},
\scmcodeintext{(KROF~$f$)},
\scmcodeintext{(FORK~$f$)},
\scmcodeintext{(NEPEED~$f$)} and
\scmcodeintext{(DEEPEN~$f$)}
can be realized as:
(here $f_{car}$ and $f_{cdr}$ are shorthands for functions \\
\scmcodeintext{(lambda~(s)~(cons~($f$~(car~s))~(cdr~s)))}
and
\scmcodeintext{(lambda~(s)~(cons~(car~s)~($f$~(cdr~s))))}
respectively).
\beql{ENIPSINV}
(ENIPS^{-1}~f) = f \funapply f^{-1}_{cdr}
\eeq
\beql{SPINEINV}
(SPINE^{-1}~f) = f^{-1}_{cdr} \funapply f
\eeq
\beql{KROFINV}
(KROF^{-1}~f) = f \funapply f^{-1}_{car} \funapply f^{-1}_{cdr}
\eeq
\beql{FORKINV}
(FORK^{-1}~f) = f^{-1}_{car} \funapply f^{-1}_{cdr} \funapply f
\eeq
\beql{NEPEEDINV}
(NEPEED^{-1}~f) = f \funapply RIBS(f^{-1})
\eeq
\beql{DEEPENINV}
(DEEPEN^{-1}~f) = RIBS(f^{-1}) \funapply f
\eeq
It is easily seen and proven by induction that by applying
the corresponding recursion scheme to these forms
recovers the original \automorphismlet{f}. %% back.
Lemma~\ref{Universal_Property} quarantees
that these are indeed unique solutions.
\paragraph{Remark.}
The six recursion schemes $SPINE$, $ENIPS$, $FORK$, $KROF$, $DEEPEN$ and $NEPEED$
are thus bijective operations on the set of all Catalan automorphisms.
However, in general they do not satisfy the group homomorphism condition, except
in some special cases.
\end{lemma}
\begin{lemma}~\label{lemma_RIBS_as_SPINE_or_ENIPS}
\normalfont
Using the notation introduced above, we can define $RIBS$ in terms of $SPINE$ or $ENIPS$:
\beql{RIBS_as_SPINE_or_ENIPS}
(RIBS~f) = (SPINE~f_{car}) = (ENIPS~f_{car})
%% \begin{array}{l l}
%% (RIBS~f) & = (SPINE~f_{car}) \\
%% & = (ENIPS~f_{car}) \\
%% \end{array}
\eeq
\end{lemma}
\begin{lemma}~\label{lemma_KROF_as_NEPEED_and_ENIPS}
\normalfont
$KROF$ is a composition of $NEPEED$ and $ENIPS$:
\beql{KROF_as_NEPEED_and_ENIPS}
(KROF~f) = (NEPEED~(ENIPS~f))
\eeq
\textit{Proof}.
This is easiest to prove formally by considering the inverses
of these operations. We have:
\beql{KROFINV_as_ENIPSINV_and_NEPEEDINV}
\begin{array}{l l}
(ENIPS^{-1}~(NEPEED^{-1}~f)) & = (ENIPS^{-1}~(f \funapply RIBS(f^{-1}))) \\
& = f \funapply RIBS(f^{-1}) \funapply (f \funapply RIBS(f^{-1}))^{-1}_{cdr} \\
& = f \funapply RIBS(f^{-1}) \funapply {RIBS(f)}_{cdr} \funapply f^{-1}_{cdr} \\
& = f \funapply f^{-1}_{car} \funapply f^{-1}_{cdr} \\
& = (KROF^{-1}~f) \\
\end{array}
\eeq
\end{lemma}
\begin{lemma}~\label{lemma_FORK_as_DEEPEN_and_SPINE}
\normalfont
$FORK$ is a composition of $DEEPEN$ and $SPINE$:
\beql{FORK_as_DEEPEN_and_SPINE}
(FORK~f) = (DEEPEN~(SPINE~f))
\eeq
\textit{Proof}.
The proof is similar to the one given for lemma~\ref{lemma_KROF_as_NEPEED_and_ENIPS}. %% above.
\end{lemma}
\begin{lemma}~\label{lemma_composing_f_and_ENIPS_g}
\normalfont
If we take an %% arbitrary
\automorphismlet{f}
and ENIPS -transform of another %% arbitrary
\automorphismlet{g},
and consider their composition as an ENIPS -transform of
some \automorphismlet{h}:
\beql{composing_f_and_ENIPS_g}
f \funapply (ENIPS~g) = (ENIPS~h)
\eeq
then
\beql{implication_of_composing_f_and_ENIPS_g}
h = f \funapply g \funapply f^{-1}_{cdr}
\eeq
\paragraph{\textit{Proof.}}
This can be also proved by considering the inverses.
We have:
\beql{proof_of_composing_f_and_ENIPS_g}
\begin{array}{l l}
(ENIPS^{-1}~(f \funapply (ENIPS~g))) & = (f \funapply (ENIPS~g)) \funapply (f \funapply (ENIPS~g))^{-1}_{cdr} \\
& = f \funapply (ENIPS~g) \funapply (ENIPS~g)^{-1}_{cdr} \funapply f^{-1}_{cdr} \\
& = f \funapply g \funapply f^{-1}_{cdr} \\
& = h \\
\end{array}
\eeq
\textit{Corollary}. If \automorphismlets2{f}{g} %% \automorphismlet{f} and $g$
are {\em non-recursive} Catalan automorphisms
(i.e. $f,~g~\in~A089840$), then so is also \automorphismlet{h}.
\end{lemma}
\begin{lemma}~\label{lemma_composing_f_and_KROF_g}
\normalfont
If we take an %% arbitrary
\automorphismlet{f}
and KROF -transform of another %% arbitrary
\automorphismlet{g},
and consider their composition as a KROF -transform of
some \automorphismlet{h}:
\beql{composing_f_and_KROF_g}
f \funapply (KROF~g) = (KROF~h)
\eeq
then
\beql{implication_of_composing_f_and_KROF_g}
h = f \funapply g \funapply f^{-1}_{car} \funapply f^{-1}_{cdr}
\eeq
\paragraph{\textit{Proof.}}
The proof is similar to the one given for lemma~\ref{lemma_composing_f_and_ENIPS_g}. %% above.
\textit{Corollary}. If \automorphismlets2{f}{g} %% \automorphismlet{f} and $g$
are {\em non-recursive} Catalan automorphisms
(i.e. $f,~g~\in~A089840$), then so is also \automorphismlet{h}.
\end{lemma}
\begin{lemma}~\label{lemma_obtaining_g_cdr}
\normalfont
If we have $g = (ENIPS~f)$, we obtain an \automorphismlet{g_{cdr}}
as
\beql{obtaining_g_cdr}
g_{cdr} = (ENIPS~f_{cdr})
\eeq
\paragraph{\textit{Proof.}}
We substitute $f$ for $g$ and
$f^{-1}$ for $f$ in the formula~\eqn{implication_of_composing_f_and_ENIPS_g},
as $g_{cdr} = f^{-1} \funapply (ENIPS~f)$.
\end{lemma}
\normalfont
\begin{definition} %% [{Preservation of X-invariance}]
\normalfont
We say that
a Catalan \automorphismlet{f} is {\em X-invariant} or {\em preserves X}
if for all $s$,
\beql{DefXinvariance}
X(f(s)) = X(s)
\eeq
Here $X$ is a function whose domain is the same set
of Catalan structures as on which \automorphismlet{f}
itself has been defined.
\end{definition}
\paragraph{Remark.}
It is immediately seen that the identity \automorphism{A001477}
preserves all functions~$X$ defined on Catalan structures,
and that the inverses and any composition of $X$-invariant automorphisms
are also $X$-invariant.
\begin{lemma}~\label{ExampleA_of_preservation_of_X_invariance}
If function~$X$ can be implemented as a fold,
i.e. satisfies~\eqn{DefHomomorphicFforBinaryTrees}
and \automorphismlet{f} is $X$-invariant,
then $f$'s recursive derivations
\scmcodeintext{(FORK~$f$)},
\scmcodeintext{(KROF~$f$)},
\scmcodeintext{(SPINE~$f$)},
\scmcodeintext{(ENIPS~$f$)},
\scmcodeintext{(RIBS~$f$)},
\scmcodeintext{(DEEPEN~$f$)} and
\scmcodeintext{(NEPEED~$f$)}
are $X$-invariant as well.
\end{lemma}
\textit{Proof}.
We prove this first for the case \scmcodeintext{(ENIPS~$f$)}.
By defining~$w$ as \scmcode{(define~(w~x~y)~(}{\em f}\scmcode{~(cons~x~y)))}
we see that
\beql{X_identity2}
\begin{array}{lll}
X(w(x,y)) & = X(f(cons(x,y))) & $\{ By $w$'s definition \}$\\
& = X(cons(x,y)) & $\{ $f$ itself $X$-preserving \}$\\
& = fold(k,v,cons(x,y)) & $\{ $X$ is a fold, $v~=~(X~\nilatom)$, $k$ unique \}$\\
& = k(x,fold(k,v,y)) & $\{ Expanding by one recursion step \}$\\
& = k(x,X(y)) & $\{ And then substituting $X$ back \}$\\
\end{array}
\eeq
%% where $v~=~(X~\nilatom)$.
By substituting $X$~for~$h$, \nilatom for~$c$, $w$ for $w$ and $k$ for $m$
in~\eqn{DefFusionPropertyFold}, we see that the left side of the implication
is satisfied, thus we are left with the right side of its implication, that is
\beql{X_identity2}
\begin{array}{ll}
X \funapply fold(w,c,s) & = fold(k,(X~\nilatom),s) \\
& = X(s) \\
\end{array}
\eeq
that is, if $g$~=~\scmcodeintext{(ENIPS~$f$)}, then
\beql{X_identity3}
\begin{array}{ll}
X(g(s)) & = X(s) \\
\end{array}
\eeq
which completes the proof that \scmcodeintext{(ENIPS~$f$)}
is also $X$-preserving, if \automorphismlet{f} itself is.
\textit{Corollary}. If $f$ and \scmcodeintext{(ENIPS~$f$)} are X-invariant,
then so is \scmcodeintext{(SPINE~$f$)},
%% because if $f$ is X-invariant, then so it is inverse $f^{-1}$,
because the inverse of the latter form,
\scmcodeintext{(ENIPS~$f^{-1}$)} is X-invariant as well,
because $f^{-1}$ is also X-invariant.
\paragraph{Examples.}
\begin{definition} %% [{Top-level length}]
\normalfont
Function \scmsym{length} in \proglangname{Lisp} and \proglangname{Scheme}
returns the top-level length of the list, or, in the context of
general trees \catint{e},
returns the degree of the root node, i.e. the first number of the
associated Lukasiewicz-word. The associated OEIS-sequence is
\EISseq{A057515}.
\end{definition}
Because \scmsym{length} can be implemented as fold,
like
\beql{SchemeFoldRight_for_length}
\begin{tabular}{l}
\scmcode{(define (length s) (fold-right (lambda (elem sum) (}{\em F}\scmcode{ (length elem) sum)) 0 s))}
\end{tabular}
\eeq
where $F$ has been defined as
\beql{SchemeFoldRight_for_length_aux_F}
\begin{tabular}{l}
\scmcode{(define (F elemlen prevlensum) (+ 1 prevlensum))}
\end{tabular}
\eeq
it follows that if \automorphismlet{f} preserves the top-level
length of the list, then all the above mentioned recursive derivations
of~\automorphismlet{f} also preserve the same property.
\begin{definition}
\normalfont
{\em Matula-Goebel encoding} is a bijection between unlabeled, non-oriented
rooted general trees and natural numbers, discovered independently
by [Matula 1968] and [Goebel 1980].
\end{definition}
\begin{definition} %% [{Top-level length}]
\normalfont
{\em Matula-Goebel signature} for unlabeled rooted plane general trees \catint{e}
assigns a unique natural number to each equivalence class of
non-oriented rooted general trees that underlies each oriented tree.
{\em XXX ---- Wording... When we discard the orientation of a plane
tree. etc.}
The associated OEIS-sequence is \EISseq{A127301}.
\end{definition}
Because Matula-Goebel signature for general trees can be computed with right fold, as
\beql{SchemeFoldRight_for_A127301}
\begin{tabular}{l}
\scmcode{(define (*A127301 s) (fold-right (lambda (t m) (* (A000040 (*A127301 t)) m)) 1 s))}
%% \scmcode{(define (*A127301 s) (fold-right (lambda (elem prod) (}{\em F}\scmcode{ (*A127301 elem) prod)) 1 s))}
\end{tabular}
\eeq
%% where $F$ has been defined as
%% \beql{SchemeFoldRight_for_A127301_aux_F}
%% \begin{tabular}{l}
%% \scmcode{(define (F elemsig prevprod) (* (A000040 elemsig) prevprod))}
%% \end{tabular}
%% \eeq
it follows that if \automorphismlet{f} preserves the Matula-Goebel
signature of a general tree (i.e., its nonoriented form), then all
the above mentioned recursive derivations
of~\automorphismlet{f} also preserve the same property.
\paragraph{Remark.}
If the \automorphismlet{f} preserves the Matula-Goebel signature for general trees,
it follows automatically that it is also Lukasiewicz-word permuting.
However, the reverse condition is not true, for example, the
\automorphism{A072797} does not preserve \EISseq{A127301},
although it is Lukasiewicz-word permuting, and not all of its
recursive derivations preserve the Lukasiewicz-word permuting property.
\begin{definition} %% [{Top-level length}]
\normalfont
{\em Matula-Goebel signature} for unlabeled rooted plane binary trees \catint{c/d}
assigns a unique natural number to each equivalence class of
non-oriented rooted binary trees that underlies each plane binary tree.
{\em XXX ---- Wording... When we discard the orientation of a plane
tree. etc.}
Because Matula-Goebel signature for binary trees can be computed with right fold, as
\beql{SchemeFoldRight_for_A127302}
\begin{tabular}{l}
\scmcode{(define (*A127302 s) (fold-right (lambda (t m) (* (A000040 (*A127302 t)) (A000040 m))) 1 s))}
\end{tabular}
\eeq
it follows that if \automorphismlet{f} preserves the Matula-Goebel
signature of a binary tree (i.e., its nonoriented form), then all
the above mentioned recursive derivations
of~\automorphismlet{f} also preserve the same property.
\paragraph{Remark.} As \autname{A127302} = \autname{A127301}~\funapply~\autname{A057123},
and also the latter has been defined as a fold:
\beql{SchemeFoldRight_for_A057123}
\begin{tabular}{l}
\scmcode{(define (*A057123 s) (fold-right (lambda (x y) (list (*A057123 x) y)) '() s))}
\end{tabular}
\eeq
it implies that \autname{A127302} can also be defined as a fold.
\end{definition}
%I A127301
%S A127301 1,2,4,3,8,6,6,7,5,16,12,12,14,10,12,9,14,19,13,10,13,17,11,32,24,24,
%T A127301 28,20,24,18,28,38,26,20,26,34,22,24,18,18,21,15,28,21,38,53,37,26,37,
%U A127301 43,29,20,15,26,37,23,34,43,67,41,22,29,41,59,31,64,48,48,56,40,48,36
%N A127301 Matula-Goebel signatures for plane general trees encoded by A014486.
%C A127301 This sequence hides a morphism that converts A000108(n) oriented (plane) rooted general trees encoded in range [A014137(n-1)..A014138(n-1)] of A014486 to A000081(n+1) non-oriented rooted general trees, encoded by their Matula-Goebel numbers. The latter encoding is explained in A061773.
%C A127301 If the signature-permutation of a Catalan automorphism SP satisfies the condition A127301(SP(n)) = A127301(n) for all n, then it preserves the non-oriented form of a general tree, which implies also that it is Lukasiewicz-word permuting. Examples of such automorphisms include A072796, A057508, A057509/A057510, A057511/A057512, A057164, A127285/A127286 and A127287/A127288.
%e A127301 A000081(n+1) distinct values occur each range [A014137(n-1)..A014138(n-1)]. As an example, A014486(5) = 44 (= 101100 in binary = A063171(5)), encodes the following plane tree:
%e A127301 .....o
%e A127301 .....|
%e A127301 .o...o
%e A127301 ..\./.
%e A127301 ...*..
%e A127301 Matula-Goebel encoding for this tree gives a code number A000040(1) * A000040(A000040(1)) = 2*3 = 6, thus a(5)=6.
%e A127301 Likewise, A014486(6) = 50 (= 110010 in binary = A063171(6)) encodes the plane tree:
%e A127301 .o
%e A127301 .|
%e A127301 .o...o
%e A127301 ..\./.
%e A127301 ...*..
%e A127301 Matula-Goebel encoding for this tree gives a code number A000040(A000040(1)) * A000040(1) = 3*2 = 6, thus a(6) is also 6, which shows these two trees are identical if one ignores their orientation.
%Y A127301 a(A014138(n)) = A007097(n+1), a(A014137(n)) = A000079(n+1) for all n. a(|A106191(n)|) = A033844(n-1) for all n >= 1. Cf. A127302.
%K A127301 nonn
%O A127301 0,2
%A A127301 Antti Karttunen (His-Firstname.His-Surname(AT)gmail.com), Jan 16 2007
%o A127301 (Scheme:) (define (A127301 n) (*A127301 (A014486->parenthesization (A014486 n)))) ;; A014486->parenthesization given in A014486.
%o A127301 (define (*A127301 s) (if (null? s) 1 (fold-left (lambda (m t) (* m (A000040 (*A127301 t)))) 1 s)))
%I A127302
%S A127302 1,4,14,14,86,86,49,86,86,886,886,454,886,886,301,301,301,886,886,301,
%T A127302 454,886,886,13766,13766,6418,13766,13766,3986,3986,3986,13766,13766,
%U A127302 3986,6418,13766,13766,3101,3101,1589,3101,3101,1849,1849,3101,13766
%N A127302 Matula-Goebel signatures for plane binary trees encoded by A014486.
%F A127302 a(n) = A127301(A057123(n)).
%C A127302 This sequence hides a morphism that converts A000108(n) oriented (plane) rooted binary trees encoded in range [A014137(n-1)..A014138(n-1)] of A014486 to A001190(n+1) non-oriented rooted binary trees, encoded by their Matula-Goebel numbers (when viewed as a subset of non-oriented rooted general trees). See also the comments at A127301.
%C A127302 If the signature-permutation of a Catalan automorphism SP satisfies the condition A127302(SP(n)) = A127302(n) for all n, then it preserves the non-oriented form of a binary tree. Examples of such automorphisms include A069770, A057163, A122351, A069767/A069768, A073286-a073289, A089854, A089859/A089863, A089864, A122282, A123492-A123494, A123715/A123716, A127377-A127380, A127387 and A127388.
%e A127302 A001190(n+1) distinct values occur each range [A014137(n-1)..A014138(n-1)]. As an example, terms 014486(4..8) encode the following five plane binary trees:
%e A127302 ........\/.....\/.................\/.....\/...
%e A127302 .......\/.......\/.....\/.\/.....\/.......\/..
%e A127302 ......\/.......\/.......\_/.......\/.......\/.
%e A127302 n=.....4........5........6........7........8..
%e A127302 The trees in positions 4, 5, 7 and 8 all produce Matula-Goebel number A000040(1)*A000040(A000040(1)*A000040(A000040(1)*A000040(1))) = 2*A000040(2*A000040(2*2)) = 2*A000040(14) = 2*43 = 86, as they are just different planar representations of the one and same non-oriented tree. The tree in position 6 produces Matula-Goebel number A000040(A000040(1)*A000040(1)) * A000040(A000040(1)*A000040(1)) = A000040(2*2) * A000040(2*2) = 7*7 = 49. Thus a(4..8) = 86,86,49,86,86.
%K A127302 nonn
%O A127302 0,2
%A A127302 Antti Karttunen (His-Firstname.His-Surname(AT)gmail.com), Jan 16 2007
\paragraph{Remark.}
There are examples of functions whose invariancy is preserved by {\em certain} recursive derivations,
although they might not be computable (XXX --- ???) as folds, because they do not satisfy
condition~\eqn{DefHomomorphicFforLists}.
Two examples follow.
If a Catalan \automorphismlet{f} preserves the characteristic function of~\EISseq{A072795}
({\em or more precisely, its signature-permutation does}), i.e. if
\beql{DefInvariantInitialNils}
\charfunforcarnil(f(s)) = \charfunforcarnil(s)
\eeq
holds for all $s$,
then the property \eqn{EqInitialNils} holds for that automorphism. %% \automorphismlet{f}.
Incidentally, this can be defined also as a fold:
\beql{SchemeFoldRight_for_char_A072795}
\begin{tabular}{l}
\scmcode{(define (*char\_A072795 s) (fold-right (lambda (x y) (if (null? x) 1 0)) 0 s))}
\end{tabular}
\eeq
although, because the function does not satisfy the condition~\eqn{DefHomomorphicFforBinaryTrees},
it cannot be computed as a fold for binary trees.
If a Catalan \automorphismlet{f} preserves the characteristic function of~\EISseq{A057548},
i.e. if
\beql{DefInvariantInitialOnes}
\charfunforcdrnil(f(s)) = \charfunforcdrnil(s)
\eeq
holds for all $s$,
then the property \eqn{EqInitialOnes} holds for that automorphism. %% \automorphismlet{f}.
Note that this function satisfies neither condition~\eqn{DefHomomorphicFforLists}
nor~\eqn{DefHomomorphicFforBinaryTrees}.
\begin{propo}~\label{constructing_horizontally_telescoping_automorphisms}
\normalfont
If \automorphismlet{f} satisfies the condition~\eqn{EqInitialNils},
that is, if it preserves {\charfunforcarnil}, %% (the characteristic function of~\EISseq{A072795}),
that is, satisfies the condition~\eqn{DefInvariantInitialNils},
then $(FORK~f)$, $(KROF~f)$, $(SPINE~f)$, $(ENIPS~f)$ and $(RIBS~f)$
are all horizontally telescoping, i.e. they satisfy the stronger
condition~\eqn{EqHorizontallyTelescoping}.
\textit{Proof.} All the aforementioned recursion schemes
recurse down to cdr-side of an S-expression.
\end{propo}
\begin{propo}~\label{constructing_vectically_telescoping_automorphisms}
\normalfont
If \automorphismlet{f} satisfies the condition~\eqn{EqInitialOnes},
that is, if it preserves {\charfunforcdrnil},
that is, satisfies the condition~\eqn{DefInvariantInitialOnes},
then $(FORK~f)$, $(KROF~f)$, $(DEEPEN~f)$ and $(NEPEED~f)$
are all vertically telescoping, i.e. they satisfy the stronger
condition~\eqn{EqVerticallyTelescoping}.
\textit{Proof.} All the aforementioned recursion schemes
recurse down to car-side of an S-expression.
\end{propo}
\begin{propo}~\label{schemeMhorizontally}
All automorphisms obtained with \scmcodeintext{RIBS}
are horizontally telescoping, that is, they satisfy the property defined in
\eqn{EqHorizontallyTelescoping}, regardless of the properties of the
automorphism to which \scmcodeintext{RIBS} is applied to.
\end{propo}
\textit{Proof}. Obvious. All automorphisms fix~\nilatom.
\begin{propo}~\label{MAP_INVERT}
If \automorphismlet{f} has a sequence $F_f$ as its counts of fixed points sequence
then \automorphismlet{g}~$\equiv$~\scmcodeintext{(RIBS~$f$)}
has as its counts of fixed points sequence
$$
F_g~=~INVERT(RIGHT(F_f)).
$$
\end{propo}
Here the operator RIGHT increases the indices of the sequence $F_f$ by
one (from zero to one-based sequence),
and the operation INVERT is the one which Cameron calls the operator~$A$ in [Cameron 1985]
and which appears with the name INVERT in [Bernstein and Sloane 1995].
It can be defined as the correspondence between two power series:
$$
1~+~\sum_{n=1}^{\infty} b_n x^n~=~{1\over1~-~\sum_{n=1}^{\infty} a_n x^n}
$$
in which case sequence $b$~=~INVERT($a$). One interpretation is that $b_n$ is the number
of ordered arrangements of items of total weight~$n$ %% (postage stamps of total value~$n$)
that can be formed if we have $a_i$ types of items of
weight~$i$,~$i~{\geq}~1$.
\textit{Proof}. We see that \automorphismlet{g} fixes precisely %% only
those S-expressions whose {\em ``car~ribs''} %% car-branches
are fixed by \automorphismlet{f}.
Thus in this case $b_n$ %% , the ordered arrangements of total weight~$n$, are all the
gives the number of S-expressions of $n$~nodes that are
fixed by \automorphismlet{g} and
$a_i$ gives all the S-expressions of $i-1$~nodes that are
fixed by \automorphismlet{f}.
Because in the {\em ``cdr~spine''} of the whole S-expression
there is one extra node for each car-branch, the resulting
numbers match. [DRAW A PICTURE!]
\begin{propo}~\label{FORK_and_DEEPEN}
If \automorphismlet{g} is a Lukasiewicz-word permuting,
and \automorphismlet{f} is the one that naturally
embeds into it in scale $n:2n$ as explained in lemma~\ref{lukaembed},
then $(FORK~f)$ embeds in the same manner
to $(DEEPEN~g)$.
\end{propo}
\textit{Proof}. Follows from the properties of $FORK$ and $DEEPEN$ transforms.
%*****************************************************
%
%
% Section G
% Automorphisms
%
%
%*****************************************************
\section{Catalan automorphisms in detail}\label{Sec_Automorphisms}
\subsection{\automorphism{A069770}}
%% \subsection{gmA069770}
%% \fbox{ }
\begin{tabular}{p{6cm}l}
%% & & ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \\
%% \multicolumn{3}{c}{\bf{A069770.}} \\
%% \hline
%% Automorphism: & \bf{A069770.} \\
Fixed points counted by: & $AERATED$(\EISseq{A000108}).
\\
Cycles counted by: & \EISseq{A007595}. \\
Max. cycle lengths given by: & $LEFT$(\EISseq{A046698}). \\ %% = 1,1,2,2,2,2,2,... \\
LCM's of cycle lengths given by: & $LEFT$(\EISseq{A046698}). \\ %% = 1,1,2,2,2,2,2,... \\
Lukasiewicz-word permuting: & No. \\
Telescoping: & No. \\
Recursive compositions: & \autname{A069770} = (FORK \autname{A129604}) = (KROF \autname{A129604}) \\
& = (ENIPS \autname{A089859}) = (SPINE \autname{A089863}). \\
Constructive definition: &
\begin{scmdefinefun}
%% \scmcode{(define} & \multicolumn{3}{l}{\scmcode{(*A069770 s)}}\\
\multicolumn{4}{l}{\scmcode{(define (*A069770 s)}}\\
& \scmcode{(if} & \scmcode{(null? s) s}\\
& & \scmcode{(cons (cdr s) (car s))))}\\
%% & \scmcode{)}\\
%% \scmcode{)}\\
\end{scmdefinefun} \\
Destructive definition: &
\begin{scmdefinefun5}
%% \multicolumn{2}{l}{\scmcode{(define}} & \multicolumn{2}{l}{\scmcode{(*A069770! s)}}\\
\multicolumn{4}{l}{\scmcode{(define (*A069770! s)}}\\
& \scmcode{(if} & \multicolumn{2}{l}{\scmcode{(pair? s)}} \\
& & \multicolumn{2}{l}{\scmcode{(let ((org-car (car s)))}} \\
& & & \scmcode{(set-car! s (cdr s))} \\
& & & \scmcode{(set-cdr! s org-car))))} \\
\end{scmdefinefun5}
\\
%% The effect on the interpretations
%% \catint{c/d} and \catint{a}
%% of the Catalan structures of size~$n$=3:
%%
%% & \fbox{
%% \begin{tabular}{c c}
%% \includegraphics{kuvat/cd4.eps} & \includegraphics{kuvat/cd7.eps} \\
%% \includegraphics{kuvat/a4.eps} & \includegraphics{kuvat/a7.eps} \\
%% \end{tabular}}
%%
%% \fbox{
%% \begin{tabular}{c c}
%% \includegraphics{kuvat/cd5.eps} & \includegraphics{kuvat/cd8.eps} \\
%% \includegraphics{kuvat/a5.eps} & \includegraphics{kuvat/a8.eps} \\
%% \end{tabular}}
%%
%% \fbox{
%% \begin{tabular}{c}
%% \includegraphics{kuvat/cd6.eps} \\
%% \includegraphics{kuvat/a6.eps} \\
%% \end{tabular}}
\end{tabular}
%% \input{a069770}
\footnote{
Here $AERATED$(\EISseq{Axxxxxx}) is used to
indicate the OEIS-sequence
\EISseq{Axxxxxx} interpolated with zeros,
and $LEFT$(\EISseq{Axxxxxx}) (or $RIGHT$(\EISseq{Axxxxxx}))
means the sequence
\EISseq{Axxxxxx} shifted left (or respectively, right) by one.
Especially, $LEFT$(\EISseq{A046698}) = 1,1,2,2,2,2,2,...
is used to indicate the sequences of maximum cycle lengths and
LCM's of cycle lengths for involutions, and
$LEFT$(\EISseq{A019590}) = 1,1,0,0,0,0,0,...
for the fixed point count sequences
of those automorphisms that fix no structures
which are larger than the trivial null and one-node structures.}
\thickspace
\thickspace
This involution, which is the simplest Catalan automorphism after the identity
automorphism, swaps the left and right-hand subtree of a binary tree.
%% Its effect on the interpretations \catint{c/d} and \catint{a} of
%% the Catalan structures of size~$n$=3 is depicted below.
How it will partition the appropriate Catalan structures of size~$n$=3
into three disjoint cycles is shown below:
\begin{figure}[!ht]
\begin{center}
\[
\xy
% For pentagon inscribed in the unit circle, the coordinates * 100 are
% (starting clockwise from the top vertex):
% (0,100),(95,31),(59,-81),(-59,-81),(-95,31):
% (0,10)*{\includegraphics{kuvat/cd6.eps}}="1o"; % For internal rim.
(0,30)*{\includegraphics{kuvat/cd6.eps}}="1o";
(0,20)*+{ \xy 0;/r.07pc/:
(0,20)*{}="1";
(19,6.2)*{}="2";
(11.8,-16.2)*{}="3";
(-11.8,-16.2)*{}="4";
(-19,6.2)*{}="5";
{\ar@{-} "1";"2"};
{\ar@{-} "3";"2"};
{\ar@{-} "4";"3"};
{\ar@{-} "5";"4"};
{\ar@{-} "5";"1"};
{\ar@{-} "1";"3"};
{\ar@{-} "1";"4"};
\endxy}="1";
(30,10)*{\includegraphics{kuvat/cd7.eps}}="2o";
(19,6.2)*+{ \xy 0;/r.07pc/:
(0,20)*{}="1";
(19,6.2)*{}="2";
(11.8,-16.2)*{}="3";
(-11.8,-16.2)*{}="4";
(-19,6.2)*{}="5";
{\ar@{-} "1";"2"};
{\ar@{-} "3";"2"};
{\ar@{-} "4";"3"};
{\ar@{-} "5";"4"};
{\ar@{-} "5";"1"};
{\ar@{-} "2";"4"};
{\ar@{-} "2";"5"};
\endxy}="2";
(20,-25)*{\includegraphics{kuvat/cd4.eps}}="3o";
(11.8,-16.2)*+{ \xy 0;/r.07pc/:
(0,20)*{}="1";
(19,6.2)*{}="2";
(11.8,-16.2)*{}="3";
(-11.8,-16.2)*{}="4";
(-19,6.2)*{}="5";
{\ar@{-} "1";"2"};
{\ar@{-} "3";"2"};
{\ar@{-} "4";"3"};
{\ar@{-} "5";"4"};
{\ar@{-} "5";"1"};
{\ar@{-} "3";"5"};
{\ar@{-} "3";"1"};
\endxy}="3";
(-20,-25)*{\includegraphics{kuvat/cd8.eps}}="4o";
(-11.8,-16.2)*+{ \xy 0;/r.07pc/:
(0,20)*{}="1";
(19,6.2)*{}="2";
(11.8,-16.2)*{}="3";
(-11.8,-16.2)*{}="4";
(-19,6.2)*{}="5";
{\ar@{-} "1";"2"};
{\ar@{-} "3";"2"};
{\ar@{-} "4";"3"};
{\ar@{-} "5";"4"};
{\ar@{-} "5";"1"};
{\ar@{-} "4";"1"};
{\ar@{-} "4";"2"};
\endxy}="4";
(-30,10)*{\includegraphics{kuvat/cd5.eps}}="5o";
(-19,6.2)*+{ \xy 0;/r.07pc/:
(0,20)*{}="1";
(19,6.2)*{}="2";
(11.8,-16.2)*{}="3";
(-11.8,-16.2)*{}="4";
(-19,6.2)*{}="5";
{\ar@{-} "1";"2"};
{\ar@{-} "3";"2"};
{\ar@{-} "4";"3"};
{\ar@{-} "5";"4"};
{\ar@{-} "5";"1"};
{\ar@{-} "5";"2"};
{\ar@{-} "5";"3"};
\endxy}="5";
{\ar@{<->}@/_1pc/ (-5,12); (+5,12)};
{\ar@{<->} "2";"3"};
{\ar@{<->} "4";"5"};
\endxy
\]
\caption{How \automorphism{A069770} acts
on binary trees of 3 internal nodes, and on the corresponding
Eulerian polygon triangulations.}
\end{center}
\end{figure}
%% $$
%% \begin{array}{c c c c c c c}
%%
%% \includegraphics{kuvat/cd4.eps} & \includegraphics{kuvat/cd7.eps} & &
%% \includegraphics{kuvat/cd5.eps} & \includegraphics{kuvat/cd8.eps} & &
%% \includegraphics{kuvat/cd6.eps} \\
%%
%% %% & \leftrightarrow & & \hfill & & \leftrightarrow & & \hfill & \bigcirc \\
%%
%% \includegraphics{kuvat/a4.eps} & \includegraphics{kuvat/a7.eps} & &
%% \includegraphics{kuvat/a5.eps} & \includegraphics{kuvat/a8.eps} & &
%% \includegraphics{kuvat/a6.eps} \\
%%
%%
%% \multicolumn{2}{c}{\longleftrightarrow} & &
%% \multicolumn{2}{c}{\longleftrightarrow} & & \fixarrow \\
%%
%%
%% \end{array}
%% $$
%% Because %% \automorphism{A069770}
This automorphism fixes only binary trees whose left and right-hand subtree are
identical (one extra, connecting node is located at the root),
thus the number of fixed points in {\Subrange} is given by the
Catalan numbers interpolated with zeros:
\beql{Eqfc_A069770}
\aligned
fcs_{A069770}(n) = \left\{ \begin{array}{lll}
0 & \mbox{~if~}n\mbox{~is~even}\, , \\
\\
C({n-1\over2}) & \mbox{~if~}n\mbox{~is~odd}\, . \\
\end{array} \right.
\endaligned
\eeq
yielding
$$
1,1,0,1,0,2,0,5,0,14,0,42,0,...
$$
As with all involutions, the cycle-counts are obtained simply
by taking the mean of Catalan numbers and the number of fixed points:
\beql{EQcc_A069770} %% {EqA007595}
\aligned
cc_{A069770}(n) = \left\{ \begin{array}{lll}
{C(n) \over 2} & \mbox{~if~}n\mbox{~is~even}\, , \\
\\
\oratio{C(n) + C(\oratio{n-1}{2})}{2} & \mbox{~if~}n\mbox{~is~odd}\, . \\
\end{array} \right.
\endaligned
\eeq
yielding
$$
1,1,1,3,7,22,66,217,715,2438,8398,29414,104006,371516,1337220,...
$$
This is the sequence \EISseq{A007595} in OEIS.
Other manifestations/meanings given to it include
{\em Number of necklaces of 2 colors with 2n beads and n-1 black
ones} [Meeussen, 2002] %% - Wouter Meeussen (wouter.meeussen(AT)pandora.be), Aug 03 2002
and {\em Number of even permutations avoiding 132}.
\begin{propo}~\label{propo_A069770_FORK_and_KROF_distributivity}
\normalfont
The following two identities hold:
\beql{eq_A069770_FORK_distributivity}
(FORK~(\autname{A069770}~{\funapply}~g)) = (FORK~\autname{A069770})~\funapply~(FORK~g)
\eeq
\beql{eq_A069770_KROF_distributivity}
(KROF~(g~{\funapply}~\autname{A069770})) = (KROF~g)~\funapply~(KROF~\autname{A069770})
\eeq
\textit{Proof}.
We prove~\eqn{eq_A069770_KROF_distributivity}
by considering the inverse
of $KROF$-operation. We let $X$ stand for the right side of~\eqn{eq_A069770_KROF_distributivity},
and so we have:
\beql{proof_of_A069770_KROF_distributivity}
\begin{array}{l l}
%% (KROF^{-1}~(KROF~g)~\funapply~(KROF~\autname{A069770})) & = (KROF~g)~\funapply~(KROF~\autname{A069770}) \\
(KROF^{-1}~X) & = (KROF~g)~\funapply~(KROF~\autname{A069770}) \\
& \funapply~((KROF~g)~\funapply~\autname{A057163}))^{-1}_{car} \\
& \funapply~((KROF~g)~\funapply~\autname{A057163}))^{-1}_{cdr} \\
& = (KROF~g)~\funapply~\autname{A057163}~\funapply~\autname{A057163}_{car}~\funapply~(KROF~g)^{-1}_{car}~\funapply~\autname{A057163}_{cdr}~\funapply~(KROF~g)^{-1}_{cdr} \\
& = (KROF~g)~\funapply~\autname{A057163}~\funapply~\autname{A057163}_{car}~\funapply~\autname{A057163}_{cdr}~\funapply~(KROF~g)^{-1}_{car}~\funapply~(KROF~g)^{-1}_{cdr} \\
& = (KROF~g)~\funapply~\autname{A069770}~\funapply~(KROF~g)^{-1}_{car}~\funapply~(KROF~g)^{-1}_{cdr} \\
& = (KROF~g)~\funapply~(KROF~g)^{-1}_{cdr}~\funapply~\autname{A069770}~\funapply~(KROF~g)^{-1}_{cdr} \\
& = (KROF~g)~\funapply~(KROF~g)^{-1}_{cdr}~\funapply~(KROF~g)^{-1}_{car}~\funapply~\autname{A069770} \\
& = g~\funapply~\autname{A069770} \\
\end{array}
\eeq
The case ~\eqn{eq_A069770_KROF_distributivity}
is proved similarly.
%% follows from the identity $(KROF~f)^{-1}~=~(FORK~f^{-1})$. ??? XXX
\end{propo}
\begin{propo}~\label{propo_A069770_conjugation_inside_FORK_or_KROF}
\normalfont
The following two identities hold:
\beql{eq_A069770_conjugation_inside_FORK}
(FORK~(\autname{A057163}~{\funapply}~g~{\funapply}~\autname{A057163})) = \autname{A057163}~\funapply~(FORK~g)~\funapply~\autname{A057163}
\eeq
\beql{eq_A069770_conjugation_inside_KROF}
(KROF~(\autname{A057163}~{\funapply}~g~{\funapply}~\autname{A057163})) = \autname{A057163}~\funapply~(KROF~g)~\funapply~\autname{A057163}
\eeq
\textit{Proof}.
This is easily proved graphically.
\end{propo}
\beginautdesc{gmA057163}
Fixed points counted by: & $AERATED$(\EISseq{A000108}).
\\
Cycles counted by: & \EISseq{A007595}. \\
Max. cycle lengths given by: & $LEFT$(\EISseq{A046698}). \\ %% = 1,1,2,2,2,2,2,... \\
LCM's of cycle lengths given by: & $LEFT$(\EISseq{A046698}). \\ %% = 1,1,2,2,2,2,2,... \\
Lukasiewicz-word permuting: & No. \\
Telescoping: & No. \\
Recursive composition: & \autname{A057163} = (FORK \autname{A069770}). \\
Constructive definition: &
\beginppschemecode
(define (*A057163 s)
(cond ((not (pair? s)) s)
(else (cons (*A057163 (cdr s))
(*A057163 (car s)))
)
)
)
\end{verbatim}
\endppschemecode
\\
Destructive definition: &
\beginppschemecode
(define (*A057163! s)
(cond ((pair? s)
(*A069770! s)
(*A057163! (car s))
(*A057163! (cdr s))
)
)
s
)
\end{verbatim}
\endppschemecode
\\
\finautdesc
\input{a057163}
This involution reflects the binary trees and polygon triangulations.
It is obtained by applying \automorphism{A069770} recursively down to
every branch of a binary tree, and it has the same cycle-count, fixed
point count, max. and LCM-sequences as the former. %% \automorphism{A069770},
However, the fixed points themselves generally are not the same,
as this one fixes the {\em symmetric} binary trees, i.e. ones whose left and right-hand sides
are (usually) not identical, but instead {\em mirror images} of each other.
How this automorphism will partition the appropriate Catalan structures of size~$n$=3
into three disjoint cycles is shown below:
$$
\begin{array}{c c c c c c c}
\includegraphics{kuvat/cd4.eps} & \includegraphics{kuvat/cd8.eps} & &
\includegraphics{kuvat/cd5.eps} & \includegraphics{kuvat/cd7.eps} & &
\includegraphics{kuvat/cd6.eps} \\
%% & \leftrightarrow & & \hfill & & \leftrightarrow & & \hfill & \bigcirc \\
\includegraphics{kuvat/a4.eps} & \includegraphics{kuvat/a8.eps} & &
\includegraphics{kuvat/a5.eps} & \includegraphics{kuvat/a7.eps} & &
\includegraphics{kuvat/a6.eps} \\
\multicolumn{2}{c}{\longleftrightarrow} & &
\multicolumn{2}{c}{\longleftrightarrow} & & \fixarrow \\
\end{array}
$$
\input{a072796}
This non-recursive automorphism exchanges the two leftmost branches of general trees
if the degree of tree's root is~$>~1$, otherwise it keeps the tree intact.
Thus the fix point count sequence gives the number of general plane trees which
are either empty (the case $n=0$), or whose root degree is either 1 (i.e. the planted trees)
or the two leftmost subtrees (of the root node) are identical.
This can be computed as a sum of planted trees (the first term) and a
convolution, where the left hand side of product gives the number of trees
that can occur as the two identical leftmost subtrees, and the right hand
side of the product gives the number of possibilities for the rest of tree.
\beql{Eqfc_A072796}
\aligned
%% fcs_{A072796}(n)
A073190(n) =
%% \left\{ \begin{array}{lll} 1 & \mbox{~if~}n\mbox{~is~zero}\, , \\
%% \\
%% We don't need this (n-i) is even condition if we define C so that
%% it returns zero on non-integral arguments. (Also needed with A001683).
C(n-1) + \mathop{\sum_{i=0}^{n-2}}_{2|(n-i)} C(\oratio{n-i-2}{2})\;C(i)
%% C(n-1) + \mathop{\sum_{i=0}^{n-2}}_{(n-i)\mbox{~is~even}} C(\oratio{n-i-2}{2})\;C(i)
%% & \mbox{~otherwise}\, . \\
%% \end{array} \right.
\endaligned
\eeq
yielding
$$
1,1,2,3,8,20,60,181,584,1916,6476,22210,77416,...
$$
Cycle counts follow as before:
\beql{Eqcc_A072796}
\aligned
A073191(n) = \oratio{C(n)+A073190(n)}{2}.
\endaligned
\eeq
yielding
$$
1,1,2,4,11,31,96,305,1007,3389,11636,40498,142714,...
$$
The \automorphism{A072797} is obtained by conjugating
\autname{A072796} with \autname{A057163},
thus it has exactly same fixed point and cycle count
sequences. It has two interesting properties:
first, it is a Lukasiewicz-permuting, thus all its recursive
derivations like \autname{A082325}, \autname{A069775},
\autname{A082339} and \autname{A069787}
are as well, and the automorphisms that their restrictions
to binaryform general trees induce will merit further
attention. ({\em XXX - No, this is not true, except for A069775 and
A069776.
Thus empirical facts has falsified our theory again. Something wrong
with
our logic, about the inheriting of property-X-preserving properties by
recursive forms???!})
Furthermore, \autname{A072797} induces it {\em itself}
with that method, i.e.
$\autname{A072797} =
\autname{A083927}\funapply\autname{A072797}\funapply\autname{A057123}$,
and similarly, it seems that
$\autname{A069775} = \autname{A083927}\funapply\autname{A069775}\funapply\autname{A057123}$,
and
$\autname{A069776} =
\autname{A083927}\funapply\autname{A069776}\funapply\autname{A057123}$.
{\em XXX --- to be proved.}
From the proposition~\ref{FORK_and_DEEPEN} then follows
that $(FORK~\autname{A072797})$, (i.e. \automorphism{A082325},
which is the \autname{A057163}-conjugate of \autname{A057511}),
embeds in the same manner into $(DEEPEN~\autname{A072797})$ = \autname{A122313}.
{\em XXX- Automorphism equations...}
For what automorphisms $f$ and $g$, $(SPINE~f{\funapply}g) = (SPINE~f)~\funapply~(SPINE~g)$ ?
At least when $f$ is one of the automorphisms that leave the right
subtree of binary trees intact. Any others?
For what automorphisms $f$, $f =
\autname{A083927}{\funapply}f{\funapply}\autname{A057123}$ ?
At least when $f=\autname{A001477}$, \autname{A072797},
\autname{A069775}, \autname{A069776}.
For what automorphisms $f$, $f^2 = \autname{A083929}{\funapply}f^3{\funapply}\autname{A083930}$ ?
At least when $f=\autname{A001477}$, \autname{A057505}, \autname{A057506}.
Prove all these.
Also these:
$$
\autname{A057501} = \autname{A083927}{\funapply}\autname{A085159}{\funapply}\autname{A057123}
$$
and
$$
\autname{A057502} = \autname{A083927}{\funapply}\autname{A085160}{\funapply}\autname{A057123}
$$
\input{a057509-a057510}
This automorphism rotates the top-level branches of general trees
by one step.
It fixes only the trees whose toplevel subtrees are all identical,
and thus the number of fixed points can be computed as
(one is subtracted from the divisor $d$ of $n$, as for each subtree
there is an extra node in the main toplevel stem of the tree.)
\beql{EQfc_A057509} %%
\aligned
fcs_{A057509}(n) = \left\{ \begin{array}{lll}
1 & \mbox{~if~}n\mbox{~is~zero}\, , \\
\\
\sum_{d | n} C(d-1) & \mbox{~otherwise}\, . \\
\end{array} \right.
\endaligned
\eeq
yielding
$$
1,1,2,3,7,15,46,133,436,1433,4878,16797,58837,208013,743034,...
$$
This is the sequence \EISseq{A034731} in OEIS, originally submitted
by Erich Friedman with the name {\em Dirichlet convolution of $b_n=1$ with Catalan numbers}.
The cycle counts are given by \EISseq{A003239},
{\em number of rooted planar trees with n non-root nodes:
circularly cycling the subtrees at the root gives equivalent trees.}
This is computed as:
\beql{Eqcc_A057509}
\aligned
A003239(n) = \oratio{1}{(2n)} \sum_{d | n}\phi(\sratio{n}{d})\;{2d\choose d}
\endaligned
\eeq
yielding
$$
1,1,2,4,10,26,80,246,810,2704,9252,32066,112720,400024,...
$$
Another manifestation/meaning given to it include
{\em number of necklaces with 2n beads, n white and n black},
from which the above formula is easily seen to be derived from.
%% (to get the correspondence, start at root, walk around outside of tree,
%% use white if move away from the root, black if towards root)
Still more manifestations mentioned are
{\em number of terms in polynomial expression for permanent
of generic circulant matrix of order n}
and
{\em number of equivalence classes of n-compositions of n under cyclic rotation}.
%% (Given a necklace, split it into runs of white followed by a black
%% bead and record the lengths of the white runs. This gives an
%% n-composition of n.) a(n)=number of n-multisets in Z mod n whose sum
%% is 0. - David Callan (callan(AT)stat.wisc.edu), Nov 05 2003
It should be easy to see that the least common multiples of
cycle sizes for trees of size $n$ is given by $a(n)=1$ when $n=0$ and
for $n{\ge}1$ by $a(n)={\rm LCM}_{i=1}^{n-1}\;i$,
thus yielding the right shifted version of OEIS-sequence \EISseq{A003418}:
1,1,1,2,6,12,60,60,420,840,2520,2520,27720,27720,360360,...
\input{a057508}
This automorphism reverses the top-level branches of general trees.
Thus the fix point count sequence gives the number of general plane trees
which are palindromic in shallow sense, i.e. whose $k$-th toplevel subtree from
the left is equal with the $k$-th subtree from the right, for all their subtrees.
This can be computed as a
convolution, where the right hand side of the product gives
the number of different kind of trees that can occur in the middle of
toplevel list (when the number of toplevel subtrees is odd),
and the left hand side of product gives the number of possibilities
that can occur at the left and right hand sides of an S-expression
so that it will be symmetric.
\beql{Eqfc_A057508}
\aligned
%% fcs_{A057508}(n)
A073192(n) = \mathop{\sum_{i=0}^{n}}_{2|(n-i)} C(\oratio{n-i}{2})\;{\breve C}(i-1)
\endaligned
\eeq
where ${\breve C}(n)=1$ if $n=-1$ and otherwise as $C(n)$ (the $n$th Catalan number).
This yields the sequence
$$
1,1,2,3,8,18,54,155,500,1614,5456,18630,64960,...
$$
Cycle counts follow as before:
\beql{Eqcc_A057508}
\aligned
A073193(n) = \oratio{C(n)+A073192(n)}{2}.
\endaligned
\eeq
yielding
$$
1,1,2,4,11,30,93,292,965,3238,11126,38708,136486,...
$$
\input{a057164}
The number of fixed points, i.e. the symmetric general trees and Dyck
paths, is given by central binomial coefficients
\beql{EQfc_A057164}
\aligned
fcs_{A057164}(n) = {n\choose \lfloor \sratio{n}{2}\rfloor}
\endaligned
\eeq
1,1,2,3,6,10,20,35,70,126,252,462,924,1716,3432,6435,12870,...
which is the sequence \EISseq{A001405} in OEIS.
For the proof, see e.g. [].
The cycle counts is computed as for all involutions
$cc_{A057164}(n) = \oratio{C(n)+fcs_{A057164}(n)}{2}$,
giving 1,1,2,4,10,26,76,232,750,2494,8524,29624,104468,...
which is the sequence \EISseq{A007123} in OEIS.
%% although stored there with the offset 1 instead of 0.
It has been submitted with the name
{\em Number of connected unit interval graphs with n nodes;
also bracelets (turn over necklaces) with n black beads and n-1 white
beads}.
This connection with binary bracelets can be easily seen/proved by
considering Raney's lemma as explained by Graham, Knuth and Patashnik.
\input{a057511-a057512}
How \automorphism{A057511/gma057512} will ``deeprotate'' a general
tree of six edges is shown below:
\begin{center}
\begin{tabular}{>{\small}p{0.07cm} p{0.4cm}
>{\small}p{0.07cm} p{0.4cm}
>{\small}p{0.07cm} p{0.4cm}
>{\small}p{0.07cm} p{0.4cm}
>{\small}p{0.07cm} p{0.4cm}
>{\small}p{0.07cm} p{0.4cm}
>{\small}p{0.07cm}}
$\hookrightarrow$&
\includegraphics{kuvat/cd74.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd95.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd135.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd76.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd89.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd154.eps} &$\hookleftarrow$ \\
%% Generate those epses first!
\includegraphics{kuvat/e74.eps} &$\leftrightarrow$&
\includegraphics{kuvat/e95.eps} &$\leftrightarrow$&
\includegraphics{kuvat/e135.eps} &$\leftrightarrow$&
\includegraphics{kuvat/e76.eps} &$\leftrightarrow$&
\includegraphics{kuvat/e89.eps} &$\leftrightarrow$&
\includegraphics{kuvat/e154.eps} &$\hookleftarrow$ \\
\end{tabular}
\end{center}
Like with shallow rotates (\automorphism{A057509} and \autname{A057510}),
the least common multiples of cycle sizes is given by the right shifted
version of \EISseq{A003418}:
1,1,1,2,6,12,60,60,420,840,2520,2520,27720,27720,360360,...
However, the size of maximum cycles for trees of size $n{\ge}1$
is given by Landau's function $g(n-1)$,
i.e. yielding the OEIS-sequence \EISseq{A000793} shifted once right:
1,1,1,2,3,4,6,6,12,15,20,30,30,60,60,84,105,140,210,210,...
{\em XXX - explain why: because a general tree can be always
``partitioned'' into any kind of subtree-combination,
and then we just take the largest of them (in Landau's function sense).}
\
To compute the $fcs_{A057511}$ and $cc_{A057511}$ we need a function
that gives the number of $n$-edge general plane trees fixed by
$k$-fold application of the \automorphism{A057511}.
This table has been submitted as \EISseq{A079216} into OEIS:
\begin{center}
\begin{tabular}{cc}
$A079216_{k,n} := $ &
\begin{tabular}{c|cccccccccccc}
$k \setminus n$ &
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\
\hline
1 & 1 & 1 & 2 & 3 & 5 & 6 & 10 & 11 & 18 & 21 & 34 & 35 \\ %% ,68,69,137,148,316,317,759,760,1869,
2 & 1 & 1 & 2 & 5 & 11 & 26 & 66 & 161 & 420 & 1093 & 2916 & 7819 \\ %% ,21304,58321,161233,448090,
3 & 1 & 1 & 2 & 3 & 8 & 18 & 43 & 104 & 273 & 702 & 1870 & 4985 \\ %% ,13562,37038,102266,283774,793189,
4 & 1 & 1 & 2 & 5 & 11 & 30 & 82 & 233 & 680 & 2033 & 6164 & 18923 \\ %% ,58768,184045,581105,1846906,
5 & 1 & 1 & 2 & 3 & 5 & 6 & 15 & 36 & 108 & 301 & 814 & 2080 \\ %% ,5223,12919,32557,83943,222591,
6 & 1 & 1 & 2 & 5 & 14 & 38 & 111 & 332 & 1029 & 3232 & 10374 & 33679 \\ %% ,110722,367252,1228558,
\end{tabular}
\\
\end{tabular}
\end{center}
\
%I A079216
%S A079216 1,1,1,2,1,1,3,2,1,1,5,5,2,1,1,6,11,3,2,1,1,10,26,8,5,2,1,1,11,66,18,11,
%T A079216 3,2,1,1,18,161,43,30,5,5,2,1,1,21,420,104,82,6,14,3,2,1,1,34,1093,273,
%U A079216 233,15,38,5,5,2,1,1,35,2916,702,680,36,111,6,11,3,2,1,1,68,7819,1870
%N A079216 Square array A(n>=0,k>=1) (listed antidiagonally: A(0,1)=1, A(1,1)=1, A(0,2)=1, A(2,1)=2, A(1,2)=1, A(0,3)=1, A(3,1)=3, ...) giving the number of n-edge general plane trees fixed by k-fold application of the automorphisms A057511/A057512 (Deep rotation of general parenthesizations/plane trees).
%C A079216 Note: the counts given here are inclusive, e.g. A(n,6) includes the counts A(n,3) and A(n,2) which in turn both include A(n,1).
%H A079216 A. Karttunen, Gatomorphisms
%H A079216 Index entries for sequences related to parenthesizing
%F A079216 A(0, k) = 1. A(n, k) = Sum_{r=1..n where r/gcd(r, k) divides n} Sum_{c as each composition of n/(r/gcd(r, k)) into gcd(r, k) parts} Product_{i as each composant of c} A(i-1, lcm(r, k))
%p A079216 with(combinat, composition); # composition(n,k) gives ordered partitions of integer n into k parts.
%p A079216 [seq(A079216(n),n=0..119)]; A079216 := n -> A079216bi(A025581(n), A002262(n)+1);
%p A079216 A079216bi := proc(n,k) option remember; local r; if(0 = n) then RETURN(1); else RETURN(add(PFixedByA057511(n,k,r),r=1..n)); fi; end;
%p A079216 PFixedByA057511 := proc(n,k,r) option remember; local ncycles, cyclen, i, c; ncycles := igcd(r,k); cyclen := r/ncycles; if(0 <> (n mod cyclen)) then RETURN(0); else add(mul(A079216bi(i-1,ilcm(r,k)),i=c),c=composition(n/cyclen,ncycles)); fi; end;
%Y A079216 A(n, A003418(n)) = A000108(n). The first row: A057546, second: A079223, third: A079224, fourth: A079225, fifth: A079226, sixth: A079227. Cf. also A079217-a079222.
This table can be computed by defining $A079216(k,~0)~=~1$, and
then computing for the larger values of $n$ with the following recurrence:
\beql{EqA079216}
\aligned
A079216(k, n) =
\mathop{\sum_{r=1}^{n}}_{(r/\gcd(r, k))|n}
\sum_{c_1 + \hdots + c_{\gcd(r,k)} = n/(r/\gcd(r, k))}
\prod_{i=1}^{\gcd(r,k)} A079216({\rm lcm}(r, k), c_{i}-1)
\endaligned
\eeq
The outer sum ranges over all the values $r=1..n$ the degree
of the root node of an $n$-edge general tree may obtain,
with the additional condition that $r/\gcd(r, k)$ (the cycle length)
must divide $n$.
Here the inner sum is iterated over each composition of
$n/(r/\gcd(r,~k))$ into $\gcd(r,~k)$ (i.e., the number of cycles) parts,
and the innermost product ranges over each of the composants.
{\em XXX - Apply generatingfunctionology and other black magic here.
E.g. if we take product over the composants, then isn't it
related to INVERT-transform then?}
Now the count of fixed points can be computed as
\beql{EQfc_A057511} %%
\aligned
fcs_{A057511}(n) = \left\{ \begin{array}{lll}
1 & \mbox{~if~}n\mbox{~is~zero}\, , \\
\\
\sum_{d | n} A079216(\sratio{n}{d},d-1) = A079216(1,n) & \mbox{~otherwise}\, . \\
\end{array} \right.
\endaligned
\eeq
yielding
$$
1,1,2,3,5,6,10,11,18,21,34,35,68,69,137,148,316,317,759,760,...
$$
This is the sequence \EISseq{A057546} in OEIS.
Note that $fcs_{A057511}(p) = fcs_{A057511}(p-1)+1$ for all primes~$p$.
The cycle count sequence follows then as
\beql{EQcc_A057511} %%
\aligned
cc_{A057511}(n) = \left\{ \begin{array}{lll}
1 & \mbox{~if~}n\mbox{~is~zero}\, , \\
\\
\oratio{1}{A003418(n-1)} \sum_{i=1}^{A003418(n-1)} A079216(i,n) & \mbox{~otherwise}\, . \\
\end{array} \right.
\endaligned
\eeq
yielding
$$
1,1,2,4,9,21,56,153,451,1357,4212,13308,42898,140276,465324,...
$$
This is the sequence \EISseq{A057513} in OEIS.
Note that we might as well write the formula in the form
\beql{EQcc_A057511v2} %%
\aligned
cc_{A057511}(n) =
\oratio{1}{n!} \sum_{i=1}^{n!} A079216(i,n)
\endaligned
\eeq
for $n{\ge}1$, as $n!$ is always a multiple of $A003418(n-1)$.
%% as $A003418(n-1)$ divides the $n$th factorial.
{\em XXX - this might or might not help to reduce the formula
to a more practical form. Explain also how it is derived!}
%S A057513 1,1,2,4,9,21,56,153,451,1357,4212,13308,42898,140276,465324,1561955,
%T A057513 5300285,18156813,62732842,218405402,765657940
%N A057513 Number of separate orbits to which permutations given in A057511/A057512 (induced by deep rotation of general parenthesizations/plane trees) partition each A000108[n] objects encoded by A014486 between A014138[n-1]+1-th and A014138[n]th terms.
%C A057513 It is much faster to compute this sequence empirically with the given C-program than to calculate the terms with the formula in its present form.
%H A057513 A. Karttunen, Gatomorphisms (with the complete Scheme source)
%H A057513 Index entries for sequences related to rooted trees
%H A057513 A. Karttunen, C-program for computing empirically the initial terms of this sequence
%F A057513 a(0)=1, a(n) = (1/A003418(n-1))*Sum_{i=1..A003418(n-1)} A079216(n, i) [Needs improvement.]
%p A057513 A057513 := proc(n) local i; `if`((0=n),1,(1/A003418(n-1))*add(A079216bi(n,i),i=1..A003418(n-1))); end;
%S A057546
%S A079223
%S A079224
%S A079225
%S A079226
%S A079227
%I A057546
%S A057546 1,1,2,3,5,6,10,11,18,21,34,35,68,69,137,148,316,317,759,760,1869,1915,4833,4834,12796,12802,
%T A057546 34108,34384,92792,92793,254752,254753,703083,704956,1958210,1958231,5485330,5485331,15427026,
%U A057546 15440591,43618394,43618395,123807695,123807696,352561832,352664217,1007481494,1007481495,2887387009
%N A057546 Number of Catalan objects fixed by the gatomorphism A057511/A057512 (deep rotation of general parenthesizations/plane trees).
%C A057546 Greater than A003238, because there exists also parenthesizations like ((() (())) ((()) ())) and (((()) ()) (() (()))) which are fixed by recursive deep rotation, corresponding to Catalan mountain ranges below:
%C A057546 ...../\..../\............................./\......../\
%C A057546 ../\/__\../__\/\.....and.its."dual"....../__\/\../\/__\
%C A057546 ./______\/______\......................./______\/______\
%C A057546 It's obvious that a(p) = a(p-1)+1 for all primes p.
%H A057546 Index entries for sequences related to parenthesizing
%F A057546 a(0)=1, a(n) = A079216(n, 1) = Sum_{d|n} A079216(d-1, n/d)
%p A057546 with(numtheory,divisors); A057546 := proc(n) local d; if(0=n) then RETURN(1); else RETURN(add(A079216bi(d-1,n/d),d=divisors(n))); fi; end;
%Y A057546 The first row of A079216. The leftmost edge of the triangle A079217 and also its row sums shifted by one. Occurs for first time in A073202 as row 12. Cf. A057513, A079223-a079227, A034731, A003238.
%S A079223 1,1,2,5,11,26,66,161,420,1093,2916,7819,21304,58321,161233,448090,
%T A079223 1253252,3521389,9941693,28175716,80152141,228747967,654817275,
%U A079223 1879602446,5408974390,15601662378,45098766532,130624550412
%N A079223 Number of Catalan objects fixed by two-fold application of the gatomorphisms A057511/A057512 (Deep rotation of general parenthesizations/plane trees).
%S A079224 1,1,2,3,8,18,43,104,273,702,1870,4985,13562,37038,102266,283774,793189,
%T A079224 2227115,6286044,17811751,50672898,144639235,414181050,1189365940,
%U A079224 3424477813,9883578364,28589660227,82870288432,240672107114
%N A079224 Number of Catalan objects fixed by three-fold application of the gatomorphisms A057511/A057512 (Deep rotation of general parenthesizations/plane trees).
%F A079224 a(n) = A079216(n, 3)
%p A079224 A079224 := n -> A079216bi(n,3);
%Y A079224 The third row of A079216. The leftmost edge of the triangle A079219 and also its row sums shifted by one. Occurs in A073202 as row 43639. Cf. A057546, A079223-a079227.
%S A079225 1,1,2,5,11,30,82,233,680,2033,6164,18923,58768,184045,581105,1846906,
%T A079225 5905364,18980465,61292929,198758704,646974285,2113163707,6923642271,
%U A079225 22749608810,74946337830,247499313730,819154110660,2716779932308
%S A079226 1,1,2,3,5,6,15,36,108,301,814,2080,5223,12919,32557,83943,222591,
%T A079226 600252,1632814,4440240,12043224,32572225,88081208,238722759,649725756,
%U A079226 1776546687,4877740703,13432630929,37063472432,102389547753
%S A079227 1,1,2,5,14,38,111,332,1029,3232,10374,33679,110722,367252,1228558,
%T A079227 4138120,14025473,47792389,163643066,562722427,1942548520,6729230281,
%U A079227 23385132060,81503084084,284815902739,997741303308,3503112067273
\input{a069767-a069768}
How it will partition the fourteen binary trees of four internal nodes (and
corresponding polygon triangulations) into three disjoint cycles is shown below:
\begin{center}
%% {cp{1cm}cp{1cm}cp{1cm}cp{1cm}cp{1cm}cp{1cm}cp{1cm}c}
%% {c c c c c c c c c c c c c c c}
%% cp{1pt}c>{\tiny}p{1pt}cp{1pt}cp{1pt}cp{1pt}cp{1pt}cp{1pt}c}
\begin{tabular}{>{\small}p{0.07cm} p{0.4cm} >{\small}p{0.07cm} p{0.4cm} >{\small}p{0.07cm} p{0.4cm} >{\small}p{0.07cm} p{0.4cm} >{\small}p{0.07cm}
p{0.4cm} >{\small}p{0.07cm} p{0.4cm} >{\small}p{0.07cm} p{0.4cm}
>{\small}p{0.07cm} p{0.4cm} >{\small}p{0.07cm}}
$\hookrightarrow$& \includegraphics{kuvat/cd9.eps} &$\leftrightarrow$& \includegraphics{kuvat/cd17.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd12.eps} &$\leftrightarrow$& \includegraphics{kuvat/cd21.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd10.eps} &$\leftrightarrow$& \includegraphics{kuvat/cd18.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd13.eps} &$\leftrightarrow$& \includegraphics{kuvat/cd22.eps}& $\hookleftarrow$ \\
& \includegraphics{kuvat/a9.eps} & & \includegraphics{kuvat/a17.eps} & &
\includegraphics{kuvat/a12.eps} & & \includegraphics{kuvat/a21.eps} & &
\includegraphics{kuvat/a10.eps} & & \includegraphics{kuvat/a18.eps} & &
\includegraphics{kuvat/a13.eps} & & \includegraphics{kuvat/a22.eps} & \\
%% $\hookrightarrow$ & & $\leftrightarrow$ & & $\leftrightarrow$ & &
%% $\leftrightarrow$ & & $\leftrightarrow$ & & $\leftrightarrow$ & &
%% $\leftrightarrow$ & & $\leftrightarrow$ & & $\hookleftarrow$ \\
\\
$\hookrightarrow$& \includegraphics{kuvat/cd14.eps} &$\leftrightarrow$& \includegraphics{kuvat/cd16.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd15.eps} &$\leftrightarrow$& \includegraphics{kuvat/cd19.eps} &$\hookleftarrow$&
& &
\includegraphics{kuvat/cd11.eps} & $\leftrightarrow$ & \includegraphics{kuvat/cd20.eps} & & & \\
& \includegraphics{kuvat/a14.eps} & & \includegraphics{kuvat/a16.eps} & &
\includegraphics{kuvat/a15.eps} & & \includegraphics{kuvat/a19.eps} & &
& &
\includegraphics{kuvat/a11.eps} & & \includegraphics{kuvat/a20.eps} & & & \\
\end{tabular}
\end{center}
\paragraph{Remark.}
Any Catalan \automorphismlet{f} for which $A127302(f(n)) = A127302(n)$ holds for all n,
keeps the nonoriented form of the underlying binary tree intact.
This holds also for $f = \autname{A069767}$ and $f = \autname{A069768}$.
In each set of~{\CatsetN}, i.e. $C_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. The above condition implies that this subset is closed with respect
to any automorphism that satisfies that condition.
Furthermore, \automorphisms2{A069767}{A069768} act transitively on that subset,
i.e. those trees form a single cycle of their own, as can be seen below.
If we map that subset to a binary strings of length $n-1$, 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 these automorphisms induce the
well-known binary wrap-around ("odometer") increment/decrement
algorithm on the binary strings that are in bijective correspondence
with such binary trees.
%I A073346
%S A073346 1,1,0,0,0,0,1,2,0,0,0,0,0,0,0,0,2,4,0,0,0,0,2,4,0,0,0,0,1,0,8,8,0,0,0,
%T A073346 0,0,0,12,16,0,0,0,0,0,0,2,12,40,16,0,0,0,0,0,0,2,12,80,48,0,0,0,0,0,0,
%U A073346 0,0,12,136,144,32,0,0,0,0,0,0,0,2,20,224,384,128,0,0,0,0,0,0,0,0,0,16
%N A073346 Table T(n,k) (listed antidiagonalwise in order T(0,0), T(1,0), T(0,1), T(2,0), T(1,1), ...) giving the number of rooted plane binary trees of size n and "contracted height" k.
%C A073346 The height of binary trees is computed here otherwise as with A073245, but whenever a complete binary tree of (2^k)-1 nodes with all its leaves at the same level, i.e. one of the following trees:
%C A073346 ____________________\/\/\/\/_
%C A073346 _____________\/__\/__\/__\/__
%C A073346 ______________\__/____\_ /___
%C A073346 ____.____\/____\/______\/____ etc.
%C A073346 is encountered as a terminating subtree, it is regarded just a variant of . (an empty tree, a single leaf) and contributes nothing to the height of the tree.
%H A073346 H. Bottomley & A. Karttunen, Notes concerning diagonals of the square arrays A073345 and A073346.
%F A073346 (See the Maple code below. Note that here we use the same convolution recurrence as with A073345, but only the initial conditions for the first two rows (k=0 and k=1) are different. Is there a nicer formula?)
%e A073346 The top-left corner of this square array:
%e A073346 1 1 0 1 0 0 0 1 ...
%e A073346 0 0 2 0 2 2 0 0 ...
%e A073346 0 0 0 4 4 8 12 12 ...
%e A073346 0 0 0 0 8 16 40 80 ...
%p A073346 A073346 := n -> A073346bi(A025581(n), A002262(n));
%p A073346 A073346bi := proc(n,k) option remember; local i,j; if(0 = k) then RETURN(A036987(n)); fi; if(0 = n) then RETURN(0); fi; 2 * add(A073346bi(n-i-1,k-1) * add(A073346bi(i,j),j=0..(k-1)),i=0..floor((n-1)/2)) + 2 * add(A073346bi(n-i-1,k-1) * add(A073346bi(i,j),j=0..(k-2)),i=(floor((n-1)/2)+1)..(n-1)) - (`mod`(n,2))*(A073346bi(floor((n-1)/2),k-1)^2) - (`if`((1=k),1,0))*A036987(n); end;
%p A073346 A025581 := n -> binomial(1+floor((1/2)+sqrt(2*(1+n))),2) - (n+1);
%p A073346 A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);
%Y A073346 Variant: A073345. The first row: A036987. Column sums: A000108. Diagonals: T(n, n) = A000007(n), T(n+1, n) = A000079(n), T(n+2, n) = A058922(n), T(n+3, n) = A074092(n) - [see the attached notes.].
%Y A073346 A073430 gives the upper triangular region of this array. Used to compute A073431. Entries on the row k are all divisible by 2^k, thus dividing them out yields the array/triangle A074079/A074080.
%Y A073346 Sequence in context: A069849 A004530 A084863 this_sequence A114099 A028613 A024362
%Y A073346 Adjacent sequences: A073343 A073344 A073345 this_sequence A073347 A073348 A073349
%K A073346 nonn,tabl
%O A073346 0,8
%A A073346 Antti Karttunen Jul 31 2002
\
\begin{propo}~\label{propo_A069767_as_KROF_of_A069768}
\normalfont
The following two identities hold:
\beql{eq_A069767_as_KROF_of_A069768}
\autname{A069767}~=~(KROF~\autname{A069768})
\eeq
\beql{eq_A069768_as_FORK_of_A069767}
\autname{A069768}~=~(FORK~\autname{A069767})
\eeq
\textit{Proof}.
We prove~\eqn{eq_A069767_as_KROF_of_A069768} by considering the inverse
of $KROF$-operation. We have:
\beql{proof_of_A069767_as_KROF_of_A069768}
\begin{array}{l l}
(KROF^{-1}~\autname{A069767}) & = \autname{A069767} \funapply \autname{A069767}^{-1}_{car} \funapply \autname{A069767}^{-1}_{cdr} \\
& = (SPINE~\autname{A069770}) \funapply \autname{A069768}_{car} \funapply \autname{A069768}_{cdr} \\
& = {(SPINE~\autname{A069770})}_{cdr} \funapply \autname{A069770} \funapply \autname{A069768}_{car} \funapply \autname{A069768}_{cdr} \\
& = \autname{A069767}_{cdr} \funapply \autname{A069768}_{cdr} \funapply \autname{A069770} \funapply \autname{A069768}_{cdr} \{ XXX - EXPLAIN! \}\\
& = \autname{A069770} \funapply (ENIPS~\autname{A069770})_{cdr} \\ %% \autname{A069768}_{cdr} \\
& = (ENIPS~\autname{A069770}) \\
& = \autname{A069768} \\
\end{array}
\eeq
The case ~\eqn{eq_A069768_as_FORK_of_A069767} follows from the identity
$(KROF~f)^{-1}~=~(FORK~f^{-1})$.
\end{propo}
\begin{propo}~\label{propo_A069768_as_KROF_of_A069767}
\normalfont
The following two identities hold:
\beql{eq_A069768_as_KROF_of_A069767}
\autname{A069768}~=~(KROF~\autname{A069767})
\eeq
\beql{eq_A069767_as_FORK_of_A069768}
\autname{A069767}~=~(FORK~\autname{A069768})
\eeq
\textit{Proof}.
We prove~\eqn{eq_A069768_as_KROF_of_A069767} by considering the inverse
of $KROF$-operation. We have:
\beql{proof_of_A069768_as_KROF_of_A069767}
\begin{array}{l l}
(KROF^{-1}~\autname{A069768}) & = \autname{A069768} \funapply \autname{A069768}^{-1}_{car} \funapply \autname{A069768}^{-1}_{cdr} \\
& = (ENIPS~\autname{A069770}) \funapply \autname{A069767}_{car} \funapply \autname{A069767}_{cdr} \\
& = (ENIPS~\autname{A069770}) \funapply \autname{A069767}_{cdr} \funapply \autname{A069767}_{car} \\
& = \autname{A069770} \funapply (ENIPS~\autname{A069770})_{cdr} \funapply \autname{A069767}_{cdr} \funapply \autname{A069767}_{car} \\
& = \autname{A069770} \funapply (ENIPS~\autname{A069770})_{cdr} \funapply (SPINE~\autname{A069770})_{cdr} \funapply \autname{A069767}_{car} \\
& = \autname{A069770} \funapply \autname{A069767}_{car} \\
& = \autname{A069770} \funapply (SPINE~\autname{A069770})_{car} \\
& = (SPINE~\autname{A069770})_{cdr} \funapply \autname{A069770} \\
& = \autname{A069767} \\
\end{array}
\eeq
The case ~\eqn{eq_A069767_as_FORK_of_A069768} follows from the identity
$(KROF~f)^{-1}~=~(FORK~f^{-1})$.
\end{propo}
\paragraph{Remark.}
We have proved that $\autname{A069767} = (FORK^{2}~\autname{A069767}) = (KROF^{2}~\autname{A069767})$
and similarly $\autname{A069768} = (FORK^{2}~\autname{A069768}) = (KROF^{2}~\autname{A069768})$.
A question remains: Are there any other nonidentity Catalan automorphisms,
for which a repeated application of $FORK$ or some other
automorphism of Catalan automorphisms %% recursion scheme
would produce a cycle of finite length?
Does the equation $f = (FORK^{2}~f)$
have just two non-identity solutions?
To compute the $fcs_{A069767}$ and $cc_{A069767}$ we need a function
that gives the number of rooted plane binary trees of size $n$ and "contracted height" $k$.
%% i.e. trees fixed by $k$-fold application of the \automorphism{A069767} ?
This table has been submitted as \EISseq{A073346} into OEIS:
\begin{center}
\begin{tabular}{cc}
$A073346_{k,n} := $ &
\begin{tabular}{c|ccccccccc}
$k \setminus n$ &
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & \\
\hline
0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & $\hdots$ \\
1 & 0 & 0 & 2 & 0 & 2 & 2 & 0 & 0 & $\hdots$ \\
2 & 0 & 0 & 0 & 4 & 4 & 8 & 12 & 12 & $\hdots$ \\
3 & 0 & 0 & 0 & 0 & 8 & 16 & 40 & 80 & $\hdots$ \\
\end{tabular}
\\
\end{tabular}
\end{center}
\
This is a variant of table \EISseq{A073345}, which was known to the Chinese mathematician Ming An-Tu,
who gave the following recurrence in the 1730s: (give it here)
%% a(0, 0) = 1, a(n, k) = Sum[a(n-1, k-1-i)( 2*Sum[ a(j, i), {j, 0, n-2}]+a(n-1, i) ), {i, 0, k-1}]. - David Callan (callan(AT)stat.wisc.edu), Aug 17 2004
[Luo Jian-Jin, 1995].
%I A073345
%S A073345 1,0,0,0,1,0,0,0,0,0,0,0,2,0,0,0,0,1,0,0,0,0,0,0,4,0,0,0,0,0,0,6,0,0,0,
%T A073345 0,0,0,0,6,8,0,0,0,0,0,0,0,4,20,0,0,0,0,0,0,0,0,1,40,16,0,0,0,0,0,0,0,
%U A073345 0,0,68,56,0,0,0,0,0,0,0,0,0,0,94,152,32,0,0,0,0,0,0,0,0,0,0,114,376
%N A073345 Table T(n,k) (listed antidiagonalwise in order T(0,0), T(1,0), T(0,1), T(2,0), T(1,1), ...) giving the number of rooted plane binary trees of size n and height k.
%D A073345 Luo Jian-Jin, Catalan numbers in the history of mathematics in China, in Combinatorics and Graph Theory, (Yap, Ku, Lloyd, Wang, Editors), World Scientific, River Edge, NJ, 1995.
%H A073345 H. Bottomley & A. Karttunen, Notes concerning diagonals of the square arrays A073345 and A073346.
%H A073345 Andrew Odlyzko, Analytic methods in asymptotic enumeration.
%F A073345 (See the Maple code below. Is there a nicer formula?)
%F A073345 This table was known to the Chinese mathematician Ming An-Tu, who gave the following recurrence in the 1730s. a(0, 0) = 1, a(n, k) = Sum[a(n-1, k-1-i)( 2*Sum[ a(j, i), {j, 0, n-2}]+a(n-1, i) ), {i, 0, k-1}]. - David Callan (callan(AT)stat.wisc.edu), Aug 17 2004
%F A073345 The generating function for row n, T_n(x):=Sum[T(n, k)x^k, k>=0], is given by T_n = a(n)-a(n-1) where a(n) is defined by the recurrence a(0)=0, a(1)=1, a(n) = 1 + x a(n-1)^2 for n>=2. - David Callan (callan(AT)stat.wisc.edu), Oct 08 2005
%e A073345 The top-left corner of this square array is
%e A073345 1 0 0 0 0 0 0 0 0 ...
%e A073345 0 1 0 0 0 0 0 0 0 ...
%e A073345 0 0 2 1 0 0 0 0 0 ...
%e A073345 0 0 0 4 6 6 4 1 0 ...
%e A073345 0 0 0 0 8 20 40 68 94 ...
%e A073345 E.g. we have A000108(3) = 5 binary trees built from 3 non-leaf (i.e. branching) nodes:
%e A073345 _______________________________3
%e A073345 ___\/__\/____\/__\/____________2
%e A073345 __\/____\/__\/____\/____\/_\/__1
%e A073345 _\/____\/____\/____\/____\./___0
%e A073345 The first four have height 3, and the last one has height 2, thus T(3,3) = 4, T(3,2) = 1, and T(3,any other value of k) = 0.
%p A073345 A073345 := n -> A073345bi(A025581(n), A002262(n));
%p A073345 A073345bi := proc(n,k) option remember; local i,j; if(0 = n) then if(0 = k) then RETURN(1); else RETURN(0); fi; fi; if(0 = k) then RETURN(0); fi; 2 * add(A073345bi(n-i-1,k-1) * add(A073345bi(i,j),j=0..(k-1)),i=0..floor((n-1)/2)) + 2 * add(A073345bi(n-i-1,k-1) * add(A073345bi(i,j),j=0..(k-2)),i=(floor((n-1)/2)+1)..(n-1)) - (`mod`(n,2))*(A073345bi(floor((n-1)/2),k-1)^2); end;
%p A073345 A025581 := n -> binomial(1+floor((1/2)+sqrt(2*(1+n))),2) - (n+1);
%p A073345 A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);
%t A073345 a[0, 0] = 1; a[n_, k_]/;k2^n-1 := 0; a[n_, k_]/;1 <= n <= k <= 2^n-1 := a[n, k] = Sum[a[n-1, k-1-i](2Sum[ a[j, i], {j, 0, n-2}]+a[n-1, i]), {i, 0, k-1}]; Table[a[n, k], {n, 0, 9}, {k, 0, 9}]
%t A073345 (* or *) a[0] = 0; a[1] = 1; a[n_]/;n>=2 := a[n] = Expand[1 + x a[n-1]^2]; gfT[n_] := a[n]-a[n-1]; Map[CoefficientList[ #, x, 8]&, Table[gfT[n], {n, 9}]/.{x^i_/;i>=9 ->0}] (Callan)
%Y A073345 Variant: A073346. Column sums: A000108. Row sums: A001699.
%Y A073345 Diagonals: A073345(n, n) = A011782(n), A073345(n+3, n+2) = A014480(n), A073345(n+2, n) = A073773(n), A073345(n+3, n) = A073774(n) - Henry Bottomley (se16(AT)btinternet.com) and AK, see the attached notes.
%Y A073345 A073429 gives the upper triangular region of this array. Cf. also A065329, A001263.
%Y A073345 Sequence in context: A019222 A019141 A086077 this_sequence A112765 A105966 A083915
%Y A073345 Adjacent sequences: A073342 A073343 A073344 this_sequence A073346 A073347 A073348
%K A073345 nonn,tabl
%O A073345 0,13
%A A073345 Antti Karttunen Jul 31 2002
The count of fixed points, the row~0 of the above table,
is given by Fredholm-Rueppel sequence. the sequence \EISseq{A036987}
in OEIS. It is defined as a characteristic function of $2^{n}-1$,
giving the terms:
$$
1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,\hdots
$$
The cycle count sequence follows then as
\beql{EQcc_A069767v1} %%
\aligned
cc_{A069767}(n) = {1 \over 2^{n-1}}\;\sum_{i=1}^{2^{n-1}} \sum_{j=0}^{A007814(i)} A073346(j,n)
\cr = -1 + {1\over 2^{n-2}}\;\sum_{i=1}^{2^{n-1}} A073346(A007814(i),n)
\cr = {1\over 2^n}\;\sum_{i=0}^n 2^{n-i}\;A073346(i,n)
\cr = \sum_{i=0}^n 2^{-i}\;A073346(i,n)
\endaligned
\eeq
Here we use sequence \EISseq{A007814}, {\em Exponent of highest power of 2
dividing n},
i.e. the binary carry sequence,
$$
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,\hdots
$$
as a kind of ``filter'', with which XXX ... are selected.
Because entries on the row $k$ of table \EISseq{A073346} are
always multiples of $2^k$, they can be divided out, to form
another table \EISseq{A074079}, and the cycle count formula
can be represented in terms of that table.
\beql{EQcc_A069767v4} %%
\aligned
cc_{A069767}(n) = \sum_{i=0}^{n} A074079(i,n)
\endaligned
\eeq
The formula gives the terms
$$
1,1,1,2,3,6,12,28,65,160,408,1074,2898,7998,22508,64426,187251,...
$$
This is the sequence \EISseq{A073431} in OEIS.
{\em XXX - Lots of explaining here! Also the cc-sequence can be
probably reduced further, by using generatingfunctionological approach.}
%I A073431
%S A073431 1,1,1,2,3,6,12,28,65,160,408,1074,2898,7998,22508,64426,187251,551730,
%T A073431 1645840,4964876,15130808,46545788,144424944,451715460
%N A073431 Number of separate orbits/cycles to which the gatomorphisms A069767/A069768 partition each A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.
%F A073431 a(0)=1, a(n) = (1/(2^(n-1))) * Sum_{i=1..(2^(n-1))} (Sum_{j=0..A007814(i)} A073346(n, j)) = (1/(2^(n-2))) * Sum_{i=1..(2^(n-1))} A073346(n, A007814(i)) - 1 = (1/2^n) * Sum_{i=0..n} (2^(n-i))*A073346(n, i) = Sum_{i=0..n} A074079(n, i)
%p A073431 A073431 := proc(n) local i; (1/2^n) * add((2^(n-i))*A073346bi(n,i),i=0..n); end;
%Y A073431 Occurs for first time in A073201 as row 6 (and 8). Column sums of the square array A074079/Row sums of the triangle A074080.
%Y A073431 Sequence in context: A104872 A006082 A014280 this_sequence A003317 A014278 A060777
%Y A073431 Adjacent sequences: A073428 A073429 A073430 this_sequence A073432 A073433 A073434
%K A073431 nonn
%O A073431 0,4
%A A073431 Antti Karttunen Jul 31 2002
\input{a057161-a057162}
\begin{figure}[!ht]
\begin{center}
\[
\xy
% For pentagon inscribed in the unit circle, the coordinates * 100 are
% (starting clockwise from the top vertex):
% (0,100),(95,31),(59,-81),(-59,-81),(-95,31):
% (0,10)*{\includegraphics{kuvat/cd6.eps}}="1o"; % For internal rim.
(0,30)*{\includegraphics{kuvat/cd6.eps}}="1o";
(0,20)*+{ \xy 0;/r.07pc/:
(0,20)*{}="1";
(19,6.2)*{}="2";
(11.8,-16.2)*{}="3";
(-11.8,-16.2)*{}="4";
(-19,6.2)*{}="5";
{\ar@{-} "1";"2"};
{\ar@{-} "3";"2"};
{\ar@{-} "4";"3"};
{\ar@{-} "5";"4"};
{\ar@{-} "5";"1"};
{\ar@{-} "1";"3"};
{\ar@{-} "1";"4"};
\endxy}="1";
(30,10)*{\includegraphics{kuvat/cd7.eps}}="2o";
(19,6.2)*+{ \xy 0;/r.07pc/:
(0,20)*{}="1";
(19,6.2)*{}="2";
(11.8,-16.2)*{}="3";
(-11.8,-16.2)*{}="4";
(-19,6.2)*{}="5";
{\ar@{-} "1";"2"};
{\ar@{-} "3";"2"};
{\ar@{-} "4";"3"};
{\ar@{-} "5";"4"};
{\ar@{-} "5";"1"};
{\ar@{-} "2";"4"};
{\ar@{-} "2";"5"};
\endxy}="2";
(20,-25)*{\includegraphics{kuvat/cd4.eps}}="3o";
(11.8,-16.2)*+{ \xy 0;/r.07pc/:
(0,20)*{}="1";
(19,6.2)*{}="2";
(11.8,-16.2)*{}="3";
(-11.8,-16.2)*{}="4";
(-19,6.2)*{}="5";
{\ar@{-} "1";"2"};
{\ar@{-} "3";"2"};
{\ar@{-} "4";"3"};
{\ar@{-} "5";"4"};
{\ar@{-} "5";"1"};
{\ar@{-} "3";"5"};
{\ar@{-} "3";"1"};
\endxy}="3";
(-20,-25)*{\includegraphics{kuvat/cd8.eps}}="4o";
(-11.8,-16.2)*+{ \xy 0;/r.07pc/:
(0,20)*{}="1";
(19,6.2)*{}="2";
(11.8,-16.2)*{}="3";
(-11.8,-16.2)*{}="4";
(-19,6.2)*{}="5";
{\ar@{-} "1";"2"};
{\ar@{-} "3";"2"};
{\ar@{-} "4";"3"};
{\ar@{-} "5";"4"};
{\ar@{-} "5";"1"};
{\ar@{-} "4";"1"};
{\ar@{-} "4";"2"};
\endxy}="4";
(-30,10)*{\includegraphics{kuvat/cd5.eps}}="5o";
(-19,6.2)*+{ \xy 0;/r.07pc/:
(0,20)*{}="1";
(19,6.2)*{}="2";
(11.8,-16.2)*{}="3";
(-11.8,-16.2)*{}="4";
(-19,6.2)*{}="5";
{\ar@{-} "1";"2"};
{\ar@{-} "3";"2"};
{\ar@{-} "4";"3"};
{\ar@{-} "5";"4"};
{\ar@{-} "5";"1"};
{\ar@{-} "5";"2"};
{\ar@{-} "5";"3"};
\endxy}="5";
{\ar@{<->} "1";"2"};
{\ar@{<->} "3";"2"};
{\ar@{<->} "4";"3"};
{\ar@{<->} "5";"4"};
{\ar@{<->} "5";"1"};
\endxy
\]
\caption{How \automorphism{A057161/A057162} acts
on binary trees of 3 internal nodes, and on the corresponding
Eulerian polygon triangulations.}
\end{center}
\end{figure}
The cycle count sequence is easiest to define in terms of
\EISseq{A001683}, {\em Number of one-sided triangulations of the
disk},
i.e. the triangulations of Eulerian polygons with $n$~sides.
\beql{EQa001683}
\aligned
A001683(n) = \oratio{1}{n}C(n-2) + \oratio{1}{2}c(\oratio{n}{2}-1) + \oratio{2}{3}\;c(\oratio{n}{3}-1)
\endaligned
\eeq
then we can simply define
\beql{EQcc_A057161v1} %%
\aligned
cc_{A057161}(n) = A001683(n+2)
\endaligned
\eeq
because a binary tree of $n$ internal nodes corresponds
to a triangulation of a polygon of $n+2$ vertices.
This gives the terms
$$
1,1,1,1,4,6,19,49,150,442,1424,4522,14924,\hdots
$$
\input{a074679-a074680}
How \automorphism{A074679/A074680} will act transitively on the
set of fourteen Catalan structures of size 4, forming a single cycle, is shown below.
\begin{figure}[!ht]
\begin{center}
\[
%\xymatrix@C=7pt{
\xymatrix@R=6pt{
& \includegraphics{kuvat/cd17.eps} &
\includegraphics{kuvat/cd9.eps} &
\includegraphics{kuvat/cd14.eps} &
\includegraphics{kuvat/cd19.eps} &
\includegraphics{kuvat/cd22.eps} &
\includegraphics{kuvat/cd13.eps} & \\
& \ar[dl] \includegraphics{kuvat/a17.eps} \ar[r] &
\ar[l] \includegraphics{kuvat/a9.eps} \ar[r] &
\ar[l] \includegraphics{kuvat/a14.eps} \ar[r] &
\ar[l] \includegraphics{kuvat/a19.eps} \ar[r] &
\ar[l] \includegraphics{kuvat/a22.eps} \ar[r] &
\ar[l] \includegraphics{kuvat/a13.eps} \ar[dr] & \\
\includegraphics{kuvat/cd12.eps} \quad \ar[dr] \includegraphics{kuvat/a12.eps} \ar[ur] & & & & & & & \ar[ul] \includegraphics{kuvat/a18.eps} \ar[dl] \quad \includegraphics{kuvat/cd18.eps} \\
& \ar[ul] \includegraphics{kuvat/a21.eps} \ar[r] &
\ar[l] \includegraphics{kuvat/a16.eps} \ar[r] &
\ar[l] \includegraphics{kuvat/a11.eps} \ar[r] &
\ar[l] \includegraphics{kuvat/a20.eps} \ar[r] &
\ar[l] \includegraphics{kuvat/a15.eps} \ar[r] &
\ar[l] \includegraphics{kuvat/a10.eps} \ar[ur] & \\
& \includegraphics{kuvat/cd21.eps} &
\includegraphics{kuvat/cd16.eps} &
\includegraphics{kuvat/cd11.eps} &
\includegraphics{kuvat/cd20.eps} &
\includegraphics{kuvat/cd15.eps} &
\includegraphics{kuvat/cd10.eps} & \\
}
\]
\caption{How \automorphism{A074679/A074680} acts
transitively on the set of fourteen
binary trees of 4 internal nodes, and on the corresponding
Eulerian polygon triangulations.}
\end{center}
\end{figure}
\begin{center}
\begin{tabular}{>{\small}p{0.07cm} p{0.4cm}
>{\small}p{0.07cm} p{0.4cm}
>{\small}p{0.07cm} p{0.4cm}
>{\small}p{0.07cm} p{0.4cm}
>{\small}p{0.07cm} p{0.4cm}
>{\small}p{0.07cm} p{0.4cm}
>{\small}p{0.07cm} p{0.4cm}
>{\small}p{0.07cm}}
& \includegraphics{kuvat/cd9.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd14.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd19.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd22.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd13.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd18.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd10.eps} & \\
& \includegraphics{kuvat/a9.eps} &&
\includegraphics{kuvat/a14.eps} &&
\includegraphics{kuvat/a19.eps} &&
\includegraphics{kuvat/a22.eps} &&
\includegraphics{kuvat/a13.eps} &&
\includegraphics{kuvat/a18.eps} &&
\includegraphics{kuvat/a10.eps} & \\
&$\updownarrow$ & & & & & & & & & & & &$\updownarrow$& \\
& \includegraphics{kuvat/cd17.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd12.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd21.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd16.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd11.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd20.eps} &$\leftrightarrow$&
\includegraphics{kuvat/cd15.eps} & \\
& \includegraphics{kuvat/a17.eps} &&
\includegraphics{kuvat/a12.eps} &&
\includegraphics{kuvat/a21.eps} &&
\includegraphics{kuvat/a16.eps} &&
\includegraphics{kuvat/a11.eps} &&
\includegraphics{kuvat/a20.eps} &&
\includegraphics{kuvat/a15.eps} & \\
\end{tabular}
\end{center}
\input{a057501-a057502}
%% %% n=8: ccs=(1 1 1 2 3 6 14 34 95) fcs=(1 1 0 0 0 0 0 0 0) mcs=(1 1 2 3 8 10 12 14 16) lcs=(1 1 2 6 8 10 12 14 16)
%%
%% %S A002995 1,1,1,1,2,3,6,14,34,95,280,854,2694,8714,28640,95640,323396,1105335,
%% %T A002995 3813798,13269146,46509358,164107650,582538732,2079165208,7457847082,
%% %U A002995 26873059986,97239032056,353218528324,1287658723550,4709785569184
%% %N A002995 Number of planar trees (also called plane trees) with n nodes.
%% %C A002995 Noncrossing handshakes of 2(n-1) people (each using only one hand) on round table, up to rotations - Antti Karttunen Sep 03 2000
%% %C A002995 a(n), n>2, is also the number of oriented cacti on n-1 unlabeled nodes with all cutpoints of separation degree 2, i.e. ones shared only by two (cyclic) blocks. These are digraphs (without loops) that have a unique Eulerian tour. Such digraphs with labeled nodes are enumerated by A102693. - Valery A. Liskovets (liskov(AT)im.bas-net.by), Oct 19 2005
%%
%% %F A002995 G.f.: 1+B(x)+(C(x^2)-C(x)^2)/2 where B is g.f. of A003239 and C is g.f. of A000108(n-1).
%% %F A002995 a(n)=1/(2*(n-1))*sum{d|(n-1)}(phi((n-1)/d)*C(2d, d)) - A000108(n-1)/2 + (if n is even) A000108(n/2-1)/2.
%% %p A002995 with (powseries): with (combstruct): n := 27: Order := n+2: sys := {C = Cycle(B), B = Union(Z,Prod(B,B))}: G003239 := (convert(gfseries(sys,unlabeled,x) [C(x)], polynom)) / x: G000108 := convert(taylor((1-sqrt(1-4*x)) / (2*x),x),polynom): G002995 := 1 + G003239 + (eval(G000108,x=x^2) - G000108^2)/2: A002995 := 1,1,1,seq(coeff(G002995,x^i),i=1..n); # Ulrich Schimke, Apr 05 2002
%% %O A002995 0,5
\begin{propo}~\label{propo_A057501_as_SPINE_of_A074680}
\normalfont
The following two identities hold:
\beql{eq_A057501_as_SPINE_of_A074680}
\autname{A057501}~=~(SPINE~\autname{A074680})
\eeq
\beql{eq_A057502_as_ENIPS_of_A074679}
\autname{A057502}~=~(ENIPS~\autname{A074679})
\eeq
\textit{Proof}.
We prove~\eqn{eq_A057502_as_ENIPS_of_A074679} by
substituting \autname{A069770} for~$f$,
and \autname{A072796} for~$g$ in lemma~\ref{lemma_composing_f_and_ENIPS_g}.
Then
\beql{A057502_as_ENIPS_of_A074679}
\begin{array}{l l}
h & = \autname{A069770} \funapply \autname{A072796} \funapply \autname{A069770}^{-1}_{cdr} \\
& = \autname{A069770} \funapply \autname{A072796} \funapply \autname{A089850} \\
& = \autname{A074679}
\end{array}
\eeq
The case ~\eqn{eq_A057501_as_SPINE_of_A074680} follows from the identity
$(ENIPS~f)^{-1}~=~(SPINE~f^{-1})$.
\end{propo}
\paragraph{Note.} There is also a nice graphical proof for this.
The cycle counts are computed as
\beql{Eqcc_A057501}
\aligned
cc_{A057501}(n) =
\oratio{1}{2n} \sum_{d|n}\phi(\oratio{n}{d})\;{2d\choose d}
-\;\oratio{C(n)}{2} + \text{\rm(if $n$ is odd)}\;\oratio{C(\oratio{n-1}{2})}{2}
%% A003239(n) = \oratio{1}{(2n)} \sum_{d | n}\phi(\sratio{n}{d})\;{2d\choose d}
\endaligned
\eeq
yielding
$$
1,1,1,2,3,6,14,34,95,280,854,2694,8714,28640,95640,323396,...
$$
which is the OEIS sequence \EISseq{A002995} shifted once left.
%% Note that the cycles of \automorphism{A057509} are
%% contained inside/in
%% confined into the cycles of \automorphism{A057501},
Note that each cycle of \automorphism{A057501}
contains one or more cycles of \automorphism{A057509},
that is, the latter
automorphism {\em refines} the partitioning of the S-expressions
effected by the former. Thus $cc_{A057501}(n)~{\le}~cc_{A057509}(n)$
for all $n$, which can also be seen from the above formula, whose first term
is actually $cc_{A057509}(n)$, i.e. \EISseq{A003239(n)}.
Note that $\EISseq{A002995(n+1)} = \EISseq{A003239(n)}-\EISseq{A007595(n)}$,
when $n$ is even and $\ge~2$.
Of the set of~{\CatsetN}, all the $C(n-1)$ planted trees are fixed by
\automorphism{A057509}
That the identity $\autname{A057501} = \autname{A57509}~\circ~\autname{A69770}$
holds can be seen immediately by comparing those definitions of
\autname{A057501} and \autname{A57509} that use the function \scmsym{append}.
\input{a057505-a057506}
%% \input{a057503-a057504}
\thickspace
\beql{EqA001405}
\aligned
A001405(n) \defequ {n\choose \lfloor \sratio{n}{2}\rfloor}
\endaligned
\eeq
\beql{EqA001683}
\aligned
A001683(n) \defequ \oratio{1}{n}C(n-2) + \oratio{1}{2}c(\oratio{n}{2}-1) + \oratio{2}{3}\;c(\oratio{n}{3}-1)
\endaligned
\eeq
\beql{EqA002995}
\aligned
A002995(n) \defequ \oratio{1}{(2(n-1))} \sum_{d|(n-1)}\phi(\oratio{n-1}{d})\;{2d\choose d}
\cr -\;\oratio{C(n-1)}{2} + \text{\rm(if $n$ is even)}\;\oratio{C(\oratio{n}{2}-1)}{2}
\endaligned
\eeq
\beql{EqA003239}
\aligned
A003239(n) \defequ \oratio{1}{(2n)} \sum_{d | n}\phi(\sratio{n}{d})\;{2d\choose d}
\endaligned
\eeq
\beql{EqA007123}
\aligned
A007123(n) \defequ \oratio{C(n) + {n\choose \lfloor \sratio{n}{2}\rfloor}}{2}
\endaligned
\eeq
\beql{EqA034731}
\aligned
A034731(n) \defequ \sum_{d | n} C(d-1)
\endaligned
\eeq
\beql{EqA073431}
\aligned
A073431(n) \defequ {1 \over 2^{n-1}}\;\sum_{i=1}^{2^{n-1}} \sum_{j=0}^{A007814(i)} A073346(n,j)
\cr \defequ -1 + {1\over 2^{n-2}}\;\sum_{i=1}^{2^{n-1}} A073346(n,A007814(i))
\cr \defequ {1\over 2^n}\;\sum_{i=0}^n 2^{n-i}\;A073346(n,i)
\cr \defequ \sum_{i=0..n} A074079(n,i)
\endaligned
\eeq
%*****************************************************
%
%
% Section SB - Acting on infinite binary trees
%
%
%*****************************************************
\section{Actions on infinite labeled binary trees}\label{Sec_infbintrees}
%% {\bf XXX - TRANSFER THIS SECTION TO THE END.}
Certain Catalan automorphisms extend naturally to act on infinite labeled
binary trees. Here the labeling is applied to the {\em internal}
vertices of the tree, {\em not} to the leaf nodes of which
there are none, precisely because the tree is of infinite size.
If we were to stare only the structure of an infinite tree,
then any automorphism will keep it identical. Instead, we are
interested about the relocations of the labels associated
with each internal node. Moreover, we must also define
the relocations of internal nodes, when a particular
non-recursive automorphism is applied. There might be
more than one possibility to fix it, but we will stick
to the one which feels the most natural. E.g. for
\automorphism{A074679} and \automorphism{A074680}
the most natural way to relocate the two internal
nodes is depicted in the figure~X.
Note that here, like with all non-recursive automorphisms,
only the first clause will ever be ``active''.
%% when applied in this way to infinite binary trees.
For example, \automorphism{A074679} will never flip
the sides of an infinite binary tree, as there is
always room to perform the rotation operation.
Next it is just natural to ask what kind of functions
(on rationals) applicable automorphisms induce, when
they act on such infinite trees of rational numbers
as are Stern-Brocot tree \EISseq{A007306}/\EISseq{A047679},
its variant \EISseq{A002487(n)}/\EISseq{A002487(n+1)},
or Kepler's harmonic tree \EISseq{A020651}/\EISseq{A086592}.
For example, \automorphism{A074679}, when acting on
full Stern-Brocot tree \EISseq{A007306}/\EISseq{A047679},
induces the following function of positive rationals:
$$
f(x) = \left\{ \begin{array}{lll}
\frac{x}{(1-x)} & \mbox{~if~} x < \frac{1}{2} \, , \\
3-\frac{1}{x} & \mbox{~if~} \frac{1}{2} \le x < 1 \, , \\
x+1 & \mbox{~if~} x \ge 1 \, .
\end{array} \right.
$$
and the \automorphism{A074680} respectively induces
an inverse of the above function:
$$
g(x) = \left\{ \begin{array}{lll}
\frac{x}{(1+x)} & \mbox{~if~} x < 1 \, , \\
\frac{1}{3-x} & \mbox{~if~} 1 \le x < 2 \, , \\
x-1 & \mbox{~if~} x \ge 2 \, .
\end{array} \right.
$$
Many recursive automorphisms make also sense when applied
to such infinite binary trees.
E.g. \automorphism{A057163} induces a map $x \to \frac{1}{x}$,
and \automorphisms2{A120705}{A120706} %% and \automorphism{A120706}
respectively the maps $x \to 2x$ and $x \to \frac{x}{2}$,
when acting on full Stern-Brocot tree \EISseq{A007306}/\EISseq{A047679}.
%% E.g. \automorphism{A057163} induces a function $r(x) := x \to \frac{1}{x}$,
%% and \automorphisms2{A120705}{A120706} %% and \automorphism{A120706}
%% respectively the functions $d(x) := x \to 2x$ and $h(x) := x \to \frac{x}{2}$,
%% when acting on full Stern-Brocot tree \EISseq{A007306}/\EISseq{A047679}.
%% \[
%% f(x) = \left\{
%% \begin{array}{lll}
%% \frac{1}{d}n & \mbox{~if~} n \equiv 0~(\bmod~ d) \, , \\
%% \frac{1}{d}(n + l(d-b))& \mbox{~if~} n \equiv b~(\bmod~ d), 1 \le b \le d-1\, ,
%% \end{array}
%% \right.
%% \]
%p A057114 sbtree_perm_1_1_right := x -> (`if`((x <= 0),x,(`if`((x < (1/2)),(x/(1-x)),(`if`((x < 1),(3-(1/x)),(x+1)))))));
%p A057115 sbtree_perm_1_1_left := x -> (`if`((x <= 0),x,(`if`((x < 1),(x/(1+x)),(`if`((x < 2),(1/(3-x)),(x-1)))))));
%% f(x) = \left\{ \begin{array}{p{5cm}p{7cm}}
%% x/(1-x) & \textrm{if $x < 1/2$} \\
%% 3-(1/x) & \textrm{if $1/2 <= x < 1$} \\
%% x+1 & \textrm{if $x >= 1$} \\
%% \end{array} \right.
%*****************************************************
%
% Section: Open questions
%
%*****************************************************
\section{Open questions - XXX - vague ideas}\label{Sec_OpenQuestions}
\begin{itemize}
\item ``Top-level'' analysis of the automorphism group. For example,
the whole group of automorphisms contains an alternating group
(consisting only of automorphisms with even permutations,
e.g. \automorphism{A089851}, whose signature permutations
contains only 3-cycles and fixed points.)
Lukasiewicz-word permuting automorphisms form a subgroup
of their own, and similarly initial-nil and other
property reserving automorphisms.
Automorphisms that leave top-level cdr-spine intact
(ones formed with e.g. RIBS-transformation)?
Can we say that the automorphisms that embed into Lukasiewicz-word permuting
automorphisms in scale $n:2n$ somehow form a subgroup?
Yes, but of the whole group, not as a subgroup of
L-word permuting automorphisms. The self-embedding
of {\em binaryform trees} induces a group homomorphism
from L-word preserving subgroup to whole automorphism group
and still the homomorphism has a non-trivial kernel,
because from any \automorphismlet{g} one can construct
a L-word preserving \automorphismlet{h} where $g$
embeds into, and this can be done in several possible
(uncountably many) ways.
Note that this homomorphism has at least two fixed points,
the identity \automorphism{A001477}, and \automorphism{A072797}.
{\em XXX -- Also \autname{A069775} and \autname{A069776}, to be proved.}
It is easy to see that the subgroup of non-recursive automorphisms is not a normal
subgroup. However, the latter itself contains further
subgroups, e.g. all {\em form-preserving} non-recursive
automorphisms of a single non-default clause with a
particular tree shape of $n$ leaves form a subgroup isomorphic with symmetry
group $S_n$ of $n$ elements. Thus there are \EISseq{A000108($n-1$)}
subgroups isomorphic with $S_n$. (more?)
Which of these subgroups are normal (with respect to non-recursive group)?
Which compositions are closed? Delve into non-recursive automorphisms in more detail,
in this same or separate paper.
\item Automorphism group of Tamari-lattice (or actually, the
corresponding {\em rotation graphs}) ?
\automorphism{A057163} is always one of the generators.
\item Groups formed by using more than one Catalan automorphism as generators.
E.g. various dihedral groups, composed of \automorphism{A057161} and
\automorphism{A057163}, or
\automorphism{A057501} and \automorphism{A057164}, etc.
``Artificial dihedral'' groups, like those composed of
\automorphism{A057511} and \automorphism{A057164} or
\automorphism{A057509} and \automorphism{A057508}?
\item Actions on Stern-Brocot tree (previous section), etc.?
\item Actions on {\em birds} (lambda-calculus)? C.f. {\em
combinatorial ornithology}. ``Simple programs''.
Use Wolframesque plots.
\item ``Measures of chaoticity''? E.g. the sequences \EISseq{A081164}
and \EISseq{A081166} for the \automorphism{A057505}.
First differences of the max-cycle sequences? (if not monotone)
Sort the automorphisms according to the growth rate of their
LCM-sequences. Involutions are then ``by definition'' the least
chaotic? Compare the fixpoint/cycle count ratios for these,
are there examples of diverging, ``chaotic'' behaviour?
Again, chaoticity, can we define
something like a ``Lyapunov-exponent'' for these?
The underlying metric (whether a distance in Tamari-lattice,
position in \EISseq{A014486}, or in the cycle
of some yet-to-be-found-natural-transitive-automorphism),
will in any case favour some automorphisms over others.
Develop a measure of chaoticity (a function) about
which something predictable can be said when two
automorphisms with known max-values or growth-rates
of that function are composed. Then prove that
some automorphisms are not like the others.
No, not at all. Like Meeussen's \autname{A057117} and its
bigger brother \autname{A072088}, maybe.
(Compute the b-files for many signature-permutations
and their contractions and plot the graphs...
E.g. compare the plot of \EISseq{A082364} with that of \EISseq{A038776}.
and \EISseq{A082363} with that of \EISseq{A070041}
What do you see? Not much difference. Well, compute further...)
At least \EISseq{A072619}'s graph seems to have something like a seed for chaos...
\item Analyze program time complexity ($O(...)$ and all that) measures?
Depends on the ``fundamental substratum'' upon which the
act is done. E.g. \automorphism{A057164} is quadratic {\em (XXX - at least sometimes?)}
when implemented as acting on S-expressions, while it is always
linear when implemented directly to act on \EISseq{A014486}-codes.
\item What is the most naturally defined automorphism that acts
transitively on S-expressions of all sizes? I.e. whose cycle-count
sequence is \EISseq{A000012} (all-one sequence)?
\item Find previously unknown manifestations of Catalania by searching
through automatically generated automorphisms with modestly (e.g. linearly) growing
LCM-sequences? ({\em or involutions}.) That is, find an automorphism of a structure
before the structure itself!
\item Nice visualizations of the global behaviour? E.g. using
something like Tamari-lattice (or all binary trees arranged in
a spiral fashion, etc.), and then drawing each cycle on it
with a different colour, or at slightly different height, if a
kind of 3D-visualization is used.
Visualization which would highlight various instances
self-embeddability?
\end{itemize}
\section*{Acknowledgements}
The author thanks Wouter Meeussen for bringing
the rich field of Catalan Automorphisms to his attention.
He also thanks Mikromuseo ry. of Finland and TKSoft Oy Inc.,
the former for providing its DEC Alphastations for
his computer runs, and the latter for letting him to polish %% finish
this paper at their premises.
%% Also Nelma Moreira, Marco Alameida and Rogerio Reis from UPT, for
%% ...
\section*{References}
\begin{description}
\item[{[Bernstein and Sloane 1995]}]
M. Bernstein and N. J. A. Sloane,
Some canonical sequences of integers,
{\em Linear Algebra and Its Applications}, vol. {\bf 226--228} (1995),
57--72.
%% \bibitem{catfine} David Callan, Some bijections and identities for the Catalan and Fine numbers,
\item[{[Callan 2004a]}]
D. Callan, Some bijections and identities for the Catalan and Fine numbers,
\htmladdnormallink{S\'{e}m. Lothar. Combin.}{http://www.math.ethz.ch/EMIS/journals/SLC/index.html}
\textbf{53} (2004/06), Art. B53e, 16 pp.
%% \bibitem{twobij04} David Callan, Two bijections for Dyck path parameters,
\item[{[Callan 2004b]}]
D. Callan, Two bijections for Dyck path parameters,
\htmladdnormallink{math.CO/0406381}{http://front.math.ucdavis.edu/math.CO/0406381}, 2004, 4pp.
\item[{[Callan 2006]}]
D. Callan, A Bijection on Dyck Paths and Its Cycle Structure,
\newline
\htmladdnormallink{http://www.stat.wisc.edu/$\,\widetilde{\ }\,$callan/papers/Motzkin\_manifestation/}
{http://www.stat.wisc.edu/~callan/papers/Motzkin_manifestation/}, 2006, 17pp.
\item[{[Cameron 1989]}]
P. J. Cameron,
Some sequences of integers,
{\em Discrete Math.}, {\bf 75} (1989), 89--102.
\item[{[Cameron 2000]}]
P. J. Cameron,
Sequences realized by oligomorphic permutation groups,
{\em J. Integ. Seqs.}, Vol. {\bf 3} (2000), \#00.1.5.
\item[{[De Bruijn and Morselt 1967]}]
N.G. De Bruijn and B.J.M. Morselt,
A note on plane trees,
{\em J. Combin. Theory}, {\bf 2} (1967), 27--34.
%% \bibitem{invol1999} Emeric Deutsch, An involution on Dyck paths and its consequences.
\item[{[Deutsch 1999]}]
E. Deutsch, An involution on Dyck paths and its consequences,
\emph{Discrete Math.} \textbf{204} (1999), no. 1-3, 163--166.
%% \bibitem{bij1998} Emeric Deutsch, A bijection on Dyck paths and its consequences,
\item[{[Deutsch 1998]}] E. Deutsch, A bijection on Dyck paths and its consequences,
\emph{Discrete Math.} \textbf{179} (1998), no. 1-3, 253--256.
%% \bibitem{ordered} Emeric Deutsch, A bijection on ordered trees
\item[{[Deutsch 2000]}] E. Deutsch, A bijection on ordered trees
and its consequences, \emph{J. Combin. Theory Ser. A} \textbf{90} (2000), no. 1, 210--215.
%% \bibitem{simple2003} Emeric Deutsch and Sergi Elizalde, A simple and unusual bijection for Dyck paths and its consequences,
\item[{[Deutsch and Elizalde]}] Emeric Deutsch and Sergi Elizalde,
A simple and unusual bijection for Dyck paths and its consequences,
\emph{Ann. Comb.} \textbf{7} (2003), no. 3, 281--297.
%% \bibitem{don80} Robert Donaghey, Automorphisms on Catalan trees and bracketings. \emph{J. Combinatorial Theory Ser. B}
%% \textbf{29} (1980), no. 1, 75--90. MR0584162
\item[{[Donaghey 1980]}]
R. Donaghey,
Automorphisms on Catalan trees and bracketing,
{\em J. Combin. Theory}, Series B, {\bf 29} (1980), 75--90.
\item[{[Er 1989]}] M. C. Er, Classes of admissible permutations that are generatable by depth-first traversals of ordered trees,
\emph{The Computer Journal} \textbf{32} (1989), no. 1, 76--85.
%% Volume 32 , Issue 1 (February 1989) table of contents
%% Pages: 76 - 85
%% Year of Publication: 1989
\item[{[Gardner 197?]}] Martin Gardner, XXX
\emph{Scientific American}
\item[{[Gibbons 2005]}] Jeremy Gibbons, Metamorphisms: Streaming Representation-Changers,
\emph{Preprint submitted to Elsevier Science}
\item[{[Gibbons, Hutton and Altenkirch 2001]}] Jeremy Gibbons, Graham Hutton and Thorsten Altenkirch, When is a function a fold or an unfold?,
\emph{Electronic Notes in Theoretical Computer Science} \textbf{44} (2001), no. 1, 14pp.
\newline
\htmladdnormallink{http://www.elsevier.nl/locate/entcs/volume44.html}
{http://www.elsevier.nl/locate/entcs/volume44.html},
\item[{[Goebel 1980]}] F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers,
\emph{J. Combin. Theory}, Series B, {\bf 29} (1980), 141--143.
\item[{[Hutton 1999]}] G. Hutton, A tutorial on the university and expressiveness of fold,
\emph{J. Functional Programming}, {\bf 9} (July 1999), 355-372.
\item[{[Nikos K, 2001]}]
Nikos K., ${\mathbf \kappa}{\mathbf \rho}{\mathbf \eta}{\mathbf
\tau}{\mathbf \iota}{\mathbf \kappa}{\mathbf o}{\mathbf \varsigma}$
${\mathbf \alpha}{\mathbf \gamma}{\mathbf \rho}{\mathbf
\iota}{\mathbf o}{\mathbf \gamma}{\mathbf \alpha}{\mathbf \tau}{\mathbf o}{\mathbf \varsigma}$,
${\mathbf \tau}{\mathbf o}$ ${\mathbf \zeta}{\mathbf \omega}{\mathbf o}$
${\mathbf \phi}{\mathbf \alpha}{\mathbf \nu}{\mathbf \tau}{\mathbf \alpha}{\mathbf \sigma}{\mathbf \mu}{\mathbf \alpha}$,
\newline
\htmladdnormallink{http://stigmes.gr/gr/grpages/articles/cat.htm}{http://stigmes.gr/gr/grpages/articles/cat.htm}
%% \bibitem{acp44} Donald Knuth, \emph{Art of Computer Programming, Vol.4, Fascicle 4: Generating all Trees -- History
\item[{[Knuth fascicle 4a]}] D. Knuth, \emph{Art of Computer Programming, Vol.4, Fascicle 4: Generating all Trees -- History of Combinatorial Generation},
Addison-Wesley, 2006, vi+120pp, draft available from
\htmladdnormallink{http://www-cs-faculty.stanford.edu/$\,\widetilde{\ }\,$knuth/fasc4a.ps.gz}
{http://www-cs-faculty.stanford.edu/~knuth/fasc4a.ps.gz}
\item[{[Kreweras 1970]}] G. Kreweras, Sur les \'{e}ventails de segments,
\emph{Cahiers du Bureau Universitaire de Recherche Op\'{e}rationelle, Cahier no. 15},
Paris, 1970, pp. 3-41.
%% \bibitem{lalanne92} J.-C. Lalanne, Une involution sur les chemins de
\item[{[Lalanne 1992]}] J.-C. Lalanne, Une involution sur les chemins de
Dyck, \emph{European J. Combin.} \textbf{13} (1992), no. 6, 477--487.
%% \bibitem{lalanne93} J.-C. Lalanne, Sur une involution sur les chemins de Dyck, Conference on Formal Power Series and Algebraic
\item[{[Lalanne 1993]}] J.-C. Lalanne, Sur une involution sur les chemins de Dyck, Conference on Formal Power Series and Algebraic
Combinatorics \emph{Theoret. Comput. Sci.} \textbf{117} (1993), no. 1-2, 203--215.
\item[{[Le Borgne 2006]}]
Y. Le Borgne, An algorithm to describe bijections involving Dyck
paths, FPSAC 06,
\htmladdnormallink{http://garsia.math.yorku.ca/fpsac06/papers/46.pdf}{http://garsia.math.yorku.ca/fpsac06/papers/46.pdf},
2006, 12pp.
\item[{[Matula 1968]}] D. Matula, A natural rooted tree enumeration by prime factorization,
\emph{SIAM Rev.}, {\bf 10} (1968).
\item[{[McCarthy 1960]}]
J. McCarthy,
Recursive functions of symbolic expressions and their computation by machine, Part I,
{\em Comm. A.C.M.}, {\bf 3} (1960), 184--195.
%% {\em Communications of the ACM}, {\bf 3} (1960), 184--195. April 1960.
\item[{[Sloane 1995--]}]
N. J. A. Sloane,
{\em \htmladdnormallink{The On-Line Encyclopedia of Integer Sequences}
{http://www.research.att.com/~njas/sequences/}},
published electronically at www.research.att.com/$\sim$njas/sequences/.
\item[{[Stanley 1999]}]
R. P. Stanley,
{\em Enumerative Combinatorics},
Vol. 2, Cambridge University Press, 1999.
\item[{[Stanley 2001--]}]
R. P. Stanley,
{\em \htmladdnormallink{Catalan addendum}
{http://www-math.mit.edu/~rstan/ec/}},
\newline
published electronically at http://www-math.mit.edu/$\sim$rstan/ec/\#catadd
\item[{[Sussman and Steele 1975]}]
G. Sussman and G. Steele,
SCHEME: An Interpreter for Extended Lambda Calculus,
{\em AI Memo 349},
MIT Artificial Intelligence Laboratory,
Cambridge, Massachusetts, December 1975.
%% \bibitem{vaille97} J. Vaill\'{e}, Une bijection explicative de plusieurs
\item[{[Vaille 1997]}] J. Vaill\'{e}, Une bijection explicative de plusieurs
propri\'{e}t\'{e}s remarquables des ponts,
\emph{European J. Combin.} \textbf{18} (1997), no. 1, 117--124.
\end{description}
\end{document}