\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{enumitem}
\usepackage{pstricks, pst-node, pst-tree}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Recursive Generation of $k$-ary Trees
}
\vskip 1cm
\large
K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras\\
Department of Informatics\\
University of Piraeus\\
18534 Piraeus\\
Greece\\
\href{mailto:kmanes@unipi.gr}{\tt kmanes@unipi.gr}\\
\href{mailto:arissap@unipi.gr}{\tt arissap@unipi.gr} \\
\href{mailto:jtas@unipi.gr}{\tt jtas@unipi.gr} \\
\href{mailto:pgtsik@unipi.gr}{\tt pgtsik@unipi.gr} \\
\end{center}


\begin{abstract}
In this paper we present a construction of every $k$-ary tree using a forest of $(k-1)$-ary trees
satisfying a particular condition. We use this method recursively for the construction of the set
of $k$-ary trees from the set of $(k-1)$-Dyck paths, thus obtaining a new bijection
$\phi$ between these two sets. 
Furthermore, we introduce a new order on $[k]^*$ which is used for the full description of this bijection.
Finally, we study some new statistics on $k$-ary trees
which are transferred by $\phi$ to statistics concerning the occurrence of strings in $(k-1)$-Dyck paths.
\end{abstract}


\newtheorem{thm}{Theorem}
\newtheorem{Proposition}[thm]{Proposition}
\newtheorem{Lemma}[thm]{Lemma}
\newtheorem{Corollary}[thm]{Corollary}

%\numberwithin{equation}{section}

\newcommand{\F}{\mathcal{F}}
\newcommand{\A}{\mathcal{A}}





\section{Introduction}\label{sec:in}

The notion of $k$-ary trees has been studied extensively in the literature. 
Some authors deal with the generation of $k$-ary trees using some encoding of them as integer sequences,
which are generated in a specific order 
(see for example \cite{Er, KlF, KL, RR, XUT, Z}).
In another direction $k$-ary trees are related to other $k$-Catalan structures such as
staircase tilings, the tennis ball problem, noncrossing contractions and K-trees 
(see for example \cite{HLM, JRZ, MSS, MSV, MN}).
Finally, there are some papers dealing with the enumeration of $k$-ary trees according to some parameters
(see for example \cite{GS, S, ZJ}).


A well known procedure for the study of trees contained in a certain set $\mathcal{T}$ is to introduce a decomposition
of these trees with respect to the size and then, using this decomposition, to rebuild $\mathcal{T}$ 
from trees of smaller size.

In this paper, we use a different procedure for the construction of the set $\mathcal{T}_k$ of all $k$-ary trees.
First, we present a decomposition of each $k$-ary tree to a forest of $(k-1)$-ary trees satisfying certain
properties and we show how these trees can be reconstructed from the associated forest.
Next, by introducing an operation on forests, we present a recursive construction (in terms of $k$)
of $\mathcal{T}_k$ using unary trees, thus obtaining a new bijection from $k$-ary trees to $(k-1)$-Dyck paths.


In Section \ref{sec:pre} we give some definitions and preliminary results.

In Section \ref{sec:gen} we associate every $k$-ary tree with a forest of $(k-1)$-ary trees such that
the path with ascent sequence consisting of the sizes of the trees in this forest is a Dyck path.
Conversely, every such forest generates the tree uniquely; consequently an algorithmic construction
is given.

In Section \ref{sec:un}, the method used in the previous section is applied recursively for every $k$-ary tree,
and terminates with a forest of unary trees such that the path with ascent sequence 
consisting of the sizes of the trees in this forest is a $(k-1)$-Dyck path. 
Conversely, this forest generates the tree uniquely, so that a new bijection $\phi$ between 
$\mathcal{T}_{k}$ and the set of all $(k-1)$-Dyck paths is obtained. 

In Section \ref{sec:max} we fully describe $\phi$, by introducing a new order on the set of maximal
paths of the $k$-ary tree.

Finally, in Section \ref{sec:enu} we enumerate the set $\mathcal{T}_{k}$ according to some parameters related
to the notions of the previous sections.







\section{Preliminaries}\label{sec:pre}
A $k$-ary tree, $k \geq 1$, is either the empty tree $\square$ or a vertex (or internal node), called the \emph{root} of the tree, with $k$ ordered children which are $k$-ary trees.
We define $\mathcal{T}_{k,n}$ to be the set of all $k$-ary trees with $n$ vertices,
and $\displaystyle \mathcal{T}_{k} = \bigcup_{n \geq 0} \mathcal{T}_{k,n}$.
Thus, every $T \in \mathcal{T}_k$ can be uniquely decomposed as follows:
\begin{equation}\label{ktree_decomposition}
T = \square \quad \text{or} \quad T = T_1T_2 \cdots T_k, \quad T_i \in \mathcal{T}_k, \quad i \in [k]
\end{equation}
(see Figure \ref{fig:tree_decomposition}).

\begin{figure}[htb]
\begin{center}
\includegraphics[]{images/fig1.eps}
\caption{The $k$-ary tree $T=T_1T_2\cdots T_k$.}
\label{fig:tree_decomposition}
\end{center}
\end{figure}


An empty child of a vertex is called a \emph{leaf} (or \emph{external node}) of the tree. 
The \emph{size} of a $k$-ary tree $T$ is the number of its vertices and it is denoted by $s(T)$;
(see for example Figure \ref{fig:T}).

\begin{figure}[htb]
\begin{center}
\includegraphics[]{images/fig2.eps}
\caption{A $3$-ary tree of size 8.}
\label{fig:T}
\end{center}
\end{figure}



Clearly, every $T \in \mathcal{T}_{k,n}$ contains $kn+1$ nodes ($k$ children for each of the $n$ internal nodes plus the root of the tree)
and $(k-1)n+1$ leaves.




It is well known (see for example \cite{123}, p.589) that $|\mathcal{T}_{k,n}|$ is equal to the $n$-th $k$-Catalan number 
\[
C_n^{(k)} = \frac{1}{kn+1}\binom{kn+1}{n} = \frac{1}{(k-1)n+1}\binom{kn}{n}.
\]
We note that $C_n^{(2)}$ are the ordinary Catalan numbers $C_n$ (\cite{OEIS}, \seqnum{A000108}).

Furthermore, the generating function 
$C_k (x)= \sum_{n\geq 0}C_n^{(k)}x^n$
of the $k$-Catalan sequence satisfies the equation
\[
C_k(x) = 1 + x(C_k(x))^k,
\]
from which it can be easily shown using the Lagrange inversion formula (\cite{Deutsch}, Appendix A) that
the coefficients of $(C_k(x))^s, s \in \mathbb{N}$, are given by the formula
\[
[x^n](C_k(x))^s = \frac{s}{kn+s}\binom{kn+s}{n}.
\]  


Every non-empty $(k-1)$-ary tree can be considered as a $k$-ary tree which has all its $k$-th children empty.

%A \emph{maximal $(k-1)$-ary subtree} $M$ of a $k$-ary tree $T$ is a $(k-1)$-ary subtree such that there is no other 
%$(k-1)$-ary subtree of $T$ containing all the nodes of $M$. Obviously, two maximal subtrees of $T$ are disjoint.


A maximal $(k-1)$-ary subtree of a $k$-ary tree $T$ is any tree obtained by choosing a $k$-th child in $T$ 
(or $T$ itself) and by deleting every $k$-th child in it.
Obviously, two maximal $k-1$-ary subtrees of $T$ are disjoint;
(see for example Figure \ref{fig:T_maximal}). 





\begin{figure}[htb]
\begin{center}
\includegraphics[]{images/fig3.eps}
\caption{The $3$-ary tree of Figure \ref{fig:T} and all its binary maximal subtrees.}
\label{fig:T_maximal}
\end{center}
\end{figure}


Consequently, if $T$ has $n$ vertices, then it contains $n+1$ maximal $(k-1)$-ary subtrees.



