\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}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\usepackage[margin=2.5cm]{geometry}
\usepackage[all]{xy}
\usepackage{subcaption}
\newcommand{\mex}{\operatorname{mex}}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\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
Enumerative Properties of Posets \\
Corresponding to a Certain Class of \\
\vskip .1in
Games of No Strategy
}
\vskip 1cm
\large
Caleb Ji \\
Department of Mathematics \\
Washington University in St. Louis \\
1 Brookings Drive \\
St.~Louis, MO 63130 \\
USA \\
\href{mailto:caleb.ji@wustl.edu}{\tt caleb.ji@wustl.edu}
\end{center}
\vskip .2 in
\begin{abstract}
In this paper, we consider a game beginning with a multiset of elements
from a group. Each move replaces two elements with their sum. This is
a game of no strategy and can be modeled by a graded poset with the
rank of a node equal to the cardinality of its multiset. We study the
enumerative properties of certain variations of this game, such as the
number of ways to play them and their numbers of end states. This
leads to several new sequences, as well as new interpretations of
classic sequences such as those found in the Catalan and Motzkin
triangles.
\end{abstract}
\section{Introduction}
Consider the following game, which we will call ``binary fusion":
\begin{quote}
There are $n$ zeroes and $n$ ones on a board where $n$ is a positive integer. On a turn, a player erases any two numbers and replaces them with a zero if they are the same number and a one if they are different numbers. There are two players. The first player wins if the final number is a zero, and the second player wins if the final number is a one.
\end{quote}
The result of this game is fixed, because the sum of the numbers written on the board taken$\pmod 2$ is invariant. Thus this is a \textit{game of no strategy}, a game whose winner is determined by the beginning conditions. These games were studied by Propp in his paper, ``Games of No Strategy and Low-Grade Combinatorics'' \cite{Propp}. Previous study of these games, e.g., in the paper ``Chocolate Numbers'' \cite{Choc}, has revealed that the number of possible states of the game and the number of ways to traverse through them can lead to interesting results.
In this paper, we study the enumerative properties of binary fusion as well as its generalizations and variations. It is possible to look at the states of this game as elements in a graded poset, where a state $x$ is covered by another state $y$ if and only if $x$ can be reached from $y$ in one move. If we alter the rules of the game slightly so that each move replaces a pair of numbers by their sum without taking modulo $2$, the game becomes a generalization of the ``refining partitions" studied by Erd\H{o}s, Guy, and Moon~\cite{Erdos}. By imposing the equivalence relations among the nodes given by the group $\mathbb{Z}/2\mathbb{Z}$ on this, we recover the rules of binary fusion.
In general, the graded posets we study begin with some multiset, or list of elements in a group as a starting node. Given any list corresponding to a node, two of its elements are combined and their sum is returned. The lists resulting from such operations comprise the elements in the poset covered by the parent node. Because each move decreases the number of elements in the lists by $1$, these posets have a natural rank function mapping each node to the cardinality of its corresponding list. Furthermore, there is exactly one end state with rank $1$, since the sum of the elements in the lists is invariant. There are several enumerative properties regarding such posets that we wish to study. The first is the number of maximal chains. This is the number of paths beginning at either end and ending at the other end, going in the same direction. This corresponds to the number of ways to play a game given a starting position. Another number we are interested in is the total number of paths that can be taken beginning at one of the two ends and ending at any node, provided that the path goes in the same direction the entire way. We also consider the total number of edges and the total number of nodes in such posets. Given a group to work in, we can generate interesting sequences by varying the starting node. Many of these sequences are new to the OEIS. Those played under the equivalence relation $2=0$, however, correspond to many classes of grid walking numbers such as the Catalan and Motzkin numbers.
The structure of this paper is as follows. In Section~\ref{binaryFusion} we review previous work~\cite{report} which showed that the number of ways to play binary fusion is equal to the numbers in the Catalan triangle through both a recursion and a bijection. We then calculate the total number of paths which leads to new sequences in the OEIS, and then determine the total number of edges and states. In Section~\ref{overZ} we review the game played over the natural numbers. In Section~\ref{mod3} we consider the game played over the group $\mathbb{Z}/3\mathbb{Z}$. The numbers we are interested in lead to several new sequences in the OEIS. We also prove a bijection between the number of states of the game played over any modulo and a certain class of partitions in this section. In Section~\ref{withX} we consider the game played over the polynomial ring $\mathbb{Z}/2\mathbb{Z}[X]$. We prove a bijection between the number of ways to play the game given a certain class of initial positions with the Motzkin triangle.
\section{Binary fusion}
\label{binaryFusion}
Consider an unordered list of $m$ zeroes and $n$ ones. There are three possible moves: removing two zeroes and adding a zero back in, removing a zero and a one and adding a one back in, and removing two ones and adding a zero. However, because the first two moves result in the same list, they are considered equivalent. Thus, a playing sequence is defined as a sequence of moves transforming the original list into one number using the moves described above, and two playing sequences are considered distinct if and only if any of their moves result in different lists at any stage.
For example, consider the case in which we begin with the list $\{0, 1, 1, 1, 1\}$. Then there are five possible playing sequences:
\begin{enumerate}
\item $\{0, 1, 1, 1, 1 \}\Rightarrow\{1, 1, 1, 1 \}\Rightarrow\{0, 1, 1 \}\Rightarrow\{1, 1 \}\Rightarrow\{0 \}$ .
\item $\{0, 1, 1, 1, 1 \}\Rightarrow\{1, 1, 1, 1 \}\Rightarrow\{0, 1, 1 \}\Rightarrow\{0, 0\}\Rightarrow\{0 \}$.
\item $\{0, 1, 1, 1, 1 \}\Rightarrow\{0, 0, 1, 1 \}\Rightarrow\{0, 1, 1 \}\Rightarrow\{1, 1 \}\Rightarrow\{0 \}$.
\item $\{0, 1, 1, 1, 1 \}\Rightarrow\{0, 0, 1, 1 \}\Rightarrow\{0, 1, 1 \}\Rightarrow\{0, 0\}\Rightarrow\{0 \}$.
\item $\{0, 1, 1, 1, 1 \}\Rightarrow\{0, 0, 1, 1 \}\Rightarrow\{0, 0, 0 \}\Rightarrow\{0, 0\}\Rightarrow\{0 \}$.
\end{enumerate}
\subsection{Number of ways to play}
In this subsection we reproduce the work Ji, Park, and Song~\cite{report} which calculates the number of playing sequences of binary fusion in order to set up later sections.
We will show that the total number of playing sequences generates the Catalan triangle through both a recursion and a bijection. The following table lists some of these values. Let $f(m, n)$ be the number of playing sequences where the initial state consists of $m$ zeroes and $n$ ones. We define $f(0,0)=1$, $f(1, 0)=1$, and $f(0, 1)=1$.
\begin{table}[htbp]
\begin{center}
\begin{tabular}{ c| c | c | c | c | c | c | c | c | c | c | }
$f(m, n)$ & \bfseries 0 & \bfseries 1 & \bfseries 2 & \bfseries 3 & \bfseries 4 & \bfseries 5 & \bfseries 6 & \bfseries 7 & \bfseries 8 & \bfseries 9\\
\hline
\bfseries 0 & 1 & 1 & 1 & 1 & 2 & 2 & 5 & 5 & 14 & 14 \\
\hline
\bfseries 1 & 1 & 1 & 2 & 2 & 5 & 5 & 14 & 14 & 42 & 42 \\
\hline
\bfseries 2 & 1 & 1 & 3 & 3 & 9 & 9 & 28 & 28 & 90 & 90 \\
\hline
\bfseries 3 & 1 & 1 & 4 & 4 & 14 & 14 & 48 & 48 & 165 & 165 \\
\hline
\bfseries 4 & 1 & 1 & 5 & 5 & 20 & 20 & 75 & 75 & 275 & 275 \\
\hline
\bfseries 5 & 1 & 1 & 6 & 6 & 27 & 27 & 110 & 110 & 429 & 429 \\
\hline
\bfseries 6 & 1 & 1 & 7 & 7 & 35 & 35 & 154 & 154 & 637 & 637 \\
\hline
\bfseries 7 & 1 & 1 & 8 & 8 & 44 & 44 & 208 & 208 & 910 & 910 \\
\hline
\bfseries 8 & 1 & 1 & 9 & 9 & 54 & 54 & 273 & 273 & 1256 & 1256 \\
\hline
\end{tabular}
\caption{The first few values of $f(m,n)$}\label{table:f}
\end{center}
\end{table}
\subsubsection{The recursion}
We will first examine the cases when there are only zeroes and when there are only ones. When there are only ones, we must combine two ones to obtain a zero, giving $f(0, n)=f(1, n-2)$ for $n\ge 2$. When there are only zeroes, the only move is to combine zeroes, so $f(m, 0)=1$ for $m\ge 2$. Note that when there is only a single one, all moves remove one zero, so $f(m, 1)=1$ as well. This principle extends to the following lemma:
\begin{lemma}
\label{binaryParity}
For all $i, k\ge 0$, we have $f(i, 2k)=f(i, 2k+1)$
\end{lemma}
\begin{proof}
Note that if the initial state has $2k+1$ ones, there will always be at least a single one by a parity argument. We claim that the set of possible playing sequences of moves beginning with $i$ zeroes and $2k$ ones corresponds with the set of possible playing sequences of first $i+2k-1$ moves beginning with $i$ zeroes and $2k+1$ ones. Clearly, any sequence beginning with the former state can be made beginning with the latter, because the first list is contained in the second. But if there is a sequence beginning with the second state that cannot be made beginning with the first, consider the first move that can be made with the second initial state that cannot be made with the first. The second state has one more one than the first, but if it has more than a single one it must have at least three ones, so the first state has at least two ones and can make any move the second can. Otherwise, the second state has a single one, so the extra move it can make is combining a one and a zero. But then there must be at least two zeroes in the first state, and combining them results in the same move. Thus, the first $i+2k-1$ moves beginning with the second initial state is in bijection with the playing sequences beginning with the first initial state. This must result in a one and a zero by a parity argument, so there is only one possible final move, implying the result.
\end{proof}
Now we give the general recursion for $f(m, n)$ for $m\ge 1$, $n\ge 2$. The first move can combine two zeroes, leaving us with $f(m-1, n)$ ways left to play. If we combine a zero and a one, we have the same result, so there are no new ways to play here. If we combine two ones, we get $f(m+1, n-2)$ ways left to play. Thus, we have \[f(m, n)=f(m-1, n)+f(m+1, n-2)\] for all $m, n\ge 2$.
\subsubsection{General formula}
Using the recursion, we prove the following general formula.
\begin{theorem}
\label{binaryWays}
For all $i, k\ge 0$, we have
\[f(i, 2k)=f(i, 2k+1)=\dfrac{(i+1)(i+k+2)(i+k+3)\cdots(i+2k)}{k!}=\dfrac{i+1}{i+k+1}\dbinom{i+2k}{k}.\]
\begin{proof}
We prove the result for $f(i, 2k)$, which is sufficient because $f(i, 2k)=f(i, 2k+1)$ by Lemma~\ref{binaryParity}. Furthermore, as shown in the preliminary analysis earlier in this section, we have $f(i,0)=f(i,1)=1$. Thus we may assume $k\ge 1$. We proceed by induction on $k$. For $k=1$ there are $i+1$ total steps, $i$ of which are eliminating one zero and one of which is combining two ones. We can choose which one of these to be the one combining two ones, so there are $i+1$ ways to play as desired.
Assume the statement for some $k\ge 1$; we now prove the statement for $k+1$. To do this, we use a second induction on $i$. For $i=0$, from the recursion and the induction hypothesis we have \[f(i, 2k)=f(0, 2k)=f(1, 2k-2)=\dfrac{2}{2k}\dbinom{1+2k}{k}=\dfrac{1}{k+1}\dbinom{2k}{k},\] as desired. Now suppose the statement holds for some $i\ge 0$. Then we have
\begin{equation}
\begin{split}
f(i, 2k+2) &= f(i-1, 2k+2)+f(i+1, 2k) \\[5pt]
&= \dfrac{i}{i+k+1}\dbinom{i+2k+1}{k+1}+\dfrac{i+2}{i+k+2}\dbinom{i+2k+1}{k} \\[5pt]
&= \dfrac{(i+2k+1)(i+2k)\cdots(i+k+2)i}{(k+1)!}+\dfrac{(i+2k+1)(i+2k)\cdots(i+k+3)(i+2)}{k!} \\[5pt]
&= \dfrac{(i+2k+1)(i+2k)\cdots(i+k+3)(i(i+k+2)+(i+2)(k+1))}{(k+1)!}
\\[5pt]
&= \dfrac{(i+2k+1)(i+2k)\cdots(i+k+2)(i^2+2ik+3i+2k+2)}{(i+k+2)(k+1)!} \\[5pt]
&= \dfrac{(i+2k+1)(i+2k)\cdots(i+k+2)(i+2k+2)(i+1)}{(i+k+2)(k+1)!} \\[5pt]
&= \dfrac{i+1}{i+k+2}\dbinom{i+2k+2}{k+1},
\end{split}
\end{equation}
as desired. This completes the induction on $i$, which in turn completes the induction on $k$, completing the proof.
\end{proof}
\end{theorem}
The entries of the Catalan triangle are defined by $C_{n, k}=\dfrac{(n+k)!(n-k+1)}{k!(n+1)!}$ and are given by sequence \seqnum{A001263} in the OEIS~\cite{OEIS}. We let $C_n$ denote the diagonal entries $C_{n, n} = \dfrac{1}{n+1}\dbinom{2n}{n}$, which are also known as the Catalan numbers and which are given by sequence \seqnum{A000108} in the OEIS~\cite{OEIS}. By Theorem~\ref{binaryWays}, we have
\begin{equation}
f(n-k,2k)=f(n-k, 2k+1)=C_{n, k}.
\end{equation}
and thus
\begin{equation}
f(0, 2n) = f(0, 2n+1) = C_n.
\end{equation}
\subsubsection{Bijective proof}
\label{CatBij}
The number $C_{n,k}$ is known to be the number of strings consisting of $n$ X's and $k$ Y's such that no initial substring contains more Y's than X's. Here we give a combinatorial proof showing that the number of ways to play binary fusion is equal to this.
Consider $f(n-k, 2k)$. We let X denote every move removing a zero and we let Y denote every move removing a pair of ones and adding a zero. After the game is over, we know there must be one zero remaining, so add a move that removes it as an X. Consider all possible ways to play the game and their respective sequences in reverse order. We know there must be precisely $k$ Y's, which means there must be a total of $n-k+k=n$ X's. If, at some point in such a sequence (going backwards), there are more Y's than X's, then let there be $c$ X's and $c'$ Y's with $c'>c$. Looking at the sequence forwards, there must be $n-c$ X's and $k-c'$ Y's played to get to the corresponding position. But then at that point, there have been $n-k+k-c'=n-c'$ zeroes total at that point or before, while $n-c$ zeroes have been removed. Since $n-c>n-c'$, this is impossible.
Conversely, if no initial string starting backwards has more Y's than X's, then there clearly will be enough zeroes and pairs of ones to remove at each point, so each sequence corresponds to a playing sequence of the game. Furthermore, every two distinct sequences must result in different moves in the game, so must result in distinct playing sequences of the game. Thus, there is a bijective correspondence between the number of sequences of X's and Y's and the number of playing sequences of the game.
\subsection{Total number of paths}
Consider the poset generated with an initial state consisting of all ones. Here we consider the total number of paths going either up or down that can be taken beginning from either end. For example, as shown in Figure~\ref{fig:6binary}, beginning from $\{1, 1, 1, 1, 1, 1\}$, there is $1$ path of length $0$, $1$ path of length $1$, $2$ paths of length $2$, $3$ paths of length $3$, $5$ paths of length $4$, and $5$ paths of length $5$ for a total of $17$ paths. Beginning from the other end with $\{0\}$, there is $1$ path of length $0$, $2$ paths of length $1$, $3$ paths of length $2$, $5$ paths of length $3$, $5$ paths of length $4$, and $5$ paths of length $5$, for a total of $21$ paths.
First we consider the paths beginning with $n$ ones. Let this sequence be $(a_n)_{n\ge 1}$. If $n$ is of the form $2k+1$, the analysis shown in Section~\ref{CatBij} implies that the poset forms the half of a square grid over which the paths correspond to Dyck paths. Then the number of paths is equal to the partial sums of the Catalan numbers given by sequence \seqnum{A014138} in the OEIS~\cite{OEIS}. Similarly, if $n$ is of the form $2k$, then the poset is equivalent to that of $n=2k+1$, without the final edge. Thus the number of total paths is equal to the number of total paths for $n=2k+1$, minus the number of ways to travel between the ends in the poset for $n=2k+1$. Thus, $a_{2k}=a_{2k+1}-C_k$, where $C_k$ is the $k^\text{th}$ Catalan number.
This forms a new sequence in the OEIS~\cite{OEIS}: \seqnum{A276033}: 1, 2, 3, 6, 8, 17, 22, 50, 64, 154, 196, 493, 625, 1626, 2055, 5487, 6917, 18851, 23713, 65703, 82499, 231725, 290511.
\begin{figure}[H]
\centering
\begin{minipage}{.5\textwidth}
\centering
\[
\xymatrix@C=0em{
111111 \ar@{-}[dr] \\
& 11110 \ar@{-}[dl] \ar@{-}[dr] \\
1111 \ar@{-}[dr]
&& 1100 \ar@{-}[dl] \ar@{-}[drr] \\
& 110 \ar@{-}[dl] \ar@{-}[dr]
&&& 000 \ar@{-}[dll] \\
11 \ar@{-}[dr]
&& 00 \ar@{-}[dl] \\
& 0
}
\]
\captionof{figure}{Poset for $n=6$ over $\mathbb{Z}/2\mathbb{Z}$}
\label{fig:6binary}
\end{minipage}%
\begin{minipage}{.5\textwidth}
\centering
\[
\xymatrix@C=0em{
1111111 \ar@{-}[dr] \\
& 111110 \ar@{-}[dl] \ar@{-}[dr] \\
11111 \ar@{-}[dr]
&& 11100 \ar@{-}[dl] \ar@{-}[drr] \\
& 1110 \ar@{-}[dl] \ar@{-}[dr]
&&& 1000 \ar@{-}[dll] \\
111 \ar@{-}[dr]
&& 100 \ar@{-}[dl] \\
& 10 \ar@{-}[dl] \\
1
}
\]
\captionof{figure}{Poset for $n=7$ over $\mathbb{Z}/2\mathbb{Z}$}
\label{fig:7binary1}
\end{minipage}
\end{figure}
Beginning from the other end, the numbers obtained are similar. The even-indexed terms are the same partial Catalan sums by symmetry. The odd-indexed terms are precisely $1$ less than the following even-numbered term, since they are simply missing the trivial path consisting of no edges.
This forms a new sequence in the OEIS~\cite{OEIS}: \seqnum{A276032}:
1, 2, 3, 7, 8, 21, 22, 63, 64, 195, 196, 624, 625, 2054, 2055, 6916, 6917, 23712, 23713, 82498, 82499, 290510, 290511, 1033410, 1033411, 3707850, 3707851, 13402695, 13402696.
\subsection{Total number of edges and states}
It is fairly straightforward to calculate the number of edges of the posets formed when the initial state consists of all ones. Given the geometry of the half-square lattice these posets form, we count the number of edges with slope $1$ and those with slope $-1$ when positioned as shown in Figure~\ref{fig:7binary1}. For $n=2k+1$, the number of edges is $2\cdot(1+2+\cdots + k)=k^2+k$. For $n=2k$, the number of edges is $1$ less than that for $n=2k+1$, i.e., $k^2+k-1$. This gives sequence \seqnum{A140144} in the OEIS~\cite{OEIS}, which has first terms: 1, 2, 5, 6, 11, 12, 19, 20, 29, 30, 41, 42, 55, 56, 71, 72.
Now consider the same question where the initial state consists of $m$ zeroes and $n$ ones.
Consider the total number of states of the game, where the initial state consists of $n$ ones. For $n=2k+1$, this is the $k+1^\text{th}$ triangular number, and for $n=2k$, this is $1$ less than the $k+1^\text{th}$ triangular number. We claim that this is equal to the number of partitions of $n$ where parts differ by at most $2$. This is given by sequence \seqnum{A117142} in the OEIS~\cite{OEIS}. The first few terms of this sequence are 1, 2, 3, 5, 6, 9, 10, 14, 15, 20, 21, 27, 28, 35, 36, 44, 45, 54, 55, 65, 66, 77, 78, 90, 91, 104, 105, 119, 120, 135, 136, 152, 153, 170, 171, 189, 190, 209, 210, 230, 231, 252, 253, 275, 276, 299, 300. We defer the proof of this claim to the next section, where we prove a more general result.
\section{Refining partitions: the game over $\mathbb{Z}$}
\label{overZ}
Consider the graded poset consisting of the distinct partitions of $n$ for any positive integer $n$. We say that a partition $x$ covers another partition $y$ if $y$ can be achieved from $x$ by removing two elements from $x$ and replacing them by their sum. Consider the number of maximal chains of this poset. This is given by the sequence \seqnum{A002846} in the OEIS~\cite{OEIS}. This is equal to the number of ways to transform a set of $n$ indistinguishable objects into $n$ singletons via a sequence of $n-1$ refinements, where a refinement is a separation of a set into two. Indeed, each maximal chain corresponds to a path from the set $\{1, 1, \ldots, 1\}$ to $\{n\}$, and each sequence of refinements is simply that path taken backwards.
Taking all elements of the nodes of the poset modulo $2$ imposes certain equivalence relations on the nodes. Namely, states which are equivalent when their elements are taken modulo $2$ now become the same node. The bijection shown in Section~\ref{CatBij} implies that the Hasse diagrams of these posets become Dyck paths under this equivalence relation.
\begin{figure}[H]
\centering
\begin{subfigure}{.5\textwidth}
\centering
\[
\xymatrix@C=0em{
&&&& 1111111 \ar@{-}[d] \\
&&&& 211111 \ar@{-}[dl] \ar@{-}[dr] \\
&&& 31111 \ar@{-}[dl] \ar@{-}[dr]
&& 22111 \ar@{-}[dlll] \ar@{-}[dl] \ar@{-}[drr] \\
&& 4111 \ar@{-}[d] \ar@{-}[drr]
&& 3211 \ar@{-}[dll] \ar@{-}[d] \ar@{-}[drrr] \ar@{-}[drrrrrrrrr]
&&& 2221 \ar@{-}[dlll] \ar@{-}[drrrrrr] \\
&& 511 \ar@{-}[d] \ar@{-}[drr]
&& 421 \ar@{-}[dll] \ar@{-}[d] \ar@{-}[drrr]
&&& 331 \ar@{-}[dlllll] \ar@{-}[d]
&&&&&& 322 \ar@{-}[dlllllllll] \ar@{-}[dllllll] \\
&& 61 \ar@{-}[drr]
&& 52 \ar@{-}[d]
&&& 43 \ar@{-}[dlll] \\
&&&& 7
}
\]
\caption{over $\mathbb{Z}$}
\label{fig:7overZ}
\end{subfigure}%
\begin{subfigure}{.5\textwidth}
\centering
\[
\xymatrix@C=0em{
1111111 \ar@{-}[dr] \\
& 111110 \ar@{-}[dl] \ar@{-}[dr] \\
11111 \ar@{-}[dr]
&& 11100 \ar@{-}[dl] \ar@{-}[drr] \\
& 1110 \ar@{-}[dl] \ar@{-}[dr]
&&& 1000 \ar@{-}[dll] \\
111 \ar@{-}[dr]
&& 100 \ar@{-}[dl] \\
& 10 \ar@{-}[dl] \\
1
}
\]
\caption{over $\mathbb{Z}/2\mathbb{Z}$}
\label{fig:7binary2}
\end{subfigure}
\caption{Posets for $n=7$ side by side}
\label{fig:test}
\end{figure}
The number of edges in these posets beginning with $n$ ones corresponds to sequence \seqnum{A000097} in the OEIS~\cite{OEIS}: 0, 1, 2, 5, 9, 17, 28, 47, 73, 114, 170. \\
\section{Playing in modulo 3}
\label{mod3}
We will now consider the same game in modulo $3$ rather than modulo $2$. The enumerative properties we are concerned with remain the same, but in this variation the numbers form new sequences.
\subsection{Number of ways to play}
Let $f(a, b, c)$ be the number of ways to play this game when beginning with $a$ zeroes, $b$ ones, and $c$ twos. If we define $f(0, 0, 0)=1$, it is easy to see that when $a+b+c\le 2$, we have $f(a, b, c)=1$. The possible moves consist of combining two zeroes, a zero and a one, a zero and a two, two ones, two twos, and a one and a two. If we define $f(a, b, c)$ to be $0$ whenever any of the arguments are negative, this leads to the following recursion:
\[
f(a, b, c) = f_1 + f_2 + f_3 + f_4
\]
where $f_1 = f(a-1, b, c)$ if $a\ge 2$ or $a, b\ge 1$ or $a, c\ge 1$, $f_2 = f(a, b-2, c+1)$ if $b\ge 2$, $f_3 = f(a, b+1, c-2)$ if $c\ge 2$, and $f_4 = f(a+1, b-1, c-1)$ if $b, c\ge 1$, and each are $0$ otherwise.
These numbers form new sequences in the OEIS~\cite{OEIS}.
\medskip
The following sequence, \seqnum{A276027} in the OEIS, is defined by $a_n = f(0, n, 0)$: \\
$1, 1, 1, 2, 4, 7, 18, 43, 93, 266, 702, 1687, 5136, 14405, 36898$.
\medskip
The following sequence, \seqnum{A276028} in the OEIS, is defined by $a_n = f(n, n, 0) = f(n, 0, n)$:
$1, 3, 10, 50, 259, 1540, 9594, 62649, 422598, 2960716, 21030711$.
\medskip
The following sequence, \seqnum{A276029} in the OEIS, is defined by $a_n = f(0, n, n)$: \\
$1, 4, 27, 228, 2226, 23778, 270693, 3229106, 39922172$.
\medskip
One can also consider playing the game in modulo $n$ for other values of $n$. Computations made by the author indicate that only for $n=2$ do the generated sequences already appear in the OEIS.
\subsection{Total number of edges and states}
If the initial state consists of $n$ ones, the number of edges in such a poset forms a new sequence in the OEIS~\cite{OEIS}: \seqnum{A276031}. The first few terms of this sequence are 0, 1, 2, 5, 9, 14, 21, 30. \\
Again consider an initial state of $n$ ones. We claim that the number of total nodes in such a poset is equal to the number of partitions of $n$ where the parts differ by at most $3$. This is sequence \seqnum{A117143} in the OEIS~\cite{OEIS}. More generally, we have the following theorem.
\begin{figure}[H]
\centering
\begin{minipage}{.5\textwidth}
\centering
\[
\xymatrix@C=0em{
&&&& 1111111 \ar@{-}[d] \\
&&&& 211111 \ar@{-}[dl] \ar@{-}[dr] \\
&&& 11110 \ar@{-}[dl] \ar@{-}[dr]
&& 22111 \ar@{-}[dlll] \ar@{-}[dl] \ar@{-}[drr] \\
&& 1111 \ar@{-}[d]
&& 2110 \ar@{-}[dll] \ar@{-}[d] \ar@{-}[drrr]
&&& 2221 \ar@{-}[dlll] \ar@{-}[dlllll] \\
&& 211 \ar@{-}[dr] \ar@{-}[drrr]
&& 220 \ar@{-}[dl] \ar@{-}[dr]
&&& 100 \ar@{-}[dllll] \\
&&& 10 \ar@{-}[dr]
&& 22 \ar@{-}[dl] \\
&&&& 1
}
\]
\captionof{figure}{Poset for $n=7$ over $\mathbb{Z}/3\mathbb{Z}$}
\label{fig:7mod3}
\end{minipage}%
\begin{minipage}{.5\textwidth}
\centering
\[
\xymatrix@C=0em{
&&&& 1111111 \\
&&&& 211111 \\
&&& 31111
&& 22111 \\
&& 4111
&& 3211
&&& 2221 \\
&& 421
&& 322
&&& 331 \\
&&& 43
&& 52 \\
&&&& 7
}
\]
\captionof{figure}{The partitions of $7$ corresponding to the nodes in Figure~\ref{fig:7mod3}}
\label{fig:7mod3partitions}
\end{minipage}
\end{figure}
\begin{theorem}
Given any positive integer $k$, consider the poset corresponding to the game beginning with $n$ ones in modulo $k$. The number of nodes in this poset is equal to the number of partitions of $n$ such that any two parts differ by at most $k$.
\begin{proof}
Consider the nodes in such a poset of rank $i$; i.e., with $i$ elements. We will prove that the number of such nodes is equal to the number of partitions of $n$ into $i$ parts such that any two parts differ by at most $k$, which will prove the result. We do this by first demonstrating an injective map from the number of partitions whose parts differ by at most $k$ to each node, and then an injective map in the opposite direction.
Take a partition of $n$: $n=m_1+m_2+\cdots +m_i$. After reducing each part modulo $k$, say the terms become $a_1$, $a_2$, $\ldots$, $a_i$. Then we claim that this is a node in the poset, and that no other partition can result in this node. To show that it is achievable through the game, note that $a_1$, $a_2$, $\ldots$, $a_i$ are all less than $k$ and that their sum is equivalent to $n$ modulo $k$. Beginning with $n$ ones, sum up the first $a_1$ ones, then the next $a_2$ ones and so on, till the list becomes $a_1$, $a_2$, $\ldots$, $a_i$, and some number of ones left over. The number of ones left over must be divisible by $k$, so adding them up will result in a $0$, which can then be removed upon combination with any of the other elements. Now assume that two partitions: $m_1$, $\ldots$, $m_i$ and $m_1'$, $\ldots$, $m_i'$ give the same result when all their elements are taken modulo $k$. Then it must be possible to reach the second partition from the first by adding multiples of $k$ to some elements and subtracting multiples of $k$ from others. Say $m_c$ is increased and $m_d$ is decreased in forming the second partition from the second, for some indices $c$ and $d$. Then $m_c'-m_d'\ge 2k-k=k$, with equality holding if and only if $m_c = m_d-k$ and $m_c$ is increased by $k$ and $m_d$ is decreased by $k$. Thus, because any two parts in the partition differ by at most $k$, all changes must be of this form. But then this does not change the original partition at all, so the second partition is not distinct from the first, contradiction. This shows that the number of nodes is at least the number of these partitions.
Now we show that we can achieve a distinct partition whose parts differ by at most $k$ from every node. Take any node, and say that it is comprised of elements $c_1\le c_2\le\cdots\le c_i$. Let $n=c_1+c_2+\cdots +c_i+tk$, where $t$ is an integer. Then make the following adjustment $t$ times: take the smallest element in the list, add $k$ to it, and reorder the list. This process preserves the property that all elements are within $k$ of each other at each step, so the result will indeed be a partition of $n$ into parts which differ by at most $k$. To show that two different nodes result in distinct partitions, note that if they resulted in the same partition, then that partition taken modulo $k$ must result in two different nodes, which is clearly impossible. This shows that the number of nodes is at most the number of these partitions, finishing the proof.
\end{proof}
\end{theorem}
This proves that the triangle of numbers of nodes in this game taken over modulo $n$ corresponds with \seqnum{A194621} in the OEIS~\cite{OEIS}.
\section{Number of ways to play over polynomial rings over $\mathbb{Z}/2\mathbb{Z}$}
\label{withX}
Playing this game over the polynomial ring $\mathbb{Z}/2\mathbb{Z}[X]$ gives a direct generalization of binary fusion. If the initial state consists of only constant terms of $0$ and $1$, then the result is described in Section~\ref{binaryFusion}. First we will consider the number of ways to play when the initial condition consists of a single $X$ and some constant terms. There are three types of moves. One can combine $0$ with another element, which results in removing a zero. One can combine two ones, resulting in a zero. One can combine $X$ or $X+1$ with $1$, changing $X$ to $X+1$ and vice versa and removing a $1$.
First, recall that the Motzkin triangle, given by sequence \seqnum{A026300} in the OEIS~\cite{OEIS}, refers to the number of king-paths of length $n$ on a grid from $(0, 0)$ to $(n, n-k)$ when denoted by $T(n, k)$. A king-path is a path in which each step increases the coordinates by $(1, 0)$, $(1, 1)$, or $(1, -1)$.
\begin{theorem}
Consider the poset generated with initial state consisting of a single $X$, $m$ zeroes, and $n$ ones. Let $f(1, m, n)$ be the number of maximal chains in this poset. Then $f(1, m, n) = T(m+n, n)$, where $T(m, n)$ refers to the Motzkin triangle.
\begin{proof}
It suffices to prove that $f(1, m, n)$ is the number of king-paths from $(0, 0)$ to $(m+n, m)$ that do not go below the $x-$axis, or equivalently, the number of king-paths from $(m+n, m)$ to $(0, 0)$ that do not go below the $x-$axis. Represent every move that removes a zero by an $A$, every move that combines two ones by a $B$, and every move that combines $X$ or $X+1$ with a one by a $C$. Given any playing sequence, associate every $A$ with a move with vector $(-1, -1)$, every $B$ with a move with vector $(-1, 1)$, and every $C$ with a move with vector $(-1,0)$. We will show that this gives a bijection between these playing sequence and the distinct king-paths from $(m+n, m)$ to $(0, 0)$ which does not go below the $x-$axis.
First, note that the number of zeroes at any stage is equal to the $y-$coordinate of the king at that stage. This can be directly checked by looking at how each move works. This implies that each king-path resulting from such a sequence can never go below the $x-$axis. Furthermore, note that each move decreases the $x-$coordinate of the king by $1$. This implies that after $m+n$ moves, the king will indeed be at $(0, 0)$. Furthermore, two different sequences must differ at some spot, and thus will generate different king-paths. Thus it remains to show that all king-paths can be generated through such a sequence. Assume the contrary. Take the first move in such a king-path that cannot be made by a playing sequence. Each move $A$ can be made since if the king is above the $x-$axis, there will be a zero that can be combined with some other term. Now consider the case where it is a $B$ move. If it cannot be made in the playing sequence, then there are no ones left. So there is an $X$ or $X+1$ and say $c$ zeroes. If the king moves to the left, then in the following $c-1$ moves, it must return to the origin. But its $y-$ coordinate is $c$, so this is not possible. Finally, consider the case where it is a $C$ move. If it cannot be made in the playing sequence, then there are either $0$ or $1$ ones left. This fails for precisely the same reason as in the previous case. Thus every king-path can be made through a playing sequence, as desired.
\end{proof}
\end{theorem}
This implies that $f(1, 0, n)=M_n$, where $M_n$ denotes the $n^\text{th}$ Motzkin number. These numbers are given by sequence \seqnum{A001006} in the OEIS~\cite{OEIS}.
\begin{figure}[H]
\centering
\begin{minipage}{.5\textwidth}
\centering
\[
\xymatrix@C=0em{
&&&&& X0111 \ar@{-}[dlll] \ar@{-}[d] \ar@{-}[drrr] \\
&& X001 \ar@{-}[d] \ar@{-}[drrr]
&&& (X+1)011 \ar@{-}[dlll] \ar@{-}[d] \ar@{-}[drrr]
&&& X111 \ar@{-}[dlll] \ar@{-}[d] \\
&& (X+1)00 \ar@{-}[drrr]
&&& X01 \ar@{-}[d] \ar@{-}[drrr]
&&& (X+1)11 \ar@{-}[dlll] \ar@{-}[d] \\
&&&&& (X+1)0 \ar@{-}[drrr]
&&& X1 \ar@{-}[d] \\
&&&&&&&& X+1
}
\]
\captionof{figure}{Poset for $f(1, 1, 3)$ }
\label{fig:Mot3}
\end{minipage}%
\begin{minipage}{.5\textwidth}
\centering
\[
\xymatrix@C=0em{
&&&&& (0, 0) \ar@{-}[dlll] \ar@{-}[d] \ar@{-}[drrr] \\
&& (1, -1) \ar@{-}[d] \ar@{-}[drrr]
&&& (1, 0) \ar@{-}[dlll] \ar@{-}[d] \ar@{-}[drrr]
&&& (1, 1) \ar@{-}[dlll] \ar@{-}[d] \\
&& (2, -1) \ar@{-}[drrr]
&&& (2, 0) \ar@{-}[d] \ar@{-}[drrr]
&&& (2, 1) \ar@{-}[dlll] \ar@{-}[d] \\
&&&&& (3, 0) \ar@{-}[drrr]
&&& (3, 1) \ar@{-}[d] \\
&&&&&&&& (4, 0)
}
\]
\captionof{figure}{Coordinates of the king-path corresponding to Figure~\ref{fig:Mot3}}
\label{fig:MotCoor}
\end{minipage}
\end{figure}
\section{Acknowledgments}
The author would like to thank Tanya Khovanova for a valuable discussion as well as the referee and editor for helpful suggestions.
\begin{thebibliography}{9}
\bibitem{Choc}
C.~Ji, T.~Khovanova, R.~Park, and A.~Song, Chocolate numbers, \textit{J. Integer Sequences} \textbf{19} (2016), \href{https://cs.uwaterloo.ca/journals/JIS/VOL19/Khovanova/khova9.html}{Article 16.1.7}.
\bibitem{report}
C.~Ji, R.~Park, and A.~Song, Combinatorial games of no strategy, manuscript, 2015, \url{http://math.mit.edu/research/highschool/primes/materials/2015/Ji-Park-Song.pdf}.
\bibitem{Erdos}
P. Erd\H{o}s, R. K. Guy, and J. W. Moon, On refining partitions, \textit{J. London Math. Soc.} \textbf{9} (1975), 565--570.
\bibitem{OEIS}
N. J. A. Sloane, The Online Encyclopedia of Integer Sequences, published electronically
at \url{http://oeis.org}.
\bibitem{Propp}
J.~G.~Propp,
Games of no strategy and low-grade combinatorics,
\url{http://faculty.uml.edu/jpropp/moves15.pdf}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent \textit{2010 Mathematics Subject Classification}: Primary 05A15.
\noindent {\it Keywords:} poset, game of no strategy, Catalan triangle,
Motzkin triangle, recursion, bijection.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000097},
\seqnum{A000108},
\seqnum{A001006},
\seqnum{A001263},
\seqnum{A002846},
\seqnum{A014138},
\seqnum{A026300},
\seqnum{A117142},
\seqnum{A117143},
\seqnum{A140144},
\seqnum{A194621},
\seqnum{A276027},
\seqnum{A276028},
\seqnum{A276029},
\seqnum{A276030},
\seqnum{A276031},
\seqnum{A276032}, and
\seqnum{A276033}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received August 26 2016;
revised versions received December 30 2016; March 20 2017.
Published in {\it Journal of Integer Sequences}, March 25 2017.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}