# The Polynomial Profile of Distance Games on Paths and Cycles

Svenja Huntemann  Department of Mathematical and Physical Sciences
Concordia University of Edmonton
Edmonton, AB, Canada  and  Lexi Nash

###### Abstract.

Distance games are games played on graphs in which the players alternately
colour vertices, and which vertices can be coloured only depends on the
distance to previously coloured vertices. The polynomial profile encodes the
number of positions with a fixed number of vertices from each player. We
extend previous work on finding the polynomial profile of several distance
games (Col, Snort, and Cis) played on paths. We give recursions and generating
functions for the polynomial profiles of generalizations of these three games
when played on paths. We also find the polynomial profile of Cis played on
cycles and the total number of positions of Col and Snort on cycles, as well
as pose a conjecture about the number of positions when playing Col and Snort
on complete bipartite graphs.

###### Key words and phrases:

Combinatorial game, polynomial profile, distance game, Col, Snort

###### 2010 Mathematics Subject Classification:

Primary 91A46; Secondary 05C30, 05C57;

The second author’s research was supported by the Natural Sciences and
Engineering Research Council of Canada (funding reference number USRA – 562933
- 2021).

##  1\. Introduction

A combinatorial game is a game with two players, Left and Right, with perfect
information, no elements of chance, and the players must alternate turns, such
as Chess or Checkers. In this paper, we will be enumerating the positions in
several distance games. These are games in which the two players place pieces
on empty vertices of the board, a finite graph, with the placement of a piece
only being restricted by the distance to previously played pieces. Two well-
known examples of distance games are Snort and Col, where pieces cannot be
placed adjacent to an opponent’s piece, respectively one of their own pieces.

A relatively new topic of interest in combinatorial game theory is the
enumeration of positions. Early work has focused on specific types of
positions, such as Go end positions [6, 5, 16] and second-player win position
for some lesser known games [7, 11]. Recently, Domineering positions, as well
as specific types of positions, were counted in [9]. Although taking a graph
theory view, positions of several other games played on grids are enumerated
in [12, 13]. Our work is motivated by Brown et al. [2], who introduced the
polynomial profile of a game, which is the generating polynomial for the
number of positions given the number of Left and Right pieces placed. They
found generating functions for the polynomial profiles of several games played
on paths, including Snort, Col, and the game Cis. We extend their work and
will find the polynomial profiles of generalizations of these three games
played on paths (Section 3), and consider the original three games when played
on cycles and complete bipartite graphs (Section 4).

In the next section, we provide some background and previous results from this
area of combinatorial game theory. This includes a few definitions and
descriptions of different placement games. We will conclude this paper with
several questions for future work in Section 5.

##  2\. Background

Many combinatorial games are ones in which the players place pieces on a board
without moving or removing them later. These are known as placement or pen-
and-paper games. We will be studying several games that belong to a subclass
of placement games. Note that for placement games, placing a piece is
equivalent to colouring the corresponding vertices of the board. For the
placement, Left will colour a vertex bLue and Right will colour in Red.

######  Definition 2.1 ([10]).

_Distance games_ are a subclass of combinatorial games played on finite
graphs, with each game uniquely identified by a pair of sets $(S,D)$. On their
turn, a player will colour in an empty vertex that is not distance $s\in S$
from a piece of the same colour or distance $d\in D$ from a piece of the
opposite (different) colour.

Although the rules of a distance game are deceptively easy to describe,
several games have been extensively studied and are still unsolved. For
example, their computational complexity has been studied in [14, 3, 8].

######  Definition 2.2.

The following are some previously studied distance games.

  * •

_Col_[1] is the distance game where $S=\\{1\\}$ and $D=\emptyset$. In other
words, pieces of different colours can be adjacent, but pieces of the same
colour cannot.

  * •

_Snort_[1] is the distance game where $S=\emptyset$ and $D=\\{1\\}$. In other
words, pieces of the same colour can be adjacent, but pieces of different
colours cannot.

  * •

_Cis_ [2] is the distance game where $S=D=\\{1\\}$. In other words, no two
pieces can be adjacent, no matter the colour.

Note that playing Cis is equivalent to playing NodeKayles. If a player can
place a piece on a vertex in either game, then so can the other player. The
difference between these games is that in NodeKayles both players colour using
the same colour, while in Cis they use different colours. This is not relevant
to the game play, but will be important for enumeration.

We will consider generalizations of the above games, the first two of which
were defined in [3].

######  Definition 2.3.

  * •

EnCol$(k)$ is the distance game where $S=\\{1,\ldots,k\\}$ and $D=\emptyset$.

  * •

EnSnort$(k)$ is the distance game where $S=\emptyset$ and
$D=\\{1,\ldots,k\\}$.

  * •

EnCis$(k)$ is the distance game where $S=D=\\{1,\ldots,k\\}$.

  * •

$\textsc{Cis}_{2}$ is the distance game where $S=D=\\{2\\}$.

We will count the positions in Snort, Col, and Cis played on cycles, stars,
and complete bipartite graphs, as well as their generalization when played on
paths. To enumerate the positions of these distance games we use a generating
function called the polynomial profile.

######  Definition 2.4 ([2]).

The _polynomial profile_ of the game $G$ played on the board $B$ with $n$
vertices is the bivariate polynomial

$P_{G,B}(x,y)=\sum_{k=0}^{n}\sum_{j=0}^{k}f_{j,k-j}x^{j}y^{k-j}$

where $f_{j,j-k}$ is the number of position with $j$ Left pieces and $k-j$
Right pieces.