A (totally ordered) \emph{forest} of $k$-ary trees is an element $\F$ of the cartesian product $\mathcal{T}_k^\lambda$, 
for some $\lambda \in \mathbb{N}^*$.
We denote, for simplicity, the forest which consists of a single tree $T$ by $T$.
%(We note that $\square$ is the non-empty forest which contains only the empty tree.)
The \emph{concatenation} of the forests $\F_1, \F_2, \ldots , \F_{\rho}$ is a new forest which consists of the trees
of each $\F_j$, $j \in [\rho]$, ordered by extending the orders of every $\F_j$, preserving at the same time
their natural order. 
The \emph{length} and the \emph{size} of a forest $\F=(T_1, T_2, \ldots, T_\lambda)$ are defined respectively by 
\[
|\F|= \lambda \quad \text{and} \quad s(\F) = \sum_{i=1}^{\lambda}s(T_i).
\]


%\subsection{Associated path of a forest} 
A non-empty \emph{$i$-path}, $i \in \mathbb{N}^*$, is a lattice path starting at the point $(0,0)$ and consisting of steps $u_i=(1,i)$ (rises) and $d=(1,-1)$ (falls).
The empty path $\varepsilon$ is the path with no steps.
For every $i$-path $P$ we denote by $r(P)$ (respectively $f(P)$) the number of rises (respectively falls) of $P$. 
An \emph{$i$-Dyck path} is an $i$-path that never falls below the $x$ axis and ends at the $x$ axis.
If $P$ is an $i$-Dyck path, then $f(P)=i\cdot r(P)$ and $P$ ends at the point $((i+1)r(P),0)$.
We will refer to a 1-path (respectively a 1-Dyck path) as a path (respectively a Dyck path);
in this case we write $u$ instead of $u_1$. 
The set of all $i$-Dyck paths with $n$ rises is denoted by $\mathcal{D}_n^{(i)}$
and $\displaystyle \mathcal{D}^{(i)} = \bigcup_{n \geq 0}\mathcal{D}_n^{(i)}$.
In particular, we write $\mathcal{D}$ (respectively $\mathcal{D}_n$) instead of $\mathcal{D}^{(1)}$ 
(respectively $\mathcal{D}_n^{(1)}$) for the ordinary Dyck paths.

Every non empty $i$-Dyck path $P$ is written in the following form, called the \emph{first return decomposition} (for $i=1$, see \cite{Deutsch}):
\begin{equation}\label{first return decomposition}
P = u_i Q_1dQ_2d \cdots Q_idQ_{i+1}
\end{equation}
where $Q_j \in \mathcal{D}^{(i)}$, $j \in [i+1]$.
Using this decomposition and the Lagrange inversion formula, it can be easily obtained that $i$-Dyck paths with $n$ rises
are counted by $C_n^{(i+1)}$.
A simple bijection $\theta$ between the $k$-ary trees and the $(k-1)$-Dyck paths is given as follows:
\[
\theta(\square) = \varepsilon \quad \text{and} \quad \theta(T_1T_2 \cdots T_k) = u_{k-1}\theta(T_1)d\theta(T_2)d \cdots \theta(T_{k-1})d\theta(T_k).
\]

Another well known decomposition of non-empty $i$-Dyck paths which will be used in this paper is based on the length of the first ascent, i.e., 

\begin{equation}\label{first ascent decomposition}
P = u_i^\mu d Q_1 d Q_2 d \cdots Q_{\mu i}
\end{equation}
where $Q_j \in \mathcal{D}^{(i)}$ and $j \in [\mu i]$.
  
Every $i$-path $P$ is uniquely determined by its sequence of ascents $(l_m)_{m \in [\mu]}$, $\mu \in \mathbb{N}^*$, 
according to the formula
$P = u_i^{l_1}du_i^{l_2}d \cdots u_i^{l_{\mu-1}}du_i^{l_\mu}$, where $u_i^j=u_iu_i \cdots u_i$ ($j$ times).
Clearly, if $P$ ends at the $x$ axis (as in the case of $i$-Dyck paths), then $l_\mu = 0$.
The sum of the elements of this sequence equals the number of rises in the path
and the number of its elements is one more than the number of falls;
(see for example Figure \ref{fig:ascent_sequence}).




\begin{figure}[htb]
\begin{center}
\includegraphics[]{images/fig4.eps}
\caption{The Dyck path having ascent sequence $(4,0,0,2,0,1,0,1,0)$.}
\label{fig:ascent_sequence}
\end{center}
\end{figure}

We note that the path $P = u_i^{l_1}du_i^{l_2}d \cdots u_i^{l_{\mu-1}}du_i^{l_\mu}$ is an $(i-1)$-Dyck path
if and only if the following two conditions hold:
\[
(i-1)\sum_{j=1}^{m}l_j \geq m, \, \, \,  \text{for all } m \in [\mu -1] \quad \text{and} \quad
(i-1)\sum_{j=1}^{\mu}l_j = \mu -1.
\]


For every forest $\F$ we denote by $P_i(\F)$ the $i$-path with ascent sequence the sequence of sizes of the trees in $\F$.
If $i=1$ we write $P(\F)$ instead of $P_1(\F)$.
It is evident that $r(P_i(\mathcal{F})) = s(\F)$ and $f(P_i(\mathcal{F})) = |\F|-1$.

We note that if $\F$ is the concatenation of the forests $\F_1, \F_2, \ldots, \F_{\rho}$, then
\begin{equation}\label{i-concat}
P_i(\F) = P_i(\F_1) d P_i(\F_2) d \cdots P_i(\F_{\rho-1}) d P_i(\F_{\rho}).
\end{equation} 












\section{Generation of $k$-ary trees from $(k-1)$-ary trees}\label{sec:gen}

For every non-empty $T \in \mathcal{T}_{k}$, $k \geq 2$, we denote by $\mathcal{F}(T)$ the forest consisting of all maximal 
$(k-1)$-ary subtrees of $T$, ordered according to the first time visit (in preorder) of the trees of $\mathcal{F}(T)$ in $T$
and by $T^*$ the first component of $\F(T)$; (see for example Figure \ref{fig:forest_path}). 


\begin{figure}[htb]
\begin{center}
\includegraphics[]{images/fig5.eps}
\caption{The forest $\F(T)$ and its corresponding path $P(\F(T))$ for the tree $T$ of Figure \ref{fig:T}.}
\label{fig:forest_path}
\end{center}
\end{figure}







Clearly, $T^*$ is rooted at the root of $T$ and can be obtained by deleting every
$k$-th child of $T$. If $T$ is empty then $T^*$ is empty and $\F(\square) = \square $.
It is clear that the last tree of $\F(T)$ is always the empty tree.

Using decomposition \eqref{ktree_decomposition}, we can easily check that $\F(T)$ is the concatenation
of $T^*$, $\widetilde{\mathcal{F}}(T_1)$, $\widetilde{\mathcal{F}}(T_2)$, $\ldots$, $\widetilde{\mathcal{F}}(T_{k-1})$, $\mathcal{F}(T_{k})$, where $T^* = T_1^*T_2^* \cdots T_{k-1}^*$ and 
$\widetilde{\mathcal{F}}(T_j)$, $j \in [k-1]$, is $\mathcal{F}(T_{j})$ excluding $T_j^*$. 

We have the following result.

\begin{Proposition}\label{forest}
For every $T=T_1T_2 \cdots T_k \in \mathcal{T}_{k}$ we have

\begin{enumerate}[label = \roman{*})]

\item $s(T^*) = 1 + \sum\limits_{j=1}^{k-1} s(T^*_j)$.

\item $s(\mathcal{F}(T)) = s(T)$.

\item $|\mathcal{F}(T)| = s(T) + 1$.

%\item $|\mathcal{F}(T^*)| = 1 + \sum\limits_{i=1}^{k} |F(T^*_i)| - \sum\limits_{i=1}^n [T_i \ne \square]$.

\item 
$P(\mathcal{F}(T)) =  u^{\nu}dP(\widetilde{\mathcal{F}}(T_1)) dP(\widetilde{\mathcal{F}}(T_2)) 
\cdots dP(\widetilde{\mathcal{F}}(T_{k-1})) d
P(\mathcal{F}(T_{k}))$, where $\nu = s(T^*)$.

\item $P(\mathcal{F}(T))$ is a Dyck path. 

\end{enumerate}
\end{Proposition}

\begin{proof} The proof of $(i)$ is obvious, whereas the proof of $(iv)$ follows immediately from relation
\eqref{i-concat}. The proofs of $(ii)$, $(iii)$ and $(v)$ use induction as follows:

