%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2018}
\articlenumber{31}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage[enableskew]{youngtab}
\usepackage[all,cmtip]{xy}
\usepackage{color}
\usepackage{qtree}
\usepackage{comment}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{problem}[theorem]{Problem}
\newtheorem*{question}{Question}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\numberwithin{table}{section}

%\newtheorem{thm}{Theorem}
%\newtheorem{lem}{Lemma}

\def\ZZ{{\mathbb Z}}\def\QQ{{\mathbb Q}}\def\CC{{\mathbb C}}\def\FF{{\mathbb F}}
\def\comb{\mathrm{comb}}\def\qand{\quad\text{and}\quad}

% Commands for leaves with no labels
\newcommand{\nola}{{\rule{2pt}{0pt}}} 
\newcommand{\Nola}{{\rule{3pt}{0pt}}} % for larger trees containing some labels
\renewcommand{\SS}{{\mathfrak S}}

\newcommand{\mat}[4]{\bigl(\begin{smallmatrix} #1 & #2 \\ #3 & #4 \end{smallmatrix}\bigr)}

\def\P{\mathcal P} \def\tC{\widetilde{C}} 
\newcommand{\T}{{\mathcal T}}
\newcommand{\D}{{\mathcal D}} \newcommand{\Par}{\mathrm{Par}}
\newcommand{\ld}{\delta} \newcommand{\rd}{\rho}
\DeclareMathOperator{\tr}{tr} 
\DeclareMathOperator{\des}{des} 

\newcommand{\defcolor}[1]{{\color{blue}{#1}}}
\newcommand{\demph}[1]{\defcolor{{\sl #1}}}
\newcommand{\edit}[1]{{\color{red}{\bf {#1}}}}

%% define your title in the usual way
\title{Variations of the Catalan numbers from some nonassociative binary operations}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Nickolas Hein\thanks{\href{mailto:nhein@benedictine.edu}{nhein@benedictine.edu}}\addressmark{1}
\and Jia Huang\thanks{\href{mailto:huangj2@unk.edu}{huangj2@unk.edu}}\addressmark{2}}

%\author{Jia Huang}
%\address{Department of Mathematics and Statistics, University of Nebraska at Kearney, Kearney, NE 68849, USA}
%\email{huangj2@unk.edu}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics and Computer Science, Benedictine College, Atchison, KS 66002, USA
\\ \addressmark{2}Department of Mathematics and Statistics, University of Nebraska, Kearney, NE 68849, USA}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We investigate certain nonassociative binary operations that satisfy a four-parameter generalization of the associative law. 
From this we obtain variations of the ubiquitous Catalan numbers and connections to many interesting combinatorial objects such as binary trees, plane trees, lattice paths, and permutations. }

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Binary operation, binary tree, Catalan number, nonassociativity}


%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{31-Hein-Huang.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

%Binary operations are widely used in mathematics and other fields. 
%Many operations are associative, such as addition, multiplication, union, intersection, and function composition.
%Others are not, including subtraction, division, exponentiation, vector cross product, and Lie algebra multiplication.
We consider an overlooked yet natural question: to what degree is a given binary operation nonassociative?
We use $*$ to denote a binary operation on a set $A$ and use $a_0, a_1, a_2,\ldots$ to denote $A$-valued indeterminates.
Let $\defcolor{\P_{*,n}}$ be the set of all parenthesizations of the otherwise ambiguous expression $a_0*\cdots*a_n$.
The set $\P_{*,n}$ is in bijection with the set $\defcolor{\T_n}$ of (full) binary trees with $n+1$ leaves.
Both sets $\P_{*,n}$ and $\T_n$ are among the hundreds of families of objects enumerated by the ubiquitous \demph{Catalan number} $\defcolor{C_n}:=\frac{1}{n+1} {2n\choose n}$; see, e.g., Stanley~\cite{StanleyCatalan}.
Figure~\ref{fig:parenthesization} below illustrates the bijection $\P_{*,3}\leftrightarrow\T_3$.
\begin{figure}[h]
\[\scriptsize\begin{array}{ccccc}
\Tree [.  [. [. 0 1 ] 2 ] 3 ] &
\Tree [.  [. 0 1 ] [. 2 3 ] ] &
\Tree [.  [. 0 [. 1 2 ] ] 3 ] &
\Tree [. 0 [. [. 1 2 ] 3 ] ] &
\Tree [. 0  [. 1 [. 2 3 ] ] ] \\
\updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow \\
\rule{5pt}{0pt}((a_0 {*} a_1) {*} a_2) {*} a_3\rule{5pt}{0pt} &
\rule{5pt}{0pt}(a_0 {*} a_1) {*} (a_2 {*} a_3)\rule{5pt}{0pt} &
\rule{5pt}{0pt}(a_0 {*} (a_1{*} a_2)) {*} a_3 \rule{5pt}{0pt} &
\rule{5pt}{0pt}a_0 {*} ((a_1 {*} a_2) {*} a_3)\rule{5pt}{0pt} &
\rule{5pt}{0pt}a_0 {*} (a_1 {*} (a_2 {*} a_3))\rule{5pt}{0pt}
\end{array}\]
\caption{binary trees and parenthesizations}
\label{fig:parenthesization}
\end{figure}

We investigate two nonassociativity measurements for the operation $*$.
Given binary trees $t,t'\in\T_n$, write $\defcolor{t \sim_* t'}$ if the corresponding parenthesizations are equal as functions from $A^{n+1}$ to $A$.
This is an equivalence relation on a set of Catalan objects, and for brevity we say its equivalence classes are \demph{$(*,n)$-classes}.
We define $\defcolor{C_{*,n}}$ to be the number of $(*,n)$-classes, and observe that $1\le C_{*,n}\le C_n$.
We now have an alternate definition of associativity that specializes to the traditional meaning: the operation $*$ is associative if $C_{*,n}=1$ for all $n\ge0$.
Thus $C_{*,n}$ measures the failure of $*$ to be associative.
We say $*$ is \demph{totally nonassociative} if $C_{*,n}$ attains its theoretical upper bound, $C_{*,n}=C_n$.

Alternatively, one may quantify nonassociativity by computing the cardinality $\defcolor{\tC_{*,n}}$ of the largest $(*,n)$-class for each $n$.
Again, we have $1\le \tC_{*,n}\le C_n$. 
One may see that $\tC_{*,n}=1$ if and only if $*$ is totally nonassociative and $\tC_{*,n}=C_n$ if and only if $*$ is associative.
Moreover, $1\le C_{*,n}+\tC_{*,n}-1\le C_n$.

%Lord~\cite{Lord} introduced a measurement of nonassociativity, called the \demph{depth of nonassociativity}, which in fact equals $\inf \{ n+1: C_{*,n}<C_n\} = \inf \{ n+1: \tC_{*,n} > 1 \}$.
%Each of the measurements we propose refines the depth of nonassociativity.

%In general, the depth of nonassociativity for $*$ is between three and infinity.
%It equals three if and only if $*$ is associative and it equals infinity if and only if $*$ is totally nonassociative.
%Lord~\cite{Lord} examined some elementary binary operations and determined their depths of nonassociativity.
%Lord~\cite{Lord} defined the \demph{depth of non-associativity} for a binary operation $*$ to be the smallest integer $n$ such that there exist a pair of distinct parenthesizations of $x_0*\cdots*x_n$ that are equal to each other; if no such integer exists then the depth is infinity.
%In general, the depth of non-associativity is at least three and at most infinity.
%Associative operations are precisely those with depth three.
%We call those operations with infinity depth of nonassociativity \demph{totally nonassociative}.
%Lord~\cite{Lord} examined a few elementary operations and determined their depths.
%Some of these examples have infinity depth, such as $a*b:=a^b$ for positive integers $a,b$, and $a*b:=a^2+b^2$ for $a,b\in \mathbb R$.
%On the other hand, for any positive integer $k$, the operation defined by $a*b:=a+\omega b$ for all $a,b\in\CC$, where $\omega$ is a primitive $k$th root of unity, has depth $k+2$.

In earlier work~\cite{CatMod}, we investigated the nonassociativity of a $1$-parameter family (depending on a positive integer $k$) of binary operations which generalize addition ($k=1$) and subtraction ($k=2$).
Now we further generalize this to a four-parameter family (depending on positive integers $d,e,k,\ell$) of binary operations which are neither associative nor totally nonassociative.
%We are mainly interested in the sequences of numbers $C_{*,n}$ and $\tC{*,n}$ for $*$ in the $4$-parameter family.
Our prototypical example is in the quotient $\CC[x,y]/I$ of the polynomial ring $\CC[x,y]$ by its ideal $I:=(x^{d+k}-x^d,y^{e+\ell}-y^e)$.
We define the binary operation $*$ by the following rule:
\begin{equation}\label{eq:*}
f*g := xf + yg, \quad\forall f,g\in \CC[x,y]/I.
\end{equation}
The relations imposed on $x$ and $y$ are motivated by the relation
satisfied by an element in a finite semigroup; see, e.g.,
Steinberg~\cite[Section 1.2]{Monoid}.
%One may change $I$ to a different ideal and study the resulting operation $*$.
%Though we are presently interested in the ideal given above, one may more generally study binary operations defined by $\eqref{eq:*}$ with $I$ being any ideal.
A parenthesization corresponding to a binary tree $t\in\T_n$ has the form
\begin{equation}\label{eq:expansion}
x^{\ld_0(t)} y^{\rd_0(t)} f_0 + \cdots + x^{\ld_n(t)} y^{\rd_n(t)} f_n. 
\end{equation}
Here we list the leaves of $t$ as $0,1,\ldots,n$ according to \demph{preorder} and define the \demph{left depth} $\defcolor{\ld_i(t)}$ (resp., \demph{right depth} $\defcolor{\rd_i(t)}$) of $i$ to be the number of left (resp., right) steps along the unique path from the root of $t$ down to $i$.
The map sending each $t\in\T_n$ to its \demph{left depth}
$\defcolor{\ld(t)} := (\ld_0(t),\ldots,\ld_n(t))$ is
one-to-one~\cite[Section 2.1]{CatMod}, and by symmetry, so is the map sending each $t\in\T_n$ to its \demph{right depth} $\defcolor{\rd(t)} := (\rd_0(t),\ldots,\rd_n(t))$.

For example, the third binary tree in Fig.~\ref{fig:parenthesization} has left depth $\ld=(2,2,1,0)$ and right depth $\rd=(0,1,2,1)$, and the corresponding parenthesization $(f_0*(f_1*f_2))*f_3$ can be written as $x^2f_0+x^2yf_1+xy^2f_2+yf_3$.

For $*$ defined by \eqref{eq:*}, comparing expressions for $t,t'\in\T_n$ of the form \eqref{eq:expansion} gives
\begin{equation}\label{eq:mod-nil-lr}
t\sim_* t' \quad\text{if and only if}\quad \ld(t) \sim_k^d \ld(t') \qand \rd(t) \sim_\ell^e \rd(t')\,.
\end{equation}
Here for any two integer sequences $\mathbf{b}=(b_0,\ldots,b_n)$ and $\mathbf{c}=(c_0,\ldots,c_n)$ we write

(1) $\defcolor{\mathbf{b} \sim_k \mathbf{c}}$ if $b_i\equiv c_i\pmod k$ for $i=0,\ldots,n$, 

(2) $\defcolor{\mathbf{b} \sim^d\mathbf{c}}$ if $\min\{b_i,c_i\}<d$ implies $b_i=c_i$ for $i=0,\ldots,n$, and 

(3) $\defcolor{\mathbf{b} \sim_k^d \mathbf{c}}$ if $\mathbf{b} \sim_k \mathbf{c}$ and $\mathbf{b} \sim^d\mathbf{c}$.
%$b_i=c_i<d$ or $\min\{b_i,c_i\}\ge d$ and $b_i \equiv c_i \mod k$ for $i=0,\ldots,n$. 


We write $\defcolor{C^{d,e}_{k,\ell,n}}:=C_{*,n}$ and $\defcolor{\tC^{d,e}_{k,\ell,n}}:=\tC_{*,n}$ for any binary operation $*$ satisfying \eqref{eq:mod-nil-lr}.
%We observe that $\mathbf{b}\sim_{k}^d\mathbf{c}$ implies $\mathbf{b}\sim_{k'}^{d'}\mathbf{c}$ if $d\le d'$ and $k\mid k'$.
Observe that if $d \le d'$, $e\le e'$, $k \mid k'$, and $\ell \mid \ell'$, then $C^{d,e}_{k,\ell,n}\le C^{d',e'}_{k',\ell',n}$ and $\tC^{d,e}_{k,\ell,n}\ge \tC^{d',e'}_{k',\ell',n}$. %and $(d,e)$-associativity at depth $(k,\ell)$ implies $(d',e')$-associativity at depth $(k',\ell')$.
%Also, the $(*,n)$-equivalence classes that determine $C_{k,\ell,n}^{d,e}$ and $\tC_{k,\ell,n}^{d,e}$ are the same as the classes that determine $C_{\ell,k,n}^{e,d}$ and $\tC_{\ell,k,n}^{e,d}$, but with each binary tree in each class reflected about a vertical line.
We symmetrically have $C^{d,e}_{k,\ell,n} = C^{e,d}_{\ell,k,n}$ and $\tC^{d,e}_{k,\ell,n} = \tC^{e,d}_{\ell,k,n}$.

%To see the connection to the usual associativity, first 
Note that the relations $\sim_1^d$ %as all integers are congruent modulo $1$, 
and $\sim_k^1$ coincide with $\sim^d$ and $\sim_k$, respectively, on left and right depths of binary trees in $\T_n$.
%since $\ld_i(t)=0 \Leftrightarrow i=n$ and $\rd_i(t)=0 \Leftrightarrow i=0$ for all $t\in\T_n$, we see 
In earlier work~\cite{CatMod}, we determined $\defcolor{C_{k,n}}:=C^{1,1}_{k,1,n}$ using plane trees, Dyck paths, and Lagrange inversion.
We call $C_{k,n}$ a \demph{($k$-)modular Catalan number} as for any binary operation $*$ satisfying \eqref{eq:mod-nil-lr} with $d=e=\ell=1$, the $(*,n)$-relation is the same as the congruence relation modulo $k$ on left depths of binary trees in $\T_n$.
We also determined $\defcolor{\tC_{k,n}} := \tC^{1,1}_{k,1,n}$ and enumerated $(*,n)$-classes with this largest size.
The ``if'' part of \eqref{eq:mod-nil-lr} with $d=e=\ell=1$  is equivalent to \demph{$k$-associativity}, given by the rule $(a_0*\cdots*a_k)*a_{k+1} = a_0*(a_1*\cdots*a_{k+1})$, where the $*$'s in parentheses are evaluated from left to right~\cite[Proposition~2.11]{CatMod}.
This gives a one-parameter generalization of the usual associativity ($k=1$). 

We will see in Section~\ref{sec:nil} that, for $e=k=\ell=1$, the ``if'' part of the $(*,n)$-relation \eqref{eq:mod-nil-lr} can be viewed as \demph{associativity at left depth $d$}, that is, $t\sim_* t'$ if $t$ can be obtained from $t'$ by a finite sequence of moves, each of which replaces the maximal subtree rooted at a node of left depth at least $d-1$ by another binary tree with the same number of leaves.
Here a \demph{subtree rooted at a node $v$} is a subtree whose root is $v$, and the \demph{maximal subtree rooted at $v$} is the subtree consisting of all descendants of $v$, including $v$ itself.

%Define $\defcolor{C^d_n} := C^{d,1}_{1,1,n}$ and $\defcolor{\tC^d_n} := \tC^{d,1}_{1,1,n}$.
%Our results in Section~\ref{sec:nil-lr} determine ${\tC^d_n}$ and enumerate $(*,n)$-classes with this maximum size.
%We also identify ${C^d_n}$ with~\cite[A080934]{OEIS} and give a closed formula for the generating function of $C^d_n$ in terms of the Fibonacci polynomials.

Motivated by the two single-parameter generalizations of associativity above, we say a binary operation $*$ is \demph{$(k,\ell)$-associative at depth $(d,e)$} if it satisfies the ``if'' part of \eqref{eq:mod-nil-lr}.
We focus on two special cases, $k=\ell=1$ and $e=\ell=1$, each giving a two-parameter generalization of the usual associativity with connections to many interesting integer sequences and combinatorial objects.


In Section~\ref{sec:nil-lr} we study the case $k=\ell=1$.
In this case the ``if'' part of \eqref{eq:mod-nil-lr} can be viewed as \demph{associativity at left depth $d$ and right depth $e$}, which recovers the associativity at left depth $d$ when $e=1$.
We determine $\defcolor{\tC^{d,e}_n} := \tC^{d,e}_{1,1,n}$ and enumerate $(*,n)$-classes with this largest size for any binary operation $*$ satisfying \eqref{eq:mod-nil-lr} with $k=\ell=1$.
We prove that the cardinality of each $(*,n)$-class is a product of Catalan numbers. %Corollary~\ref{cor:prod-cat}.
We provide a recursive formula for the generating function $\defcolor{C^{d,e}(x)}:= \sum_{n\ge0} C^{d,e}_n x^{n+1}$ of the number $\defcolor{C^{d,e}_n} :=  C^{d,e}_{1,1,n}$ of $(*,n)$-classes
%\begin{theorem}
%Let $d,e\ge1$.
%If $0\le n<d+e$ then $\tC^{d,e}_n=1$.
%If $n\ge d+e$ then $\tC^{d,e}_n=C_{n+2-d-e}$ and the number of $(*,n)$-classes with this size is ${d+e-2\choose d-1}$.
%Moreover, $C^{d,e}(x) = x + C^{d-1,e}(x)C^{d,e-1}(x)$.
%\end{theorem}
%$\defcolor{C^{d,e}(x)} := \sum_{n\ge0} C^{d,e}_n x^{n+1}$ 
%By symmetry, $C^{d,e}(x) = C^{e,d}(x)$.
%If $d$ or $e$ is zero then we treat it as one.
and give closed formulas for $C^{d,e}(x)$ and $C^{d,e}_n$ when $e=1,2$.
It turns out that $C^{d,1}(x)$ is a well-known continued fraction and $C^{d,1}_n$ enumerates many families of objects (see Andrews--Krattenthaler--Orsina--Luigi--Papi~\cite{AdNilIdeals}, de Bruijn--Knuth--Rice~\cite{DBKR}, Flajolet~\cite{Flajolet},  Kitaev--Remmel--Tiefenbruck~\cite{KRT12}, Kreweras~\cite{Kreweras}, and The OEIS~\cite[A080934]{OEIS}).
\begin{comment}
\begin{itemize}
\item
binary trees with $n+1$ leaves of left depth at most $d$ (by~Proposition~\ref{prop:MC}),
\item
plane trees with $n+1$ nodes of depth at most $d$ (de Bruijn, Knuth, and Rice~\cite{DBKR}),
\item
Dyck paths of length $2n$ with height at most $d$ (Flajolet~\cite{Flajolet} and Kreweras~\cite[page 38]{Kreweras}),
\item
permutations in $\SS_n$ avoiding $132$ and $123\cdots(d+1)$ (Kitaev, Remmel, and Tiefenbruck~\cite{KRT12}), %\S3.1
% (this is the same as the dash-pattern avoidance used in our earlier work~\cite{CatMod}),
\item
ad-nilpotent ideals of the Borel subalgebra of the Lie algebra $\mathfrak{sl}_n(\mathbb C)$ of order at most $d-1$ (Andrews, Krattenthaler, Orsina, and Papi~\cite{AdNilIdeals}).
\end{itemize}
\end{comment}
Our formula for $C^{d,1}_n$ is different from the existing formulas~\cite{AdNilIdeals,DBKR}.
We find no existing result on $C^{d,e}_n$ for $d,e\ge2$ except $C^{2,2}_n$ and $C^{3,2}_n$~\cite[A045623,A142586]{OEIS}.
%The number $C^{d,2}_n$ occurs in OEIS only for $d\le3$~\cite[A045623,A142586]{OEIS} and 
%We find no result on $C^{d,2}$ for $d\ge4$ or $C^{d,3}_n$ for $d\ge 3$ in OEIS~\cite{OEIS}.

In Section~\ref{sec:mod-nil} we study the case $e=\ell=1$.
In this case the ``if'' part of \eqref{eq:mod-nil-lr} can be viewed as \demph{$k$-associativity at left depth $d$}, which recovers the $k$-associativity when $d=1$ and recovers the associativity at left depth $d$ when $k=1$.
We show that the number $\defcolor{C^d_{k,n}} := C^{d,1}_{k,1,n}$ enumerates binary trees and Dyck paths with certain constraints, and establish a recursive formula for its generating function $\defcolor{C^d_k(x)}:=\sum_{n\ge0} C^d_{k,n} x^{n+1}$.
%Then we study $C^d_{k,n}$ when $d=1,2,3$ or $k=1,2$.
We have $C_1^d(x)=C^{d,1}(x)$ and $C_2^d(x) = C^{d+1,1}(x)$ for $d,n\ge0$.
The number $C_{3,n}^d$ appears in The OEIS~\cite[A005773, A054391--A054394]{OEIS} for $d=1,\ldots,5$.
Barcucci, Del Lungo, Pergola, and Pinzani~\cite{CatPerm} studied $C_{3,n}^d$ in terms of pattern avoidance in permutations and obtained a closed formula for $C_3^d(x)$, but no closed formula for $C_{3,n}^d$.
We provide a different formula for $C_3^d(x)$ and derive a closed formula for $C_{3,n}^d$ from it.
We also give closed formulas for $C^2_{k,n}$ using Lagrange inversion and our earlier work~\cite{CatMod} on $C^1_{k,n}$.

%We compute $\defcolor{\C^d_{k,n}} := \C^{d,1}_{k,1,n}$ for $d,k\ge1$ and enumerate $(*,n)$-classes with this size ??
%We provide a recursive formula for the generating function of $\defcolor{C^d_{k,n}} := C_{*,n}$ for $d,k\ge1$.

Another 2-parameter specialization of \eqref{eq:mod-nil-lr} is obtained by taking $d=e=1$ and
%Let $\defcolor{C_{k,\ell,n}} := C^{1,1}_{k,\ell,n}$.
computations suggest a conjecture: $C^{1,1}_{k,\ell,n} = C_{k+\ell-1,n}$ for all $k,\ell\ge1$ and $n\ge0$.
We will also explore the case $k,\ell,d,e>1$ in the future.

%\tableofcontents

\section{Associativity at left depth $d$ and right depth $e$}\label{sec:nil-lr}

In this section we study $\defcolor{C^{d,e}_n} := C_{*,n}$ and $\defcolor{\tC^{d,e}_n} := \tC_{*,n}$ for any operation $*$ satisfying \eqref{eq:mod-nil-lr} with $k=\ell=1$, i.e., when $t\sim_* t' \Leftrightarrow \ld(t) \sim^d \ld(t')$ and $\rd(t) \sim^{e} \rd(t')$ for all $t,t'\in \T_n$.

We first introduce some notation.
If a node in a binary tree has left depth $\ld\ge d-1$ and right depth $\rd\ge e-1$ then we say this node is \demph{$(d,e)$-contractible}, or simply \demph{contractible} if $d$ and $e$ are clear from the context.
We call a contractible node \demph{maximal} if its parent is not contractible.
One sees that a node with left depth $\ld$ and right depth $\rd$ is a maximal contractible node if and only if $\ld=d-1$ and $\rd\ge e-1$ when $v$ is the left child of its parent, or $\ld\ge d-1$ and $\rd=e-1$ when $v$ is the right child of its parent.

Let $t\in\T_n$ and assign each leaf weight one. 
For each maximal contractible node $v$, we contract its subtree to a single node and assign $v$ a weight equal to the number of leaves in this subtree.
Denote by $\defcolor{\phi(t)}$ the resulting weighted binary tree.
This gives a map $\phi:\T_n\to\T^{d,e}_n$ by $t\mapsto\phi(t)$, where $\defcolor{\T^{d,e}_n}$ is the set of all leaf-weighted binary trees such that every contractible leaf is maximal and has a positive integer weight, every non-contractible leaf has weight one, and the sum of all leaf weights is $n+1$.
%\text{if $m=1$ and $v$ is the left child of its parent then $\ld<h$ or $\rd<h'-1$;} \\
%\text{if $m=1$ and $v$ is the right child of its parent then $\ld<h-1$ or $\rd<h'$;} \\
%\text{if $m\ge2$ and $v$ is the left child of its parent then $\ld=h-1$ and $\rd\ge h'-1$;} \\
%\text{if $m\ge2$ and $v$ is the right child of its parent then $\ld\ge h-1$ and $\rd=h'-1$.}

Conversely, if $\bar t\in\T^{d,e}_n$ has leaves $v_0,\ldots,v_r$ with weights $m_0,\ldots,m_r$, respectively, then replacing $v_i$ by $t_i\in\T_{m_i-1}$ for $i=0,\ldots,r$ gives a binary tree $\defcolor{\phi^{-1}(\bar t;t_0,\ldots,t_r)}$.

\begin{lemma}\label{lem:phi}
(i) We have a surjection $\phi:\T_n\twoheadrightarrow\T^{d,e}_n$. 

\noindent(ii) For each $\bar t\in\T^{d,e}_n$ whose leaves $v_0,\ldots,v_r$ are weighted $m_0,\ldots,m_r$, its \demph{fiber} is
\[ \phi^{-1}(\bar t) = \{ \phi^{-1}(\bar t;t_0,\ldots,t_r) : t_i\in \T_{m_i-1}\}. \]

\noindent (iii) We have $t\sim_* t'$ whenever $\phi(t)=\phi(t')$.
\end{lemma}

\begin{comment}
We first prove the third statements, and the others quickly follow.
Let $\bar t\in\T^{d,e}_n$ with leaves $v_0,\ldots,v_r$ having weight $m_0,\ldots,m_r$.
As $\sim_*$ is an equivalence relation, so, to prove (iii) it suffices to show $t=\phi^{-1}(\bar t;t_0,\ldots,t_r) \sim_* t'=\phi^{-1}(\bar t;t'_0,\ldots,t'_r)$, where $t_j$ are $t'_j$ are distinct binary trees with $m_j$ leaves for some $j\in\{0,\ldots,r\}$ and $t_i$ and $t'_i$ are the same binary tree with $m_i$ leaves for all $i\ne j$.
Suppose the $j$th leaf $v_j$ has left depth $\ld$ and right depth $\rd$.
Since $v_j$ is contractible by the definition of $\T^{d,e}_n$, we have $\ld\ge d-1$ and $\rd\ge e-1$.
We also know $m_j\ge 3$ as $t_j\ne t'_j$, so in $t$ we have:
\begin{itemize}
\item
the first leaf of $t_j$ has left depth at least $\ld+1\ge d$ and right depth equal to $\rho$, 
\item
the last leaf of $t_j$ has left depth equal to $\ld$ and right depth at least $\rd+1\ge e$, and  \item
all other leaves of $t_j$ have left depths at least $\ld+1\ge d$ and right depths at least $\rd+1\ge e$.
\end{itemize}
Similarly, the leaves of $t'_j$ satisfy the same properties.
Thus $\ld(t) \sim^d \ld(t')$ and $\rd(t) \sim^{e} \rd(t')$.
This proves (iii).

The argument above implies that each descendant of a contractible node is contractible, so (ii) also holds.
Furthermore, each fiber $\phi^{-1}(\bar t)$ is nonempty as one can choose trees $t_i$ with $m_i$ leaves for each $i$.
This implies the surjectivity of $\phi$.
\end{comment}

\begin{theorem}\label{thm:nil-lr}
Let $*$ be a binary operation satisfying \eqref{eq:mod-nil-lr} with $k=\ell=1$.
Then the fibers of $\phi$ are precisely the $(*,n)$-classes.
%\begin{corollary}\label{cor:prod-cat}
Thus the cardinality of a $(*,n)$-class is a product of Catalan numbers $C_{m_0-1}\cdots C_{m_r-1}$ for some positive integers $m_0,\ldots,m_r$ satisfying $m_0+\cdots+m_r = n+1$.
%\end{corollary}
\end{theorem}

\begin{comment}
By Theorem~\ref{thm:nil-lr}, every $(*,n)$-class can be written as $\phi^{-1}(\bar t)$ for some $\bar t\in\T^{d,e}_n$.
If the leaves of $\bar t$ have weights $m_0,\ldots,m_r$ then $|\phi^{-1}(\bar t)| = C_{m_0-1}\cdots C_{m_r-1}$ by Lemma~\ref{lem:phi}. 
We have $m_0+\cdots+m_r = n+1$ by the definition of $\T^{d,e}_n$.
\end{comment}

%We first determine the largest size  $\tC^{d,e}_n$ of a $(*,n)$-class.

\begin{theorem}
Let $d,e\ge1$.
If $0\le n<d+e$ then $\tC^{d,e}_n=1$.
If $n\ge d+e$ then $\tC^{d,e}_n=C_{n+2-d-e}$ and the number of $(*,n)$-classes with this size is ${d+e-2\choose d-1}$.
\end{theorem}

\begin{comment}
It is well known that the Catalan sequence $\{C_n\}$ is \demph{log-convex}, i.e., $C_m C_n\le C_{m+1}C_{n-1}$ for $m\ge n\ge1$.
Hence for each $r\ge 0$ the largest result from products of the form $C_{m_0-1}\cdots C_{m_r-1}$ with $m_0+\ldots+m_r=n+1$ is $C_{n-r}$, which is attained when all but one of $m_0,\ldots,m_r$ equal one.

Now let $\bar t\in\T^{d,e}_n$ with leaves $v_0,\ldots,v_r$ weighted $m_0,\ldots,m_r$.
If $m_0=\cdots=m_r=1$ then $C_{m_0-1}\cdots C_{m_r-1}=1$.
Assume $m_i>1$ for some $i$. 
Then $v_i$ is contractible, i.e. $\ld(v_i)\ge d-1$ and $\rd(v_i)\ge e-1$.
Hence the unique path from the root of $\bar t$ to $v_i$ has length at least $d+e-2$.
This implies that $\bar t$ has at least $d+e-2$ internal nodes and thus $r\ge d+e-2$. 
It follows that $|\phi^{-1}(\bar t)|\le C_{n+2-d-e}$, in which equality holds only if $r=d+e-2$ and all but one of $m_0,\ldots,m_r$ equal one.
We have $n+1=m_0+\cdots+m_r\ge r+2 \ge d+e$, i.e., $n\ge d+e-1$.
If $n=d+e-1$ then $C_{n+2-d-e}=C_1=1$.
Thus we assume $n\ge d+e$ below.

It remains to show that there are precisely ${d+e-2\choose d-1}$ many trees in $\T^{d,e}_n$ with $d+e-1$ leaves, one having weight larger than one and all others having weight one.
Suppose that $\bar t$ is such a tree and let $v$ be its unique leaf with weight larger than one.
Then the unique path from the root of $\bar t$ down to $v$ has length $d+e-2$.
This path has $d-1$ left steps and $e-1$ right steps.
Thus there are precisely ${d+e-2\choose d-1}$ many choices for this path.
The entire tree $\bar t$ is determined by this path as all nodes not on this path must be leaves.
\end{comment}

%Now we study the other nonassociativity measurement $C^{d,e}_n$ and its generating function
%\[ \defcolor{C^{d,e}(x)} := \sum_{n\ge0} C^{d,e}_n x^{n+1}.\]
%By symmetry we have $C^{d,e}(x) = C^{e,d}(x)$.
%If $d$ or $e$ is zero then we treat it as one.
%Theorem~\ref{thm:nil-lr} implies a recurrence relation for $C^{d,e}(x)$.

For $d,e\ge1$ let $\defcolor{C^{d,e}(x)} := \sum_{n\ge0} C^{d,e}_n x^{n+1}$, $\defcolor{C^{0,e}(x)} := C^{1,e}(x)$, and $\defcolor{C^{d,0}(x)} := C^{d,1}(x)$.

\begin{proposition}\label{prop:nil-lr-recurrence}
For $d,e\ge1$ we have $C^{d,e}(x) = x + C^{d-1,e}(x)C^{d,e-1}(x).$
\end{proposition}

\begin{comment}
By Theorem~\ref{thm:nil-lr}, $C^{d,e}_n=|\T^{d,e}_n|$.
For any $\bar t\in\T^{d,e}_n$, let $\bar t_L$ and $\bar t_R$ denote the (maximal) weighted subtrees rooted at the left and right children of the root of $\bar t$.
Then $\bar t_L\in\T^{d-1,e}_m$ and $\bar t_R\in\T^{d,e-1}_{n-m-1}$ for some $m$.
Two trees $\bar s$ and $\bar t$ in $\T^{d,e}_n$ are equal if and only if $\bar s_L=\bar t_L$ and $\bar s_R = \bar t_R$.
The result follows.
\end{comment}

%Corollary~\ref{cor:nil} recursively determines $C^{d,e}(x)$ for all $d,e\ge1$.
We apply Proposition~\ref{prop:nil-lr-recurrence} to study $C^{d,e}(x)$ for $e=1,2$, respectively, in the next two subsections.
We find no result on $C^{d,3}_n$ for $d\ge 3$ in The OEIS~\cite{OEIS}.


\begin{comment}
There is a natural bijection between Dyck paths of length $2n$ and binary trees given by the following process.
When a Dyck path takes a step up, a left child is added to the most recently added node of the tree, and, when the path takes a step down, a right child is added to the most recently added node of the tree which already has one child.
In this correspondence, height in a Dyck path corresponds to left depth in a tree.

A subpath of a Dyck path $U\cdots D$ beginning with an up step and ending with a down step is a \demph{(weakly) rising path} if its terminal height is not less than its initial height.
In particular, if a subpath of a Dyck path is again a Dyck path, then it is weakly rising as its terminal height is equal to its initial height.
Moreover, if a subpath of a Dyck path begins at the origin and ends in a down step, then it is a rising path as a Dyck path never passes below its starting point.

Right depth of a node in a binary tree can be detected in its corresponding Dyck path in the following way.
If the corresponding node of the Dyck path occurs at the end of a down step, then the right depth of the corresponding tree node is equal $\rho$ such that the subpath from the origin to that node can be written as $\rho$ consecutive rising path but cannot be written as $\rho+1$ consecutive rising paths.
If the corresponding node of the Dyck path occurs at the end of an up step, then its right depth is the same as that of the most recently drawn node occurring after a down step.

Here is an illustrative example.
Consider the Dyck path $U^2DU^2DUD^2U^2D^3$ and the node at the end of the subpath $P=U^2DU^2DUD^2U^2$, beginning at the origin. This node corresponds to a leaf of a binary tree with left depth $3$ and right depth $\rho = 2$.  The left depth is $3$ because $P$ terminates at height $3$.
We may check $\rho = 2$ by counting rising paths.
Note that up-steps at the end of a subpath do not affect right depth, so we only count consecutive rising paths of $Q=U^2DU^2DUD^2$.
Since $Q$ is itself a rising path $\rho\ge 1$.
Conversely, $\rho\le 3$ as the subpath $UD$ must appear in any rising path, and it only appears $3$ times in $Q$.
It turns out that there is only one way to decompose $Q$ into more than one rising path, and that is the rising path $U^2D$ followed by the rising path, $U^2DUD^2$, so $\rho=2$. 

One may prove the previous theorems using similar techniques on Dyck paths instead of binary trees.
\edit{If we decide this remark should remain in the paper, I could add some helpful diagrams.  (Dyck paths with rising paths marked off.)}
\end{comment}

\subsection{Associativity of left depth $d$: The case $e=k=\ell=1$}\label{sec:nil}
Assume $e=k=\ell=1$ in this subsection.
Then the ``if'' part of the $(*,n)$-relation \eqref{eq:mod-nil-lr} may be regarded as \demph{associativity at left depth $d$}, as Theorem~\ref{thm:nil-lr} implies that two trees $t,t'\in\T_n$ satisfy $t\sim_* t'$ if and only if $t$ can be obtained from $t'$ by a finite sequence of moves, each of which replaces the maximal subtree rooted at a node of left depth at least $d-1$ by another binary tree with the same number of leaves.

We use Proposition~\ref{prop:nil-lr-recurrence} to determine the number $\defcolor{C^d_n} := C^{d,1}_n$ of $(*,n)$-classes from its generating function $\defcolor{C^d(x)} := C^{d,1}(x)$ for all $d\ge1$.
%To state a formula for $C^d(x)$, 
We need the \demph{Fibonacci polynomials} defined by $\defcolor{F_n(x)} := F_{n-1}(x) - x F_{n-2}(x)$ for $n\ge2$ with $\defcolor{F_i(x)}:=i$ for $i=0,1$. % and $\defcolor{F_1(x)}:=1$.
For $n\ge1$ we have~\cite[(8), (9), (10)]{DBKR}
\begin{align*}
F_n(x) &= \frac{1}{\sqrt{1-4x}} \left( \left(\frac{1+\sqrt{1-4x}}{2}\right)^n - \left( \frac{1-\sqrt{1-4x}}{2} \right)^n \right) \\
&= \sum_{0\le i\le(n-1)/2} {n-1-i\choose i}(-x)^i 
= \prod_{1\le j\le (n-1)/2} (1-4x\cos^2(j\pi/n)). %=  \prod_{1\le j\le (n-1)} (1-2\sqrt x\cos(j\pi/n))
\end{align*} 
%For example, $F_2(x) = 1$, $F_3(x) = 1-x$, $F_4(x) = 1-2x$, and $F_5(x) = 1-3x+x^2$.
%, $F_6(x) = 1-4x+3x^2$, $F_7(x) = 1-5x+6x^2-x^3$, and so on.


\begin{corollary}[{Kreweras~\cite{Kreweras}}]\label{cor:nil}
For $d\ge1$ we have (with $\defcolor{C^0(x)}:=x$)
\[ C^{d}(x) = \frac{x}{1-C^{d-1}(x)}= \frac{ xF_{d+1}(x) }{ F_{d+2}(x)} .\]
%= x + \frac{x^2 F_d(-x)}{ F_{d+2}(-x)} 
\end{corollary}

\begin{comment}
Observe that $C^1(x) = x/(1-x)$.
By Proposition~\ref{prop:nil-lr-recurrence}, we have $C^{d}(x) = x + C^{d-1}(x)C^{d}(x)$ and thus $C^{d}(x) = x / (1-C^{d-1}(x))$.
By induction on $d$ we have $C^{d}(x) = xF_{d+1}(-x)/F_{d+2}(-x)$.
\end{comment}

Corollary~\ref{cor:nil} follows from Proposition~\ref{prop:nil-lr-recurrence} and implies that $C^d(x)$ is a well-known continued fraction~\cite{DBKR,Flajolet}:
\[ C^{1}(x) = \frac x{1-x}, \  
C^{2}(x)  = \frac x { 1- \frac x {1-x} } = \frac{x(1-x)}{1-2x}, \ 
C^{3}(x)  = \frac x {1- \frac x { 1- \frac x {1-x} } } = \frac{x(1-2x)}{1-3x+x^2}, \ldots.
\]
Hence $(C^d_n)_{d\ge1,n\ge0}$ coincides with an array in The OEIS~\cite[A080934]{OEIS} and enumerates 

\noindent(i) Dyck paths of length $2n$ with height at most $d$ (Flajolet~\cite{Flajolet}, Kreweras~\cite[page 38]{Kreweras}),

%\item
%binary trees with $n+1$ leaves of left depth at most $d$ (Proposition~\ref{prop:MC}),

\noindent(ii) permutations in $\SS_n$ avoiding $132$ and $12\cdots(d+1)$ (Kitaev--Remmel--Tiefenbruck~\cite{KRT12}),

\noindent (iii) 
plane trees with $n+1$ nodes of depth at most $d$ (de Bruijn--Knuth--Rice~\cite{DBKR}), and %\S3.1
% (this is the same as the dash-pattern avoidance used in our earlier work~\cite{CatMod}),

\noindent(iv) ad-nilpotent ideals of the Borel subalgebra of the Lie algebra $\mathfrak{sl}_n(\mathbb C)$ of order at most $d-1$ (Andrews--Krattenthaler--Orsina--Papi~\cite{AdNilIdeals}).

%Note that plane trees with $n+1$ nodes of depth at most $d$ correspond to binary trees with $n+1$ leaves of left depth at most $d$.
%The latter is a family of objects more relevant to our current work and can also be obtained from our later result Proposition~\ref{prop:MC} by setting $k=1$. % or using bijection between Dyck paths and binary trees,

One has $C^2_n=2^{n-1}$, $C^{3}_n = F_{2n-1}$, % (a Fibonacci number), 
and $C^{4}_n = \frac12 (1+3^{n-1})$ for $n\ge1$~\cite{AdNilIdeals,KRT12}.
In general, 
%There are many known closed formulas for the number $C^d_n$, such as
%~\cite[Cor. 4.3, Thm. 4.5]{AdNilIdeals} \cite[(14)]{DBKR}:
\begin{align*}
C^d_n &= \sum_{i\in\mathbb Z} \frac{2i(d+2)+1}{2n+1}
\binom{2n+1}{n-i(d+2)} \qquad \text{\cite[Theorem 4.5]{AdNilIdeals}} \\ 
& = \det \left[ \binom{i-\max\{-1,j-d\}}{j-i+1} \right]_{i,j=1}^{n-1} 
% = \det \left[ \binom{i-j+d}{j-i+1} \right]_{i,j=1}^{n-1} This formula seems wrong
\qquad \text{\cite[Theorem 4.5]{AdNilIdeals}} \\
&= \sum_{0=i_0\le i_1\le \cdots \le i_{d-1}\le i_{d}=n} \ \prod_{0\le j\le d-2} \binom{i_{j+2}-i_j-1}{i_{j+1}-i_j} 
\qquad \text{\cite[Corollary 4.3]{AdNilIdeals}} \\
&= \frac{2^{2n+1}}{d+2} \sum_{1\le j\le d+1} \sin^2(j\pi/(d+2)) \cos^{2n}(j\pi/(d+2)).  
\qquad \text{\cite[(14)]{DBKR}} 
\end{align*}

Now we derive a closed formula for $C^d_n$ from the generating function $C^d(x)$.
We write $\defcolor{\alpha\models n}$ if $\alpha$ is a \demph{composition} of $n$, i.e., if $\alpha=(\alpha_1,\ldots,\alpha_\ell)$ is a sequence of positive integers such that $\alpha_1+\cdots+\alpha_\ell=n$.
We also define $\defcolor{\ell(\alpha)}:=\ell$ and $\defcolor{\max(\alpha)} := \max\{\alpha_1,\ldots,\alpha_\ell\}$.

\begin{proposition}\label{prop:d1}
For $n,d\ge1$ we have
\[ C^d_n =  \sum_{ \substack{\alpha\models n \\ \max(\alpha) \le (d+1)/2 } } (-1)^{n-\ell(\alpha)} \binom{d-\alpha_1}{\alpha_1-1} \prod_{2\le r\le \ell(\alpha)} \binom{d+1-\alpha_i}{\alpha_i}. \]
\end{proposition}

\begin{comment}

For $d\ge1$ we have
\begin{align*}
C^{d}(x) & =  x + \frac{x^2 F_d(x)}{ F_{d+2}(x)} 
= x + \frac{\sum_{0\le i\le(d-1)/2} {d-1-i\choose i} (-x)^{i+2}} 
{ 1+ \sum_{1\le i\le(d+1)/2} {d+1-i\choose i} (-x)^i } \\
%= x + \frac{\sum_{0\le i\le(d-1)/2} {d-1-i\choose i} (-x)^{i+2}} 
%{ \prod_{1\le j\le (d+1)/2} (1-4x\cos^2(j\pi/(d+2)))} \\
&= x + \sum_{0\le i\le(d-1)/2} {d-1-i\choose i} (-x)^{i+2} \sum_{j\ge0} \left(\sum_{1\le i\le(d+1)/2} {d+1-i\choose i} (-1)^{i-1} x^i \right)^j
\end{align*}
Extracting the coefficient of $x^{n+1}$ from $C^d(x)$ gives
%C^d_n &= \sum_{0\le i\le(d-1)/2} (-1)^i 4^{n-1-i} {d-1-i\choose i}  
%\sum_{ \substack{ r_1,\ldots, r_{d+1} \ge0 \\ r_1+\cdots+r_{d+1} = 2(n-1-i) }} \prod_{1\le j\le d+1} \cos^{r_j}(j\pi/(d+2))  \\
%\sum_{ \substack{ r_1,\ldots, r_{\lfloor (d+1)/2\rfloor} \ge0 \\ r_1+\cdots+r_{\lfloor (d+1)/2\rfloor} = (n-1-i) }} \prod_{1\le j\le (d+1)/2} \cos^{2r_j}(j\pi/(d+2)) 
\begin{align*}
C^d_n & = \sum_{0\le i\le (d-1)/2} (-1)^i {d-1-i\choose i} \sum_{j\ge0} \sum_{ \substack{ 1\le i_1,\ldots,i_j\le (d+1)/2 \\ i_1+\cdots+i_j = n-1-i } } \prod_{1\le r\le j} (-1)^{i_r-1} \binom{d+1-i_r}{i_r} \\
&=  \sum_{j\ge0} (-1)^{n-1-j} \sum_{ \substack{ 1\le i_0,i_1,\ldots,i_j\le (d+1)/2 \\ i_0+i_1+\cdots+i_j = n} } \binom{d-i_0}{i_0-1} \prod_{1\le r\le j} \binom{d+1-i_r}{i_r} .
\end{align*}
Viewing $(i_0,\ldots,i_j)$ as a composition $\alpha$ of $n$ gives the desired formula. 
\end{comment}

This alternating formula differs from the other known formulas.
For example, it gives $C^4_3 = 1\cdot4\cdot 4 - 2\cdot 4 - 1\cdot 3 =5$ and the determinant formula gives $C^4_3 = 2\cdot3-1=5$.

Next, we give an interpretation of the number $C^d_n$ which is very similar to the one by Andrews--Krattenthaler--Orsina--Papi~\cite{AdNilIdeals}.
We do not know any direct way (e.g., using the exponential map) to convert one to the other.

Let $\defcolor{\mathcal U_n}$ be the algebra of $n$-by-$n$ upper triangular matrices over a field $\FF$, with the usual matrix product. 
%Using column operations one can write a (two-sided) ideal $I$ of $\mathcal U_n$ as an upper triangular matrix $[a_{ij}]_{1\le i,j\le n}$ with $a_{ij}\in\{0,*\}$ such that $a_{ij}=*$ implies $a_{ij'}=*$ for all $j'\ge j$ and $a_{i'j}=*$ for all $i'\le i$.
%The elements of $I$ are all matrices in $\mathcal U_n$ whose $(i,j)$-entry is arbitrary if $a_{ij}=*$ or zero if $a_{ij}=0$. 
%The ideal $I = [a_{ij}]_{1\le i,j\le n}$ is nilpotent if and only if $a_{ii}=0$ for all $i\in[n]$.
%Thus the stars in the matrix form of a nilpotent ideal $I$ give a partition inside the staircase $(n-1,\ldots,1,0)$. % with lower boundary corresponding to a Dyck path of length $2n$ rotated through $45^\circ$ clockwise.
A nilpotent (two-sided) ideal of $\mathcal U_n$ can be represented by an $n$-by-$n$ matrix whose entries are either zero or arbitrary such that these two kinds of entries are separated by a lattice path above the main diagonal from the upper left corner to the lower right corner. 
Thus the number of nilpotent ideals of $\mathcal U_n$ is the Catalan number $C_n$.
L. Shapiro~\cite{Shapiro} showed that the number of commutative ideals of $\mathcal U_n$ is $2^{n-1}$.
Motivated by the observation that an ideal $I$ of $\mathcal U_n$ is commutative if and only if $I^2=0$, we generalize Shapiro's result below, using the \demph{(nilpotent) order} of a nilpotent ideal $I$, which is defined as $\inf\{d:I^d=0\}$.
We are grateful to Brendon Rhoades for giving a proof for this result.

\begin{proposition}\label{thm:NumberOfIdeals}
For $d\ge1$, nilpotent ideals of order at most $d$ in $\mathcal U_n$ are enumerated by $C^d_n$.
\end{proposition}

\begin{comment}
A nilpotent ideal $I$ of $\mathcal U_n$ is determined by the lower boundary $D$ of the stars in its matrix form, which can be identified as a Dyck path of length $2n$.
We say a sequence $(i_1,i_2,\ldots,i_d)$ of $d$ integers between $1$ and $n$ is \emph{$D$-admissible} if the matrix entry $(i_j,i_{j+1})$ lies to the northeast of $D$ for all $j=1,2,\ldots,d-1$.
For any positive integer $m$, we have $I^m\ne0$ if and only if there exists a $D$-admissible sequence $(i_1,i_2,\ldots,i_{m+1})$.
Thus the order of $I$ is the largest integer $d$ such that there exists a $D$-admissible sequence $(i_1,\ldots,i_d)$.

Next, we construct the \emph{bounce path} of $D$ by starting from the northwest corner, going east until hitting a south step of $D$, then turning south and bouncing off the main diagonal to proceed east, and repeating this process all the way to the southeast corner.
The bounce path must be of the form $E^{b_1}S^{b_1}E^{b_2}S^{b_2}\cdots E^{b_k}S^{b_k}$, where $E$ is an east step, $S$ is a south step, and $(b_1,b_2,\ldots,b_k)$ is a composition of $n$.
We say this bounce path has $k$ \emph{parts}.

For $j=1,\ldots,k-1$, the matrix entry $(a_j,a_{j+1})$, defined by $a_1=1$ and $a_{j+1}=a_j+b_j$, is immediately to the right of the first south step of the segment $S^{b_j}$, which also lies to the northeast of $D$. 
Thus $(a_1,\ldots,a_k)$ is $D$-admissible.
This shows that $d\ge k$.

On the other hand, the longest $D$-admissible sequence $(i_1,\ldots,i_d)$ must satisfy $i_1=1=a_1$; 
otherwise $(1,i_1,\ldots,i_d)$ would be an even longer $D$-admissible sequence. 
Let $m$ be the largest integer such that $a_j=i_j$ for $j=1,2,\ldots,m$.
If $m<k$ then $a_{m+1}<i_{m+1}$ and $(a_1,\ldots,a_m,a_{m+1},i_{m+2},\ldots,i_d)$ is also $D$-admissible.
Repeating this process gives a $D$-admissible sequence $(a_1,a_2,\ldots,a_k,i_{k+1},\ldots,i_d)$.
But there is no entry on the $a_k$-th row to the northeast of $D$. 
This implies $d=k$.

There exists a bijection between Dyck paths of length $2n$ with exactly $h$ parts in their bounce paths and Dyck paths of length $2n$ with height $h$; see, e.g., Haglund~\cite[Theorem 3.15 and Remark 3.16]{Haglund}.
Thus nilpotent ideals of order at most $d$ in $\mathcal U_n$ are in bijection with Dyck paths of length $2n$ with height at most $d$; the latter family is known to be enumerated by $C^d_n$~\cite{Flajolet} or \edit{Kreweras~\cite[page 38]{Kreweras}?}
This establishes the result.
\end{comment}



\subsection{Associativity at left depth $d$ and right depth $e=2$}
Now we give closed formulas for the generating function $C^{d,2}(x)$ and the number $C^{d,2}_n$.

\begin{proposition}\label{prop:d2}
For $d,n\ge2$ we have 
\[ C^{d,2}(x) %= \frac{xF_4(-x)F_{d+1}(-x)+x^{d+2}}{F_4(-x) F_{d+2}(-x)}
%= x + \frac{x^2 F_d(-x)}{F_{d+2}(-x)} + \frac{x^{d+2}}{(1-2x) F_{d+2}(-x)}
= C^d(x) + \frac{x^{d+2}}{(1-2x) F_{d+2}(x)} \quad \text{and} \]
%Consequently, for $n,d\ge2$ we have
\[ C^{d,2}_n = C^d_n + \sum_{1\le i\le n-d} 2^{i-1} \sum_{ \substack{ \alpha\models n-d-i \\ \max(\alpha) \le (d+1)/2 }} (-1)^{n-d-i-\ell(\alpha) } \prod_{1\le j\le \ell(\alpha)} \binom{d+1-\alpha_j}{\alpha_j} .\]
\end{proposition}

\begin{comment}
By Proposition~\ref{prop:nil-lr-recurrence} and Corollary~\ref{cor:nil}, we can verify the formula for $d=2$, 
\[ C^{2,2}(x) = x + \frac{x^2(1-x)^2}{(1-2x)^2} = \frac{x(1-2x)(1-x)+x^4}{(1-2x)^2}. \]
%\[ C^{d,2}(x) = \frac{x^d F_3(-x)^2\prod_{j=4}^{d+1} F_j(-x)}{F_4(-x)^2\prod_{j=5}^{d+2} F_j(-x)} 
%+ \sum_{i=1}^{d-1} \frac{ x^i \prod_{j=d+3-i}^{d+1} F_j(-x)}{\prod_{j=d+4-i}^{d+2} F_j(-x)}. \]
For $d\ge3$ we obtain the desired formula for $C^{d,2}(x)$ by induction on $d$, Proposition~\ref{prop:nil-lr-recurrence}, and Corollary~\ref{cor:nil}.
It follows that
\begin{align*}
C^{d,2}(x) %& = C^d(x) + \frac{x^{d+2}}{(1-2x) F_{d+2}(-x)} \\
&= C^d(x) + \frac{\sum_{i\ge0} 2^i x^{d+i+2} }{ 1 + \sum_{1\le i\le (d+1)/2} \binom{d+1-i}{i} (-x)^i } \\
&= C^d(x) + \sum_{i\ge0} 2^i x^{d+i+2} \sum_{j\ge0} \left( \sum_{1\le i\le (d+1)/2} \binom{d+1-i}{i} (-1)^{i-1} x^i \right)^j .
\end{align*}
Hence
\begin{align*}
C^{d,2}_n &= C^d_n + \sum_{i\ge0} 2^{i} \sum_{j\ge0}  (-1)^{n-1-d-i-j} \sum_{ \substack{ 1\le i_1,\ldots,i_j\le (d+1)/2 \\ i_1+\cdots+i_j = n-1-d-i } } \prod_{1\le r\le j} \binom{d+1-i_r}{i_r} .
%&= C^d_n + \sum_{1\le i\le n-d} 2^{i-1} \sum_{ \substack{ \alpha\models n-d-i \\ \max(\alpha) \le (d+1)/2 }} (-1)^{n-d-i-\ell(\alpha) } \prod_{1\le j\le \ell(\alpha)} \binom{d+1-\alpha_j}{\alpha_j} \\
%&= C^d_n + \sum_{ \substack{ \alpha\models n-d \\ \alpha_2,\ldots,\alpha_{\ell(\alpha)} \le (d+1)/2 }} (-1)^{n-d-\alpha_1-\ell(\alpha)+1 } 2^{\alpha_1-1} \prod_{2\le j\le \ell(\alpha)} \binom{d+1-\alpha_j}{\alpha_j} .
\end{align*}
This implies the desired formula for $C^{d,2}_n$.
\end{comment}
%$C^{3,3}(x) = C^{3,2}(x) + \frac{x^5(1-2x)(F_4(x)+F_5(x)-2F_6(x))+x^{10}}{(1-2x)^2 F_5(x)^2}$, $C^{4,3}$ is more complicated.

Using Proposition~\ref{prop:d2} we find $C^{2,2}_n$ and $C^{3,2}_n$ in The OEIS.
The sequence $\{C^{2,2}_n:n\ge0\}$ is the binomial transformation of $1,1,2,2,3,3,\ldots$, it has a simple formula $C^{2,2}_n = (n+2)2^{n-3}$ for $n\ge2$, and it enumerates a few families of objects.
These objects include copies of $r$ in all compositions of $n+r$ for any positive integer $r$, weak compositions of $n-1$ with exactly one zero, triangulations of a regular $(n+3)$-gon in which each triangle contains at least one side of the polygon, and more~\cite[A045623]{OEIS}.
The sequence $(C^{3,2}_n)_{n\ge0}$ is the binomial transformation of $(\lfloor (\frac{1+\sqrt5}2)^n \rfloor )_{n\ge0}$ and satisfies the formula $C^{3,2}_n = \left(\frac{1+\sqrt5}{2}\right)^{2n-2} + \left(\frac{1-\sqrt5}{2}\right)^{2n-2} - 2^{n-2}$ for $n\ge2$~\cite[A142586]{OEIS}. 
We do not see $C^{4,2}_n$ in The OEIS, but it also has a simple formula.

\begin{proposition}
For $n\ge3$ we have $C^{4,2}_n = 1+ 5\cdot 3^{n-3} - 2^{n-3}$.
\end{proposition}

\begin{comment}
By Proposition~\ref{prop:d2} we have
\begin{align*}
C^{4,2}(x) & = x + \frac{x^2(1-2x)}{1-4x+3x^2} + \frac{x^6}{(1-2x)(1-4x+3x^2)} \\
&= x + \left( \frac{1}{1-x}+\frac{1}{1-3x}\right) \frac{x^2}{2} + \left( \frac{1}{1-x} - \frac{8}{1-2x} + \frac{9}{1-3x} \right) \frac{x^6}{2} .
\end{align*}
This implies the desired formula for $C^{4,2}_n$. 
\end{comment}

%By Proposition~\ref{prop:nil-lr-recurrence} and Proposition~\ref{prop:d2}, we have 
%\begin{eqnarray*}
%C^{3,3}(x) &=& x + \frac{(xF_4(-x)^2+x^5)^2}{F_4(-x)^2F_5(-x)^2} \\
%&=& \frac{xF_4(-x)^2F_5(-x)^2+x^2F_4(-x)^4+2x^6F_4(-x)^2+x^{10}}{F_4(-x)^2F_5(-x)^2}.
%\frac{x^{10} + 8x^8 - 4x^7 - 10x^6 + 37x^5 - 50x^4 + 31x^3 - 9x^2 + x}{4x^6 - 28x^5 + 69x^4 - 74x^3 + 39x^2 - 10x + 1} \\
%\end{eqnarray*}


\section{$k$-associativity of left depth $d$}\label{sec:mod-nil}

In this section we study $\defcolor{C^d_{k,n}} := C_{*,n}$ and $\defcolor{\tC^d_{k,n}} := \tC_{*,n}$ for any binary operation $*$ satisfying \eqref{eq:mod-nil-lr} with $e=\ell=1$, i.e., when $t\sim_* t'$ if and only if $\ld(t) \sim_k^d \ld(t')$ for all $t,t'\in\T_n$. 

%\subsection{Equivalence classes}
We first study $(*,n)$-classes using rotations on binary trees.
%Given a node $v$ in a binary tree $t$, a \demph{subtree rooted at $v$} is a subtree of $t$ whose root is $v$, and the \demph{maximal subtree rooted at $v$} is the subtree consisting of all descendants of $v$, including $v$ itself.
Given two binary trees $s$ and $t$, we say \demph{$t$ contains $s$ at left depth $d$} if $t$ contains $s$ as a (possibly non-maximal) subtree rooted at a node of left depth $d$ and say \demph{$t$ avoids $s$ at left depth $d$} otherwise. 



Given binary trees $s$ and $t$, write $\defcolor{s\wedge t}$ for the binary tree whose root has left and right maximal subtrees $s$ and $t$, respectively.
%There is a natural bijection between the set of parenthesizations of $x_0*\cdots *x_n$ and the set $\defcolor{\T_n}$ of binary trees with $n+1$ leaves by replacing each $x_i$ by a leaf labeled $i$ and replacing each $*$ by $\wedge$.
%When we write $s\wedge t\wedge\cdots \wedge r$ without parentheses, we assume that the operations $\wedge$ are performed left-to-right.
Let $v$ be a node of $t$.
If the maximal subtree of $t$ rooted at $v$ can be written as $(t_0\wedge\cdots\wedge t_k)\wedge t_{k+1}$, where $t_0,\ldots,t_{k+1}$ are binary trees, then replacing this subtree with $t_0\wedge(t_1\wedge\cdots\wedge t_{k+1})$ in $t$ gives another binary tree $t'$.
Here the operations $\wedge$ in parentheses are performed left-to-right.
We call the operation $t\mapsto t'$ a \demph{right $k$-rotation at $v$} (see Fig.~\ref{fig:3-rotation}), and call the inverse operation $t'\mapsto t$ a \demph{left $k$-rotation at $v$}. 


\begin{figure}[h]
\[
\Tree[. [. [. [. {\nola} {\nola} ] {\nola} ] {\nola} ] {\nola} ] \quad\rightarrow\quad
%\Tree[. [. [. {\nola} [. {\nola} {\nola} ] ] {\nola} ] {\nola} ]
%\quad\rightarrow\quad
%\Tree[. [. {\nola}  [. [. {\nola}  !\qsetw{.2in} {\nola} ] {\nola} ] ]  !\qsetw{.5in} {\nola} ]
%\quad\rightarrow\quad
\Tree[. {\nola} !\qsetw{-.2in} [. [. [. {\nola} {\nola} ] {\nola} ] {\nola} ] ] 
\]
\caption{A right $3$-rotation}\label{fig:3-rotation}
\end{figure}

\begin{lemma}\label{lem:rotation}
A left or right $k$-rotation at a node $v$ in a binary tree $t$ produces another binary tree $t'$ satisfying $t\sim_k^d t'$ if and only if the left depth of $v$ in $t$ is at least $d-1$. 
\end{lemma}

\begin{comment}
A right $k$-rotation $t\mapsto t'$ at $v$ replaces the maximal subtree $t_0\wedge\cdots\wedge t_{k+1}$ of $t$ rooted at $v$ with $t_0\wedge(t_1\wedge\cdots\wedge t_{k+1})$.
This corresponds to a change in left depth by subtracting $k$ from the left depth of each leaf of $t_1$ and leaving the left depths of all other leaves of $t$ invariant. 
If $\ld(v)$ is the left depth of $v$ in $t$, then the rightmost leaf of $t_1$ has left depth $\ld(v)+1+k$ in $t$, which is the smallest among all leaves of $t$, and has left depth $\ld(v)+1$ in $t'$.
Hence $t \sim_k^d t'$ if and only if $\ld(v)\ge d-1$.
For a left $k$-rotation the proof is similar. 
\end{comment}

If $s\in \T_n$ can be obtained from $t\in \T_n$ by finitely many left $k$-rotations at nodes of left depths at least $d-1$ then we say $s\le_k^d t$.
We call this partial order on $\T_n$ the \demph{${d\choose k}$-order}, which includes the \defcolor{$k$-associative order} introduced in earlier work~\cite{CatMod} as a special case ($d=1$).
A binary tree minimal or maximal under the ${d\choose k}$-order is called \demph{${d\choose k}$-minimal} or \demph{${d\choose k}$-maximal}.
For each $k\ge1$ we define $\defcolor{\comb_k} := t_0\wedge\cdots\wedge t_k$ and $\defcolor{\comb_k^1} := t_0\wedge\comb_k$ where $t_0=\cdots=t_k$ is the unique tree in $\T_0$.
%Connected components of the Hasse diagram of the ${d\choose k}$-order on $\T_n$ are called \demph{${d\choose k}$-components}.

\begin{proposition}\label{prop:comb}
Let $t$ be a binary tree. For $d,k\ge1$ we have

\noindent(i) $t$ is ${d\choose k}$-minimal if and only if it avoids $\comb_k^1$ at each left depth at least $d-1$, and

\noindent(ii) $t$ is ${d\choose k}$-maximal if and only if it avoids $\comb_{k+1}$ at each left depth at least $d-1$.
\end{proposition}

%If a binary tree contains $\comb_k^1$ at left depth $d\ge\ell-1$ then applying a left $k$-rotation at this node gives another binary tree smaller than $t$ in the ${d\choose k}$-order.
%Hence an ${d\choose k}$-minimal binary tree must avoid $\comb_k^1$ at left depth $d$ for any $d\ge h-1$. 

\begin{comment}
Let $t\in\T_n$.
The \demph{left border} of $t$ is the set of all nodes with right depth zero in $t$. 
Let $r_1,r_2,\ldots,r_h$ be the nodes on the left border of $t$ so that $r_1$ is the root and $r_{i+1}$ is the left child of $r_i$ for all $i=1,\ldots,h-1$.
For $2\le i\le h$ we define a tree $\defcolor{t^{+i}}\in\mathcal T_{n+1}$ by first cutting $t$ at $r_i$ to get the maximal subtree $s$ of $t$ rooted at $r_i$ and another subtree $s'$ of $t$ with leftmost leaf $r_i$, and then inserting the tree $u\in\mathcal T_1$, identifying the root of $u$ with the leaf $r_i$ in $s'$ and the right leaf of $u$ with the root $r_i$ of $s$.
The tree $\defcolor{t^{+1}}$ is obtained analogously by attaching $t$ to the right leaf of the tree $u\in\mathcal T_1$.
By construction, $\ld(t^{+i})=(i,\ld_0(t),\dotsc,\ld_n(t))$ for all $i=1,2,\ldots,h$.
For example, the left picture below is a tree $t\in\mathcal T_8$ with $\ld(t) = (5,4,3,3,3,2,2,1,0)$ and the right picture below is the tree $t^{+3}\in\mathcal T_9$ with $\ld(t^{+3}) = (3,5,4,3,3,3,2,2,1,0)$.

\begin{figure}
{\vskip10pt\scriptsize
 \Tree[. [. [. [. [. {\nola} {\nola} ] {\nola} ] [. {\nola} [. {\nola} {\nola} ] ] ] [. {\nola} {\nola} ] ] {\nola} ] 
 \Tree[. [. [. {\nola} [. [. [. {\nola} {\nola} ] {\nola} ] [. {\nola} [. {\nola} {\nola} ] ] ] ] !\qsetw{1in} [. {\nola} {\nola} ] ] {\nola} ] }
\end{figure}

Conversely, write $\defcolor{t_-}$ for the binary tree in $\T_{n-1}$ obtained from $t\in\T_n$ by contracting the leftmost leaf, its sibling, and their parent to a single node.
One sees that $\ld(t^-) = (\ld_1,\ldots,\ld_n)$.
Thus $s\sim_k^d t$ implies $s^- \sim_k^d t^-$. 
Furthermore, if $\ld_0(t)=i$ then $t_-^{+i}:=(t_-)^{+i}=t$.
\end{comment}

%\begin{proposition}\label{prop:minimal}
%Assume $*$ satisfies \eqref{eq:mod-nil-lr} with $e=\ell=1$. 
%Every $(*,n)$-class has a unique ${d\choose k}$-minimal element.
%\end{proposition}

\begin{comment}
Since $\T_n$ is a finite set, each $(*,n)$-class must contain a ${d\choose k}$-minimal element.
%If a binary tree $t$ contains $\comb_k^1$ as a subtree rooted at a node of left depth at least $d-1$,  then $t$ is not ${d\choose k}$-minimal, since one can apply a left $k$-rotation at this node and the resulting tree $t'$ satisfies $t\sim_k^d t'$ by Lemma~\ref{lem:rotation}.
We prove by induction on $n$ that each $(*,n)$-class has only one ${d\choose k}$-minimal element.
Let $s$ and $t$ are distinct binary trees in $\T_n$ such that $s\sim_k^d t$. 
We need to show that either $s$ or $t$ is not ${d\choose k}$-minimal, i.e., contains $\comb_k^1$ at left depth at least $d-1$.

First assume $s_-\ne t_-$. 
Since $s\sim_k^d t$ implies $s_- \sim_k^d t_-$, it follows from the induction hypothesis that, either $s_-$ or $t_-$, say the former, contains $\comb_k^1$ at left depth at least $d-1$.
Hence $s$ also contains $\comb_k^1$ at left depth at least $d-1$.

Next assume $s_-=t_-$.
This together with $s\ne t$ implies that $i=\ld_0(s)$ and $j=\ld_0(t)$ are distinct.
Assume $i<j$, without loss of generality.
Then $s=s_-^{+i}=t_-^{+i}$ contains $\comb_{j-i}^1$ at left depth $i-1$. 
Since $s\sim_k^d t=t_-^{+j}$, we have $i\ge d$ and $j=i+km$ for some $m>0$.
%Since the left border of $t$ contains $j$ internal nodes, 
Thus $s$ contains $\comb_k^1$ at left depth $i-1\ge d-1$.
\end{comment}


\begin{theorem}\label{thm:mod-nil}
%Let $d,k\ge1$ and $n\ge0$.
%Assume $*$ is a binary operation satisfying \eqref{eq:mod-nil-lr} with $e=\ell=1$.
The $(*,n)$-classes are precisely the connected components of the Hasse diagram of the ${d\choose k}$-order on $\T_n$.
%the ${d\choose k}$-components of $\T_n$.
%one can be obtained from the other by a sequence of $k$-rotations at nodes of left depth at least $h-1$.
Every $(*,n)$-class has a unique ${d\choose k}$-minimal element.
\end{theorem}

\begin{comment}
By Lemma~\ref{lem:rotation}, each ${d\choose k}$-component of $\T_n$ is contained in some ${d\choose k}$-class.
We have the quality holds by Proposition~\ref{prop:minimal}.
\end{comment}

A subpath $L'$ of a lattice path $L$ is \demph{at height} $h$ if the initial point of $L'$ has height $h$.
We say $L$ \demph{avoids} $L'$ \demph{at height} $h$ if $L$ contains no subpath $L'$ at height $h$.

\begin{proposition}\label{prop:objects}
For $k,d\ge1$ and $n\ge0$, the number $C_{k,n}^d$ enumerates 

\noindent(i)
binary trees with $n+1$ leaves avoiding $\comb_k^1$ at any left depth at least $d-1$, and

%\item
%plane trees with multi-degree $(d_0,\ldots,d_n)$ satisfying $d_0+\cdots+d_{i-1}-i \ge d \Rightarrow d_i<k$, $\forall i\in[n]$,
\noindent(ii)
Dyck paths of length $2n$ avoiding $DU^k$ at height at least $d$.
\end{proposition}

\begin{comment}
By Proposition~\ref{prop:minimal} and Theorem~\ref{thm:mod-nil}, $C_{k,n}^d$ enumerates the ${d\choose k}$-minimal elements in $\T_n$. 
Combining this with Proposition~\ref{prop:comb} establishes (1).

A binary tree $t$ with $n+1$ leaves corresponds to a plane tree $T$ with $n+1$ nodes by contracting northeast-southwest edges in $t$. 
By~\cite[Proposition~2.10]{CatMod}, the relation between the left depth $\ld(t) = (\ld_0,\ldots,\ld_n)$ and the multi-degree $d(T) = (d_0,\ldots,d_n)$ is given by 
\[ \ld_i = d_0 + \cdots + d_i - i ,\quad\forall i\in\{0,1,\ldots,n\}.\]
A left $k$-rotation at a node $v$ in $t$ corresponds to an up $k$-slide at a node of degree $d_i\ge k$ in $T$ for some $i\in[n]$.
One can check that the left depth of $v$ equals $d_0+\cdots+d_{i-1}-i$.
Thus $t$ is ${d\choose k}$-minimal if and only if $d_0+\cdots+d_{i-1}-i \ge d \Rightarrow d_i<k$ for all $i\in[n]$.
This implies (2).

Next, a plane tree with multi-degree $(d_0,\ldots,d_n)$ corresponds to a Dyck path $U^{d_0}DU^{d_1}\cdots DU^{d_n}$.
The height of the initial point of the $i$th down-step in this Dyck path is $d_0+\cdots+d_{i-1}-i+1$.
Thus (3) follows from (2).
\end{comment}

\begin{remark}\label{rem:LimitCkd}
For any fixed $n$ and $k$, the limit of $C_{k,n}^d$ as $d\to\infty$ is the Catalan number $C_{n}$ since the constraints in Proposition~\ref{prop:objects} are redundant if $d$ is large enough.
\end{remark}

Let $\defcolor{M_{k,n}^d}$ be the number of binary trees in $\T_n$ avoiding $\comb_{k+1}$ at any node of left depth at least $d-1$.  %$k\ge0$
This number counts ${d\choose k}$-maximal elements in $\T_n$ by~Proposition~\ref{prop:comb}, and is  closely related to $C_{k,n}^d$.
The number $\defcolor{M_{k,n}} := M_{k,n}^1$ was called a \demph{generalized Motzkin number} in our previous work~\cite{CatMod} and also studied by Tak\'acs~\cite{Takacs}. 
%Things counted by $M_{k,n}^d$?
%\subsection{Generating functions}
For $d,k\ge1$ we define 
%\[ C_k^{(0)}(x) := \sum_{n\ge0} M_{k-1,n} x^{n+1} \qand
\[ \defcolor{C_k^d(x)} := \sum_{n\ge0} C_{k,n}^d x^{n+1} \qand
\defcolor{M_{k-1}^d(x)} := \sum_{n\ge0} M_{k-1,n}^d x^{n+1}. \]
%We also set .
%To study these generating functions we use Lagrange inversion~{Stanley~\cite[Theorem~5.4.2]{EC2}}.
%Suppose that $A(x)$ and $B(x)$ are formal power series such that $A(0)=B(0)=0$ and $A(B(x))=x$. Let $n,\ell\in\ZZ$. Then 
%\[ n[x^n]B(x)^\ell = \ell[x^{n-\ell}] (x/A(x))^n.\]

%Also recall the following binomial expansion for $m\ge0$:
%\[ (1+x)^n = \sum_{i\ge0} {n\choose i} x^i. \]
%In particular, when $n=-m$ is a negative integer we have
%\[ (1-x)^{-m} = \sum_{i\ge0} {m+i-1\choose i} x^i. \]

\begin{proposition}\label{prop:Ckd}
For $m,n,d\ge0$ and $k\ge1$ we have (with $\defcolor{C_k^0(x)} := M_{k-1}^1(x)$)
\[ C_k^{d+1}(x) = x \Big/ \left( 1-C_k^d(x) \right) \qand \]% = \sum_{m\ge0} x \left( C_k^d(x) \right)^m
\[ [x^{n+m}] C_k^{d+1}(x)^m = \sum_{0\le i\le n} { m+i-1 \choose i} [x^n] C_k^d(x)^i. \]
\end{proposition}

\begin{comment}
For $d=0$ the first equation follows from~\cite[(6)]{CatMod}.
Assume $d\ge1$. Let $t\in\T_n$ with $n\ge1$. 
Denote by $t_L$ and $t_R$ the maximal subtrees rooted at the left and right children of the root of $t$.
By Proposition~\ref{prop:comb}, $t$ is ${d+1\choose k}$-minimal if and only if $t_L$ is ${d\choose k}$-minimal and $t_R$ is ${d+1\choose k}$-minimal. 
Combining this with Proposition~\ref{prop:objects} we have
\[ C_k^{d+1}(x) =  x + C_k^d(x) C_k^{d+1}(x)\]
This implies the first equation.
Applying the binomial expansion gives the second equation.
\end{comment}

\begin{proposition}\label{prop:MC}
%For $n,d\ge0$ and $k\ge1$ we have $M_{k-1}^{d+1}(x) = C_k^d(x)$ and $M_{k-1,n}^{d+1} = C_{k,n}^d$.
For $d,k\ge1$ and $n\ge0$ we have 
$M_{k-1}^{d}(x) = C_k^{d-1}(x)$, $M_{k-1,n}^{d} = C_{k,n}^{d-1}$, and $M_{k-1,n}^d \le C_{k,n}^d\le M_{k,n}^d$.
%Combining Proposition~\ref{prop:MC} and Corollary~\ref{cor:interlace} 
%
%
%
%Consequently, we have the following diagram for $d,k\ge1$.
%\[ \xymatrix @R=7pt @C=1pt { 
%\cdots & & \cdots \ar@{=}[d] & & \cdots & & \cdots \ar@{=}[d] & & \cdots & & \cdots \ar@{=}[d] & & \cdots \\
%\cdots & \le & M_{k-1,n}^d & \le & C_{k,n}^d \ar@{=}[d] & \le & M_{k,n}^d & \le & C_{k+1,n}^d \ar@{=}[d] & \le & M_{k+1,n}^d & \le & C_{k+2,n}^d & \le & \cdots \\
%& & \cdots & \le & M_{k-1,n}^{d+1} & \le & C_{k,n}^{d+1} & \le & M_{k,n}^{d+1} & \le & C_{k+1,n}^{d+1} & \le & M_{k+1,n}^{d+1} \ar@{=}[u] & \le & C_{k+2,n}^{d+1} & \le & \cdots \\
%& & & & \cdots & & \cdots \ar@{=}[u] & & \cdots & & \cdots \ar@{=}[u] & & \cdots & & \cdots \ar@{=}[u] & & \cdots \\
%} \]
%
%
Consequently, we have the following additional inequalities for $d,k\ge 1$:
\[\cdots\le C_{k,n}^d \le C_{k,n}^{d+1} \le C_{k+1,n}^d \le C_{k+1,n}^{d+1} \le C_{k+2,n}^{d} \le C_{k+2,n}^{d+1} \le \cdots.\]
\end{proposition}

\begin{comment}
The result holds for $d=0$ by definition. 
Similarly to the proof of Proposition~\ref{prop:Ckd}, we have
\[ M_k^{d+1}(x) =  x + M_k^d(x) M_k^{d+1}(x), \quad\forall\, d,k\ge0.\]
Hence $M_k^{d+1}(x) = x/(1-M_k^d(x))$.
The result then follows from induction on $d$.
\end{comment}
 
%\begin{corollary}\label{cor:interlace}
%For $d,k\ge1$ and $n\ge0$ we have $M_{k-1,n}^d \le C_{k,n}^d\le M_{k,n}^d$.
%\end{corollary}

\begin{comment}
The first inequality follows from Proposition~\ref{prop:comb} and the second from Proposition~\ref{prop:minimal}.
\end{comment}

%Question: bijective proof?


\begin{proposition}
For $d\ge1$ and $n\ge0$ we have $M_1^d(x) = C_1^d(x)$ and $M_{1,n}^d = C_{1,n}^d$.
\end{proposition}

\begin{comment}
We have $M_1^{1}(x) = x/(1-x) = C_1^{1}(x)$. 
The result then follows from induction on $d$, using the recurrence relations in Proposition~\ref{prop:Ckd} and the proof of Proposition~\ref{prop:MC}.
\end{comment}


\subsection{The case $k\le3$}\label{sec:k=3}

We studied $C_{1,n}^d = C^d_n = C^{d,1}_n$ in Section~\ref{sec:nil}.
We now give their relationship to $C_{2,n}^d$.

\begin{proposition}\label{prop:k=2}
For $d,n\ge0$ we have $C_2^d(x) = C_1^{d+1}(x)$ and $C_{2,n}^d=C_{1,n}^{d+1}$.
\end{proposition}

\begin{comment}
By definition, $C_{2}^{0}(x) = x/(1-x) =C_1^{1}(x)$.
By Proposition~\ref{prop:Ckd}, we have the same recurrence relation $C_k^{d+1}(x) = x/(1-C_k^d(x))$ for all $k\ge1$.
The result follows from induction on $d$.
\end{comment}

Next, we study $C_{3,n}^d$. 
It follows from our earlier work~\cite{CatMod} that $C_{3,n}^{0}$ is the \demph{Motzkin number}~\cite[A001006]{OEIS}, which has many closed formulas, and its generating function is
\[ C_3^{0}(x) = \frac{1 - x - \sqrt{1-2x-3x^2} }{2x} = \frac x{1-x-\frac{x^2}{1-x-\frac{x^2}{\cdots} } }.\]
Applying Proposition~\ref{prop:Ckd} to this gives a continued fraction
\begin{equation}\label{eq:C3} 
C_3^d(x) = \frac{x}{1-\frac{x}{1- \cdots \frac{x}{1-C_3^{0}(x) }} } 
\end{equation}
where the number of ones is $d$.
Equation~\eqref{eq:C3} is a special case of the generating function studied by Flajolet~\cite{Flajolet} for \demph{labeled positive paths}.
Such a path $L$ starts at $(0,0)$ and stays weakly above the line $y=0$, with three kinds of steps $U=(1,1)$, $D=(1,-1)$, and $H=(1,0)$.
Each step is labeled with some weight, and the \demph{total weight} of $L$ is the sum of all weights of the steps.
The \demph{height} of $L$ is the largest $y$-coordinate of a point on $L$.


%Taking the limit of $C_3^d(x)$ as $d\to\infty$ gives the generating function of the Catalan numbers.
By Equation~\eqref{eq:C3} or Remark~\ref{rem:LimitCkd}, the number $C_{3,n}^d$ interpolates between the Motzkin number $C_{3,n}^0$ and the Catalan number $C_n=\lim_{d\to\infty} C_{3,n}^d$.
For $d=1,\ldots,5$, the sequences $\{C_{3,n}^d\}$ are recorded in The OEIS~\cite[A005773, A054391--A054394]{OEIS}. 
For an arbitrary $d$, Barcucci, Del Lungo, Pergola, and Pinzani~\cite{CatPerm} studied $C_{3,n}^d$ in terms of permutations avoiding certain \demph{barred patterns} and provided a closed formula~\cite[p. 47]{CatPerm} for the generating function $C_3^d(x)$, but no formula for the number $C_{3,n}^d$. 


\begin{comment}
As a warm-up, we derive some closed formulas for $C_{3,n}^0$, which are probably well known, from the generating function $C_3^0(x)$. 
(\edit{This should be condensed in the final version.})
We have
\[ \sqrt{1-2x-3x^2} = \sqrt{1-3x} \cdot \sqrt{1+x}  = \left( \sum_{i\ge0} \binom{1/2}{i} (-3x)^i \right) \left( \sum_{j\ge0} \binom{1/2}{j} x^j \right) .\]
Thus for $n\ge0$,
\[ C_{3,n}^0 = -\frac12 \sum_{0\le i\le n+2} (-3)^i\binom{1/2}{i} \binom{1/2}{n+2-i}. \]
On the other hand, we have
\[ \sqrt{1-2x-3x^2} = \sum_{i\ge0} \binom{1/2}{i} (-x)^i(2+3x)^i = \sum_{i\ge0} \binom{1/2}{i} (-x)^i \sum_{0\le j\le i} \binom{i}{j} 2^{i-j}3^jx^j. \]
Thus 
\[ C_{3,n}^0 = -\frac12 \sum_{0\le j\le (n+2)/2} (-1)^{n+2-j} 2^{n+2-2j} 3^j \binom{1/2}{n+2-j} \binom{n+2-j}{j}.\]
\end{comment}


\begin{proposition}
For $d,n\ge0$ the number $C_{3,n}^d$ enumerates

\noindent (i) labeled positive paths with no $H$-step strictly below $y=d$ and with total weight $n$, where each $U$-step or $D$-step weakly below $y=d$ has a weight $1/2$ and each other step has a weight $1$, and

\noindent (ii) permutations of $1,2,\ldots,n$ avoiding $321$ and $(d+3)\bar1(d+4)23\cdots(d+2)$ (barred pattern).
\end{proposition}


\begin{comment}
A specialization of work of Flajolet~\cite[Theorem 1]{Flajolet} gives the first family of objects enumerated by $C_{3,n}^d$.
The second one follows from Barcucci, Del Lungo, Pergola, and Pinzani~\cite[(12)]{CatPerm}.
%Let $\SS_n^{(j)}$ be the set of permutations of $[n]$ avoiding $321$ and $(j+2)\bar1(j+3)2\cdots(j+1)$ for $j\ge1$.
%It is well known that $\{ |\SS_n^{(1)}| \}$ is the sequence of Motzkin numbers~\cite[A001006]{OEIS}, which agrees with $\{C_{3,n}^{0}\}$.
%By Barcucci, Del Lungo, Pergola, and Pinzani~\cite[(12)]{CatPerm}, the generating functions 
%\[ \overline M^{(j)}(x) := \sum_{n\ge0} \left| \SS_n^{(j)} \right| x^n\]
%satisfy the recurrence relation $\overline M^{(j)}(x) = 1/(1-x\overline M^{(j-1)}(x))$ for all $j\ge2$.
%Comparing this with Proposition~\ref{prop:Ckd} we have $C_3^d(x) = x \overline M^{(d+1)}(x)$ for all $d\ge0$.
\end{comment}

We give a new closed formula for $C_3^d(x)$ %different from the existing formula~\cite[p. 47]{CatPerm} 
and derive a closed formula for $C_{3,n}^d$ from that.
We have not found the sequences $\{ C_{k,n}^d \}$ for $k\ge4$ (and $d\ge2$) in The OEIS.

\begin{theorem}\label{thm:C3d}
For $d\ge0$ we have
\[ C_3^d(x) = \frac{2xF_{d+1}(x)F_{d+2}(x)-x^d-x^{d+1} + x^d\sqrt{1-2x-3x^2}}{2(F_{d+2}(x)^2-x^d-x^{d+1})}. \]
%=  \frac{2xF_{d+1}(x)F_{d+2}(x)-x^d-x^{d+1} + x^d\sqrt{1-2x-3x^2}}{2(F_{d+1}(x)F_{d+3}(x)-x^d)}
\end{theorem}

\begin{comment}
We induct on $d$. 
The result is trivial if $d=0$. 
For $d\ge1$, it follows from Proposition~\ref{prop:Ckd} and the induction hypothesis that
\begin{align*}
C_3^d(x) &= \frac{x}{1-C_3^{d-1}(x)} \\
&= \frac{2x(F_{d+1}(x)^2-x^{d-1}-x^{d}) }{2F_{d+1}(x)^2-2x^{d-1}-2x^d-2xF_{d}(x)F_{d+1}(x)+x^{d-1}+x^{d} - x^{d-1}\sqrt{1-2x-3x^2}} \\
&= \frac{2x(F_{d+1}(x)^2-x^{d-1}-x^{d}) } {2F_{d+1}(x)F_{d+2}(x)-x^{d-1}-x^d-x^{d-1}\sqrt{1-2x-3x^2}} \\
&= \frac{2x(F_{d+1}(x)^2-x^{d-1}-x^{d}) (2F_{d+1}(x)F_{d+2}(x)-x^{d-1}-x^d + x^{d-1}\sqrt{1-2x-3x^2}) } {(2F_{d+1}(x)F_{d+2}(x)-x^{d-1}-x^d)^2-x^{2d-2}(1-2x-3x^2)} \\
&= \frac{(2F_{d+1}(x)^2-2x^{d-1}-2x^{d})(2xF_{d+1}(x)F_{d+2}(x)-x^{d}-x^{d+1} + x^{d}\sqrt{1-2x-3x^2})}{4F_{d+1}(x)^2 F_{d+2}(x)^2-4(x^{d-1}+x^d)F_{d+1}(x)F_{d+2}(x) +4x^{2d-1}+4x^{2d} }.
\end{align*}
This implies the desired expression of $C_3^d(x)$ since
\begin{align*}
& (F_{d+1}(x)^2-x^{d-1}-x^{d}) (F_{d+2}(x)^2-x^d-x^{d+1}) \\
=& F_{d+1}(x)^2 F_{d+2}(x)^2 - (x^{d-1}+x^d) (F_{d+2}(x)^2+xF_{d+1}^2(x)) + x^{2d-1}+2x^{2d}+x^{2d+1} \\
=& F_{d+1}(x)^2 F_{d+2}(x)^2 - (x^{d-1}+x^d) F_{d+2}(x)F_{d+1}(x) +x^{2d-1}+x^{2d}.
\end{align*}
Here the last step follows from
\[ F_{d+2}(x)^2+xF_{d+1}^2(x) = F_{d+2}(x)F_{d+1}(x)-xF_{d+2}(x)F_d(x) + xF_{d+1}^2(x)
= F_{d+2}(x)F_{d+1}(x)+x^{d+1} \]
as one can show $F_{d+1}(x)^2-F_d(x) F_{d+2}(x) = x^d$ by induction on $d$.
%$F_{d+1}(x)F_{d+2}(x) - F_d(x)F_{d+3}(x) = x^d$
\end{comment}

%For example, we have 
%\[ C_3^{0}(x) = \frac{1 - x - \sqrt{1-2x-3x^2} }{2x} \]
%\[ C_3^1(x) %= \frac{2x^2}{3x-1 + \sqrt{1-2x-3x^2} } 
%= \frac{x-3x^2+x\sqrt{1-2x-3x^2}}{2(1-3x)}, \quad C_3^2(x) = \frac{2x-7x^2+3x^3 +x^2\sqrt{1-2x-3x^2}}{2(1-4x+3x^2-x^3)} .\] %x(1-3x)(2-x)
%\[ C_3^3(x) = \frac{2x-10^2+13x^3-5x^4 +x^3\sqrt{1-2x-3x^2}}{2(1-6x+11x^2-7x^3)} \] %x(1-x)(2-8x+5x^2)

%Next, we derive a closed formula for $C_{3,n}^d$ from the expression of $C_3^d(x)$ given by Theorem~\ref{thm:C3d}.

\begin{theorem}\label{thm:C3dn}
For $d\ge1$ and $n\ge0$ we have
%%% I CHANGED THE FOLLOWING: THE OLD VERSION IS COMMENTED OUT BELOW.
{ \begin{align*}
C_{3,n}^d = \sum_{ \substack{ \alpha\models n+1 \\ h>1\Rightarrow \alpha_h\le d+1} } 
& -\left( C_{3,\alpha_1-d-2}^0 %\frac{\binom{\alpha_1-d-1}{1}_2}{\alpha_1-d-1} 
+ \frac{\delta_{\alpha_1,d}}2 +  (-1)^{\alpha_1}\sum_{i+j=\alpha_1-1} \binom{d-i}{i} \binom{d+1-j}{j} \right) \\
& \cdot \prod_{h\ge2} \left( \left(\delta_{\alpha_h,d}+(-1)^{\alpha_h-1}\sum_{i+j=\alpha_h} \binom{d+1-i}{i} \binom{d+1-j}{j} \right) \right) 
\end{align*} }
%%% BEGINNING OF WHAT USED TO BE IN THE FORMULA %%%
%{\small \begin{align*}
%C_{3,n}^d = \sum_{ \substack{ \alpha\models n+1 \\ h>1\Rightarrow \alpha_h\le d+1} } 
%& \left( -\frac{\delta_{\alpha_1,d}}2 +  (-1)^{\alpha_1-1}\sum_{i+j=\alpha_1-1} \binom{d-i}{i} \binom{d+1-j}{j} + \sum_{i+j=\alpha_1-d} \frac{(-3)^i}2 \binom{\frac12}{i} \binom{\frac12}{j} \right) \\
%& \cdot \prod_{h\ge2} \left( \left(\delta_{\alpha_h,d}+(-1)^{\alpha_h-1}\sum_{i+j=\alpha_h} \binom{d+1-i}{i} \binom{d+1-j}{j} \right) \right) 
%\end{align*} }
%%% END OF WHAT USED TO BE IN THE FORMULA %%%
where 
\[ \defcolor{C_{3,m}^0} :=
\begin{cases} 1/2, & m=-1, \\
-1/2, & m=-2, \\
0 , & m\le-3, 
\end{cases} 
\quad \text{and} \quad 
\defcolor{\delta_{m,d}}:=
\begin{cases} 
1, & m\in\{d,d+1\}, \\ 
0, & \text{otherwise.} 
\end{cases} \]
\end{theorem}

\begin{comment}
We have
\[ F_r(x)F_s(x) = \sum_{0\le i\le (r-1)/2} (-x)^i\binom{r-1-i}{i} \sum_{0\le j\le (s-1)/2} (-x)^j\binom{s-1-j}{j}, \]
%&= \sum_{0\le n\le (r+s-2)/2} (-1)^n x^{n} \sum_{i+j=n} \binom{r-1-i}{i} \binom{s-1-j}{j} ,
%\begin{align*}
%xF_{d+1}(x)F_{d+2}(x) 
%&= x \sum_{0\le i\le d/2} (-x)^i\binom{d-i}{i} \sum_{0\le j\le (d+1)/2} (-x)^j\binom{d+1-j}{j} \\
%&= \sum_{0\le n\le d} (-1)^n x^{n+1} \sum_{\max\{0,n-\frac{d+1}2\}\le i\le \min\{n,\frac d2\}} %\binom{d-i}{i} \binom{d+1+i-n}{n-i} 
%\end{align*}
%\[ F_{d+2}(x)^2 = \sum_{0\le n\le d+1} (-1)^n x^{n} \sum_{i+j=n} \binom{d+1-i}{i} \binom{d+1-j}{j} \]
\[ \sqrt{1-2x-3x^2} = \sqrt{1-3x} \cdot \sqrt{1+x}  = \left( \sum_{i\ge0} \binom{1/2}{i} (-3x)^i \right) \left( \sum_{j\ge0} \binom{1/2}{j} x^j \right) .\]
%\[ \sqrt{1-2x-3x^2} = \sum_{i\ge0} \binom{1/2}{i} (-x)^i(2+3x)^i = \sum_{i\ge0} \binom{1/2}{i} (-x)^i \sum_{0\le j\le i} \binom{i}{j} 2^{i-j}3^jx^j. \]
Hence
\begin{align*}
& 2xF_{d+1}(x)F_{d+2}(x)-x^d-x^{d+1} + x^d\sqrt{1-2x-3x^2} \\
=& \sum_{n\ge1} x^{n} \left( -\delta_{n,d} +  (-1)^{n-1}2\sum_{i+j=n-1} \binom{d-i}{i} \binom{d+1-j}{j} + \sum_{i+j=n-d} (-3)^i \binom{1/2}{i} \binom{1/2}{j} \right) ,
\end{align*}
\[ F_{d+2}(x)^2-x^d-x^{d+1} = 1 - \sum_{1\le n\le d+1} x^{n} \left(\delta_{n,d}+(-1)^{n-1}\sum_{i+j=n} \binom{d+1-i}{i} \binom{d+1-j}{j} \right) .\] 
Substituting these expressions in the formula for $C_3^d(x)$ given by Theorem~\ref{thm:C3d} and extracting the coefficient of $x^{n+1}$ we obtain the desired formula for $C_{3,n}^d$. 
\end{comment}


%\edit{In order to apply the recurrence $C_k^d(x) = x/(1-C_k^{d-1}(x))$, we have to know $C_k^0(x)=C_k(x)$, which was studied in our earlier work~\cite{CatMod}.
%We did not have any closed formula for $C_k(x)$ when $k\ge4$, but we had some closed formulas for $C_{k,n}$.
%Perhaps one could substitute these formulas in $C_k(x)=\sum_{n\ge0} C_{k,n}x^{n+1}$ to find a formula for $C_k^d(x)$.}


\subsection{The case $d\le2$}\label{sec:d=2}
As the second formula in Proposition~\ref{prop:Ckd} gives a way to obtain the number $C_{k,n}^{d+1}$ from $C_k^d(x)^m$, we study $[x^{n+m}]C_k^d(x)^m$ for fixed $d$.
We first generalize the closed formulas~\cite[(9) and (11)]{CatMod} for $C_k^{0}(x) = M_{k-1}(x)$ and $C_k^{1}(x) = C_k(x)$.
%To state our result, we review some notation below.
%Let $\lambda=(\lambda_1,\ldots,\lambda_n)$ be a partition with $m_i$ parts equal to $i$ for $i=0,1,2,\ldots$.
%Then $|\lambda|=n$ if and only if $m_1+2m_2+\cdots+km_k=n$, and $\lambda\subseteq k^n$ if and only if $m_0+\cdots+m_k=n$ and $m_{k+1}=m_{k+2}=\cdots=0$.
Recall that the \demph{monomial symmetric function} $m_\lambda(x_1,\ldots,x_n)$ indexed by a partition $\lambda=(\lambda_1,\ldots,\lambda_n)$ is the sum of $x_1^{a_1}\cdots x_n^{a_n}$ for all rearrangement $(a_1,\ldots,a_n)$ of the partition $\lambda=(\lambda_1,\ldots,\lambda_n)$. 
%Taking $x_1=\cdots=x_n=1$ in $m_\lambda$ gives %the multinomial coefficient % in Proposition~\ref{prop:C^l}:
%\[ m_\lambda(1^n) = {n\choose m_0,m_1,m_2,\ldots}. \]

%\begin{equation}\label{eq:monomial}
%\prod_{1\le i\le n} (1+x_i+x_i^2+\cdots+x_i^k)^n = \sum_{\lambda\subseteq k^n} m_\lambda(x_1,\ldots,x_n). 
%\end{equation}

\begin{proposition}\label{prop:l=0}
For $k,m\ge1$ and $n\ge0$, the number of plane forests with $m$ components and $n+m$ nodes, each of degree less than $k$, is 
\begin{align*}
[x^{n+m}] M_{k-1}(x)^m %= \frac{m}{n+m} [x^n] \frac{(1-x^k)^{n+m}} {(1-x)^{n+m} } 
&= \frac{m}{n+m} \sum_{0\le j\le n/k} (-1)^j {n+m\choose j} {2n+m-jk-1\choose n+m-1} \\
&= \frac{m}{n+m} \sum_{ \substack{ \lambda\subseteq(k-1)^{n+m} \\ |\lambda|=n } } m_\lambda(1^{n+m}). 
\end{align*}
\end{proposition}

\begin{comment}
The result follows from~\cite[Proposition~4.5 and (12)]{CatMod}. 
For completeness we include a direct proof here.
Plane forests with $m$ components and $n+m$ total nodes, each of degree less than $k$, are enumerated by $[x^{n+m}]M_{k-1}(x)^m$.
We have $M_{k-1}(x) = x( 1 - M_{k-1}(x)^k ) / (1-M_{k-1}(x) )$ by~\cite[(5)]{CatMod}.
Applying Lagrange inversion to $A(x) = x(1-x)/(1-x^k)$ and $B(x) = M_{k-1}(x)$ gives
\begin{eqnarray}
 [x^n](M_{k-1}(x))^m &=& \frac{m}{n} [x^{n-m}] \frac{(1-x^k)^{n}} {(1-x)^n} \label{eq:l=0a} \\
 &=& \frac{m}{n} [x^{n-m}] \left(1+x+x^2+\cdots+x^{k-1}\right)^n. \label{eq:l=0b}
\end{eqnarray}
Applying binomial expansion to \eqref{eq:l=0a} and replacing $n$ with $n+m$ gives the first formula.
Applying \eqref{eq:monomial} to \eqref{eq:l=0b} and replacing $n$ with $n+m$ gives the second formula.
\end{comment}

\begin{remark} 
%For $k=1$ we have $M_{k-1}(x) = x$. Thus
We have $([x^{n+m}] M_0(x)^m)_{n\ge0} = (1,0,0,\ldots)$ for any fixed $m\ge0$ and also 
%For $k=2$ we have $M_{k-1}(x) = x/(1-x)$. Thus 
$[x^{n+m}] M_{1}(x)^m = {m+n-1\choose n}$ for all $m,n\ge0$.
For $k=3$ the array $([x^{n+m}]M_{k-1}(x)^m)_{m,n\ge0}$ gives the diagonals of the Motzkin triangle~\cite[A026300]{OEIS}; see~\cite[A002026, A005322--A005325]{OEIS} for $m=2,\ldots,6$.
We find no result in The OEIS when $k\ge4$ and $m\ge2$.
\end{remark}

\begin{proposition}\label{prop:d=1}
For $k,m,n\ge1$, the number of plane forests with $m$ components and $n$ non-root nodes, each of degree less than $k$, is 
\begin{align*}
[x^{n+m}] C_k(x)^m &= \frac{m}{n} \sum_{0\le j\le (n-1)/k} (-1)^j {n\choose j} {2n+m-jk-1\choose n+m} \\
&= \sum_{\lambda\subseteq(k-1)^n} \frac{n-|\lambda|}{n}{m+n-|\lambda|-1\choose n-|\lambda|} m_\lambda(1^n).
%\sum_{1\le i\le n} \frac{i}{n}{m+i-1\choose i} \sum_{ \substack{ \lambda\subseteq(k-1)^n \\ |\lambda|=n-i} } m_\lambda(1^n).
\end{align*}
\end{proposition}

\begin{comment}
Combining Proposition~\ref{prop:Ckd} with \eqref{eq:l=0a} we have
\begin{eqnarray}
[x^{n+m}] C_k(x)^m %&=& \sum_{i\ge0} { m+i-1 \choose i} [x^n](C_k^{(0)}(x))^i \\
%&=& \sum_{i\ge0} { m+i-1 \choose i} \frac i n \sum_{0\le j\le (n-i)/k } (-1)^j {n\choose j} {2n-i-1-jk \choose n-1} \\
&=& \sum_{1\le i\le n} { m+i-1 \choose i} \frac{i}{n} [x^{n-i}] \frac{(1-x^k)^n} {(1-x)^{n} } \label{eq:d=1a} \\
&=& \sum_{1\le i\le n} \frac{m}{n} { m+i-1\choose i-1} [x^{n-i}] \frac{(1-x^k)^n} {(1-x)^{n} } \label{eq:d=1b} \\
&=& \frac{m}{n} [x^{n-1}] \frac{(1-x^k)^n} { (1-x)^{n+m+1} } \label{eq:l=1c}
%&=& \frac{m}{n} \sum_{0\le j\le (n-1)/k} (-1)^j {n\choose j} {2n+m-jk-1\choose n+m} 
%&=& \frac{m}{n} {m+2n-1\choose m+n} + m \sum_{1\le j\le (n-1)/k} \frac{(-1)^j}{j} {n-1\choose j-1} {m+2n-jk-1\choose m+n}
\end{eqnarray} 
Applying binomial expansion to \eqref{eq:l=1c} gives the first formula.
Applying \eqref{eq:monomial} to \eqref{eq:d=1a} gives the second formula.
\end{comment}

A \demph{weak composition} of $n$ with $m$ parts is a sequence of $m$ nonnegative integers whose sum is $n$.
For $k=1,2$, Proposition~\ref{prop:d=1} is related to weak compositions.

\begin{corollary}\label{cor:l=1}
For $m,n\ge0$, weak compositions of $n$ with $m$ parts are enumerated by 
\[ [x^{n+m}] C_1(x)^m = {m+n-1\choose n} \]
and weak compositions of $n$ with $m-1$ zero parts are enumerated by
\[ [x^{n+m}] C_2(x)^m = \sum_{0\le i\le m} {m\choose i} {n-1\choose n-i} 2^{n-i}
= \sum_{0\le i \le n} {m+i-1 \choose i} {n-1\choose n-i}.\]
\end{corollary}

\begin{comment}
By Proposition~\ref{prop:d=1}, weak compositions of $n$ into $m$ parts are enumerated by 
\[ [x^{n+m}]C_1(x)^m = {m+n-1\choose n} \]
since they are in bijection with plane forests with $m$ components and $n$ non-root nodes, each of degree less than $k=1$.
In fact, such a forest is completely determined by the numbers of non-root nodes in its components.   
This implies the above bijection.
%Taking $k=1$ in Proposition~\ref{prop:d=1} gives the desired formula for $[x^{n+m}]C_1(x)^m$.

Similarly, weak compositions of $n$ with $m-1$ zero parts are enumerated by $[x^{n+m}]C_2(x)^m$, since they are in bijection with plane forests with $m$ components and $n$ non-root nodes, each of degree less than $k=2$. 
To see this bijection, let $v_1,\ldots,v_r$ be the children of the roots of such a forest.
Since non-root nodes have degree at most one, the maximal subtree rooted at each $v_i$ is a path consisting of $a_i$ nodes, and this forest is determined by $a_1,\ldots,a_r$.
We have $a_1+\cdots+a_r=n$ and thus $(a_1,0,a_2,0,\ldots,a_{r-1},0,a_r)$ is a weak composition of $n$ with $m-1$ zero parts. 

Now using Proposition~\ref{prop:Ckd} and Proposition~\ref{prop:k=2} we have
\begin{align*}
[x^{n+m}]C_2(x)^m &= [x^n] \frac{(1-x)^m}{(1-2x)^m} \\
&= [x^n] \left(1+\frac{x}{1-2x}\right)^m \\
&= \sum_{0\le i\le m} {m\choose i} [x^{n-i}](1-2x)^{-i} \\
&= \sum_{0\le i\le m} {m\choose i} {n-1\choose n-i} 2^{n-i} .
\end{align*}
%Combining the formula of $[x^{n+m}]C_1(x)^m$ with Proposition~\ref{prop:Ckd} we have 
The second formula of $[x^{n+m}]C_2(x)^m$ follows from \eqref{eq:d=1a}.
\end{comment}

\begin{comment}
One cannot write ${n-1\choose n-i} = {n-1\choose i-1}$ in the above corollary since when $n=0$ we have ${-1\choose 0} = 1 \ne 0 = {-1\choose -1}$. 
(\edit{Remove this remark?})
\end{comment}

The case $k=1$ of Corollary~\ref{cor:l=1} is well known and the case $k=2$ has been studied by Janji\'c and Petkovi\'c~\cite{WeakComp} with a different approach from ours.
For $k=2$ and $1\le m\le 10$ see the sequences~\cite[A011782, A045623, A058396, A062109, A169792--A169797]{OEIS}.
%The sequence $\{[x^{n+2}]C_3(x)^2\}_{n\ge0}$ is related to directed animals
We find no result for $k\ge3$ and $m\ge2$ except the special case $(k,m)=(3,2)$~\cite[A036908]{OEIS}.

Now we study the case $d=2$.

\begin{proposition}
Let $m,n\ge0$ and $k\ge1$. Then
{\small \begin{align*}
[x^{n+m}] C_k^{2}(x)^m &= {m+n-1\choose n} + \sum_{i=1}^{n-1} {m+i-1\choose i} \frac{i}{n-i} \sum_{0\le j\le \frac{n-i-1}k} (-1)^j {n-i\choose j} {2n-i-jk-1\choose n} \\
&= {m+n-1\choose n} + \sum_{i=1}^{n-1} {m+i-1\choose i} \sum_{\lambda\subseteq(k-1)^{n-i}} \frac{n-i-|\lambda|}{n-i}{n-|\lambda|-1\choose n-|\lambda|-i} m_\lambda(1^{n-i}).
\end{align*} }
In particular,
\begin{align*}
C_{k,n}^{2} (x) &= 1+ \sum_{i=1}^{n-1} \frac{i}{n-i} \sum_{0\le j\le (n-i-1)/k} (-1)^j {n-i\choose j} {2n-i-jk-1\choose n} \\
&= 1 + \sum_{i=1}^{n-1} \sum_{\lambda\subseteq(k-1)^{n-i}} \frac{n-i-|\lambda|}{n-i}{n-|\lambda|-1\choose n-|\lambda|-i} m_\lambda(1^{n-i}).
\end{align*}
\end{proposition}

\begin{comment}
Proposition~\ref{prop:Ckd} implies
\begin{eqnarray*}
[x^{n+m}] C_k^{2}(x)^m &=& \sum_{0\le i\le n} {m+i-1\choose i} [x^n] C_k^{1}(x)^i \\
&=& {m+n-1\choose n} + \sum_{1\le i\le n-1} {m+i-1\choose i} [x^n] C_k^{1}(x)^i. 
\end{eqnarray*}
Substituting formulas from Proposition~\ref{prop:d=1} establishes the result.
\end{comment}

\begin{comment}
Details of the above proof: (\edit{Remove this from the final version?})
\begin{eqnarray*}
[x^{n+m}] C_k^{2}(x)^m &=& \sum_{0\le i\le n} {m+i-1\choose i} [x^n] C_k^{1}(x)^i \\
&=& {m+n-1\choose n} + \sum_{1\le i\le n-1} {m+i-1\choose i} \frac{i}{n-i} [x^{n-i-1}] \frac{(1-x^k)^{n-i}} { (1-x)^{n+1} } \\
&=& {m+n-1\choose n} + \sum_{1\le i\le n-1} {m+i-1\choose i} \frac{i}{n-i} \sum_{0\le j\le (n-i-1)/k} (-1)^j {n-i\choose j} {2n-i-jk-1\choose n} \\
&=& {m+n-1\choose n} + \sum_{1\le i\le n-1} {m+i-1\choose i} \frac{i}{n-i} {2n-i-1\choose n} \\
& & + m \sum_{1\le i\le n-1} { m+i-1 \choose i-1} \sum_{1\le j\le (n-i-1)/k} \frac{(-1)^j}{j} {n-i-1\choose j-1} {2n-i-jk-1\choose n}  \\
&=& {m+n-1\choose n} + \frac{m}{n} \sum_{1\le i\le n-1} {m+i-1\choose i-1} {2n-i-1\choose n-i}  \\
& & + m \sum_{1\le j\le (n-2)/k} \frac{(-1)^j}{j} \sum_{1\le i\le n-1-jk} { m+i-1 \choose i-1} {n-i-1\choose j-1} {2n-i-jk-1\choose n} 
\end{eqnarray*}
(It does not simplify the result this way.)
\end{comment}

%We next study the special case when $d=k=2$.

\begin{proposition}
Let $m,n\ge0$. Then
\[ [x^{n+m}] C_2^{2}(x)^m = \sum_{0\le i\le n} {m+i-1\choose i} \sum_{0\le j\le n-i}{i+j-1\choose j}{n-i-1\choose n-i-j}.\]
In particular, 
\[ C_{2,n}^{2} = \sum_{0\le j\le n} {n+j-1\choose 2j} = F_{2n-1}.\]
\end{proposition}
\begin{comment}
Let $m,n\ge0$.
Proposition~\ref{prop:k=2} gives $C_1^{2}(x)=C_2^{1}(x)$ and thus Corollary~\ref{cor:l=1} implies 
\[ [x^{n+m}] C_1^{2}(x)^m %= \sum_{0\le i\le m} {m\choose i} {n-1\choose n-i} 2^{n-i}
= \sum_{0\le i \le n} {m+i-1 \choose i} {n-1\choose n-i}.\]
Combining this with Proposition~\ref{prop:Ckd} we have
\[ [x^{n+m}] C_2^{2}(x)^m = \sum_{0\le i\le n} {m+i-1\choose i} \sum_{0\le j\le n-i}{i+j-1\choose j}{n-i-1\choose n-i-j} \]
In particular, taking $m=1$ we have
\begin{eqnarray*}
C_{2,n}^{2} &=& \sum_{0\le i\le n} \sum_{0\le j\le n-i}{i+j-1\choose j}{n-i-1\choose n-i-j} \\
&=& \sum_{0\le j\le n} \sum_{0\le i\le n-j} {i+j-1\choose j} {n-i-1\choose n-i-j} \\
&=& \sum_{0\le j\le n} {n+j-1\choose 2j}
\end{eqnarray*}
where the last step follows from choosing $2j$ elements from $[n+j-1]$, assuming the $(j+1)$th chosen element is $i+j$ for some $i$.
\end{comment}

\begin{remark}
Let $\defcolor{C(x)} := \sum_{n\ge0} C_n x^{n+1}$ be the generating function of the Catalan numbers.
The limit of $[x^{n+m}]C_k^d(x)^m$ as $k\to\infty$ or $d\to\infty$ is below, which gives the diagonals of Catalan's triangle~\cite[A009766]{OEIS}:
%It is well known that $C(x) = x/(1-C(x))$.
%Thus for $m\ge1$ and $n\ge0$ applying Lagrange inversion to $A(x) := x(1-x)$ and $B(x) :=C(x) $ gives
\[ [x^{n+m}] C(x)^m = \frac{m}{n+m}{2n+m-1\choose n}. \] % = \frac{m}{n} {2n+m-1\choose n-1}. \]
\end{remark}

\acknowledgements{The authors thank Corbin Groothuis, Alex Miller, and Brendon Rhoades for helpful conversations, % for pointing out a proof of Proposition~\ref{thm:NumberOfIdeals} to us, 
and thank the anonymous referees for helpful comments and suggestions.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography

\end{document}