Setting $x=y$ we get the univariate polynomial

$P_{G,B}(x):=P_{G,B}(x,x)=\sum_{i=0}^{n}c_{i}x^{i},$

where $c_{i}$ is the number of positions with exactly $i$ pieces. Finally, the
total number of legal positions can be obtained by setting $x=y=1$.

The polynomial profile counts the number of positions without assuming
alternating play. In many combinatorial games, including distance games, the
board naturally breaks into smaller, independent components as game play
progresses. On their turn, a player then chooses which component to play in
and makes their move there. In combinatorial game theory, this is called the
_disjunctive sum_ of the components. Although game play in the entire game is
alternating, in a component it can be non-alternating. In many cases in
combinatorial game theory, including enumeration of positions, it helps to
assume that a game is a component of a larger game and the condition of
alternating play is dropped. If desired, we can find the number of positions
restricted to alternating play from the polynomial profile by taking only the
terms where the exponents on $x$ and $y$ differ by at most 1. More information
on combinatorial game theory and common techniques can be found in [1, 15].

To illustrate these concept, we will look at a relatively simple example.

######  Example 2.5.

Consider Cis played on $P_{4}$. There is one empty position, four positions
with a single Left or Right piece each, three positions with two pieces of the
same colour, and six positions with one piece each by Left and Right (shown in
Figure 1). Thus the polynomial profile is

$P_{\textsc{Cis},P_{4}}(x,y)=1+4x+4y+3x^{2}+6xy+3y^{2}.$

The univariate polynomial is

$P_{\textsc{Cis},P_{4}}(x)=1+8x+12x^{2}$

and the total number of positions is $P_{\textsc{Cis},P_{4}}(1)=21$.

|  |
---|---|---
|  |
Figure 1. Possible positions of Cis on $P_{4}$ with one Left piece and one
Right piece played.

Taking only the relevant terms for alternating play from
$P_{\textsc{Cis},P_{4}}(x,y)$, we get that the positions in alternating play
are enumerated by $1+4x+4y+6xy$.

We can find the polynomial profile of a game by using the auxiliary board.

######  Definition 2.6.

The _auxiliary board_ $\Gamma_{G,B}$ of a distance game $G$ on a board $B$ is
the graph that represents all minimal illegal moves. The vertex set of
$\Gamma_{G,B}$ is given by $V(\Gamma)=V(B)\times\\{1,2\\}$ where the vertex
$(x_{i},1)$ represents Left moving in vertex $x_{i}$ in $B$ and similarly
$(x_{j},2)$ is a move by Right in vertex $x_{j}$. Two vertices $(x_{i},a)$ and
$(x_{j},b)$ are adjacent if the corresponding moves are at an illegal
distance.

Note that the auxiliary board can be generalized to many other placement
games, and the resulting simplicial complex is known as the illegal complex
[4].

######  Example 2.7.

Consider Col played on $C_{4}$. The auxiliary board
$\Gamma_{\textsc{Col},C_{4}}$, shown in Figure 2, has vertex set
$V(G_{\textsc{Col},C_{4}})=\\{x_{1},x_{2},x_{3},x_{4}\\}\times\\{1,2\\}$.
Vertices $(x_{i},p)$ and $(x_{j},q)$ are adjacent if $x_{i}\sim x_{j}$ and
$p=q$ or if $i=j$ and $p\neq q$.

$(x_{0},1)$$(x_{1},1)$$(x_{2},1)$$(x_{3},1)$$(x_{0},2)$$(x_{1},2)$$(x_{2},2)$$(x_{3},2)$
Figure 2. Auxiliary board for Col on $C_{4}$.

From Figure 2 we can see that there are eight independent sets of size 1, four
of which are for Left and four for Right, this gives us the terms $4x$ and
$4y$ in the polynomial profile. We can also see that there are twelve
independent sets with one blue and one red piece, which gives us the term
$12xy$. We do this for every possible combinations of blue and red pieces to
get the full polynomial

$P_{\textsc{Col},C_{4}}(x,y)=1+4x+4y+2x^{2}+12xy+2y^{2}+4x^{2}y+4xy^{2}+2x^{2}y^{2}.$

######  Example 2.8.

Consider Snort played on $C_{4}$ . The auxiliary board
$\Gamma_{\textsc{Snort},C_{4}}$, shown in Figure 3, has vertex set
$V(G_{\textsc{Snort},C_{4}})=\\{x_{1},x_{2},x_{3},x_{4}\\}\times\\{1,2\\}$.
Vertices $(x_{i},p)$ and $(x_{j},q)$ are adjacent if $i=j$ and $p\not=q$ or if
both $x_{i}\sim x_{j}$ and $p\not=q$.

$(x_{0},1)$$(x_{1},1)$$(x_{2},1)$$(x_{3},1)$$(x_{0},2)$$(x_{1},2)$$(x_{2},2)$$(x_{3},2)$
Figure 3. Auxiliary board for Snort on $C_{4}$.

From Figure 3 we can see that there are two independent sets of size 4, one
for Left and one for Right, this gives us the terms $x^{4}$ and $y^{4}$ in the
polynomial profile. We can also see that there are eight independent sets of
size 3, four of which are for Left and four for Right, this gives us the
entries $4x^{3}$ and $4y^{3}$. We do this for every possible combinations of
blue and red pieces to get the full polynomial

$P_{\textsc{Snort},C_{4}}=1+4x+4y+6x^{2}+4xy+6y^{2}+4x^{3}+4y^{3}+x^{4}+y^{4}.$

We will now turn our attention to determining the polynomial profiles in
greater generality.