\begin{align*}
s(\F(T)) 	& = s(T^*) + \sum\limits_{j=1}^{k-1} (s(\F(T_j)) - s(T_j^*)) + s(\F(T_{k})) \\ 
			& = s(T^*) + \sum\limits_{j=1}^{k} (s(T_j)) - \sum\limits_{j=1}^{k-1} s(T_j^*) 
			 = 1 + \sum\limits_{j=1}^{k} s(T_j) 
			 = s(T).
\end{align*}

\begin{align*}
|\F(T)| & = 1 + \sum\limits_{j=1}^{k-1} (|\F(T_j)| - 1) + |\F(T_{k})| 
        = 1 + \sum\limits_{j=1}^{k-1} s(T_j) + 1 + s(T_{k}) 
        = 1 + s(T).
\end{align*}

Finally, since each $P(\F(T_i)), i \in [k]$ is a Dyck path,
it follows that the path 
\[uP(\F(T_1)) P(\F(T_2)) \cdots P(\F(T_{k-1}))dP(\F(T_k))\] 
is also a Dyck path and hence,
using the equalities $P(\F(T_j)) = u^{s(T_j^*)}dP(\widetilde{\F}(T_j))$, $j \in [k-1]$, and $(i), (iv)$, 
we obtain that $P(\F(T))$ is a Dyck path.
\end{proof}



%\subsection{Recursive decomposition}
In the sequel we will show that $k$-ary trees can be generated by certain forests of $(k-1)$-ary trees.
For this, we will introduce a new decomposition of $k$-ary trees. 
For $T \in \mathcal{T}_{k}$,
we denote by $Z_i$ the $k$-th child in $T$ of the $i$-th (in postorder) vertex of $T^*$.
Clearly, $T$ can be uniquely recovered by attaching each $Z_i$ as the $k$-th child to the $i$-th (in postorder)
vertex of $T^{*}$.   
The trees $T^{*}, Z_1, Z_2, \ldots, Z_{\nu}$, where $\nu = s(T^*)$, form a decomposition of $T$ 
called the \emph{first component decomposition}; (see for example Figure \ref{fig:T_fcd}).





\begin{figure}[htb]
\begin{center}
\includegraphics[]{images/fig6.eps}
\caption{The first component decomposition of the tree of Figure \ref{fig:T}.}
\label{fig:T_fcd}
\end{center}
\end{figure}



\begin{Proposition}\label{T^*-decomposition}
For every $T \in \mathcal{T}_k$, the forest $\F(T)$ is the concatenation of the forests $T^*, \F(Z_1)$, $\F(Z_2), \ldots , \F(Z_{\nu})$.
\end{Proposition}
\begin{proof}
It is enough to show that if $X, Y$ are two trees in $\F(Z_i), \F(Z_j)$ respectively then
$X$ precedes $Y$ in $\F(T)$ if and only if $i<j$ or $i=j$ and $X$ precedes $Y$ in $\F(Z_i)$.

We will prove this using induction on the size of the tree $T$.


If $T = T_1 T_2 \cdots T_{k}$, then it is evident %\footnote{postorder!} 
that $Z_{\nu} = T_{k}$.

Clearly, each $Z_i$, $i \in [\nu-1]$ is a subtree of a unique $T_{\xi_i}$, $\xi_i \in [k-1]$,
such that $\xi_i \leq \xi_j$ whenever $i < j$.
Then $X, Y$ belong to $\F(T_{\xi_i})$, $\F(T_{\xi_j})$ respectively and $X \neq T^*_{\xi_i}$, $Y \neq T^*_{\xi_j}$.
We consider two cases:

\begin{enumerate}

\item  If $\xi_i \ne \xi_j$ then $X$ precedes $Y$ in $\F(T)$ if and only if $\xi_i < \xi_j$ or equivalently $i<j$.

\item If $\xi_i = \xi_j$ then $X$ precedes $Y$ in $\F(T)$ if and only if $X$ precedes $Y$ in $\F(T_{\xi_i})$
or equivalently, by the induction hypothesis $i<j$ or $i=j$ and $X$ precedes $Y$ in $\F(Z_i)$.
\end{enumerate}

Hence, in every case $X$ precedes $Y$ in $\F(T)$ if and only if $i<j$ or $i=j$ and $X$ precedes $Y$ in $\F(Z_i)$.
\end{proof}


 From Proposition \ref{T^*-decomposition} and relation \eqref{i-concat} we obtain a new, simpler expression for $P(\F(T))$, using the Dyck paths $P(\F(Z_j))$, $j \in [\nu]$.
\begin{equation}\label{Z path}
P(\mathcal{F}(T)) = 
u^{\nu} d P(\mathcal{F}(Z_1)) d P(\mathcal{F}(Z_2))\ldots d P(\mathcal{F}(Z_{\nu})), \quad \text{where }\nu=s(T^*).
\end{equation}

\begin{Proposition}\label{inverse F}
The mapping $T \rightarrow \F(T)$ is a size preserving bijection between $\mathcal{T}_{k}$ and the set of forests $\F$ %of size $n$ 
of $(k-1)$-ary trees with $P(\F) \in \mathcal{D}$.

\end{Proposition}

\begin{proof}
Given a forest $\F$ of $(k-1)$-ary trees such that $P(\F) \in \mathcal{D}$, we will show by induction that 
there exists a unique tree $T \in \mathcal{T}_{k}$
such that $\mathcal{F} = \mathcal{F}(T)$. 

Using the first ascent decomposition \eqref{first ascent decomposition}
we have $P(\mathcal{F}) = u^\nu dQ_1dQ_2 \cdots dQ_\nu$, where $\nu$ is the size of the first element $S$ of
$\mathcal{F}$ and $Q_j \in \mathcal{D}$, for all $j \in [\nu]$.
Since 
\[
\sum_{j=1}^{\nu}(r(Q_j)+1) = \sum_{j=1}^{\nu}r(Q_j) + \nu = r(P(\F)) = s(\F) = |\F|-1,
\]
it follows that there exists a sequence of forests $(\mathcal{F}_j)$, $j \in [\nu]$, 
such that $\F$ is the concatenation of $S, \F_1, \F_2, \ldots, F_{\nu}$ and $|\F_j| = r(Q_j)+1$,

It follows from relation \eqref{i-concat}
that $P(\F_j) = Q_j$ and hence it is a Dyck path, for every $j \in [\nu]$. 
Thus, by the induction hypothesis, there exists $Z_j \in \mathcal{T}_{k}$, $j \in [\nu]$, 
such that $\mathcal{F}_j = \mathcal{F}(Z_j)$.
Then $T$ is the tree constructed by attaching $Z_j$ to the $j$-th (in postorder) vertex of $S$
as its $k$-th child; from Proposition \ref{T^*-decomposition} it follows immediately that $\mathcal{F} = \mathcal{F}(T)$.

For the proof of the uniqueness, let $\F(X)=\F(T)$; then $T^* = X^*$.
If $T^*,Z_1, Z_2, \ldots , Z_{\nu}$ and $T^*,Y_1, Y_2, \ldots , Y_{\nu}$
are the first component decompositions of $T$ and $X$ respectively, then since $P(\F(T)) = P(\F(X))$,
by relation \eqref{Z path} it follows that $P(\F(Z_i)) = P(\F(Y_i))$, for every $i \in [\nu]$.
Furthermore, since $|\F(Z_i)| = f(P(\F(Z_i)))+1 = f(P(\F(Y_i)))+1 = |\F(Y_i)|$
for every $i \in [\nu]$, by Proposition \ref{T^*-decomposition}
we obtain that $\F(Z_i) = \F(Y_i)$, for every $i \in [\nu]$.
Thus, by the induction hypothesis, $Z_i = Y_i$ for each $i \in [\nu]$, so that $T = X$.
\end{proof}



We close this section with the following algorithmic construction of the tree $T \in \mathcal{T}_k$
such that $\F(T) = \F$, where $\F$ is a given forest of $(k-1)$-ary trees with $P(\F)\in \mathcal{D}$:

