\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{qtree}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\newcommand\T{\mathcal{T}}
\newcommand\CC{\mathbb{C}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf The Nonassociativity of the Double Minus \\
\vskip .1in Operation}
\vskip 1cm
\large
Jia Huang, Madison Mickey, and Jianbai Xu\footnote{
The second and third authors were supported by the Undergraduate Research Fellows program of the University of Nebraska at Kearney.} \\
Department of Mathematics and Statistics \\
University of Nebraska at Kearney \\
Kearney, NE 68849 \\
USA \\
\href{mailto:huangj2@unk.edu}{\tt huangj2@unk.edu} \\
\href{mailto:mickeym2@lopers.unk.edu}{\tt mickeym2@lopers.unk.edu} \\
\href{mailto:xuj2@lopers.unk.edu}{\tt xuj2@lopers.unk.edu} \\
\end{center}
\vskip .2 in
\begin{abstract}
The sequence \seqnum{A000975} in the
{\it Encyclopedia of Integer Sequences} can
be defined by $A_1=1$, $A_{n+1}=2A_n$ if $n$ is odd, and $A_{n+1}=2A_n+1$ if $n$ is even.
This sequence satisfies other recurrence relations, admits some closed formulas, and is known to enumerate several interesting families of objects.
We provide a new interpretation of this sequence using a binary operation defined by $a\ominus b := -a -b$.
We show that the number of distinct results obtained by inserting parentheses in the expression $x_0\ominus x_1\ominus \cdots\ominus x_n$ equals $A_n$, by investigating the leaf depth in binary trees.
Our result can be viewed as a quantitative measurement for the nonassociativity of the binary operation $\ominus$.
\end{abstract}
\section{Introduction}\label{sec:intro}
The sequence \seqnum{A000975} in \emph{The On-Line Encyclopedia of Integer Sequences} (OEIS)~\cite{OEIS} starts with $1,2,5,10,21,42,85,\ldots$.
With its $n$th term denoted by $A_n$, this sequence has the following (equivalent) characterizations.
\begin{itemize}
\item
$A_1=1$, $A_{n+1}=2A_n$ if $n$ is odd, and $A_{n+1}=2A_n+1$ if $n$ is even.
\item
$A_1=1$ and $A_n=2^n-1-A_{n-1}$ for $n\ge2$.
\item
$A_1=1$, $A_2=2$, and $A_n=A_{n-2}+2^{n-1}$ for $n\ge3$.
\item
$A_n$ is the positive integer with an alternating binary representation of length $n$. %$A_n = (\underbrace{1010\cdots}_n)_2$
\end{itemize}
There are also some known closed formulas for this sequence:
\begin{equation}\label{eq:An}
A_n= \left\lfloor \frac{2^{n+1}}3 \right\rfloor = \frac{2^{n+2}-3-(-1)^n}{6}
=\begin{cases}
\displaystyle \frac{2^{n+1}-1}3, & \text{if $n$ is odd}; \\[15pt]
\displaystyle \frac{2^{n+1}-2}3, & \text{if $n$ is even}.
\end{cases}
\end{equation}
According to
Hinz~\cite{Hinz}, this sequence dates back to 1769, when %Georg Christoph
Lichtenberg studied it in connection with the Chinese Rings puzzle (baguenaudier).
This sequence has many interesting interpretations, some of which are listed below.
\begin{itemize}
\item
$A_n$ is the number of moves required to solve the $n$-ring Chinese Rings puzzle~\cite{Hinz}.
\item
$A_n$ is the distance between $0^n$ and $1^n$ in an $n$-bit binary Gray code~\cite[Ch. 1]{HanoiTower}.
\item
$A_n$ is the number of ways to partition $n+2$ people sitting at a circular table into three nonempty groups with no two members of the same group seated next to each other~\cite{CircSet}.
\end{itemize}
The sequence \seqnum{A000975} also has connections to some other sequences in OEIS~\cite{OEIS}, such as \seqnum{A000217}, \seqnum{A048702}, \seqnum{A155051}, \seqnum{A265158}, and so on.
See Stockmeyer~\cite{A000975} for more details.
In this paper we present a new interpretation for the sequence \seqnum{A000975} using a binary operation which is not associative.
This naturally connects to the ubiquitous Catalan numbers and objects counted by Catalan numbers, such as binary trees.
In fact, let $*$ be a binary operation defined on a set $S$ and let $x_0, x_1,\ldots, x_n$ be indeterminates taking values from $S$.
It is well known that the number of ways to insert parentheses in the expression $x_0 * x_1 * \cdots * x_n$ is the \emph{Catalan number} $C_n:=\frac{1}{n+1} \binom{2n}{n}$, which enumerates many families of interesting objects~\cite{EC2}.
A natural question is how many distinct results can be obtained by inserting parentheses in $x_0 * x_1 * \cdots * x_n$ for a given binary operation $*$.
To be more precise, observe that each parenthesization of $x_0 * x_1 * \cdots * x_n$ gives a function from $S^{n+1}\to S$, and if two parenthesizations give the same function then they are said to be \emph{$*$-equivalent}.
Hein and the first author~\cite{CatMod} defined $C_{*,n}$ to be the number of $*$-equivalence classes of parenthesizations of $x_0 * x_1 * \cdots * x_n$.
This provides a quantitative measurement for the nonassociativity of $*$, as we have inequalities $1\le C_{*,n}\le C_n$ where the first equality holds if and only if $*$ is \emph{associative}, i.e., $(a*b)*c=a*(b*c)$ for all $a,b,c\in S$.
Lord~\cite{Lord} introduced the \emph{depth of nonassociativity} of a binary operation and examined this depth for some elementary binary operations.
The nonassociativity measurement $C_{*,n}$ is much finer than the depth of nonassociativity of $*$ since the latter can be written as $\inf \{ n+1: C_{*,n}