##  3\. Distance Games on Paths

The positions of Col, Snort, and Cis played on paths were enumerated in [2].
The generating functions for these three games were found to be

$\displaystyle GF_{\textsc{Col}}(x,y,t)$
$\displaystyle=\frac{(1+xt)(1+yt)}{1-(xyt^{2}+t(1+xt)(1+yt))}$ $\displaystyle
GF_{\textsc{Snort}}(x,y,t)$
$\displaystyle=\frac{1-xyt^{2}}{1-(xt+yt+xyt^{2}+t(1-xyt^{2}))}$
$\displaystyle GF_{\textsc{Cis}}(x,y,t)$
$\displaystyle=\frac{1+xt+yt}{1-t-xt^{2}-yt^{2}},$

where the coefficient of $t^{n}$ is the polynomial profile when playing on a
path of $n$ vertices. Note that there was a typo in the generating function of
Cis in [2]. We have given the corrected function here.

We will now generalize this and enumerate the positions of various other
distance games when played on paths.

As a step to find the generating function we take into account the empty
vertices in positions by using an $e$ to represent them, we then set $e=1$ to
get the polynomial profile.

###  3.1. EnCis($k$)

In this section we find the recursions for the polynomial profile and the
number of positions of EnCis($k$) played on paths, as well as the generating
function.

######  Proposition 3.1.

The polynomial profile for the distance game $\textsc{EnCis}(k)$ played on
$P_{n}$ for $n\leq k$ is

$P_{\textsc{EnCis}(k),P_{n}}(x,y)=1+nx+ny$

and for $n>k$ it is recursively given by

$P_{\textsc{EnCis}(k),P_{n}}(x,y)=P_{\textsc{EnCis}(k),P_{n-1}}(x,y)+(x+y)P_{\textsc{EnCis}(k),P_{n-(k+1)}}(x,y).$

The total number of positions is recursively given by

$P_{\textsc{EnCis}(k),P_{n}}(1)=P_{\textsc{EnCis}(k),P_{n-1}}(1)+2P_{\textsc{EnCis}(k),P_{n-(k+1)}}(1)$

with $P_{\textsc{EnCis}(k),P_{n}}(1)=2n+1$ for $n\leq k$.

###### Proof.

When $n\leq k$, no pair of pieces can be placed. Therefore the only positions
are the empty board and the $n$ positions each with a single blue or red
piece, giving the initial terms.

For the recursion, consider the leftmost vertex of the path.

If this vertex is uncoloured, the rest of the $n-1$ vertices can be any legal
position on $P_{n-1}$.

If this vertex is coloured blue or red, then the next $k$ vertices must be
empty, which leaves any legal position on $P_{n-(k+1)}$ vertices.

This gives the desired recursion. Setting $x=y=1$ gives the recursion for the
total number of positions. ∎

For large $k$, this recursion will require a large amount of initial terms.
Although we are not able to give a closed form of the polynomial profile, we
will now turn to determining the generating function, which is

$GF_{G,P_{n}}(x,y,t)=\sum_{n=0}^{\infty}P_{G,P_{n}}(x,y)t^{n}.$

As an in-between step, we will often consider a refined polynomial profile
$P_{G,P_{n}}(e,x,y)$ where the exponent on $e$ indicates the number of empty
vertices, i.e. the degree of every term will be $n$. The generating function
for this polynomial is denoted $GF_{G,P_{n}}(e,x,y,t)$ and we have
$P_{G,P_{n}}(x,y)=P_{G,P_{n}}(1,x,y)$ and
$GF_{G,P_{n}}(x,y,t)=GF_{G,P_{n}}(1,x,y,t)$.

######  Proposition 3.2.

The generating function for the polynomial profile of $\textsc{EnCis}(k)$
played on $P_{n}$ is

$GF_{\textsc{EnCis}(k),P_{n}}(x,y,t)=\frac{1-t+xt+yt-
xt^{k+1}-yt^{k+1}}{(1-t)(1-t-xt^{k+1}-yt^{k+1})}.$

The total number of positions is generated by

$GF_{\textsc{EnCis}(k),P_{n}}(1,1,t)=\frac{1+t-2t^{k+1}}{(1-t)(1-t-2t^{k+1})}.$

###### Proof.

In EnCis($k$), no pair of vertices at distance $1,2,\ldots,k$ can be coloured
simultaneously. Therefore, the positions on a path are exactly those that
satisfy the following pattern:

  1. (1)

Starts with zero or more empty vertices;

  2. (2)

followed by repeated patterns taken from

     * •

a blue vertex followed by $k$ empty

     * •

a red vertex followed by $k$ empty

followed by zero or more empty vertices; and

  3. (3)

ends with

     * •

a blue vertex followed by $0$ to $k-1$ empty,

     * •

a red vertex followed by $0$ to $k-1$ empty, or

     * •

nothing added.

For example, for $\textsc{EnCis}(2)$ this gives the regular expression

$E^{*}[(B|R)EEE^{*}]^{*}(B|BE|R|RE|\epsilon).$

For the general case, we use the notation $S_{B}^{k-1}$ to represent the
string

$B|BE|BEE|\ldots|BE^{k-1}.$

Similarly, we set

$S_{R}^{k-1}=R|RE|REE|\ldots|RE^{k-1}.$

The regular expression for $\textsc{EnCis}(k)$ is then

$E^{*}[(B|R)E^{k}E^{*}]^{*}[S_{B}^{k-1}|S_{R}^{k-1}|\epsilon].$