We start with the first tree of $\F$. 
At each step, we add as the $k$-th child of the first (in postorder) vertex which does not have
a $k$-th child, the first tree of $\F$ that has not already been used.
%\begin{enumerate}
%\item we traverse $T$ in postorder,
%\item before leaving for the last time a vertex which has not yet a $k$-th child, we add the first tree 
%of $\F(T)$ that we haven't aldready used, as the $k$-th child of that vertex and we continue the traversal.
%\end{enumerate}
For example, the tree $T$ of Figure \ref{fig:T} can be constructed from the forest of Figure \ref{fig:forest_path}
as shown in Figure \ref{fig:F2T}.



\begin{figure}[htb]
\begin{center}
\includegraphics[]{images/fig7.eps}
\caption{Construction of $T$ from $\F$.}
\label{fig:F2T}
\end{center}
\end{figure}










\section{Generation of $k$-ary trees from unary trees}\label{sec:un}
In this section we show how every $k$-ary tree can be uniquely decomposed into a forest of unary trees
which leads to a new bijection between the sets $\mathcal{T}_k$ and $\mathcal{D}^{(k-1)}$.
For this, we first introduce a mapping on forests denoted by $( \enspace )^{\prime}$.

For every forest $\F = (T_1, T_2, \ldots , T_{\lambda})$ of $k$-ary trees,
we define the forest $\F^{\prime}$ of $(k-1)$-ary trees to be the concatenation of the forests
$\mathcal{F}(T_1), \mathcal{F}(T_2), \ldots , \mathcal{F}(T_{\lambda})$.
Using Proposition \ref{forest} $(ii), (iii)$, we deduce the following equalities:
\begin{equation}\label{size}
s(\F^{\prime}) = s(\F) \qquad \text{and} \qquad |\F^{\prime}| = s(\F) + |\F|.
\end{equation}
Furthermore, it can be easily checked that if $\F$ is the concatenation of the forests 
$\F_1, \F_2, \ldots , \F_{\rho}$,
then $\F^{\prime}$ is the concatenation of the forests $\F_1^{\prime}, \F_2^{\prime}, \ldots , \F_{\rho}^{\prime}$.

The following two results establish additional properties of $( \enspace )^{\prime}$.




\begin{Proposition}\label{1-1}
For any pair of forests $\F, \mathcal{G}$, we have that if $\F^{\prime} = \mathcal{G}^{\prime}$ then $\F = \mathcal{G}$.
\end{Proposition}
\begin{proof}
Since $|\F| = |\F^{\prime}| - s(\F^{\prime}) = |\mathcal{G}^{\prime}| - s(\mathcal{G}^{\prime}) = |\mathcal{G}|$, we can write
\[\F = (T_1, T_2, \ldots , T_{\lambda}) \quad \text{and} \quad \mathcal{G} = (X_1, X_2, \ldots , X_{\lambda}).\]

We assume that $\F \neq \mathcal{G}$ and we choose $\rho$ to be the least element of $[\lambda]$ such that 
$T_{\rho} \neq X_{\rho}$. 
Since $\F^{\prime} = \mathcal{G}^{\prime}$ and $\F(T_{\rho}) \neq \F(X_{\rho})$, it follows that $|\F(T_{\rho})| \neq |\F(X_{\rho})|$;
without loss of generality we assume that $|\F(T_{\rho})| < |\F(X_{\rho})|$. Then, there exists
a forest $\mathcal{H}$ such that $\F(X_{\rho})$ is the concatenation of $\F(T_{\rho})$ and $\mathcal{H}$.
It follows that $P(\F(X_{\rho})) = P(\F(T_{\rho})) d P(\mathcal{H})$ which is not a Dyck path, giving the required contradiction.
\end{proof}








\begin{Proposition}\label{step}
For every forest $\F$, we have that  $P_{i-1}(\F) \in \mathcal{D}^{(i-1)}$
if and only if $P_{i}(\F^{\prime}) \in \mathcal{D}^{(i)}$.
\end{Proposition}
\begin{proof}
Let $\F = (T_1, T_2, \ldots, T_{\lambda})$; then
\[
P_{i-1}(\F) = u_{i-1}^{s(T_1)} d u_{i-1}^{s(T_2)} d \cdots u_{i-1}^{s(T_{\lambda -1})} d u_{i-1}^{s(T_{\lambda})}
\]
and by relation \eqref{i-concat}
\[
P_{i}(\F^{\prime}) = P_{i}(\F(T_1)) d P_{i}(\F(T_2)) d \cdots P_{i}(\F(T_{\lambda - 1})) d P_{i}(\F(T_{\lambda})).
\]

Clearly, since for every $j \in [\lambda]$ the path $P(\F(T_j))$ is a Dyck path, the path $P_i(\F(T_j))$ 
lies above the $x$ axis and ends at height $(i-1)s(T_j)$.
Furthermore, the fall following $P_i(\F(T_j))$ in the path $P_i(\F^{\prime})$ is at the same height as the fall following the
ascent $u_{i-1}^{s(T_j)}$ in the path $P_{i-1}(\F)$, for all $j \in [\lambda - 1]$,
giving the required result.
\end{proof}



We now have the following result.


\begin{Proposition}\label{inverse i}
For every forest of $(k-1)$-ary trees $\F$ such that $P_i(\F) \in \mathcal{D}^{(i)}$, there exists a unique forest $\mathcal{G}$
of $k$-ary trees such that $\mathcal{G}^{\prime} = \F$ and $|\mathcal{G}| = 1 + (i-1)s(\F)$.
\end{Proposition}
\begin{proof}
Clearly, if $\F = \square$, the result holds for $\mathcal{G} = \square$, while
, if $i=1$ the result follows from Proposition \ref{inverse F}.
Otherwise, since $P_i(\F) \in \mathcal{D}^{(i)}$, the path $P(\F)$ starts at the origin with a rise and ends at a point below 
the $x$-axis attaining the least possible height; so, there exists a sequence $(Q_j)_{j \in [\lambda]}$ of Dyck paths, such that 
\[P(\F) = Q_1dQ_2d \cdots Q_{\lambda -1}d Q_{\lambda}\]
and $Q_1 \neq \varepsilon$. 
Then, since 
\[|\F| = 1 + f(P(\F)) = 1 + \lambda -1 + \sum_{j=1}^{\lambda}f(Q_j) = \sum_{j=1}^{\lambda}(r(Q_j)+1), \]
there exists a unique sequence $(\F_j)_{j \in [\lambda]}$ of forests of $(k-1)$-ary trees such that $|\F_j| = r(Q_j)+1$, for all $j \in [\lambda]$
and $\F$ is the concatenation of the forests $\F_1, \F_2, \ldots , \F_{\lambda}$. Then, by relation \eqref{i-concat}, it follows that
\[ P( \F ) = P(\F_1)d P(\F_2)d \cdots P(\F_{\lambda -1})d P(\F_{\lambda}).\]

Since for all $j \in [\lambda]$ we have that $f(P(\F_j)) = |\F_j| - 1 = f(Q_j)$, from the above two expressions of $P(\F)$ it follows that $P(\F_j) = Q_j$.
Thus, $P(\F_j)$ is a Dyck path and by Proposition \ref{inverse F} there exists a unique $T_j \in \mathcal{T}_k$ such that $\F_j = \F(T_j)$.
Then, for $\mathcal{G} = (T_1, T_2, \ldots , T_{\lambda})$, we obtain $\mathcal{G}^{\prime} = \F$.

Now, since $P_i(\F) \in \mathcal{D}^{(i)}$ and $Q_j \in \mathcal{D}$ for each $j \in [\lambda]$, we have that
\[
ir(P_i(\F)) = f(P_i(\F)) = f(P(\F)) = \lambda - 1 + \sum_{j=1}^{\lambda}f(Q_j) =
\lambda - 1 + \sum_{j=1}^{\lambda}r(Q_j) = \lambda - 1 + r(P(\F)).
\]

Furthermore, since $r(P_i(\F)) = r(P(\F)) = s(\F)$ and $|\mathcal{G}| = \lambda$,
it follows that $|\mathcal{G}| = 1 + (i-1)s(\F)$.

The uniqueness of $\mathcal{G}$ follows from Proposition \ref{1-1}.
\end{proof}


The next result follows directly from Propositions \ref{step} and \ref{inverse i}.
\begin{Proposition}\label{bijection prime}
The mapping $( \enspace )^\prime$ from the set of forests of $(k-i+1)$-ary trees with $P_{i-1}(\F) \in \mathcal{D}^{(i-1)}$ to the set of forests of $(k-i)$-ary trees with 
$P_i(\F) \in \mathcal{D}^{(i)}$ where $i \geq 2$, is a bijection.
\end{Proposition}


