%% 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]{FPSAC2023}
\articlenumber{10}
%% 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{hyphenat}
\usepackage{tikz}
\usepackage{comment}
\usetikzlibrary{math,calc}

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

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

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

\numberwithin{table}{section}

\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}

\newcommand{\IN}{\ensuremath{\mathbb{N}}}

\newcommand{\NOR}{\ensuremath{\mathbin{\downarrow}}}

\newcommand{\nset}[1]{\ensuremath{[{#1}]}}
\newcommand{\card}[1]{\ensuremath{\lvert{#1}\rvert}}

\newcommand{\spac}[2][n]{\ensuremath{s^\mathrm{ac}_{#1}({#2})}}
\newcommand{\finespac}[2][n]{\ensuremath{\sigma^\mathrm{ac}_{#1}({#2})}}
\newcommand{\spa}[2][n]{\ensuremath{s^\mathrm{a}_{#1}({#2})}}
\newcommand{\finespa}[2][n]{\ensuremath{\sigma^\mathrm{a}_{#1}({#2})}}

% 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\RR{\mathbb{R}}
\def\P{\mathcal P} \def\tC{\widetilde{C}} 
\newcommand{\T}{{\mathcal T}}
\newcommand{\D}{{\mathcal D}} \newcommand{\Par}{\mathrm{Par}}
\DeclareMathOperator{\ld}{\delta} \DeclareMathOperator{\rd}{\rho}
\DeclareMathOperator{\tr}{tr} 
\DeclareMathOperator{\des}{des} 
\DeclareMathOperator{\pr}{pr}
\DeclareMathOperator{\var}{var}
\DeclareMathOperator{\dom}{dom}

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


%\usepackage{lipsum}

%% define your title in the usual way
\title{The associative-commutative spectrum of a binary operation}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Jia Huang\thanks{\href{mailto:huangj2@unk.edu}{huangj2@unk.edu}.}\addressmark{1} \and Erkko Lehtonen\thanks{\href{mailto:e.lehtonen@fct.unl.pt}{e.lehtonen@fct.unl.pt}. Erkko Lehtonen was partially supported by National Funds through the FCT---Funda\c{c}\~{a}o para a Ci\^{e}ncia e a Tecnologia, I.P., under the scope of the project UIDB/00297/2020 (Center for Mathematics and Applications) and the project PTDC/MAT-PUR/31174/2017.}\addressmark{2,3}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics and Statistics,
University of Nebraska, Kearney, NE 68849, USA \\ 
\addressmark{2}Department of Mathematics, Khalifa
University, P.O. Box 127788, 
Abu Dhabi, United Arab Emirates \\
\addressmark{3}Centro de Matem\'atica e Aplica\c{c}\~oes, Faculdade de Ci\^encias e
Tecnologia, Universidade Nova de Lisboa, Quinta da Torre, 2829-516
Caparica, Portugal 
}

%% 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 initiate the study of a quantitative measure for the failure of a binary operation to be commutative and associative. We call this measure the associative-commutative spectrum as it extends the associative spectrum (also known as the subassociativity type), which measures the nonassociativity of a binary operation. In fact, the associative-commutative spectrum (resp., associative spectrum) is the cardinality of the symmetric (resp., nonsymmetric) operad obtained naturally from a groupoid (a set with a binary operation). In this paper we provide some general results on the associative-commutative spectrum, precisely determine this measure for certain binary operations, and propose some problems for future study.}

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

\keywords{Associative-commutative spectrum; associative spectrum; binary operation; tree}

%% 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; i.e., [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{AC-Spectrum-FPSAC.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}\label{sec:Intro}

Associativity and commutativity are important properties for binary operations.
Although many familiar operations satisfy both properties, some only satisfy one or neither of them.
Moreover, nonassociativity and noncommutativity arise in many algebraic structures, such as Lie algebras, Poisson algebras, and so on.
The operad theory models both nonassociativity and noncommutativity using binary trees.
It was developed by Boardman, May, Vogt, and others, with applications recently found in many branches of mathematics (see, e.g., Loday and Vallette~\cite{Operads}).
We recall some basic definitions below.

A \emph{nonsymmetric operad} %(or an \emph{operad without permutations}) 
is an indexed family $\P = \{\P(n)\}_{n\ge1}$ of sets with an identity element $1\in \P(1)$ and, for all positive integers $n,m_1,\ldots,m_n$, a \emph{composition map} 
%\begin{align}
${\circ} \colon \P(n)\times \P(m_1)\times\cdots\times \P(m_n) %& 
\to \P(m_1+\cdots+m_n)$, %\\
$(P,P_1,\ldots,P_n) %& 
\mapsto P \circ (P_1,\ldots,P_n)$
%\end{align}
such that $P\circ(1,\ldots,1)=P = 1\circ P$ and
%\begin{multline*}
$P\circ(P_1\circ(P_{1,1},\ldots,P_{1,m_1}), \ldots, P_n\circ(P_{n,1},\ldots,P_{n,m_n})) %\\
= (P\circ(P_1,\ldots,P_{n})) \circ(P_{1,1},\ldots,P_{1,m_1},\ldots,P_{n,1},\ldots,P_{n,m_n})$
%\end{multline*}
for any $P \in \P(n)$, $P_i \in \P(n_i)$, $P_{i,j} \in \P(n_{i,j})$ ($1 \leq i \leq n$, $1 \leq j \leq n_i$).
A nonsymmetric operad can thus be seen as a many\hyp{}sorted algebra with a nullary operation $1$ and operations $\circ_{n,m_1,\dots,m_n}$ for all positive integers $n, m_1, \dots, m_n$, but for notational simplicity, the same symbol $\circ$ is used to denote all of the latter.
The elements of $\P(n)$ are called \emph{$n$-ary operations}.
The \emph{Hilbert series} of a nonsymmetric operad $\P$ is 
$\sum_{n=1}^\infty \card{\P(n)} t^n.$

On the other hand, a \emph{symmetric operad} is a nonsymmetric operad $\P = \{ \P(n) \}_{n\ge1}$ with a right action of the symmetric group $\SS_n$ on $\P(n)$ for each $n\ge1$ satisfying the equivariance conditions 
$(P\cdot w)\circ(P_{w^{-1}(1)},\ldots,P_{w^{-1}(n)}) = (P\circ(P_1,\ldots,P_n))\cdot w$ and
$P\circ(P_1\cdot w_1,\ldots,P_n\cdot w_n) = (P\circ(P_1,\ldots,P_n))\cdot(w_1,\ldots,w_n)$ for any $P\in\P(n)$, $w\in \SS_n$, $P_i\in\P(m_i)$, and $w_i\in\SS_{m_i}$.
Here by abuse of notation, the permutation $w$ on the right side of the first equation  is a permutation of the set $\{1, \dots, m_1 + \dots + m_n\}$ that breaks the set into $n$ blocks of sizes $m_1, \dots, m_n$ and then permutes the $n$ blocks by $w$.
The \emph{Hilbert series} of a symmetric operad $\P = \{ \P(n) \}_{n\ge1}$ is
$\sum_{n=1}^\infty \frac{\card{\P(n)}}{n!} t^n.$

Now recall that a \emph{groupoid} is a set $G$ with a single binary operation $*$.\footnote{Note that the term \emph{groupoid} has a different meaning in category theory.}
A \emph{bracketing} of $n$ variables is a groupoid term over the set $X_n := \{x_1, \dots, x_n\}$ of variables that is obtained by inserting parentheses in $x_1 * x_2 * \dots * x_n$ in a valid way.
With $\P_*(n)$ denoting the set of all $n$\hyp{}ary term operations on $(G,*)$ induced by the bracketings of $n$ variables, we obtain the non\hyp{}symmetric operad $\P_* := \{\P_*(n)\}_{n\ge1}$.
The cardinality $\card{\P_*(n)}$ measures to some extent the failure of $*$ to be associative.
In general, we have $1 \leq \card{\P_*(n)} \leq C_{n-1}$ where $C_n := \frac{1}{n+1}\binom{2n}{n}$ is the ubiquitous \emph{Catalan number}.

Cs\'{a}k\'{a}ny and Waldhauser~\cite{AssociativeSpectra1} called the sequence $(\spa{*} := \card{\P_*(n)})_{n \in \IN_{+}}$ the \emph{associative spectrum} of the binary operation $*$, while Braitt and Silberger~\cite{Subassociative} named it the \emph{subassociativity type} of the groupoid $(G,*)$.
Independently, Hein and the first author~\cite{CatMod} proposed the study of $\spa{*} = \card{\P_*(n)}$ for a binary operation $*$ and provided an explicit formula when $*$ satisfies \emph{$k$\hyp{}associativity} (a generalization of associativity).
The associative spectra of many other binary operations have been determined~\cite{VarCat, DoubleMinus, GraphAlgebra1, GraphAlgebra2,AssociativeSpectra2}.


For each $n\ge1$, let $\overline{\P}_*(n)$ be the set of all $n$-ary term operations induced on $(G,*)$ by \emph{full linear terms} of $n$ variables, i.e., groupoid terms over $X_n$ in which each variable $x_1, \dots, x_n$ occurs exactly once (but in an arbitrary order, as opposed to bracketings).
This gives a symmetric operad $\overline{\P}_* := \{ \overline{\P}_*(n)\}_{n\ge1}$ with Hilbert series
$\sum_{n=1}^\infty \frac{\card{\overline{\P}_*(n)}}{n!} t^n.$
We call the sequence $(\spac{*})_{n \in \IN_{+}}$, where $\spac{*} := \card{\overline{\P}_*(n)}$, the \emph{associative\hyp{}commutative spectrum} (in brief, \emph{ac\hyp{}spectrum}) of the binary operation $*$, which measures both the nonassociativity and the noncommutativity of $*$.
We will determine the ac\hyp{}spectra for some binary operations and exhibit connections to other interesting combinatorial objects and results.

It is clear that $\spac{*} \ge1$ and the equality holds for all $n \in \IN_{+}$ if and only if $*$ is both commutative and associative.
On the other hand, we have the following upper bounds. % for the ac-spectrum.

%\begin{enumerate}[label={\upshape(\roman*)}]
%\item
\noindent(i) Since full linear terms over $X_n$ are in bijection with (ordered) binary trees with $n$ labeled leaves, we have $\spac{*}\le n!C_{n-1}$ for an arbitrary binary operation $*$.

%\item
\noindent(ii) Since the equivalence classes of full linear terms over $X_n$ modulo the equational theory of associative groupoids (semigroups) are in bijection with the set of permutations of $\{1, \dots, n\}$, we have $\spac{*} \leq n!$ if $*$ is an associative binary operation.

%\item
\noindent(iii) Since the equivalence classes of full linear terms over $X_n$ modulo the equational theory of commutative groupoids are in bijection with unordered binary trees with $n$ labeled leaves, we have $\spac{*} \leq (2n-2)!/(2^{n-1}(n-1)!)$~\cite[A001147]{OEIS} if $*$ is commutative.
This upper bound is the solution to Schr\"oder's third problem~\cite[p.~178]{EC2}.
%\end{enumerate} 

In \cref{sec:Free} we show that the above upper bounds can be achieved by the free groupoid on one generator, the free associative groupoid (i.e., the free semigroup) on two generators, and the free commutative groupoid on one generator, respectively.

In \cref{sec:associative-commutative} we focus on associative or commutative binary operations.
For an associative noncommutative binary operation $*$, we show that its ac-spectrum $\spac{*}$ attains the upper bound $n!$ if it has a neutral element (i.e., identity element), and give some other examples for which $\spac{*}<n!$. % in \cref{sec:associative}.
%In \cref{sec:commutative} and \cref{sec:commutative-neutral}, 
We provide some concrete examples of commutative groupoids whose ac\hyp{}spectra reach the upper bound $(2n-2)!/(2^{n-1}(n-1)!)$, but for the arithmetic, geometric, and harmonic means, we show that their ac\hyp{}spectra coincide with an interesting sequence that counts ways to express $1$ as an ordered sum of powers of $2$~\cite[A007178]{OEIS}.
The last example shows that the ac\hyp{}spectrum of a commutative operation may not achieve the upper bound $(2n-2)!/(2^{n-1}(n-1)!)$ even if it is \emph{totally nonassociative}, i.e., its associative spectrum equals the upper bound $C_{n-1}$.
However, we show that the converse does hold: a commutative groupoid is totally nonassociative if its ac\hyp{}spectrum reaches that upper bound.

In \cref{sec:anticommutative} we show that the ac-spectrum of some anticommutative algebras over a field, including the cross product and certain Lie brackets, is exactly two times the upper bound $(2n-2)!/(2^{n-1}(n-1)!)$ for the ac-spectrum of a commutative operation.

In \cref{sec:TN}, we determine the ac\hyp{}spectra of some more examples of totally nonassociative operations, including the exponentiation, the (converse) implication, and the negated disjunction (NOR).
The exponentiation and the converse implication satisfy the identity $x(yz) \approx x(zy)$ and their ac-spectrum reaches the upper bound $n^{n-1}$ for the ac-spectrum of any binary operation satisfying the above identity. 
Here $n^{n-1}$ shows up because it is the number of unordered rooted trees with $n$ labeled vertices.
The negated disjunction is commutative and its ac-spectrum reaches the upper bound $(2n-2)!/(2^{n-1}(n-1)!)$ for commutative operations.
Together with \cref{ex:two-element-groupoids}, this completely describes the ac-spectra of all two\hyp{}element groupoids.

In \cref{sec:DepthEq} %we see that for some groupoids, two full linear terms induce the same term operation if and only if the corresponding binary trees are equivalent with respect to certain attributes related to the depths of the leaves.
%In \cref{sec:RightDepth} 
we obtain a formula involving the Stirling numbers of the second kind for the ac\hyp{}spectrum of a binary operation $*$  satisfying the property that any two full linear terms agree on $*$ if and only if the right depth sequences of their corresponding binary trees are congruent modulo $k$ (this is equivalent to the $k$-associativity mentioned earlier).
An example is given by $a*b:=a+e^{2\pi i/k} b$, which becomes addition and subtraction when $k=1$ and $k=2$.
Related to this example is the operation $a*b:= e^{2\pi i/k}(a+b)$.
When $k=2$ this becomes the \emph{double minus operation} $a \ominus b := -a-b$ whose associative spectrum is $\card{\P_*(n)} = \lfloor 2^n/3 \rfloor$~\cite[A000975]{OEIS}, as shown by Cs\'{a}k\'{a}ny and Waldhauser~\cite[\S~5.3]{AssociativeSpectra1} and independently by the first author, Mickey, and Xu~\cite{DoubleMinus}.
%In \cref{sec:k-depth} 
We show that $\spac{\ominus}=(2^n-(-1)^n)/3$, which is the well-known \emph{Jacobsthal sequence}~\cite[A001045]{OEIS}.
The more general operation $a*b:= e^{2\pi i/k}(a+b)$ satisfies the \emph{$k$\hyp{}depth\hyp{}equivalence} studied recently by the second author.
Computations show that neither the associative spectrum nor the ac\hyp{}spectrum of this operation is in OEIS~\cite{OEIS} when $k>2$.

In \cref{sec:conclusion}, we give remarks and indicate possible directions for further research.


%\tableofcontents

\section{Preliminaries}\label{sec:Prelim}

In this section we briefly recall some fundamental concepts %concerning algebras, terms and identities, as well as trees, 
that are necessary for our work and introduce the \emph{\textup{(}fine\textup{)} associative\hyp{}commutative spectrum} of a groupoid.
%This is a modification of the (fine) associative spectrum, introduced by Cs\'ak\'any and Waldhauser \cite{AssociativeSpectra1} and Liebscher and Waldhauser \cite{AssociativeSpectra2}.


Let $*$ be a binary operation on a set $G$. 
Then $\mathbf{G} = (G,*)$ is called a \emph{groupoid}.
Define $\IN_+ := \{1,2,3,\ldots\}$ and $\nset{n} := \{1, \dots, n\}$.
Let $X$ be a set of variables; some common choices are $X_\omega := \{x_1, x_2, \dots\}$ and $X_n := \{x_1, \dots, x_n\}$ for $n \in \IN_{+}$.
A \emph{term} over $X$ is of the form $x_{i_1}*\cdots* x_{i_\ell}$ with $\ell-1$ pairs of parentheses inserted in a valid way, where $x_{i_1},\ldots,x_{i_\ell}\in X$.
We may omit $*$ from a term if there is no confusion to do so.

Let $T(X)$ denote the set of all terms over $X$.
A term $t\in T(X)$ is \emph{linear} if no variable occurs more than once in $t$, or \emph{full} if every variable $x\in X$ occurs in $t$.
A full linear term over $X_n$ can be obtained by inserting $n-1$ pairs of parentheses in a valid way into $x_{\sigma(1)}*\cdots* x_{\sigma(n)}$ for some permutation $\sigma\in\mathfrak{S_n}$.
If $\sigma$ happens to be the identity permutation then we get a \emph{bracketing} over $X_n$.
Let $F_n$ and $B_n$ denote the set of all full linear terms over $X_n$ and the set of all bracketings over $X_n$, respectively.
It is well known that the number of bracketings over $X_n$ equals the $(n-1)$\hyp{}st Catalan number $C_{n-1} = \frac{1}{n} \binom{2n-2}{n-1}$, i.e., $\card{B_n} = C_{n-1}$.
Consequently, $\card{F_n} = n! C_{n-1}$.
%If $s, t \in B_n$ ($s, t \in F_n$, resp.)\ for some $n \in \IN$, then we call $s \approx t$ a \emph{bracketing identity} (a \emph{full linear identity,} resp.).

Each $t\in F_n$ corresponds to an $n$-ary operation $t^{\mathbf{G}}$ on $G$.
Given two terms $s,t\in F_n$, we have an \emph{identity} $s \approx t$ satisfied by $\mathbf{G}$ if $s^{\mathbf{G}} = t^{\mathbf{G}}$.
The \emph{fine associative\hyp{}commutative spectrum} (in brief, \emph{fine ac\hyp{}spectrum}) of $\mathbf{G}$ is the sequence $(\finespac{\mathbf{G}})_{n \in \IN_{+}}$, where $\finespac{\mathbf{G}}$ is the set of all $(s,t)\in F_n$ with $s^{\mathbf{G}} = t^{\mathbf{G}}$.
%$\finespac{\mathbf{G}} := \{ (s,t) \in F_n \times F_n \mid \mathbf{G} \models s \approx t \}$.
%In other words, $\finespac{\mathbf{G}}$ is the restriction of the equational theory of $\mathbf{G}$ to full linear identities over $X_n$.
It is clear that $\finespac{\mathbf{G}}$ is an equivalence relation on $F_n$.
The \emph{associative\hyp{}commutative spectrum} (in brief, \emph{ac\hyp{}spectrum}) of $\mathbf{G}$ is the sequence $(\spac{\mathbf{G}})_{n \in \IN}$, where $\spac{\mathbf{G}} := \card{F_n / \finespac{\mathbf{G}}}$, i.e., the number of equivalence classes of $\finespac{\mathbf{G}}$.
Equivalently, $\spac{\mathbf{G}}$ is the number of distinct term operations on $\mathbf{G}$ induced by the full linear terms over $X_n$, in symbols,
$\spac{\mathbf{G}} = \card{F_n^\mathbf{G}} = \card{\{ t^\mathbf{G} \mid t \in F_n \}}$.
The \emph{fine associative spectrum} $(\finespa{\mathbf{G}})_{n \in \IN_{+}}$ and the \emph{associative spectrum} $(\spa{\mathbf{G}})_{n \in \IN_{+}}$ of $\mathbf{G}$ were defined analogously by Liebscher and Waldhauser \cite{AssociativeSpectra2} by taking bracketings instead of full linear terms, i.e., by replacing $F_n$ with $B_n$ in the above definitions.
These numbers satisfy
$1 \leq \spa{\mathbf{G}} \leq \card{B_n} = C_{n-1}$ and $1 \leq \spac{\mathbf{G}} \leq \card{F_n} = n! C_{n-1}$.
We say $\mathbf{G}$ is \emph{totally nonassociative} if $\spa{\mathbf{G}} = C_{n-1}$ for all $n \geq 1$.
For notational simplicity, %we may avoid giving a name to the groupoid and refer only to its fundamental operation, and hence we may sometimes replace $\mathbf{G}$ with $*$ in the notations introduced above.
%For example, 
we may write $t^{*}$ for $t^\mathbf{G}$ or $\spac{*}$ for $\spac{\mathbf{G}}$.

It is easy to see that isomorphic or antiisomorphic groupoids have the same associative spectrum and the same ac-spectrum.
The following facts follow immediately from the fact that varieties (classes of groupoids axiomatized by identities) are closed under homomorphic images, subgroupoids, and direct products.

%\begin{enumerate}[label={\upshape(\roman*)}]
%\item 
(i) If $\mathbf{A}$ is a homomorphic image of $\mathbf{B}$, then $\finespac{\mathbf{A}} \supseteq \finespac{\mathbf{B}}$ and $\spac{\mathbf{A}} \leq \spac{\mathbf{B}}$.

%\item 
(ii) If $\mathbf{A}$ is a subgroupoid of $\mathbf{B}$, then $\finespac{\mathbf{A}} \supseteq \finespac{\mathbf{B}}$ and $\spac{\mathbf{A}} \leq \spac{\mathbf{B}}$.

%\item 
(iii) If $\mathbf{C} = \mathbf{A} \times \mathbf{B}$, then $\finespac{\mathbf{C}} = \finespac{\mathbf{A}} \cap \finespac{\mathbf{B}}$ and $\spac{\mathbf{C}} \geq \max \{ \spac{\mathbf{A}}, \spac{\mathbf{B}} \}$.
%\end{enumerate}


%\subsection{Trees}
%Now recall that a (finite, undirected) graph is an ordered pair $(V,E)$ where $V$ is a (finite) set whose elements are called \emph{vertices} and $E$ is a set of unordered pairs of vertices called \emph{edges}.
%A graph is \emph{connected} if for any pair of vertices $u, v\in V$, there exists a sequence of vertices $(v_0, v_1, \ldots,v_\ell)$ such that $v_0=u$, $v_iv_{i+1}\in E$ for $i=0, 1,\ldots, \ell-1$, and $v_\ell=v$.
%A \emph{cycle} is a sequence of distinct vertices $(v_0, v_1, \ldots,v_\ell)$ such that $v_iv_{i+1}\in E$ for all $i=0, 1, \ldots, \ell-1$ and $v_\ell v_0\in E$.
%A \emph{tree} is a connected graph without any cycle.


Now let $T$ be a \emph{rooted} tree, i.e., a tree with a distinguished vertex called the \emph{root} and with edges oriented away from the root (usually downward).
%We usually draw $T$ in such a way that its root appears at the very top and each vertex $v$ has a nonnegative number of children (i.e., out-neighbors) hanging below $v$.
A vertex in $T$ is a \emph{leaf} if it has no children, or an \emph{internal vertex} otherwise.
%Let $\card{T}$ denote the number of leaves in $T$.
A rooted tree $T$ is \emph{ordered}%
\footnote{Ordered trees are often called \emph{plane trees} since a plane embedding of a tree induces a cyclic ordering of the neighbours of each vertex; moreover, if the root is drawn at the top -- following our drawing convention -- then the embedding specifies a linear ordering for the children of each internal vertex.}
if the children of each internal vertex are linearly ordered, or \emph{unordered} otherwise.
Given an ordered tree $T$, the unordered tree obtained from $T$ by simply ignoring the order of children of each internal vertex is called the \emph{underlying unordered tree} of $T$ and denoted by $T^\mathrm{u}$.
A rooted tree is \emph{labeled} if all of its vertices are labeled.
Given a vertex $v$ in a rooted tree $T$, the \emph{subtree of $T$ rooted at $v$} consists of all the vertices and edges weakly below $v$.
A rooted tree $T$ is a \emph{binary tree} if each internal vertex has exactly two children.
A binary tree is \emph{leaf-labeled} if its leaves are labeled.
The \emph{left subtree} $T_\mathrm{L}$ and \emph{right subtree} $T_\mathrm{R}$ of an ordered binary tree $T$ are the subtrees rooted at the left child and at the right child of the root of $T$, respectively.
If $S$ and $T$ are two ordered binary trees, then $S \wedge T$ is the ordered binary tree whose left and right subtrees are $S$ and $T$, respectively.
One can naturally extend these definitions to unordered binary trees by not distinguishing left and right.

Let $T$ be a binary tree with $n$ leaves labeled $1, \ldots, n$ in some order.
The \emph{left depth} $\delta_T(i)$, \emph{right depth} $\rho_T(i)$, and \emph{depth} $d_T(i)$ of a leaf $i$ in an ordered binary tree $T$ is the number of left, right, and all steps in the path from the root to the leaf labeled $i$.
This leads to the \emph{left depth sequence} $\delta_T:= (\delta_T(1), \dots, \delta_T(n))$, the \emph{right depth sequence} $\rho_T:= (\rho_T(1), \dots, \rho_T(n))$ and the \emph{depth sequence} $d_T := (d_T(1), \dots, d_T(n))$ of $T$.
If the leaves of $t$ are labeled $1, \dots, n$ from left to right, then each sequence above determines the ordered binary tree $T$ uniquely~\cite{AssociativeSpectra1, CatMod, DoubleMinus}.
The depth sequence can also be defined for unordered leaf-labeled binary trees.

There is a bijection between the set $T(X)$ of all terms over $X$ and the set of ordered binary trees with leaves labeled by the variables in $X$ (if $X=X_\omega$ then we may identify a label $x_i$ with $i$), defined recursively as follows:
each variable $x \in X$ corresponds to a tree with just one vertex labeled with $x$,
and
if the terms $t_1$ and $t_2$ correspond to trees $T_1$ and $T_2$, respectively, then the term $(t_1 t_2)$ corresponds to the tree $T_1 \wedge T_2$.
We write $T_t$ for the binary tree corresponding to the term $t$ via this bijection, and we write $t_T$ for the term corresponding to the binary tree $T$ via its inverse map.

\section{Free groupoids}\label{sec:Free}

In this section we show that the various upper bounds for the associative-commutative spectra mentioned in \cref{sec:Intro} can be achieved by certain free groupoids.

Recall that a \emph{groupoid} $\mathbf{G}=(G,{*})$ is a set $G$ with a single binary operation $*$.
A groupoid is \emph{commutative} if it satisfies the identity $x * y \approx y * x$ (\emph{commutative law}),
and it is \emph{associative} if it satisfies the identity $x * (y * z) \approx (x * y) * z$ (\emph{associative law}).
An associative groupoid is called a \emph{semigroup.}
The \emph{free semigroup} over $X$ is isomorphic to the semigroup $\mathbf{X}^{+} = (X^+, \cdot)$ of nonempty words over $X$ endowed with the operation $\cdot$ of concatenation.
%Let $\mathbf{T}(X_k)$ denote the \emph{free groupoid on $k$ generators}.

We first show that the upper bound $\spac{\mathbf{G}} \le n!C_{n-1}$ for the ac-spectrum $\spac{\mathbf{G}}$ of an arbitrary groupoid $\mathbf{G}$ becomes an equality when $\mathbf{G}$ is the free groupoid on one generator.



\begin{proposition}
\label{prop:free-groupoid}
If $\mathbf{G}$ is a free groupoid with one generator then $\spac{\mathbf{G}}=n!C_{n-1}$ for all $n\ge1$.
%For every $n \in \IN_{+}$, the $n$\hyp{}th term of the ac\hyp{}spectrum of the free groupoid $\mathbf{T}(X_1)$ with one generator is $\spac{\mathbf{T}(X_1)} = n!C_{n-1}$.
\end{proposition}


If $\mathbf{G}$ is a semigroup then $\spac{\mathbf{G}} \leq n!$ for all $n \in \IN_+$, since all bracketings over $X_n$ induce the same term operation on $\mathbf{G}$ and it is only the order of variables in a full linear term that matters.
We show that the equality in this upper bound holds when $\mathbf{G}$ is the free semigroup with two generators.
%\begin{remark}
Note that %we need (at least) two generators for the above proof to work. In fact, 
the ac\hyp{}spectrum of the free semigroup with one generator is the constant $1$
sequence.
%\end{remark}



\begin{proposition}
\label{prop:free-semigroup}
If $\mathbf{G}$ is a free semigroup with two generators then $\spac{\mathbf{G}} = n!$ for all $n \geq 1$.
\end{proposition}


If $\mathbf{G}$ is a commutative groupoid then $\spac{\mathbf{G}}$ is bounded above by the number $(2n-2)!/(2^{n-1}(n-1)!)$ of unordered binary trees with $n$ labeled leaves~\cite[A001147]{OEIS}, i.e., the solution to Schr\"oder's third problem; see, e.g., Stanley~\cite[p.~178]{EC2}.


\begin{proposition}\label{prop:free-com}
If $\mathbf{G}$ is a free commutative groupoid %$\mathbf{T}(X_1) / \Sigma^\mathrm{c}_{X_1}$ 
with one generator then its ac-spectrum achieves the above upper bound:
$\spac{\mathbf{G}} = (2n-2)! / (2^{n-1} (n-1)!)$ for all $n\ge1$.
\end{proposition}


\section{Associative or commutative groupoids}\label{sec:associative-commutative}

In this section we study the ac\hyp{}spectra of some associative or commutative groupoids.

%\subsection{Associative groupoids (semigroups)}\label{sec:associative}
First assume that $*$ is an associative binary operation on a set $G$, i.e., $\mathbf{G} = (G,{*})$ is a semigroup.
We know that the upper bound $\spac{\mathbf{G}} \leq n!$ is reached by the free semigroup with two generators (Proposition \ref{prop:free-semigroup}).
Now we provide another example of a family of groupoids for which this upper bound is achieved.

Recall that a \emph{monoid} is a semigroup $\mathbf{G} = (G,{*})$ with a \emph{neutral element} (or \emph{identity element}), i.e., an element $e \in G$ such that $e * x = x = x * e$ for all $x \in G$.

\begin{proposition}
If $\mathbf{G} = (G,{*})$ is a noncommutative monoid, then $\spac{\mathbf{G}} = n!$ for all $n \geq 1$.
\end{proposition}



The above proposition would no longer be true if we omitted the assumption that the groupoid has a neutral element, as shown by the following example.

\begin{example}\label{ex:two-element-groupoids}
Cs\'{a}k\'{a}ny and Waldhauser~\cite[Section~4]{AssociativeSpectra1} determined the associative spectrum of every two\hyp{}element groupoid.
Such a groupoid is isomorphic or anti\hyp{}isomorphic to $\mathbf{G} = (\{0,1\},*)$, where $x*y$ is defined as one of the following: (1) $1$, (2) $x$, (3) $\min\{x,y\}$, (4) $x+y \pmod 2$, (5) $x+1 \pmod 2$, (6) $x \NOR y$
(negated disjunction, NOR) or (7) $x \rightarrow y$ (implication).
%We now set out to determine their ac\hyp{}spectra.
We have $\spac{\mathbf{G}} = 1$ for all $n \in\IN_+$ if $*$ defined by (1), (3), or (4) since $*$ is both associative and commutative in these three cases.
The operation $*$ defined by (2) is associative but not commutative, and we have $\spac{\mathbf{G}} = n$ for all $n \in\IN_+$. %since for any $t \in F_n$ with $t = t'[x_{\tau(1)}, \dots, x_{\tau(n)}]$, where $t' \in B_n$ and $\tau \in \SS_n$, we have $t^\mathbf{G} = \pr^{(n)}_{\tau(1)}$.
For the operation $*$ defined by (5), we can show that $\spac[1]{\mathbf{G}} = 1$, $\spac[2]{\mathbf{G}} = 2$, and $\spac{\mathbf{G}} = 2n$ for all $n \geq 3$. % since for any $t \in F_n$ with $t = t'[x_{\tau(1)}, \dots, x_{\tau(n)}]$, where $t' \in B_n$ and $\tau \in \SS_n$, we have $t^\mathbf{G}(a_1, \dots, a_n) = a_{\tau(1)} + d \pmod 2$, where $d$ is the left depth of the leftmost leaf in the binary tree corresponding to $t$.
The groupoids given by (6) and (7) are totally nonassociative and their ac-spectra will be determined in \cref{sec:TN}.
\end{example}

%\subsection{Commutative groupoids}\label{sec:commutative}
Assume that $\mathbf{G} = (G,{*})$ is a commutative groupoid.
Recall that we have an upper bound $\spac{\mathbf{G}} \le (2n-2)!/(2^{n-1}(n-1)!)$ which is attained by a free commutative groupoid with one generator (Proposition \ref{prop:free-com}).
The following lemma shows that any commutative groupoid $\mathbf{G}$ reaching this upper bound must be totally nonassociative.

\begin{lemma}
\label{lem:com:large-implies-na}
Let $\mathbf{G} = (G,{*})$ be a commutative groupoid.
If $\spac{\mathbf{G}} = (2n-2)!/(2^{n-1}(n-1)!)$ for $n \in \IN_{+}$, then $\mathbf{G}$ is totally nonassociative, i.e., $\spa{\mathbf{G}} = C_{n-1}$ for all $n \in \IN_+$.
\end{lemma}


The converse of Lemma~\ref{lem:com:large-implies-na} does not hold.
If $*$ is the arithmetic, geometric, or harmonic mean, then $\spa{*} = C_{n-1}$ for all $n \geq 1$ (see Cs\'ak\'any and Waldhauser~\cite{AssociativeSpectra1}).
However, as we are going to show next, its
ac\hyp{}spectrum agrees with an interesting sequence in OEIS~\cite[A007178]{OEIS}, which enumerates different ways to write $1$ as an ordered sum of $n$ powers of $2$ (i.e., \emph{compositions of $1$ into powers of $2$}) and is also related to the \emph{prefix codes} or \emph{Huffman codes} (see, e.g., Even and Lempel~\cite{EvenLempel}, Giorgilli and Molteni~\cite{GM}, Knuth~\cite{Knuth}, Krenn and Wagner~\cite{KrennWagner} and Lehr, Shallit and Tromp~\cite{LST}).

\begin{proposition}\label{prop:mean}
If $*$ is the arithmetic mean on $\RR$ or the geometric/harmonic mean on $\RR_{+}$ then $\spac{*}$ equals the number of ways to write $1$ as an ordered sum of $n$ powers of $2$ for all $n \geq 1$.
\end{proposition}



\begin{proposition}
For the rock\hyp{}paper\hyp{}scissors operation $*$ defined on $\{\text{rock}, \text{paper}, \text{scissors}\}$ by $x * y = y * x := x$ if $x$ beats $y$ or $x=y$ (rock beats scissors, scissors beat paper, and paper beats rock) we have $\spac{*} = (2n-2)!/(2^{n-1}(n-1)!)$ and $\spa{*} = C_{n-1}$ for all $n \geq 1$.
\end{proposition}

We next study nonassociative commutative groupoids with neutral elements.
%For a commutative groupoid $\mathbf{G}$ with a neutral element, we show that there are only two distinct possibilities: either $\mathbf{G}$ is associative, in which case $\spac{\mathbf{G}} = 1$, or it is totally nonassociative and $\spac{\mathbf{G}} = (2n-2)!/(2^{n-1}(n-1)!)$.
An example is the \emph{Jordan algebras} of $n \times n$ self\hyp{}adjoint matrices over $\RR, \CC$, or $\mathbb{H}$ (the algebra of quaternions) with a product defined by $x\circ y := (xy+yx)/2$. 
The identity matrix $I_n$ is the neutral element for this commutative algebra.

\begin{theorem}
\label{thm:com-neutral}
Let $\mathbf{G} = (G,{*})$ be a commutative groupoid with neutral element $e$.
Then either

%\begin{enumerate}[label={\upshape(\roman*)}]
%\item 
(i) $\mathbf{G}$ is associative, in which case $\spa{\mathbf{G}} = \spac{\mathbf{G}} = 1$ for all $n \geq 1$, or

%\item 
(ii) $\spa{\mathbf{G}} = C_{n-1}$ and $\spac{\mathbf{G}} = (2n-2)!/(2^{n-1}(n-1)!)$ for all $n \geq 1$.
%\end{enumerate}
\end{theorem}





\section{Anticommutative algebras}\label{sec:anticommutative}

We now turn our attention to ac\hyp{}spectra of bilinear products in algebras over a field.
An algebra over a field $\FF$ of characteristic not $2$ is \emph{anticommutative} if it satisfies the identity $xy \approx -yx$, which implies the identity $xx \approx 0$ since $xx \approx -xx$.

%\subsection{Commutative version}
Given an anticommutative algebra
over a field, we can turn the product $*$ into a commutative bilinear product $\circledast$ as follows.
Let $A$ be the universe of the algebra.
Let $g$ be any choice function on the collection $C := \{ \{ a, -a \} \mid a \in A \}$ and let $f \colon A \to C$, $f(a) := \{a, -a\}$.
(Recall that a \emph{choice function} on a collection $C$ of subsets of some base set $X$ is a mapping $g \colon C \to X$ such that $g(S) \in S$ for every $S \in C$.
Note that any map $f$ arising in this way is \emph{even,} i.e., it satisfies $f(a) = f(-a)$ for all $a \in A$.)
Now we can fix a basis $B$ of the vector space $A$, and for all basis vectors $a, b \in B$, we define $a \circledast b := g(f(a * b))$.
This partial operation extends to a commutative bilinear product on $A$.
(It is well known that any partial operation on $A$ with domain $B$ extends in a unique way to a bilinear product on $A$, and a bilinear product is commutative if and only if its restriction to the basis is commutative.)
Such a product $\circledast$ will be referred to as a \emph{commutative version} of $*$.


\begin{theorem}\label{thm:anticommutative}
Let $*$ be the bilinear product of an anticommutative algebra over a field with a commutative version $\circledast$
satisfying $s^{\circledast} \ne \pm t^\circledast$ for any terms $s,t\in F_n$ with $T^\mathrm{u}_s \ne T^\mathrm{u}_t$.
Then

%\begin{enumerate}[label={\upshape(\roman*)}]
%\item

(i) $s^{\mathrm{ac}}_n(\circledast) = (2n-2)!/(2^{n-1}(n-1)!)$ and $\spa{\circledast} = C_{n-1}$ for all $n\ge1$;

%\item
(ii) $s^{\mathrm{ac}}_n(*) = 2s^{\mathrm{ac}}_n(\circledast)$ %= (2n-2)!/(2^{n-2}(n-1)!)$ 
for all $n\ge2$ and $\spa{*} = C_{n-1}$ for all $n\ge1$.
%\end{enumerate}
\end{theorem}



Since the cross product is anticommutative, we can determine its ac-spectrum by using a commutative operation associated with it.
Define $\Join$ on a three-dimensional real vector space $V$ with a basis $\{u,v,w\}$ by letting $x\Join x:=0$ for all $x\in \{u,v,w\}$ and $x\Join y := z$ for all distinct $x,y\in\{u,v,w\}$, where $z \in \{u,v,w\} \setminus \{x,y\}$, and extending this bilinearly from $\{u,v,w\}$ to $V$. %, i.e.,
%\[ (\alpha u + \beta v + \gamma w) \Join (\alpha' u + \beta' v + \gamma' w) = (\beta \gamma' + \gamma \beta') u + (\gamma \alpha' + \alpha \gamma') v + (\alpha \beta' + \beta \alpha') w \]
%for any scalars $\alpha$, $\beta$ and $\gamma$.
This operation occurs in recent studies of the Norton algebras of certain distance regular graphs and it is commutative and totally nonassociative~\cite[Example~3.11, Remark~5.10]{Hamming}.

\begin{corollary}\label{cor:cross}
For the cross product $\times$ on $\RR^3$ and its commutative version $\Join$, we have 

(i) $\spac{\Join} = (2n-2)!/(2^{n-1}(n-1)!)$ for all $n \geq 1$, 

(ii) $\spac{\times} = 2 \spac{\Join} = (2n-2)!/(2^{n-2}(n-1)!)$ for all $n \geq 2$, and

(iii) $\spa{\times} = \spa{\Join} = C_{n-1}$ for all $n\ge1$.
\end{corollary}


Now we study Lie algebras.
A triple $(e,f,h)$ of nonzero elements of a Lie algebra is called an \emph{$\mathfrak{sl}_2$\hyp{}triple} if $[e,f] = h$, $[h,e] = 2e$, and $[h,f] = -2f$.
It is well known that $\mathfrak{sl}_2$\hyp{}triples exist in every semisimple Lie algebra over a field of characteristic zero.



\begin{corollary}\label{cor:Lie}
Let $\mathbf{L}$ be a Lie algebra over a field of characteristic distinct from $2$ with an $\mathfrak{sl}_2$-triple.
For the Lie bracket $[-,-]$ of $\mathbf{L}$, it holds that $\spac{[-,-]} = (2n-2)!/(2^{n-2}(n-1)!)$ for all $n \geq 2$ and $\spa{[-,-]} = C_{n-1}$ for all $n \geq 1$.
\end{corollary}




\section{Totally nonassociative operations}\label{sec:TN}

In this section we focus on the ac\hyp{}spectra of some totally nonassociative operations that are not commutative or anticommutative.
Recall that a binary operation $*$ is said to be \emph{totally nonassociative} if $\spa{*} = C_{n-1}$ for all $n \geq 1$.
The arithmetic, geometric, and harmonic means, the cross product on $\RR^3$, and the Lie brackets of Lie algebras over fields of characteristic distinct from $2$ with an $\mathfrak{sl}_2$-triple are all totally nonassociative and their ac-spectra have been determined in earlier sections.
There are many other examples of totally nonassociative operations~\cite{AssociativeSpectra1,Hamming}.
We will study the exponentiation, the implication, and the negated disjunction (NOR) in this section.

%\subsection{Exponentiation}
Recall that any binary operation $*$ satisfies $\spac{*} \leq n! C_{n-1}$ for all $n \geq 1$, and the equality is achieved by the free groupoid on one generator (Proposition \ref{prop:free-groupoid}).
We show that if $*$ is the exponentiation then $\spac{*}$ is strictly less than this upper bound.

%We need the following lemma, which applies to the exponentiation.



\begin{proposition}\label{prop:exp}
Let $\mathbf{G} = (G,*)$ be a groupoid satisfying the identity $(xy)z \approx (xz)y$.
If $s, t \in T(X_\omega)$ are linear terms such that the corresponding ordered labeled trees $P_s$ and $P_t$ have equal underlying unordered trees, i.e., $P_s^{\mathrm{u}} =  P_t^{\mathrm{u}}$, then $s^{\mathbf{G}} = t^{\mathbf{G}}$. (See~\cref{sec:Prelim} for definitions.) 
Consequently, $\spac{\mathbf{G}} \le n^{n-1}$.
Moreover, if the equality holds, then $\spa{\mathbf{G}}=C_{n-1}$.
\end{proposition}


\begin{proposition}
\label{prop:exponentiation}
For $\mathbf{G} = (\RR_{\geq 0}, {*})$, where $*$ is the exponentiation operation defined by $a * b := a^b$ for all $a, b \in \RR_{\geq 0}$, we have $\spac{\mathbf{G}} = n^{n-1}$. 
\end{proposition}


%\subsection{Implication}
Next we study the implication $\rightarrow$ defined on $\{0,1\}$ by $x \rightarrow y :=0$ if $(x,y)=(1,0)$ or $x \rightarrow y :=1$ otherwise.
%It turns out to be more convenient to use the converse implication $\leftarrow$ defined on $\{0,1\}$ by $x \leftarrow y := y \rightarrow x$.
%As the groupoids $(\{0,1\},{\rightarrow})$ and $\{0,1\},{\leftarrow})$ are antiisomorphic, their ac-spectra coincide; therefore it suffices to consider only $\leftarrow$.


%Note that the implication $\rightarrow$ and the converse implication $\leftarrow$ are surjective operations on $\{0,1\}$, and their Cayley tables have no two identical columns nor two identical rows.
%Hence Lemma~\ref{lem:surjective} applies to $\rightarrow$ and $\leftarrow$.


\begin{proposition}\label{prop:implication}
For $\mathbf{G} = (\{0,1\}, {\rightarrow})$, we have $\spac{\mathbf{G}} = n^{n-1}$.
\end{proposition}


%\subsection{Negated disjunction (NOR)}
Now we study the ac-spectrum of the groupoid $\mathbf{G} = (\{0,1\}, {\NOR})$, where $\NOR$ is the \emph{negated disjunction} (\emph{NOR}), defined by the rule $x \NOR y = 1$ if and only if $x = y = 0$.
%Note that the negated disjunction is surjective and its Cayley table has no two identical columns nor two identical rows.
%Hence Lemma~\ref{lem:surjective} applies thereto.


\begin{proposition}\label{prop:Sheffer}
For $\mathbf{G} = (\{0,1\}, {\NOR})$, we have $\spac{\mathbf{G}} = (2n - 2)! / (2^{n-1}(n-1)!)$.
\end{proposition}


\section{Depth equivalence relations}
\label{sec:DepthEq}

In this section we study binary operations $*$ satisfying the property that two full linear terms agree on $*$ if and only if their corresponding binary trees are equivalent with respect to certain attributes related to the depths of the leaves.
%More precisely, two binary trees are considered equivalent if their (right) depth sequences are congruent modulo some positive integer $k$.
%Here all binary trees are ordered and their leaves are unlabeled unless otherwise stated.
 
%\subsection{The $k$-right-depth-equivalence}\label{sec:RightDepth}
A groupoid $\mathbf{G} = (G,{*})$ and the corresponding binary operation $*$ are said to be \emph{right $k$\hyp{}associative} if
$\mathbf{G}$ satisfies the identity
%\begin{equation}\label{eq:k-associative}
$( [ x_1 x_2 \cdots x_{k+1} ]_\mathrm{R} x_{k+2} ) \approx ( x_1 [ x_2 \cdots x_{k+2} ]_\mathrm{R} )$,
%\end{equation}
where $[ \cdots ]_\mathrm{R}$ is a shorthand for the rightmost bracketing of the variables occurring between the square brackets, e.g., $[ x_1 x_2 \cdots x_{k+1} ]_\mathrm{R} = ( x_1 ( x_2 ( \cdots ( x_k x_{k+1} ) \cdots ) ) )$.
Typical examples of $k$-associative operations are the ones defined by $a * b := a + \omega b$ for all $a,b\in\CC$, where $\omega = e^{2 \pi i / k}$ is a $k$\hyp{}th primitive root of unity. 
This reduces to addition and subtraction when $k = 1, 2$, respectively.
One can also define the \emph{left $k$\hyp{}associativity} similarly.
The left or right $k$\hyp{}associativity becomes the usual associativity when $k = 1$.

Previous work~\cite{CatMod} showed that the equivalence relation on binary trees induced by the left $k$\hyp{}associativity is the same as the congruence relation on the left depth sequences of binary trees modulo $k$; this is called the \emph{$k$\hyp{}left\hyp{}depth\hyp{}equivalence relation} by the second author.
The number of equivalence classes is called the \emph{$k$-modular Catalan number}, which counts many restricted families of Catalan objects and has interesting closed formulas~\cite{CatMod}.
Of course, the right $k$\hyp{}associativity corresponds to the \emph{$k$\hyp{}right\hyp{}depth\hyp{}equivalence relation}, whose equivalence classes are also counted by the $k$\hyp{}modular Catalan number.

Now we consider a stronger form of the right $k$\hyp{}associativity.
The $k$\hyp{}right\hyp{}depth\hyp{}equivalence relation extends immediately from binary trees with unlabeled leaves to ones with labeled leaves.
Let $T$ and $T'$ be binary trees with $n$ leaves labeled by $x_1, \dots, x_n$ (in an arbitrary order).
We say that $T$ and $T'$ are \emph{$k$\hyp{}right\hyp{}depth\hyp{}equivalent} if $\rho_T(x_i) \equiv \rho_{T'}(x_i) \pmod{k}$ for all $i \in \nset{n}$, i.e., the right\hyp{}depth sequences $\rho_T$ and $\rho_{T'}$ are componentwise congruent modulo $k$.
Suppose that a binary operation $*$ satisfies the property that any two full linear terms agree on $*$ if and only if $T_s$ and $T_t$ are $k$\hyp{}right\hyp{}depth\hyp{}equivalent, i.e., 
\begin{equation}\label{eq:k-depth}
\forall s, t\in F_n,\ s^{*} = t^{*} \Longleftrightarrow \rho_{T_s}(x_i) \equiv \rho_{T_t}(x_i) \pmod{k}, \quad i = 1, 2,\ldots, n. 
\end{equation}
It is clear that such a binary operation $*$ must be $k$\hyp{}right\hyp{}associative.
The above example $a*b := a + e^{2 \pi i / k} b$ satisfies property~\eqref{eq:k-depth} and another example is given by $f*g := xf + yg$ for all $x, y \in \CC[x,y] / (y^k - 1)$~\cite{VarCat}.
The associative spectrum of these examples is given by the $k$\hyp{}modular Catalan numbers mentioned above.
We determine the ac\hyp{}spectrum $\spac{*}$ of a binary operation $*$ satisfying property~\eqref{eq:k-depth}. % and its exponential generating function.
If $k = 1$ then we clearly have $\spac{*} = 1$ for all $n \geq 1$. % with exponential generating function $\sum_{n \geq 1} t^n / n! = e^t - 1$.
Thus we assume $k \geq 2$ in the remainder of this section.

For $k=2$ we are looking at subtraction. 
We have $\spac{-} = 2^n - 2$ for $n\ge2$ since the term operations in $F_n^{-}$ are precisely the operations of the form $(a_1, \dots, a_n) \mapsto \pm a_1 \pm a_2 \cdots \pm a_n$ with at least one plus sign and at least one minus sign.
 % and
%\begin{split}
%$\sum_{n = 1}^\infty \spac{-} t^n/n! 
%& = t + \sum_{n \geq 2} \frac{2^n - 2}{n!} t^n \\
%& = t + e^{2t} - 1 - 2t - 2(e^t-1-t) \\ 
%& = t + e^{2t} - 2e^t + 1 \\
%& = t + (e^t-1)^2$.
%\end{split}
For $k\ge2$ we need to use the \emph{Stirling number of the second kind} $S(n,k)$, which counts partitions of the set $\nset{n} = \{1, 2, \dots, n\}$ into $k$ (unordered) blocks. 
%whose exponential generating function is 
%$\sum_{n \geq 1} S(n,k) {t^n}/{n!} = (e^t-1)^k/k!.$



\begin{theorem}
Let $*$ be a binary operation satisfying property~\eqref{eq:k-depth} with $k \geq 2$.
Then
\[ 
\spac{*} = k! S(n,k) + n \sum_{0 \leq i \leq k-2} i! S(n-1,i), 
\qquad \forall n \geq 1.
\]
%\[ \sum_{n=1}^\infty \frac{\spac{*}}{n!} t^n = (e^t - 1)^k + \sum_{0 \leq i \leq k-2} t(e^t-1)^{i}. \]
\end{theorem}


\begin{remark}
When $k = 3$ we have $n \sum_{1 \leq i \leq k-2} i! S(n-1,i) = n$ for all $n \geq 2$.
When $k = 4$, the sequence $n \sum_{1 \leq i \leq k-2} i! S(n-1,i)$ is recorded in OEIS~\cite[A058877]{OEIS} and has simple closed formulas:
$n 2^{n-1} - n = \sum_{1 \leq j \leq n} (n - 2 + j) 2^{n-j-1} 
= \sum_{1 \leq j \leq n-1} \binom{n}{j} (n-j)$.
\end{remark}

Recently, Hein and the first author~\cite{VarCat} generalized the $k$\hyp{}associativity to the \emph{$(k,\ell)$\hyp{}associativity}, based on the example $f * g := xf + yg$ for all $x, y \in \CC[x,y] / (x^k-1, y^\ell-1)$, which satisfies the following for $i = 1, 2,\ldots, n$. 
\begin{equation}\label{eq:k-l-depth}
\forall s, t\in F_n,\ s^{*} = t^{*} \Longleftrightarrow \delta_{T_s}(x_i) \equiv \delta_{T_t}(x_i) \pmod{k},\quad \rho_{T_s}(x_i) \equiv \rho_{T_t}(x_i) \pmod{\ell}
\end{equation}
For $*$ satisfying the above property~\eqref{eq:k-l-depth}, computations show that $\spac{*}$ is not in OEIS.

%$(k,\ell) = (2,2)$: $1$, $2$, $12$, $54$, $260$, $1080$, \ldots 

%$(k,\ell) = (3,2)$: $1$, $2$, $12$, $84$, $590$, $4110$, \ldots 

%$(k,\ell) = (4,2)$: $1$, $2$, $12$, $84$, $770$, $7080$, \ldots

%$(k,\ell) = (3,3)$: $1$, $2$, $12$, $108$, $960$, $9240$, \ldots

%\subsection{The $k$-depth-equivalence}\label{sec:k-depth}
Next, define $a * b := e^{2 \pi i / \ell} a + e^{2 \pi i / k} b$ for all $a,b\in \CC$, which generalizes the example $a * b := a + e^{2 \pi i / k} b$ mentioned earlier.
When $k = \ell$, one sees that two full linear terms agree on $*$ if and only if their corresponding binary trees are $k$\hyp{}depth\hyp{}equivalent, i.e.,
\begin{equation}\label{eq:depth} 
\forall s,t\in F_n,\ s^{*} = t^{*} \Leftrightarrow d_{T_s}(x_i) \equiv d_{T_t}(x_i) \pmod{k} .
\end{equation}
Further generalizations of depth equivalence were studied recently by the second author.

For $k = 2$, the resulting operation is
the \emph{double minus operation} $a \ominus b := -a - b$.
The first author, Mickey, and Xu~\cite{DoubleMinus} showed that
%\[ \spa{\ominus} =
%\begin{cases} 
%\displaystyle \frac{2^{n}-1}{3}, & \text{if $n$ is even}, \\[10pt]
%\displaystyle \frac{2^{n}-2}{3}, & \text{if $n$ is odd}.
%\end{cases} \]
$\spa{\ominus}$ coincides with an interesting sequence in OEIS~\cite[A000975]{OEIS}. 
We show that $\spac{\ominus}$ (or the ac-spectrum of any binary operation satisfying property~\eqref{eq:depth} with $k=2$) agrees with the well\hyp{}known \emph{Jacobsthal sequence}~\cite[A001045]{OEIS}.
%One sees that this theorem holds for any binary operation $*$ satisfying property~\eqref{eq:depth} with $k=2$.
For $k \geq 3$, computations show that neither $\spa{*}$ nor $\spac{*}$ occurs in OEIS.

%$\spa{*}$ for $k = 3$: $1$, $2$, $5$, $14$, $42$, $129$, $398$, $1223$, $3752$, $11510$, \ldots

%$\spa{*}$ for $k = 4$: $1$, $2$, $5$, $14$, $42$, $132$, $429$, $1429$, $4849$, $16689$, \ldots

%$\spac{*}$ for $k = 3$: $1$, $3$, $13$, $35$, $101$, $315$, \ldots

%$\spac{*}$ for $k = 4$: $1$, $3$, $13$, $75$, $285$, $1099$, \ldots



\begin{theorem}
For $n \geq 1$ we have $\spac{\ominus} = (2^n - (-1)^n) / 3$.
\end{theorem}



\section{Remarks and questions}
\label{sec:conclusion}

Cs\'{a}k\'{a}ny and Waldhauser~\cite[Section~4]{AssociativeSpectra1} examined the associative spectra of all two\hyp{}element groupoids (up to isomorphism).
The ac-spectra of two-element groupoids are given in \cref{ex:two-element-groupoids}, \cref{prop:implication} and \cref{prop:Sheffer}.
As possible directions for further research, one could study the associative spectra and the ac-spectra of groupoids with three elements or groupoids satisfying some properties weaker than associativity,
%We would like to mention a few examples of such properties that have emerged in different branches of algebra.
such as alternative, flexible, or power associative groupoids.
We already studied the Jordan algebra in \cref{sec:associative-commutative}, which is commutative (hence flexible), power associative, but not associative. 
Another example is the Okubo algebra, which is flexible and power associative but not associative nor alternative. 





\begin{acknowledgements}
The authors thank the anonymous referees for their helpful comments and suggestions.
\end{acknowledgements}

%% 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}

\begin{thebibliography}{99}

\bibitem{amrsa}
amrsa, Why an alternative magma need not even be power\hyp{}associative?, Mathematics Stack Exchange, URL: \url{https://math.stackexchange.com/q/3132319} (version: 2019-03-01).

\bibitem{Bergman}
C. Bergman, {\it Universal Algebra. Fundamentals and selected topics,} Pure and Applied Mathematics (Boca Raton), 301, CRC Press, Boca Raton, 2012.

\bibitem{Birkhoff}
G. Birkhoff, On the structure of abstract algebras, Proc.\ Cambr.\ Philos.\ Soc.\ {\bf 31} (1935), 433--454.

\bibitem{Subassociative}
M. S. Braitt and\ D. Silberger, Subassociative groupoids, Quasigroups Related Systems {\bf 14} (2006), no.~1, 11--26.

\bibitem{AssociativeSpectra1}
B. Cs\'{a}k\'{a}ny and\ T. Waldhauser, Associative spectra of binary operations, Mult.-Valued Log. {\bf 5} (2000), no.~3, 175--200.

\bibitem{EvenLempel}
S. Even and\ A. Lempel, Generation and enumeration of all solutions of the characteristic sum condition, Information and Control {\bf 21} (1972), 476--482.

\bibitem{CatMod}
N. Hein and J. Huang, Modular Catalan numbers, European J. Comb.\ 61 (2017), 197--218.

\bibitem{VarCat}
N. Hein\ and\ J. Huang, Variations of the Catalan numbers from some nonassociative binary operations, Discrete Math.\ {\bf 345} (2022), no.~3, Paper No. 112711, 18 pp.

\bibitem{Hamming}
J. Huang, Norton algebras of the Hamming graphs via linear characters, Electron.\ J. Combin.\ {\bf 28} (2021), no.~2, Paper No. 2.30, 36 pp.

\bibitem{DoubleMinus}
J. Huang, M. Mickey and\ J. Xu, The nonassociativity of the double minus operation, J. Integer Seq.\ {\bf 20} (2017), no.~10, Art. 17.10.3, 11 pp. 

\bibitem{GM}
A. Giorgilli and G. Molteni, Representation of a 2-power as sum of $k$ 2-powers: a recursive formula, J. Number Theory {\bf 133} (2013), no.~4, 1251--1261.

\bibitem{Knuth}
D. E. Knuth, Letter to R. E. Tarjan and N. J. A. Sloane, Jul. 1975, \url{https://oeis.org/A007178/a007178.pdf}.

\bibitem{KrennWagner}
D. Krenn and S. Wagner, Compositions into powers of $b$: asymptotic enumeration and parameters, Algorithmica {\bf 75} (2016), no.~4, 606--631.

\bibitem{LST}
S. Lehr, J. Shallit and J. Tromp, On the vector space of the automatic reals, Theoret.\ Comput.\ Sci.\ {\bf 163} (1996), no.~1--2, 193--210. 

\bibitem{GraphAlgebra1}
E. Lehtonen and T. Waldhauser, Associative spectra of graph algebras I. Foundations, undirected graphs, antiassociative graphs, J. Algebraic Combin.\ {\bf 53} (2021), no.~3, 613--638.

\bibitem{GraphAlgebra2}
E. Lehtonen\ and\ T. Waldhauser, Associative spectra of graph algebras II. Satisfaction of bracketing identities, spectrum dichotomy, J. Algebraic Combin. {\bf 55} (2022), no.~2, 533--557. 

\bibitem{AssociativeSpectra2}
S. Liebscher and T. Waldhauser, On associative spectra of operations, Acta Sci.\ Math.\ (Szeged) {\bf 75} (2009), no.~3--4, 433--456.

\bibitem{Operads}
J.-L. Loday and B. Vallette, {\it Algebraic operads}, Grundlehren der mathematischen Wissenschaften, 346, Springer, Heidelberg, 2012.

\bibitem{OEIS}
OEIS Foundation Inc. (2011), The On-Line Encyclopedia of Integer Sequences, \url{http://oeis.org}.

\bibitem{Schafer}
R. D. Schafer, On the algebras formed by the Cayley-Dickson process, Amer. J. Math. {\bf 76} (1954), 435--446. 

\bibitem{EC2}
R. P. Stanley, {\it Enumerative combinatorics. Vol. 2}, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, Cambridge, 1999.

\bibitem{Takacs}
L. Tak\'acs, Enumeration of rooted trees and forests, Math.\ Sci.\ {\bf 18} (1993) 1--10.

\end{thebibliography}