The corresponding expression in the generating function to the term
$S_{B}^{k-1}$ is

$xt\frac{1-e^{k}t^{k}}{1-et},$

similarly for $S_{R}^{k-1}$ we get

$yt\frac{1-e^{k}t^{k}}{1-et}.$

The generating function taking empty vertices into account is then

$\displaystyle GF_{\textsc{EnCis}(k)}(e,x,y,t)$
$\displaystyle=\left(\frac{1}{1-et}\right)\left(\frac{1}{1-(\frac{xe^{k}t^{k+1}}{1-et}+\frac{ye^{k}t^{k+1}}{1-et})}\right)$
$\displaystyle\qquad\quad\times\left(\frac{xt(1-e^{k}t^{k})}{1-et}+\frac{yt(1-e^{k}t^{k})}{1-et}+1\right),$

and setting $e=1$ gives

$GF_{\textsc{EnCis}(k)}(x,y,t)=\frac{1-t+xt+yt-
xt^{k+1}-yt^{k+1}}{(1-t)(1-t-xt^{k+1}-yt^{k+1})}.$
$GF_{\textsc{EnCis}(k)}(1,1,t)=\frac{1+t-2t^{k=1}}{(1-t)(1-t-2t^{k+1}}\qed$

###  3.2. $\textsc{EnSnort}(k)$

To find the generating function for the polynomial profile of
$\textsc{EnSnort}(k)$, we will introduce the following shorthand notation for
the regular expression:

$\displaystyle\mathbf{S}_{B}^{k}$ $\displaystyle=B|BE|BEE|...|BE^{k}$
$\displaystyle\mathbf{S}_{R}^{k}$ $\displaystyle=R|RE|REE|...|RE^{k}$
$\displaystyle\mathbf{T}_{B}^{k}$
$\displaystyle=B(\mathbf{S}_{B}^{k})^{*}|B(\mathbf{S}_{B}^{k})^{*}E|\ldots|B(\mathbf{S}_{B}^{k})^{*}E^{k-1}$
$\displaystyle\mathbf{T}_{R}^{k}$
$\displaystyle=R(\mathbf{S}_{R}^{k})^{*}|R(\mathbf{S}_{R}^{k})^{*}E|\ldots|R(\mathbf{S}_{R}^{k})^{*}E^{k-1}.$

The regular expression for $\textsc{EnSnort}(k)$ is then

$E\mbox{*}[(B(\mathbf{S}_{B}^{k})\mbox{*}|R(\mathbf{S}_{R}^{k})\mbox{*}))E^{k}E\mbox{*}]\mbox{*}[\mathbf{T}_{B}^{k}|\mathbf{T}_{R}^{k}|\epsilon].$

######  Example 3.3.

Consider $\textsc{EnSnort}(2)$ played on $P_{n}$. The regular expression for
$\textsc{EnSnort}(2)$ is

$\displaystyle E^{*}$ $\displaystyle[B(BE|B)^{*}|R(RE|R)^{*}|EE^{*}]^{*}.$
$\displaystyle\qquad[B(BE|B)^{*}|B(BE|B)^{*}E|R(RE|R)^{*}|R(RE|R)^{*}E|\epsilon],$

giving that the generating function for the polynomial profile is

$\displaystyle GF_{\textsc{EnSnort}(2)}$
$\displaystyle(x,y,t)=\left(\frac{1}{1-t}\right)\left(\frac{1}{1-(\frac{xt}{1-xt-
xt^{2}}\frac{yt}{1-yt-yt^{2}})(\frac{t^{2}}{1-t})}\right)$
$\displaystyle\left(\frac{xt}{1-xt-xt^{2}}+\frac{xt^{2}}{1-xt-
xt^{2}}+\frac{yt}{1-yt-yt^{2}}+\frac{yt^{2}}{1-yt-yt^{2}}+\epsilon\right)$

The first few polynomial profiles are in Table 1.

n | $P_{\textsc{EnSnort}(2),P_{n}}(x,y)$ | $P_{\textsc{EnSnort}(2),P_{n}}(x)$ | $P_{\textsc{EnSnort}(2),P_{n}}(1)$
---|---|---|---
$0$ | $1$ | $1$ | $1$
$1$ | $1+1x+1y$ | $1+2x$ | $3$
$2$ | $1+2x+2y+x^{2}+y^{2}$ | $1+4x+2x^{2}$ | $7$
$3$ | $1+3x+3y+3x^{2}+3y^{2}+x^{3}+y^{3}$ | $1+6x+6x^{2}+2x^{3}$ | $15$
Table 1. First few initial terms for the recursion of the polynomial profile
of $\textsc{EnSnort}(2)$

In general, we get the following.

######  Proposition 3.4.

The generating function for the polynomial profile of $\textsc{EnSnort}(k)$ on
$P_{n}$ is

$\displaystyle GF_{\textsc{EnSnort(k)},P_{n}}$
$\displaystyle(x,y,t)=\left(\frac{1}{1-t}\right)\left(\frac{1}{\displaystyle
1-\frac{xt}{\displaystyle 1-\sum_{i=1}^{k}xt^{i}}+\frac{yt}{\displaystyle
1-\sum_{i=1}^{k}yt^{i}}(\frac{t^{k}}{1-t})}\right)$
$\displaystyle\times\left(\sum_{n=1}^{k}\frac{xt^{n}}{\displaystyle
1-\sum_{i=1}^{k}xt^{i}}+\sum_{n=1}^{k}\frac{yt^{n}}{\displaystyle
1-\sum_{i=1}^{k}yt^{i}}+1\right).$