Using the mapping $( \enspace )^\prime$, for every $T \in \mathcal{T}_k$ and $i \in [k-1]$, 
we define recursively the forest $\F^{i}(T)$ by the relations
\[
\F^{0}(T) = T \qquad \text{and} \qquad \F^{i}(T) = (\F^{i-1}(T))^{\prime}.
\]
For example, for the tree $T$ of Figure \ref{fig:T} for which $\F(T)$ has been already constructed (see Figure \ref{fig:forest_path}),
we can easily obtain that $\F^2(T)$ is the forest of Figure \ref{fig:F2}.


\begin{figure}[htb]
\begin{center}
\includegraphics[]{images/fig8.eps}
\caption{The forest $\F^2(T)$.}
\label{fig:F2}
\end{center}
\end{figure}




Clearly, the forest $\mathcal{F}^i(T)$ consists of $(k-i)$-ary trees.
Furthermore, from \eqref{size} we obtain inductively the following generalization of equalities $(ii), (iii)$ of Proposition \ref{forest}:
\[
s(\F^i(T))=s(T) \qquad \text{and} \qquad |\F^i(T)|=is(T)+1.
\]


In particular, the second equality for $i=k-1$ shows that we have a 1-1 correspondence between 
the leaves of the tree $T$  and the unary trees of $\F^{k-1}(T)$.


Using Propositions \ref{step} and \ref{inverse i} we can easily show by induction that
$P_i(\F^i(T)) \in \mathcal{D}^{(i)}$, for every $i \in [k-1]$.
Furthermore, using Proposition \ref{bijection prime} we deduce by induction the following result which is a generalization
of Proposition \ref{inverse F}.


\begin{Proposition}\label{bijection i}
For every $i \in [k-1]$, the mapping $T \rightarrow \F^i(T)$ is a size preserving bijection between $\mathcal{T}_k$
and the set of forests $\F$ of $(k-i)$-ary trees with $P_i(\F) \in \mathcal{D}^{(i)}$.
\end{Proposition}



An application of the previous result for $i=k-1$ gives that the mapping 
$\mathcal{T} \rightarrow \F^{k-1}(\mathcal{T})$
is a size preserving bijection between $\mathcal{T}_k$ and the set of forests $\F$ of unary trees with 
$P_{k-1}(\F) \in \mathcal{D}^{(k-1)}$.
Clearly, since any such forest $\F$ can be identified with the associated path $P_{k-1}(\F)$, we obtain the following result.

\begin{Proposition}
The mapping $\phi : \mathcal{T}_k \rightarrow \mathcal{D}^{(k-1)}$ with
$\phi(T) = P_{k-1}(\F^{k-1}(T))$ is a bijection such that $s(T) = r(\phi(T))$.
\end{Proposition}


Notice that the classical bijection $\theta$ mentioned in Section \ref{sec:pre} is different from the bijection
$\phi$ of the previous Proposition. For example, for the tree $T$ of Figure \ref{fig:T} we have
\[
\theta (T) = u_2 u_2 d u_2 d d d d u_2 d d u_2 u_2 d d d d u_2 d d d u_2 d d, 
\]
whereas
\[
\phi (T) = u_2 u_2 d u_2 d d u_2 d d d d u_2 u_2 d d d d u_2 d d d u_2 d d.
\]

Both bijections use recursion, $\theta$ with respect to the size, whereas $\phi$ with respect to $k$.










\section{Maximal paths of $k$-ary trees}\label{sec:max}

In this section we show that every $k$-ary tree can be uniquely expressed by the set of its maximal paths.
Furthermore, using this expression, we give an equivalent simple formula for the bijection $\phi$.

Let $\mathcal{A}_k$ be the set of all subsets $A$ of $[k]^*$ 
(the set of all words on the alphabet $[k]$) satisfying the following two conditions:

\begin{enumerate}[label = \roman{*})]
\item
If $x=\rho \alpha \in A$, where $\rho,\alpha \in [k]^*$ and $\alpha \neq \varepsilon$,
then, for all $i \in [k]$, the set $A$ contains at least one word of the form 
$\rho i \gamma_i$, where $\gamma_i \in [k]^*$.

\item
If $\rho \in A$ and $\alpha \in [k]^*$, then $\rho \alpha \in A$ if and only if $\alpha = \varepsilon$.
\end{enumerate}


 From the above two conditions, it follows easily that $\{ \varepsilon \} \in \mathcal{A}_k$
and $\varepsilon \notin A$ for all $A \in \mathcal{A}_k$ with $A \neq \{ \varepsilon \}$.

We define recursively the mapping
$\psi : \mathcal{T}_k \rightarrow \mathcal{A}_k$ by
\[
\psi(\square) = \{ \varepsilon \} \qquad \text{and} \qquad
\psi(T_1 T_2 \cdots T_k) = \{ i \alpha : \alpha \in \psi(T_i), i \in [k] \}.
\]

For example, for the tree $T$ of Figure \ref{fig:T} we have
\[
\psi(T) = \{ 11, 121, 122, 123, 13, 21, 22, 2311, 2312, 2313, 232, 2331, 2332, 2333, 31, 32, 33 \}.
\]

It is easy to check that $\psi$ is a bijection, such that 
$|\psi(T)| = (k-1)s(T) + 1$, for all $T \in \mathcal{T}_k$.  
Furthermore, the elements of $\psi(T)$ code the maximal paths of $T$.
In fact, the maximal path $S=v_1v_2 \cdots v_{\ell+1}$ of $T$
or, equivalently, its associated leaf $v_{\ell+1}$,
is coded by the word
$\alpha = a_1a_2\cdots a_{\ell} \in \psi(T)$ if and only if $v_{i+1}$ is the $a_i$-th child of $v_i$,
for all $i \in [\ell]$.


Additionally, since $|\F^{k-1}(T)|= |\psi(T)|$, there exists a 1-1 correspondence between the 
sequences of $\psi(T)$ and the trees of $\F^{k-1}(T)$ such that every $x \in \psi(T)$
corresponds to a unique unary tree $T_x$ of $\F^{k-1}(T)$, which is the left path of the leaf 
which is coded by $x$.
For example, the word $x=2311$ of $\psi(T)$ in the tree $T$ of Figure \ref{fig:T} corresponds to the 8-th
element of the forest $\F^2(T)$ of Figure \ref{fig:F2}.

Using the above expression of $k$-ary trees, we will give a method for the construction
of a $(k-1)$-Dyck path from a set $A \in \mathcal{A}_k$ endowed with a total order.
Firstly, for each $x \in [k]^*$, we set $l(x)$ to be the number of trailing 1's of $x$.
Clearly, $l(x) = s(T_x)$, for every $x \in \psi(T)$.



\begin{Proposition}\label{order conditions}
Let $\preceq$ be a partial order on $[k]^*$ satisfying the following conditions:
\begin{enumerate}
\item the restriction of $\preceq$ on $A$ is a total order and 
$\min A$ is the element of $A$ which contains only 1's,

\item $i\alpha \preceq i\beta$ if and only if $\alpha \preceq \beta$, for all $\alpha,\beta \in A$ and $i \in [k]$,
\end{enumerate}
for each $A \in \mathcal{A}_k$. 
Then we have that
\[
u_{k-1}^{l(\alpha_1)}d u_{k-1}^{l(\alpha_2)}d \cdots 
u_{k-1}^{l(\alpha_{\mu-1})}d u_{k-1}^{l(\alpha_{\mu})} \in \mathcal{D}^{(k-1)},
\]
for all $A \in \mathcal{A}_k$, where
$A = \{ \alpha_1, \alpha_2 , \ldots, \alpha_{\mu}\}$ and 
$\alpha_1 \preceq \alpha_2 \preceq \cdots \preceq \alpha_{\mu}$.
\end{Proposition}

\begin{proof}
In order to prove that the above path is a $(k-1)$-Dyck path,
it suffices to prove that
\[
(k-1)\sum_{\substack{x \in A \\ x \preceq y}} l(x) \geq | \{x \in A: x \preceq y\} |,
\qquad \text{and} \qquad 
(k-1) \sum_{x \in A} l(x) = |A| - 1,
\]
where $y \in A \setminus \{ \alpha_{\mu} \}$.
We will use induction with respect to the cardinality of $A \in \mathcal{A}_k$.