###  3.3. $\textsc{Cis}_{2}$

In this section we find the recursion for the polynomial profile and number of
positions of $\textsc{Cis}_{2}$ played on paths, as well as the generating
function for the polynomial profile.

######  Proposition 3.5.

The polynomial profile for $\textsc{Cis}_{2}$ played on $P_{n}$ is given by

$\displaystyle P_{\textsc{Cis}_{2},P_{n}}(x,y)$
$\displaystyle=P_{\textsc{Cis}_{2},P_{n-1}}(x,y)+(x+y)P_{\textsc{Cis}_{2},P_{n-3}}(x,y)$
$\displaystyle\qquad+(x^{2}+y^{2}+2xy)P_{\textsc{Cis}_{2},P_{n-4}}(x,y),$

for $n\geq 4$.

The total number of positions111OEIS sequence A138495 is recursively given by

$P_{\textsc{Cis}_{2},P_{n}}(1)=P_{\textsc{Cis}_{2},P_{n-1}}(1)+2P_{\textsc{Cis}_{2},P_{n-3}}(1)+4P_{\textsc{Cis}_{2},P_{n-4}}(1).$

The initial terms are given in Table 2.

n | $P_{\textsc{Cis}_{2},P_{n}}(x,y)$ | $P_{\textsc{Cis}_{2},P_{n}}(x)$ | $P_{\textsc{Cis}_{2},P_{n}}(1)$
---|---|---|---
$0$ | $1$ | $1$ | $1$
$1$ | $1+x+y$ | $1+2x$ | $3$
$2$ | $1+2x+2y+x^{2}+y^{2}+2xy$ | $1+4x+3x^{2}$ | $9$
$3$ | $1+3x+3y+2x^{2}+2y^{2}+4xy$ | $1+6x+8x^{2}$ | $15$
Table 2. Initial terms for the recursion of the polynomial profile of
$\textsc{Cis}_{2}$

###### Proof.

The initial cases can be checked computationally.

For the recursion, consider the leftmost vertex of the path. If this vertex is
uncoloured, the rest of the $n-1$ vertices can be any legal position for this
game on $P_{n-1}$, which gives $P_{\textsc{Cis}_{2},P_{n-1}}(x,y)$ as a term
in the recursion. On the other hand, if this vertex is coloured blue or red,
then either the next two vertices in the path are both empty or the next
vertex is also coloured blue or red, followed by the next two empty. The first
case leaves any legal position on $P_{n-3}$, which gives
$xP_{\textsc{Cis}_{2},P_{n-3}}(x,y)$ for blue and
$yP_{\textsc{Cis}_{2},P_{n-3}}(x,y)$ for red. The second case results in two
coloured vertices followed by two empty vertices, leaving any legal position
on $P_{n-4}$. In this case, the two leftmost vertices can be any combination
of one blue and one red, two blue, or two red, giving us the term
$(x^{2}+y^{2}+2xy)P_{\textsc{Cis}_{2},P_{n-4}}(x,y)$.

This gives the recursion

$\displaystyle P_{\textsc{Cis}_{2},P_{n}}(x,y)$
$\displaystyle=P_{\textsc{Cis}_{2},P_{n-1}}(x,y)+(x+y)P_{\textsc{Cis}_{2},P_{n-3}}(x,y)$
$\displaystyle\qquad+(x^{2}+y^{2}+2xy)P_{\textsc{Cis}_{2},P_{n-4}}(x,y).$

Setting $x=y=1$, we get the recursion for the total number of positions as
desired. ∎

Using the shorthand $\mathbf{U}=BB|BR|RB|RR|B|R$, the regular expression is

$E^{*}(\mathbf{U}EEE^{*})^{*}(\mathbf{U}|\mathbf{U}E|\epsilon).$

Thus we get the following:

######  Proposition 3.6.

The generating function for the polynomial profile of $\textsc{Cis}_{2}$
played on paths is

$\displaystyle GF_{\textsc{Cis}_{2},P_{n}}(x,y,t)$
$\displaystyle=\frac{1+xt+yt+(xt+yt)^{2}+et(xt+yt+(xt+yt)^{2})}{1-et-e^{2}t^{2}(xt+yt+(xt+yt)^{2})}.$

The total number of positions is generated by

$GF_{\textsc{Cis}_{2},P_{n}}(1,1,t)=\frac{1+2t+6t^{2}+4t^{3}}{1-t-2t^{3}-4t^{4}}.$

##  4\. Col, Snort, and Cis

###  4.1. Cis on Cycles

We will generalize the results of [2] for Cis on paths to cycles. We will find
the polynomial profiles using the polynomial profiles on paths, as well as the
generating function for the polynomial profile.

######  Proposition 4.1.

The polynomial profile when playing Cis on $C_{n}$ for $n\geq 4$ is given by

$P_{Cis,C_{n}}(x,y)=P_{\text{Cis},P_{n-1}}(x,y)+(x+y)P_{\textsc{Cis},P_{n-2}}(x,y).$

The number of positions is $2^{n}+(-1)^{n}$.

###### Proof.

We fix one vertex in the cycle and label it $v_{0}$. We then label the rest of
the vertices as $v_{1},\ldots,v_{n-1}$ in a clockwise rotation.

If $v_{0}$ is coloured, then the adjacent vertices ($v_{1}$ and $v_{n-1}$)
must be empty. This leaves any possible position on $P_{n-3}$ which gives
$xP_{\textsc{Cis},P_{n-3}}(x,y)$ if it is a blue vertex and
$yP_{\textsc{Cis},P_{n-3}}(x,y)$ if it is a red vertex.

If $v_{0}$ is uncoloured, this leaves any possible position on $P_{n-1}$, thus
contributing the term $P_{\text{Cis},P_{n-1}}(x,y)$.

This gives the recursion

$P_{Cis,C_{n}}(x,y)=(x+y)P_{\textsc{Cis},P_{n-3}}(x,y)+P_{\text{Cis},P_{n-1}}(x,y).$

We then set $x=y=1$ to get the number of positions recursively as

$P_{Cis,C_{n}}(1)=2P_{\textsc{Cis},P_{n-3}}(1)+P_{\text{Cis},P_{n-1}}(1).$

In [2], the number of positions for Cis on paths was found to be
$P_{\textsc{Cis},P_{n}}(1)=\frac{2^{n}-(-1)^{n}}{3}$. Substituting this into
the recursion, we get

$\displaystyle P_{\textsc{Cis},C_{n}}(1)$
$\displaystyle=2P_{\textsc{Cis},P_{n-3}}(1)+P_{\textsc{Cis},P_{n-1}}(1)$
$\displaystyle=2\left(\frac{2^{n-3}-(-1)^{n-3}}{3}\right)+\left(\frac{2^{n-1}-(-1)^{n-1}}{3}\right)$
$\displaystyle=2^{n-2}+(-1)^{n}.\qed$

######  Proposition 4.2.

The generating function for the polynomial profile of Cis played on cycles is

$GF_{\textsc{Cis},C_{n}}(1,x,y,t)=\frac{1+x^{2}t^{2}+y^{2}t^{2}}{1-t-xt^{2}-yt^{2}},$

and thus the generating function for the total number of positions is

$GF_{\textsc{Cis},C_{n}}(1,1,1,t)=\frac{1+2t^{2}}{1-t-2t^{2}}.$

###### Proof.

For Cis on a cycle, we will fix a vertex $v$ and will consider a position on
$C_{n}$ as a position on $P_{n+1}$, where the first and last vertex are
simultaneously either empty, blue, or red. Recall that no adjacent vertices
can both be coloured. Therefore, the positions on the equivalent path
$P_{n+1}$ are exactly those that satisfy one of the following pattern:

  1. (1)

Starts with an empty vertex;

     * •

followed by zero or more empty vertices;

     * •

followed by repeated patterns taken from

       * –

a blue vertex followed by an empty vertex

       * –

a red vertex followed by an empty vertex

followed by zero or more empty vertices; or

  2. (2)

Starts with a blue vertex;

     * •

followed by at least one empty vertex;

     * •

followed by repeated patterns taken from

       * –

a blue vertex followed by an empty vertex

       * –

a red vertex followed by an empty vertex

followed by zero or more empty vertices;

     * •

ends with a blue vertex; or

  3. (3)

Starts with a red vertex;

     * •

followed by at least one empty vertex;

     * •

followed by repeated patterns taken from

       * –

a blue vertex followed by an empty vertex

       * –

a red vertex followed by an empty vertex

followed by zero or more empty vertices;

     * •

ends with a red vertex.

The regular expression for Cis then is

$[EE^{*}(BEE^{*}|REE^{*})^{*}]|[BEE^{*}(BEE^{*}|REE^{*})^{*}(B)]|[REE^{*}(BEE^{*}|REE^{*})^{*}(R)].$

The generating function for the three cases count the first and last vertex
separately, while they are the same for us on the cycle. To adjust for this,
we divide the generating function for the first case by $et$, the second by
$xt$, and the third by $yt$. This gives us the following generating function
for the cycle $C_{n}$:

$\displaystyle GF_{\textsc{Cis},C_{n}}(e,x,y,t)$
$\displaystyle=\left(\frac{1}{1-et}\right)\left(\frac{1-et}{1-et-
xet^{2}-yet^{2}}\right)$
$\displaystyle\qquad+\left(\frac{xet^{2}}{1-et}\right)\left(\frac{1-et}{1-et-
xet^{2}-yet^{2}}\right)$
$\displaystyle\qquad+\left(\frac{yet^{2}}{1-et}\right)\left(\frac{1-et}{1-et-
xet^{2}-yet^{2}}\right).$

Setting $e=1$ and simplifying gives the desired generating function. ∎

###  4.2. Recursion for Col and Snort on Cycles

We will give the recursions for the total number of positions of Col and Snort
on cycles. The recursion for the polynomial profile can be found similarly. As
the latter do not simplify nicely, we will only give the former.

######  Proposition 4.3.

The number of positions222This sequence seems to be the OEIS sequence A051927.
We have confirmed this for $n\leq 12$. when playing Col on $C_{n}$ is given by

$P_{\textsc{Col},C_{n}}(1)=P_{\textsc{Col},P_{n-1}}(1)+3P_{\textsc{Col},P_{n-3}}(1)+2P_{\textsc{Col},P_{n-4}}(1)+P_{\textsc{Col},C_{n-2}}(1).$

###### Proof.

We fix one vertex in the cycle and label it $v_{0}$. We then label the rest of
the vertices as $v_{1},\ldots,v_{n-1}$ in a clockwise rotation.

If $v_{0}$ is uncoloured, this leaves any possible position on $P_{n-1}$, this
gives us $P_{\text{Col},P_{n-1}}(1)$ possible positions.

If $v_{0}$ is coloured, then there are three cases to consider:

  1. (1)

both $v_{1}$ and $v_{n-1}$ are empty;

  2. (2)

both $v_{1}$ and $v_{n-1}$ are coloured, necessarily the same colour as
$v_{0}$; and

  3. (3)