For $A = \{ \varepsilon \}$, the result is true. 
For $A \neq \{ \varepsilon\}$ we will prove only the inequality, since the equality can be proved analogously.

We define $A_i = \{ \alpha \in [k]^*: i\alpha \in A \}$, for each $i \in [k]$. It is easy to check that
$A_i \in \mathcal{A}_k$, for every $i \in [k]$.
Furthermore, we define $I = \{i \in [k]: i\alpha \preceq y \text{ for some } \alpha \in A_i \}$.
Obviously, $1 \in I$. For each $i \in I$, we denote by $\alpha_i$ the maximum element of
$A_i$ with $i\alpha_i \preceq y$. Then, we have

\begin{align*}
(k-1)\sum_{\substack{x \in A \\ x \preceq y}} l(x) 
& = (k-1)\sum_{i \in I} \sum_{\substack{\alpha \in A_i \\ i\alpha \preceq y}} l(i\alpha) 
  = (k-1)\sum_{i \in I} \sum_{\substack{\alpha \in A_i \\ \alpha \preceq \alpha_i}} l(i\alpha) \\
& = (k-1)\sum_{i \in I \setminus \{1\} } \sum_{\substack{\alpha \in A_i \\ \alpha \preceq \alpha_i}} l(\alpha) 
  + (k-1)(1 + \sum_{\substack{\alpha \in A_1 \\ \alpha \preceq \alpha_1}} l(\alpha) ) \\
&  = \sum_{i \in I }(k-1) \sum_{\substack{\alpha \in A_i \\ \alpha \preceq \alpha_i}} l(\alpha) +  (k-1) \\
& \geq \sum_{i \in I \setminus \{k\}}(|\{ \alpha \in A_i : \alpha \preceq \alpha_i\}|-1) + 
		\sum_{i \in I \cap \{k\}} |\{ \alpha \in A_i : \alpha \preceq \alpha_i\}| + (k-1) \\
& = \sum_{i \in I} |\{ \alpha \in A_i : \alpha \preceq \alpha_i\}| - |I \setminus \{k\}| + k-1 
		\geq |\{ x \in A : x \preceq y\}|.	
\end{align*}
\end{proof}




 From the previous proposition, it follows that given a partial order ``$\preceq$'' on $[k]^*$
satisfying conditions 1, 2, we have that
\[
(k-1)\sum_{j=1}^m l(\alpha_j) \geq m, \quad \text{for every } m \in [\mu-1] \qquad \text{and} \qquad
(k-1)\sum_{j=1}^\mu l(\alpha_j) = \mu -1,
\]
for every set $A = \{ \alpha_1, \alpha_2, \ldots, \alpha_{\mu} \} \in \mathcal{A}_k$ 
with $\alpha_t \preceq \alpha_s$ if and only if $t \leq s$.
Thus, the mapping $\chi$ on $\mathcal{A}_k$ defined by
\[
\chi(\{ \varepsilon \}) = \varepsilon, \qquad 
\chi(A) = u_{k-1}^{l(\alpha_1)}d u_{k-1}^{l(\alpha_2)}d \cdots u_{k-1}^{l(\alpha_{\mu-1})}d
\]
takes values in $\mathcal{D}^{(k-1)}$.

Clearly, this mapping depends on the choice of the partial order ``$\preceq$''. 
If ``$\preceq$'' is the lexicographic order on $[k]^*$
(which obviously satisfies the conditions of Proposition \ref{order conditions}), then
the resulting mapping $\chi$ may be used in order to give an explicit formula of the bijection $\theta$.






In order to describe the bijection $\phi$ using the above equivalent expression
of $k$-ary trees, we need an ordering for the elements of each $A \in \mathcal{A}_k$.
Thus we define a partial order on $[k]^*$, denoted by ``$\preceq$'', as follows:
If $x=\rho \alpha$ and $y=\rho \beta$, where $\rho$ is the maximal common initial part 
(possibly empty) of $x$ and $y$, then

\[
x \preceq y \Leftrightarrow 
\begin{cases} 
\alpha = \beta = \varepsilon, \text{ or} \\
\max \alpha < \max \beta, \text{ or} \\
\max \alpha = \max \beta \quad \text{and first element of $\alpha$ $<$ first element of $\beta$.}
\end{cases}
\]

Clearly, from condition ii) in the definition of $\mathcal{A}_k$, it follows that
``$\preceq$'' is a total order on each $A \in \mathcal{A}_k$.



For example, the elements of $\psi(T)$ for the tree $T$ of Figure \ref{fig:T} are ordered as follows:
\begin{align*}
11 & \preceq 121 \preceq 122 \preceq 21 \preceq 22 \preceq 123 \preceq 13 \preceq 2311 \\
& \preceq 2312 \preceq 232 \preceq 2313 \preceq 2331 \preceq 2332 \preceq 2333 \preceq 31 \preceq 32 \preceq 33.
\end{align*}

So, for the set $A = \psi(T)$, we have the following 2-Dyck path:
\[
\chi(A) = u_2^2 d u_2 d d u_2 dddd u_2^2 ddddu_2 ddd u_2 dd.
\]


\begin{Proposition}\label{mfl dyck}
For every $k \in \mathbb{N}^*$ and $T \in \mathcal{T}_k$, we have that
\[ \chi(\psi(T)) = \phi(T).\]
\end{Proposition}
\begin{proof}
Using the first component decomposition $T^*, Z_1, \ldots, Z_{\nu}$, where $\nu = s(T^*)$,
of a tree $T \in \mathcal{T}_k$, it follows inductively using Proposition \ref{T^*-decomposition} that
$\F^{k-1}(T)$ is the concatenation of the forests
$\F^{k-2}(T^*), \F^{k-1}(Z_1), \ldots, \F^{k-1}(Z_\nu)$.
We will show by induction with respect to $k$ and to the size of the tree, that
if $x,y \in \psi(T)$ and $T_x, T_y$ are their associated trees in $\F^{k-1}(T)$, then
$T_x$ precedes $T_y$ in $\F^{k-1}(T)$ if and only if $x \preceq y$.

We consider the following cases:
\begin{enumerate}%[(i)]%[label=\roman{*})]
\item 
$T_x, T_y$ are in $\F^{k-2}(T^*)$. 
Then $x,y \in \psi(T^*)$ and hence, using the induction hypothesis 
(with respect to $k$), we deduce that $x \preceq y$.

\item 
$T_x$ is in $\F^{k-2}(T^*)$ and $T_y$ is in $\F^{k-1}(Z_i)$, for some $i \in [\nu]$. 
Then $x \prec y$, since $\max x < k = \max y$.

\item 
$T_x, T_y$ are in $\F^{k-1}(Z_i)$, for some $i \in [\nu]$. 
Then $x = \rho k \alpha$ and $y = \rho k \beta$, where $\rho \in [k-1]^*$ and $\alpha, \beta \in [k]^*$.
It follows that $\alpha, \beta \in \psi(Z_i)$ and hence, using the induction hypothesis 
(with respect to the size of the tree), we deduce that $\alpha \preceq \beta$ and therefore $x \preceq y$.

\item 
$T_x$ is in $\F^{k-1}(Z_i)$ and $T_y$ is in $\F^{k-1}(Z_j)$, where $i,j \in [\nu]$ and $i \neq j$.
Then $i<j$, so that the parent of $Z_i$ precedes the parent of $Z_j$ (in postorder).
Thus, $x = \rho \alpha$ and $y = \rho \beta$, $\rho \in [k-1]^*$
(where $\rho$ is the initial common part of $x$ and $y$) and $\alpha, \beta \in [k]^*$.
It follows that $\max \alpha = \max \beta = k$ and first element of $\alpha$ $<$ first element of $\beta$,
and hence $x \preceq y$.
\end{enumerate}

This shows that in all cases, $x \preceq y$. 

The converse now follows obviously, since $\F^{k-1}(T)$ is totally ordered.

Finally, since $l(x) = s(T_x)$, for every $x \in \psi(T)$, the $(k-1)$-paths
$\chi(\psi(T))$ and $\phi(T)$ have the same ascent sequence and therefore they are identical. 
\end{proof}