either $v_{1}$ or $v_{n-1}$ is coloured, necessarily the same colour as
$v_{0}$, with the other being empty.

The first case leaves any possible position on $P_{n-3}$, whether $v_{0}$ is
blue or red, thus there are $2P_{\text{Col},P_{n-3}}(1)$ possible positions
for this case.

The second case can be reduced to a cycle on $n-2$ vertices where the fixed
vertex cannot be empty. This gives us
$P_{\text{Col},C_{n-2}}(1)-P_{\text{Col},P_{n-3}}(1)$ possible positions.

The third case reduces to a coloured path on $n-2$ vertices. Let $f_{B}(n)$
denote the polynomial enumerating the positions when playing Col on $C_{n}$
with one vertex coloured blue, and similarly for $f_{R}(n)$ and $f_{E}(n)$.
This gives us

$\displaystyle f_{E}(n-3)(1)$
$\displaystyle+f_{B}(n-3)(1)+f_{E}(n-3)(1)+f_{R}(n-3)(1)$
$\displaystyle=P_{\text{Col},C_{n-3}}(1)-f_{R}(n-3)(1)+P_{\text{Col},C_{n-3}}(1)-f_{B}(n-3)(1)$
$\displaystyle=2P_{\text{Col},C_{n-3}}(1)-(f_{R}(n-3)(1)+f_{B}(n-3)(1))$
$\displaystyle=2P_{\text{Col},C_{n-3}}(1)-(P_{\text{Col},C_{n-3}}(1)-P_{\text{Col},C_{n-4}}(1))$
$\displaystyle=P_{\text{Col},C_{n-3}}(1)+P_{\text{Col},C_{n-4}}(1).$

We count this case twice, once for $v_{0}$ being empty and $v_{n-1}$ being
coloured and once for the other way around, this gives us
$2P_{\text{Col},C_{n-3}}(1)+2P_{\text{Col},C_{n-4}}(1)$.

All together we get

$P_{\text{Col},C_{n}}(1)=P_{\text{Col},P_{n-1}}(1)+3P_{\text{Col},P_{n-3}}(1)+2P_{\text{Col},C_{n-4}}(1)+P_{\text{Col},C_{n-2}}(1).\qed$

The proof for Snort on cycles is similar to the proof for Col on cycles and is
thus omitted.

######  Proposition 4.4.

The number of positions333This sequence seems to be OEIS sequence A124696. We
have confirmed this for $n\leq 13$. when playing Snort on $C_{n}$ is given by

$P_{\textsc{Snort},C_{n}}(1)=P_{\textsc{Snort},P_{n-1}}(1)+3P_{\textsc{Snort},P_{n-3}}(1)+2P_{\textsc{Snort},P_{n-4}}(1)+P_{\textsc{Snort},C_{n-2}}(1).$

###  4.3. Col, Snort, and Cis on Complete Bipartite Graphs

When playing Col, Snort, or Cis on the star $K_{1,n}$, the state of the
central vertex will completely determine the possible positions.

For Col and Snort, if the central vertex is coloured blue, the outer vertices
can each independently be red or empty, respectively blue or empty. Similarly
if it is coloured red. If the central vertex is uncoloured, the outer vertices
can independently be empty or either colour.

For Cis, if the central vertex is coloured, the outer vertices have to be
empty, while if it is uncoloured, then the outer vertices can independently be
empty or either colour.

This gives us the following result.

######  Proposition 4.5.

When playing on a star, the total number of positions is given by

$\displaystyle P_{\textsc{Col},K_{1,n}}(1)$ $\displaystyle=2^{n+1}+3^{n}$
$\displaystyle P_{\textsc{Snort},K_{1,n}}(1)$ $\displaystyle=2^{n+1}+3^{n}$
$\displaystyle P_{\textsc{Cis},K_{1,n}}(1)$ $\displaystyle=2+3^{n}.$

That the number of positions for Col and Snort on $K_{1,n}$ is the same is not
a surprise. It is known that this is the case for any bipartite board:

######  Theorem 4.6 (Theorem 4.2 in [2]).

If $B$ is a bipartite graph, then
$P_{\textsc{Col},B}(x)=P_{\textsc{Snort},B}(x)$. In particular,
$P_{\textsc{Col},B}(1)=P_{\textsc{Snort},B}(1)$, i.e., the number of positions
is the same for Col and Snort when playing on a bipartite graph.

We have computed the number of positions on other complete bipartite graphs
for Col and Snort and these can be found in Table 3.

$m/n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
0 | 1 | 3 | 9 | 27 | 81 | 243 | 729 | 2187 | 6561 | 19683 | 59049 | 177147 | 531441 | 1594323
1 | 3 | 7 | 17 | 43 | 113 | 307 | 857 | 2443 | 7073 | 20707 | 61097 | 181243 | 539633 |
2 | 9 | 17 | 35 | 77 | 179 | 437 | 1115 | 2957 | 8099 | 22757 | 65195 | 189437 |  |
3 | 27 | 43 | 77 | 151 | 317 | 703 | 1637 | 3991 | 10157 | 26863 | 73397 |  |  |
4 | 81 | 113 | 179 | 317 | 611 | 1253 | 2699 | 6077 | 14291 |  |  |  |  |
5 | 243 | 307 | 437 | 703 | 1253 | 2407 | 4877 | 10303 |  |  |  |  |  |
6 | 729 | 857 | 1115 | 1637 | 2699 | 4877 | 9395 |  |  |  |  |  |  |
7 | 2187 | 2443 | 2957 | 3991 | 6077 | 10303 |  |  |  |  |  |  |  |
8 | 6561 | 7073 | 8099 | 10157 | 14291 |  |  |  |  |  |  |  |  |
9 | 19683 | 20707 | 22757 | 26863 |  |  |  |  |  |  |  |  |  |
10 | 59049 | 61097 | 65195 | 73397 |  |  |  |  |  |  |  |  |  |
11 | 177147 | 181243 | 189437 |  |  |  |  |  |  |  |  |  |  |
12 | 531441 | 539633 |  |  |  |  |  |  |  |  |  |  |  |
13 | 1594323 |  |  |  |  |  |  |  |  |  |  |  |  |