\section{Enumerations}\label{sec:enu}

In this section, we study some statistics on $k$-ary trees related to the notions studied in the previous sections.

\subsection{Enumeration of $\mathcal{T}_k$ according to the number of non-empty trees of $\F^i(T)$}\label{sec:enu1}

Given $i,k \in \mathbb{N}^*$ with $i \leq k-1$ and $T \in \mathcal{T}_k$, we denote by 
$p_{i,k}(T)$ the number of non-empty trees of $\F^i(T)$ and by $F_{i,k}$ the generating function
\[
F_{i,k}(x,y) = \sum_{T \in \mathcal{T}_k} x^{s(T)}y^{p_{i,k}(T)}.
\]

It follows that
\[ 
p_{i,k}(\square)=0 \qquad \text{and} \qquad
p_{i,k}(T_1T_2 \cdots T_k) = 1 + \sum_{j=1}^{k}p_{i,k}(T_j) - \sum_{j=1}^{k-i}[T_j \neq \square],
\]
where $[P]$ is the well known Iverson notation defined by 
$[P] = \begin{cases} 1, & \text{ if $P$ is true;} \\ 0, & \text{ if $P$ is false.} \end{cases}$

The above equality can be proved by induction (with respect to $k$).
Indeed, since the forest $\F(T)$ is the concatenation of 
$T^*, \widetilde{\F}(T_1), \widetilde{\F}(T_2), \ldots, \widetilde{\F}(T_{k-1}),\F(T_k)$, where 
$T^* = T_1^*T_2^* \cdots T_{k-1}^*$,
we can easily check that the forest $\F^i(T)$ is the concatenation of 
\[
\F^{i-1}(T^*), \widetilde{\F^i}(T_1), \widetilde{\F^i}(T_2), \ldots, \widetilde{\F^i}(T_{k-1}), {\F^i}(T_k).
\]
Furthermore, using the induction hypothesis for the tree $T^* \in \mathcal{T}_{k-1}$, we obtain that

\begin{align*}
p_{i,k}(T) & = p_{i-1,k-1}(T^*) + \sum_{j=1}^{k-1} (p_{i,k}(T_j) - p_{i-1,k-1}(T_j^*)) + p_{i,k}(T_k) \\
& = 1 + \sum_{j=1}^{k-1}p_{i-1,k-1}(T_j^*) - \sum_{j=1}^{k-1-(i-1)}[T_j^* \neq \square] +
	\sum_{j=1}^{k-1}p_{i,k}(T_j) - \sum_{j=1}^{k-1}p_{i-1,k-1}(T_j^*) + p_{i,k}(T_k) \\
& = 1 + \sum_{j=1}^{k}p_{i,k}(T_j) - \sum_{j=1}^{k-i}[T_j \neq \square].
\end{align*}

 From the above relation, it follows that the generating function $F_{i,k}(x,y)$ satisfies the following equation:
\[
F_{i,k}(x,y) = 1 + xy(F_{i,k}(x,y))^i(1+ \frac{1}{y}(F_{i,k}(x,y)-1))^{k-i}.
\]



%By letting $H = H(x,y) = 1+\frac{1}{y}(F_{i,k}-1)$, we have that
%\[H = 1 + x \left(y(H-1)+1 \right)^iH^{k-i}.\]

%Let $P(\lambda) = \left(y(\lambda -1)+1\right)^i\lambda^{k-i}$; then 
%$H = 1+x(P(H))$ and by the Lagrange Inversion Formula we have that
%\[
%[x^n]H = \frac{1}{n}[\lambda^{n-1}](P(\lambda+1))^n, \qquad n \in \mathbb{N}^*.
%\]

%Since, 
%\begin{align*}
%(P(\lambda+1))^n & = (y\lambda + 1)^{ni} (\lambda + 1)^{(k-i)n} 
%= \Big{(} \sum_{\mu=0}^{ni} \binom{ni}{\mu}y^\mu \lambda^\mu \Big{)} 
%	\Big{(} \sum_{\nu=0}^{(k-i)n} \binom{(k-i)n}{\nu}\lambda^\nu \Big{)} \\
%&=\sum_{\xi = 0}^{nk}\sum_{\mu = 0}^{\min{ \lbrace \xi, ni \rbrace }}\binom{ni}{\mu}\binom{(k-i)n}{\xi - \mu}
%y^\mu \lambda^\xi,	
%\end{align*}
%for $\xi = n-1$ we obtain that  
%\[
%[x^n]H = \frac{1}{n}\sum_{\mu=0}^{n-1}\binom{ni}{\mu}\binom{(k-i)n}{n-\mu-1}y^\mu, 
%\]
%and hence
%\[ 
%H(x,y) = 1 + \sum_{n = 1}^{\infty} \frac{1}{n}\sum_{\mu=0}^{n-1}\binom{ni}{\mu}\binom{(k-i)n}{n-\mu-1}y^\mu x^n
%\]  
%and 
%\[ 
%F_{i,k}(x,y) = 1 + \sum_{n = 1}^{\infty} \frac{1}{n}\sum_{\mu=0}^{n-1}\binom{ni}{\mu}\binom{(k-i)n}{n-\mu-1}
%y^{\mu+1} x^n =	1 + \sum_{n = 1}^{\infty} \frac{1}{n}\sum_{j=1}^{n}\binom{ni}{j-1}\binom{(k-i)n}{n-j}y^{j} x^n.
%\]  

 Using the Lagrange inversion formula, we obtain the following result.

\begin{Proposition}\label{Enum1}
The number of all $k$-ary trees of size $n$ for which the forest $\F^i(T), i \in [k-1]$,
contains exactly $j$ non-empty trees is equal to 
\[ [x^n y^j]F_{i,k} = \frac{1}{n}\binom{ni}{j-1}\binom{(k-i)n}{n-j}. \]
\end{Proposition}


The above result is of special interest for the cases $i=k-1$ and $i=1$.
In particular, using the bijection $\varphi$, we can easily check that 
$p_{k-1,k}(T) = N_{ud}(\phi(T))$, where $N_{ud}(\phi(T))$ denotes the number of $ud$'s (peaks) in $\phi(T)$;
thus the above two parameters are equidistributed, which implies that
the number of $(k-1)$-Dyck paths having $n$ rises and $j$ peaks is equal to
$\frac{1}{n}\binom{(k-1)n}{j-1}\binom{n}{j}$. 

We note that since the number $p_{k-1,k}(T)-1$, which counts the non-empty trees in $\F^{k-1}(T)$
other than the first one, is equal to $N_{du}(\phi(T))$ we can easily deduce that the number of 
$(k-1)$-Dyck paths with $n$ rises and $j$ valleys is equal to 
$\frac{1}{n} \binom{(k-1)n}{j} \binom{n}{j+1}$.


Furthermore, since $|\F^{k-1}(T)|= (k-1)s(T)+1$, we obtain that the number of empty trees
in $\F^{k-1}(T)$ other than the last one (which is always empty) is equal to
$(k-1)s(T) - p_{k-1,k}(T)$. Since we can easily check that this number is equal to $N_{dd}(\phi(T))$,
we deduce that the number of $(k-1)$-Dyck paths having $n$ rises and $j$ doublefalls is equal to
$\frac{1}{n} \binom{(k-1)n}{j+1} \binom{n}{(k-1)n-j}$.


On the other hand, using a variation $\theta^\prime$ of $\theta$ defined by
\[
\theta^\prime(\square) = \varepsilon \qquad \text{and} \qquad 
\theta^\prime(T_1T_2 \cdots T_k) = u \theta^\prime(T_k)d \theta^\prime(T_{k-1})  \cdots
d \theta^\prime(T_2) d \theta^\prime(T_1),
\]
we can easily check by induction that
$N_{uu}(\theta^\prime(T)) = p_{1,k}(T) - [T \neq \square]$, for every $T \in \mathcal{T}_k$.
 From this equality, it follows easily that the number of all
$(k-1)$-Dyck paths having $n$ rises and $j$ doublerises is equal to
$\frac{1}{n}\binom{n}{j}\binom{(k-1)n}{n-j-1}$.


S. Heubach et al. \cite{HLM} give analogous results on similar generalized Dyck paths.