Table 3. The number of positions when playing Col or Snort on $K_{m,n}$

Based on this data, we pose the following conjecture.

######  Conjecture 4.7.

The number of positions when playing Col or Snort on the complete bipartite
graph $K_{m,n}$ are recursively given by

$P_{\textsc{Col},K_{m,n}}(1)=5P_{\textsc{Col},K_{m,n-1}}(1)-6P_{\textsc{Col},K_{m,n-2}}(1)+c_{m}$

with initial terms as per Table 3 and $c_{m}$ is given by the OEIS sequence
A260217 (first few terms are $c_{2}=4$, $c_{3}=24$, $c_{4}=100$, $c_{5}=360$,
and $c_{6}=1204$).

For Cis, similarly to the situation of the star, as soon as a single vertex is
coloured, only vertices in the same part of $K_{m,n}$ are able to be coloured.
Ensuring that we do not count the empty position twice, we get the following
result.

######  Proposition 4.8.

The number of positions when playing Cis on the complete bipartite graph
$K_{m,n}$ is given by

$P_{\textsc{Cis},K_{m,n}}(1)=3^{m}+3^{n}-1.$

##  5\. Future Work

As was the case in [2] for Col, $\textsc{EnCol}(k)$ appears the most
complicated of the generalizations of Col, Snort, and Cis that we considered.
We are still looking into finding a recursion, as well as a generating
function, for $\textsc{EnCol}(k)$ played on paths.

For Col and Snort played on cycles we have found recursion for the polynomial
profiles and the number of positions, but have not yet found the generating
functions. For complete bipartite graphs, in addition to trying to prove 4.7,
we also would like to find generating functions for this case.

Of course, this work could also be extended by considering other distance
games or looking at the generalizations when played on boards other than
paths.

Finally, we are interested in the ratio of positions in purely alternating
play, which can also be found from the polynomial profile, to the total number
of positions.

## References

  * [1] E. R. Berlekamp, J. H. Conway, and R. K. Guy.  Winning Ways for your Mathematical Plays. Vol. 1.  AK Peters Ltd., Wellesley, MA, second edition, 2004.
  * [2] J. I. Brown, D. Cox, A. Hoefel, N. McKay, R. Milley, R. J. Nowakowski, and A. A. Siegel.  A note on polynomial profiles of placement games.  In Urban Larsson, editor, Games of No Chance 5, volume 70 of Mathematical Sciences Research Institute Publications, pages 249–265. Cambridge University Press, 2019.
  * [3] Kyle Burke, Silvia Heubach, Melissa Huggan, and Svenja Huntemann.  Keeping your distance is hard.  To appear in: Games of No Chance 6.
  * [4] Sara Faridi, Svenja Huntemann, and Richard J. Nowakowski.  Simplicial complexes are game complexes.  Electron. J. Combin., 26(3):Paper No. 3.34, 24, 2019.
  * [5] G. Farr and J. Schmidt.  On the number of Go positions on lattice graphs.  Inform. Process. Lett., 105(4):124–130, 2008.
  * [6] G. E. Farr.  The Go polynomials of a graph.  Theoret. Comput. Sci., 306(1-3):1–18, 2003.
  * [7] G. Hetyei.  Enumeration by kernel positions.  Adv. Appl. Math., 42(4):445–470, 2009.
  * [8] Melissa Huggan and Brett Stevens.  Polynomial time graph families for Arc Kayles.  Integers, 16:Paper No. A86, 14, 2016.
  * [9] Svenja Huntemann and Neil Anderson McKay.  Counting Domineering positions.  J. Integer Seq., 24(4):Art. 21.4.8, 24, 2021.
  * [10] Svenja Huntemann and Richard J. Nowakowski.  Doppelgänger placement games.  Recreat. Math. Mag., (1):55–61, 2014.
  * [11] Richard J Nowakowski, Gabriel Renault, Emily Lamoureux, Stephanie Mellon, and Timothy Miller.  The game of Timber.  Journal of Combinatorial Mathematics and Combinatorial Computing, 85:213–225, May 2013.
  * [12] Seungsang Oh.  Maximal independent sets on a grid graph.  Discrete Math., 340(12):2762–2768, 2017.
  * [13] Seungsang Oh and Sangyop Lee.  Enumerating independent vertex sets in grid graphs.  Linear Algebra Appl., 510:192–204, 2016.
  * [14] T. J. Schaefer.  On the complexity of some two-person perfect-information games.  Journal of Computer and System Sciences, 16(2):185–225, 1978.
  * [15] Aaron N. Siegel.  Combinatorial Game Theory, volume 146 of Graduate Studies in Mathematics.  American Mathematical Society, 2013.
  * [16] J. Tromp and G. Farnebäck.  Combinatorics of Go.  In Proceedings of the 5th International Conference on Computers and Games, CG’06, pages 84–99. Springer-Verlag, 2007.