\subsection{Enumeration according to the size of the first element of $\F^i(T)$}\label{sec:enu2}
For every $T \in \mathcal{T}_k$ we denote by $q_{i,k}(T), i \in [k-1]$,
the size of the first element of $\F^i(T)$ and $G_{i,k}(x,y)$ the generating function
\[
G_{i,k}(x,y) = \sum_{T \in \mathcal{T}_{k}} x^{s(T)}y^{q_{i,k}(T)}.
\]
It follows that 
\[
q_{i,k}(\square)=0 \qquad \text{and} \qquad q_{i,k}(T_1T_2 \cdots T_k) = 1+ \sum_{j=1}^{k-i} q_{i,k}(T_j).
\]
The above equality can be proved easily by induction (with respect to $k$), using the equality
$q_{i,k}(T) = q_{i-1,k-1}(T^*)$.

 From the above relation, it follows that the generating function $G_{i,k}(x,y)$ satisfies the following equation:
\[ G_{i,k}(x,y) = 1 + xy (G_{i,k}(x,1))^i (G_{i,k}(x,y))^{k-i} = 1 + xy (C_{k}(x))^i (G_{i,k}(x,y))^{k-i}. \] 


%Let $Q(\lambda) = x(C_{k}(x,y))^i\lambda^{k-i}$; 
%then $G_{i,k} = 1 + yQ(G_{i,k})$ and by applying the Lagrange Inversion Formula we have that
%\[
%[y^j]G_{i,k} = \frac{1}{j}[\lambda^{j-1}](Q(\lambda + 1))^j.
%\]

%Since, 
%\begin{align*}
%(Q(\lambda+1))^j & = x^j(C_k(x))^{ij}(\lambda + 1)^{(k-i)j} = 
%x^j(C_k(x))^{ij} \sum_{\mu=0}^{(k-i)j}\binom{(k-i)j}{\mu}\lambda^\mu,
%\end{align*}
%for $\mu = j-1$ we obtain that
%\[
%[y^j]G_{i,k}(x) = \frac{1}{j} x^j (C_k(x))^{ij} \binom{(k-i)j}{j-1}, \quad n \in \mathbb{N}^*.
%\]

%Thus, we have that
%\begin{align*}
%G_{i,k}(x,y) &= 1 + \sum_{j=1}^{\infty} \frac{1}{j} x^j (C_{k}(x))^{ij} \binom{(k-i)j}{j-1} y^j \\ 
%& = 1 + \sum_{j=1}^{\infty} \frac{1}{j} 
%\sum_{\nu=0}^{\infty} \frac{ij}{k\nu + ij} \binom{k\nu +ij}{\nu} \binom{(k-i)j}{j-1} x^{j+\nu} y^j \\
%&= 1+\sum_{n=1}^{\infty}\sum_{j=1}^{n} \frac{i}{k(n-j)+ij}\binom{k(n-j)+ij}{n-j} \binom{(k-i)j}{j-1} x^{n} y^j.
%\end{align*}

 Using the Lagrange inversion formula, we obtain the following result.
\begin{Proposition}\label{Enum2}
The number of all $k$-ary trees $T$ of size $n$, for which the first element of $\F^i(T), i \in [k-1]$,
has size $j$ is equal to 
\[
[x^ny^j]G_{i,k}(x,y) = \frac{i}{(n-j)k+ij} \binom{(n-j)k+ij}{n-j} \binom{(k-i)j}{j-1}.
\]
\end{Proposition}



For the case $i=k-1$, using the bijection $\varphi$, we can easily check that 
$q_{k-1,k}(T)$ is the length of the first ascent of $\phi(T)$,
thus the number of $(k-1)$-Dyck paths having $n$ rises and length of first ascent equal to $j$ is
$\frac{(k-1)j}{kn-j}\binom{kn-j}{n-j}$. 










\begin{thebibliography}{99}
%
\bibitem{AN}
H. Ahrabian and A. Nowzari-Dalini, Parallel generation of $t$-ary trees
in A-order, \textit{Computer J.} \textbf{50} (2007),
581--588.

%
\bibitem{Deutsch}
E. Deutsch, Dyck path enumeration, \textit{Discrete Math.} \textbf{204} (1999), 167--202.

%
\bibitem{Er}
M. C. Er, Lexicographic listing and ranking of $t$-ary trees, 
\textit{Computer J.} \textbf{30} (1987), 569--572.

%
\bibitem{Er2}
M. C. Er,  Efficient generation of $k$-ary trees in natural order,
\textit{Computer J.} \textbf{35} (1992), 306--308.

%
\bibitem{GS}
I. M. Gessel and S. Seo, A refinement of Cayley's formula for trees,
\textit{Electron. J. Combin.} \textbf{11} (2006), {\#}R2.

%
\bibitem{HLM} S. Heubach, N. Y. Li and T. Mansour, Staircase tilings
and k-Catalan structures, \textit{Discrete Math.} \textbf{308} (2008),
5954--5964.

%
\bibitem{JRZ}
M. Jani, R. G. Rieper, and M. Zeleke, Enumeration of K-trees and applications,
\textit{Ann. Comb.} \textbf{6} (2002), 375--382.
%
\bibitem{123}
D. E. Knuth. \textit{The Art of Computer Programming. Fundamental Algorithms}, 
Vol.\ 1, Addison-Wesley, 3{rd} edition, 1997.
%
\bibitem{K}
J. F. Korsh, A-order generation of $k$-ary trees with $4k - 4$ letter
alphabet, \textit{J. Inform. Opt. Sci.}
\textbf{16} (1995), 557--567.

%
\bibitem{KlF}
J. F. Korsh and P. LaFollette, Loopless generation of Gray codes for $k$-ary trees,
\textit{Inform. Process. Lett.} \textbf{70} (1999), 7--11.
%
\bibitem{KL}
J. F. Korsh and S. Lipschutz, Shifts and loopless generation of $k$-ary trees,
\textit{Inform. Process. Lett.} \textbf{65} (1998), 235--240.
%
\bibitem{MSS}
T. Mansour, M. Schork and S. Severini, Noncrossing normal ordering for functions of boson operators,
\textit{Internat. J. Theoret. Phys.} \textbf{47} (2008), 832--849.
%
\bibitem{MSV}
D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, 
\textit{J. Combin. Theory Ser. A} \textbf{99} (2002), 307--344.
%
\bibitem{MN}
A. Mier and M. Noy, A solution to the tennis ball problem, 
\textit{Theoret. Comput. Sci.} \textbf{346} (2005), 254--264.
%
\bibitem{OEIS}
N. J. A. Sloane,
\href{http://www.research.att.com/~njas/sequences/}{The On-Line
Encyclopedia of Integer Sequences}, 2009.
%
\bibitem{P}
J. Pallo, Generating trees with n nodes and m leaves,
\textit{Int. J. Comput. Math.} \textbf{21} (1987), 133--144.
%
\bibitem{RR}
D. Roelants van Baonaigien and F. Ruskey, Generating $t$-ary trees in A-order, 
\textit{Inform. Process. Lett.} \textbf{27} (1988), 205--213.
%
\bibitem{R}
F. Ruskey, Generating $t$-ary trees lexicographically,
\textit{SIAM J. Comput.} \textbf{7} (1978), 424--439.
%
\bibitem{S}
G. Seroussi, On the number of $t$-ary trees with a given path length, 
\textit{Algorithmica} \textbf{46} (2006), 557--565.
%
\bibitem{XUT}
L. Xiang, K. Ushijima and C. Tang, On generating $k$-ary trees in computer representation,
\textit{Inform. Process. Lett.} \textbf{77} (2001), 231--238.
%
\bibitem{Z}
S. Zaks, Generation and ranking of $k$-ary trees, 
\textit{Inform. Process. Lett.} \textbf{14} (1982), 44--48.
%
\bibitem{ZJ}
M. Zeleke and M. Jani, k-trees and Catalan identities, \textit{Congr. Numer.} \textbf{165} (2003), 39--49.
%
\end{thebibliography}





\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 05A19.

\noindent \emph{Keywords: }
Generalized Dyck words, $k$-ary trees, $k$-Catalan numbers.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A000108}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 14 2009;
revised version received  November 3 2009.
Published in {\it Journal of Integer Sequences}, November 4 2009.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}