\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{mathdots}
\usepackage{wasysym}
\usepackage{comment}

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

\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 
Non-Attacking Bishop and King Positions on\\
\vskip .1in
Regular and Cylindrical Chessboards}
\vskip 1cm
\large
Richard M. Low 
and Ardak Kapbasov\\
Department of Mathematics\\
San Jose State University\\
San Jose, CA 95192\\
USA \\
\href{mailto:richard.low@sjsu.edu} {\tt richard.low@sjsu.edu} \\
\href{mailto:ardak.kapbasov@yahoo.com} {\tt ardak.kapbasov@yahoo.com}\\
\end{center}

\vskip .2 in

\begin{abstract}
In this paper, we count the number of non-attacking bishop and king positions on the regular and cylindrical $m \times n$ (where $m = 1, 2, 3)$ chessboards. This is accomplished through the use of scientific computing, recurrence relations, generating functions and closed-form formulas.
\end{abstract}

\section{Introduction} \label{S:intro}

Stevens \cite{Stevens} gave a nice combinatorial proof of the Fibonacci identity $F_n^2 = 2(F_{n-1}^2 + F_{n-2}^2) - F_{n-3}^2$. This was accomplished by enumerating the non-attacking bishop positions on a $2 \times n$ chessboard in two different ways. Inspired by his result, we sought to generalize his method to an $m \times n$ chessboard and hoped to establish other combinatorial identities. As it turned out, this was not so easy to do. In pursuing our original goal, we had to count the number of non-attacking bishop and king positions on various types of chessboards. This is the focus of our paper.

\section{Regular chessboards} \label{S:regboards}

Let $n \geq 1$. Clearly, there are $2^n$ non-attacking bishop positions on a $1 \times n$ chessboard. Stevens \cite{Stevens} pointed out that the number of non-attacking bishop positions on a $2 \times n$ chessboard is $F_{n+2}^2$ (where $F_0 = 0, F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$, for $n \geq 2$). Let us count the non-attacking bishop positions on a $3 \times n$ chessboard. Each non-attacking bishop position (on a $3 \times n$ chessboard) can be associated with a string of length $n$ (using the digits $0$ through $7$) as described in Figure \ref{Fig1}.\\

\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{Fig1.eps}} \caption{} \label{Fig1}
\end{center}
\end{figure}

\noindent
The length $n$ strings that we are interested in do not contain the following substrings: 

\begin{itemize}
\item12, 13, 16, 17, 21, 23, 24, 25, 26, 27, 31, 32, 33, 34, 35, 36, 37, 42, 43, 46, 47, 52, 53, 56, 57, 61, 62, 63, 64, 65, 66, 67, 71, 72, 73, 74, 75, 76, 77.
\item 104, 105, 106, 107, 114, 115, 144, 145, 154, 155, 304, 305, 306, 307, 401, 403, 405, 407, 411, 415, 441, 445, 451, 455, 501, 503, 504, 505, 506, 507, 511, 514, 515, 541, 544, 545, 551, 554, 555, 601, 603, 605, 607, 701, 703, 704, 705, 706, 707.
\end{itemize}

 \begin{table}[h]
  \[
  \begin{array}{llll} \\
  $$n$$ &\quad $$b(n)$$ &\quad $$w(n)$$ &\quad $$B_3 (n)$$\\
  \hline
   0  & \quad \quad $1$ &\quad \quad $1$ &\quad \quad $1$\\
   1  & \quad \quad $4$ &\quad \quad $2$ &\quad \quad $8$ \\
   2  & \quad \quad $5$ & \quad \quad $5$ & \quad \quad $$25$$ \\
   3  & \quad \quad $10$ & \quad \quad $7$ & \quad \quad $70$\\
   4  & \quad \quad $15$ & \quad \quad $15$ & \quad \quad $$225$$\\
   5  & \quad \quad $34$ & \quad \quad $22$ & \quad \quad $748$\\
   6 & \quad \quad $49$ & \quad \quad $49$ & \quad \quad 2401\\
   7 & \quad \quad $108$ & \quad \quad $71$ & \quad \quad 7668\\
   8 & \quad \quad $157$ & \quad \quad $157$ & \quad \quad 24649\\
   9 & \quad \quad $348$ & \quad \quad $228$ & \quad \quad 79344\\
   10 & \quad \quad $505$ & \quad \quad $505$ & \quad \quad $255025$\\
  \hline
  \end{array}
  \]
  \medskip
  \caption{The number of non-attacking bishop positions on a $3 \times n$ chessboard, where $n \geq 0$.}
  \label{Tab1}
  \end{table}

Throughout this paper, we assume that the chessboard has a black square in the upper left-hand corner. A chessboard is viewed as being fixed in position and orientation. Let $B_3 (n)$ denote the number of non-attacking bishop positions on a $3 \times n$ chessboard. Let $b(n)$ and $w(n)$ denote the number of non-attacking bishop positions on the black and white squares of a $3 \times n$ chessboard, respectively. For the degenerate case where $n = 0$, we set $b(0) = w(0) = 1$ and $B_3 (0) = b(0) \cdot w(0) = 1$. A computer program was created and calculated the values found in Table \ref{Tab1}. We note that the sequences $b(n), w(n)$ and $B_3 (n)$ do not appear in \cite{Sloane}.

The computations were performed on the following platform: Intel Q9400 @ 2.6 GHz with 8 GB RAM. The program was written in C. For $n = 1, 2, \dots, 8$, the computational runtimes were nearly instantaneous. However, approximately four minutes were required for the $n = 9$ case and 30 minutes for the $n = 10$ case. Although this computational approach works, it is clear that it does not scale well as $n$ gets large. We now use a combinatorial approach to gain better insight on this enumeration problem.

For odd $n \geq 1$, a \textit{truncated} $3 \times n$ chessboard has a missing black square in the lower righthand corner of the board. Let $b_T(n)$, for odd $n \geq 1$, denote the number of non-attacking bishop positions on the black squares of a truncated $3 \times n$ board. Clearly, $b_T(1) = 2$.

\begin{lemma}\label{b_t(n)}
For $n \geq 1$, $b_T(2n+1) = b(2n) + b_T(2n-1) = b(2n) + b(2n - 2) + \cdots + b(2) + b_T(1)$.
\end{lemma}
\begin{proof}
We establish the claim using strong mathematical induction. Let $P(n)$ be the statement: $b_T(2n+1) = b(2n) + b_T(2n-1) = b(2n) + b(2n - 2) + \cdots + b(2) + b_T(1)$.
\begin{itemize}
\item Base Case. Note that $b_T (3) = 7 = 5 + 2 = b(2) + b_T (1)$. Thus, $P(1)$ is true. 
\item Inductive Step. Assume $P(n)$ is true, for all $n \leq k$. Now, consider $b_T (2(k+1) + 1)$, the number of non-attacking bishop positions on the black squares of a truncated $3 \times (2(k+1) + 1)$ chessboard. Any such position either has no bishop or a bishop on the black square of the last column of the truncated chessboard. See Figure \ref{FigTrun_odd}.
Thus, 
\begin{align}
b_T (2(k+1) + 1) &= b(2(k+1)) + b_T(2(k+1) - 1) \notag{}\\
&= b(2(k+1)) + b_T(2k+1) \notag{}\\
&= b(2(k+1)) + b(2k) + b(2k - 2) + \cdots + b(2) + b_T(1) \notag{}\\
&= b(2(k+1)) + b(2(k+1) - 2) + b(2(k+1) - 4) + \cdots + b(2) + b_T(1).  \notag 
\end{align}
\end{itemize}
Hence, $P(n)$ is true, for all $n \geq 1$.
\end{proof}
\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{FigTrun_odd.eps}} \caption{The two possible cases for a non-attacking bishop position on the black squares of a truncated $3 \times (2(k+1) + 1)$ chessboard, where $k \geq 1$.} \label{FigTrun_odd}
\end{center}
\end{figure}

\begin{table}[h]
  \[
  \begin{array}{ll} \\
  $$n$$ &\quad $$b_T(n)$$\\
  \hline
   1  & \quad \quad $2$ \\
   3  & \quad \quad $7$ \\
   5  & \quad \quad $22$ \\
   7  & \quad \quad $71$ \\
   9  & \quad \quad $228$\\
   11 & \quad \quad $733$\\
  \hline
\end{array}
  \]
  \medskip
  \caption{The number of non-attacking bishop positions on the black squares of a truncated $3 \times n$ chessboard, where $n \geq 1$ and odd.}
  \label{Tab2}
  \end{table}

\indent
For odd $n \geq 1$, the sequence $b_T(n)$ (\seqnum{A030186}) is found in \cite{Sloane}. See Table \ref{Tab2}. There, we see the sequence described in the following way:
\[
a_k = 3a_{k-1} + a_{k-2} - a_{k-3}, \textnormal{ for } k \geq 3, \textnormal{ and } a_0 = 1, a_1 = 2, a_2 = 7.
\]

\begin{table}[h]
  \[
  \begin{array}{ll} \\
  $$k$$ &\quad $$a_k$$\\
  \hline
   0  & \quad $1$ \\
   1  & \quad $2$ \\
   2  & \quad $7$ \\
   3  & \quad $22$ \\
   4  & \quad $71$\\
   5 & \quad $228$\\
  \hline
\end{array}
  \]
  \medskip
  \caption{Some values of $a_{k}$.}
  \label{Tab3}
  \end{table}

\noindent
Its generating function is
\[
\mathcal{A}(x) = \frac{1-x}{1 - 3x - x^2 + x^3} = \sum_{k=0}^\infty a_k x^k.
\]

\begin{lemma}\label{b(2n+1)}
For $n \geq 2$, $b(2n+1) = b(2n) + b_T(2n-1) + b_T(2n-1) + b(2n-2)$.
\end{lemma}
\begin{proof}
Let $n \geq 2$. Every non-attacking bishop position on the black squares of a $3 \times (2n + 1)$ chessboard is in one of several cases: there is no bishop, one bishop or two bishops in the last column of the chessboard. See Figure \ref{Fig_b3(2n+1)}. Thus, $b(2n+1) = b(2n) + b_T(2n-1) + b_T(2n-1) + b(2n-2)$.
\end{proof}
\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{Fig_b3(2n+1).eps}} \caption{The possible cases for a non-attacking bishop position on the black squares of a $3 \times (2n+1)$ chessboard, where $n \geq 2$.} \label{Fig_b3(2n+1)}
\end{center}
\end{figure}

\begin{lemma}\label{b(2n)}
For $n \geq 2$, $b(2n) = b(2n-1) + b(2n-2)$ and $w(2n) = b(2n)$. Furthermore, $B_3 (2n) = (b(2n-1) + b(2n-2))^2$.
\end{lemma}
\begin{proof}
Let $n \geq 2$. Every non-attacking bishop position on the black squares of a $3 \times 2n$ chessboard is in one of two cases: there is no bishop or one bishop in the last column of the chessboard. See Figure \ref{Fig_b3(2n)}. Thus, $b(2n) = b(2n-1) + b(2n-2)$. On a $3 \times 2n$ chessboard, the configuration of white squares is identical to the configuration of black squares. Hence, $w(2n) = b(2n)$. Since bishops on white squares cannot attack bishops on black squares, $B_3 (2n) = (b(2n-1) + b(2n-2))^2$.
\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{Fig_b3(2n).eps}} \caption{The possible cases for a non-attacking bishop position on the black squares of a $3 \times 2n$ chessboard, where $n \geq 2$.} \label{Fig_b3(2n)}
\end{center}
\end{figure}
\end{proof}

\begin{lemma}\label{w(n)}
For $n \geq 0$, $w(2n + 1) = b_T(2n + 1) = a_{n+1}$.
\end{lemma}
\begin{proof}
Note that $w(1)  = b_T (1) = 2 = a_1$. Let $n \geq 1$. From Figure \ref{Fig_w3(2n+1)} and Lemma \ref{b(2n)}, we see that 
\begin{align}
w(2n+1) &= w(2n) + w(2n-1) \notag{}\\
&= b(2n) + w(2n-1).  \notag 
\end{align}
Through iteration, one obtains $w(2n+1) = b(2n) + b(2n - 2) + \cdots + b(2) + b_T(1)$. By Lemma \ref{b_t(n)}, this yields $w(2n+1) = b_T (2n+1) = a_{n+1}$.
\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{Fig_w3(2n+1).eps}} \caption{The possible cases for a non-attacking bishop position on the white squares of a $3 \times (2n+1)$ chessboard, where $n \geq 1$.} \label{Fig_w3(2n+1)}
\end{center}
\end{figure}
\end{proof}

For even $n \geq 2$, a \textit{truncated} $3 \times n$ chessboard has a missing white square in the lower righthand corner of the board. Let $w_T(n)$, for even $n \geq 2$, denote the number of non-attacking bishop positions on the white squares of a truncated $3 \times n$ board. For example, $w_T(2) = 3$. Note that for the degenerate case (where $n = 0$), we set $w_T(0) = 1$.

\begin{lemma}\label{w_t(n)}
For $n \geq 2$, $w_T(2n) = w(2n - 1) + w_T(2n-2) = w(2n-1) + w(2n - 3) + \cdots + w(3) + w_T(2)$.
\end{lemma}
\begin{proof}
We establish the claim using strong mathematical induction. Let $P(n)$ be the statement: $w_T(2n) = w(2n - 1) + w_T(2n-2) = w(2n-1) + w(2n - 3) + \cdots + w(3) + w_T(2)$.
\begin{itemize}
\item Base Case. From Figure \ref{FigTrun_w3(4)}, we see that $w_T (4) = w(3) + w_T (2)$. Thus, $P(2)$ is true. 
\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{FigTrun_w3(4).eps}} \caption{The possible cases for a non-attacking bishop position on the white squares of a truncated $3 \times 4$ chessboard.} \label{FigTrun_w3(4)}
\end{center}
\end{figure}
\item Inductive Step. Assume $P(n)$ is true, for all $n \leq k$. Now, consider $w_T (2(k+1))$, the number of non-attacking bishop positions on the white squares of a truncated $3 \times 2(k+1)$ chessboard. Any such position either has no bishop or a bishop on the white square of the last column of the truncated chessboard. Thus, 
\begin{align}
w_T (2(k+1)) &= w(2(k+1) - 1) + w_T(2(k+1) - 2) \notag{}\\
&= w(2(k+1) - 1) + w_T(2k) \notag{}\\
&= w(2(k+1) - 1) + w(2k - 1) + w(2k - 3) + \cdots + w(3) + w_T(2) \notag{}\\
&= w(2(k+1) - 1) + w(2(k+1) - 3) + w(2(k+1) - 5) + \cdots \notag{}\\
&\quad \quad + w(3) + w_T(2).  \notag 
\end{align}
\end{itemize}
Hence, $P(n)$ is true, for all $n \geq 2$.
\end{proof}

 \begin{table}[h]
  \[
  \begin{array}{ll} \\
  $$n$$ &\quad $$w_T(n)$$\\
  \hline
   0  & \quad \quad $1$\\
   2  & \quad \quad $3$ \\
   4  & \quad \quad $10$ \\
   6  & \quad \quad $32$ \\
   8  & \quad \quad $103$ \\
   10  & \quad \quad $331$\\
  \hline
  \end{array}
  \]
  \medskip
  \caption{The number of non-attacking bishop positions on the white squares of a truncated $3 \times n$ chessboard, where $n \geq 0$ and even.}
  \label{Tab4}
  \end{table}

\indent The sequence $w_T(2n)$ (\seqnum{A033505}) is found in \cite{Sloane}. See Table \ref{Tab4}. There, we see that $w_T(2n) = \sum_{i = 0}^n a_i$, for $n \geq 0$. Its generating function is 
\[
\mathcal{W}_T(x) = \frac{1}{1 - 3x - x^2 + x^3} = \sum_{k = 0}^\infty w_T(2k) x^k
\]
and hence, 
\[
\mathcal{W}_T (x^2) = \frac{1}{1 - 3x^2 - x^4 + x^6} = \sum_{k = 0}^\infty w_T(2k) x^{2k}.
\]

\begin{lemma}
For $n \geq 2$, $w(2n) = w(2n - 1) + w_T(2n - 2) + w_T(2n - 2) + w(2n - 3) = w(2n - 1) + w(2n - 3) + 2 \sum_{i = 0}^{n-1} a_i$. Also, $w(2) = 5$.
\end{lemma}
\begin{proof}
It is clear that $w(2) = 5$. Let $n \geq 2$. From Figure \ref{Fig_w3(2n)}, we see that $w(2n) = w(2n - 1) + w_T(2n - 2) + w_T(2n - 2) + w(2n - 3)$. By remarks preceding this Lemma, we have $w_T (2n-2) = w_T (2(n-1)) = \sum_{i = 0}^{n-1} a_i$. Thus, the claim is established.
\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{Fig_w3(2n).eps}} \caption{The possible cases for a non-attacking bishop position on the white squares of a $3 \times 2n$ chessboard, where $n \geq 2$.} \label{Fig_w3(2n)}
\end{center}
\end{figure}
\end{proof}

Using the results above, we have the following systems of recurrence relations:\\

\noindent
System for $b(k)$: For $n \geq 3$, 

\begin{align} \label{system_b(k)}
b(2n+ 1) = & \text{ } b(2n) + 2 a_n + b(2n - 2), \notag{}\\ 
b(2n) = &\text{ } b(2n - 1) + b(2n - 2), \notag{}\\
a_n = &\text{ } 3 a_{n-1} + a_{n-2} - a_{n-3}, \notag \\ \notag 
\end{align}
where $a_0 = 1, a_1 = 2, a_2 = 7, b(1) = 4, b(2) = 5, b(3) = 10, b(4) = 15$ and $b(5) = 34$.\\ 

\noindent
This can be written as the piecewise-defined recurrence relation\\
\[
b(k) =
\begin{cases}
b(k-1) + 2a_{\frac{k-1}{2}} + b(k-3), &\text{if $k$ is odd;}\\
b(k-1) + b(k-2), &\text{if $k$ is even,}
\end{cases}
\]

\vspace{10pt}

\noindent
for $k \geq 3$, and $b(0) = 1$, $b(1) = 4$ and $b(2) = 5$.\\

\noindent
System for $w(k)$: For $n \geq 3$, 

\begin{align} 
w(2n+1) = & \text{ } b_T(2n + 1) = a_{n+1}, \notag{}\\ 
a_n = &\text{ } 3 a_{n-1} + a_{n-2} - a_{n-3}, \notag \\ \notag 
\end{align}
where $a_0 = 1, a_1 = 2, a_2 = 7$, $w(1) = 2, w(3) = 7$ and $w(5) = 22$.\\

We now find generating functions for these systems of recurrence relations. \\

\noindent
For $k$ odd, we have $b(k) = b(k-1) + 2a_{\frac{k-1}{2}} + b(k-3)$. Set $k = 2t + 1$. Then, $2a_t = b(2t + 1) - b(2t) - b(2t-2)$. Substituting this into $2a_k = 3 \cdot 2a_{k-1} + 2a_{k-2} - 2a_{k-3}$ yields

\begin{align}
b(2k+1) - b(2k) - b(2k - 2) = &\textnormal{ } 3 (b(2k-1) - b(2k-2) - b(2k-4)) + \notag{}\\ 
&\textnormal{ } (b(2k-3) - b(2k-4) - b(2k-6)) - \notag{}\\ 
&\textnormal{ } (b(2k-5) - b(2k-6) - b(2k-8)). \notag \\ \notag
\end{align}
\noindent
Thus,
\begin{align}
b(2k+1) = &\textnormal{ } b(2k) + b(2k-2) + 3b(2k-1) - 3b(2k-2) - \notag{}\\ 
&\textnormal{ } 3b(2k-4) + b(2k-3) - b(2k-4) - b(2k-6) - \notag{}\\ 
&\textnormal{ } b(2k-5) + b(2k-6) + b(2k-8). \notag \\ \notag
\end{align}
\noindent
Hence,
\begin{align}
b(2k+1) = &\textnormal{ } b(2k) + 3b(2k-1) - 2b(2k-2) + b(2k-3) -  \notag{}\\ 
&\textnormal{ } 4b(2k-4) - b(2k-5) + b(2k-8). \notag \\ \notag
\end{align}

\noindent
For $k$ even, we have $b(k) = b(k-1) + b(k-2)$. Thus, $b(2t) = b(2t-1) + b(2t-2)$.\\

\indent
Now, set $g(k) = b(2k)$ and $h(k) = b(2k+1)$. Then, \\
\[
g(k) = b(2k) = h(k-1) + g(k-1), 
\] 
and 
\begin{align}
h(k) = b(2k+1) = &\textnormal{ } g(k) + 3h(k-1) - 2g(k-1) + h(k-2) - \notag{}\\ 
&\textnormal{ } 4g(k-2) - h(k-3) + g(k-4). \notag \\ \notag
\end{align}
\noindent
Using Maple, we obtain the generating functions
\[
\mathcal{G}(x) = \frac{1 + 2x - x^2}{1 - 3x - x^2 + x^3} = \sum_{k=0}^\infty g(k) x^k = \sum_{k=0}^\infty b(2k) x^k, 
\]

\vspace{10pt}

\noindent
and 
\[
\mathcal{H}(x) = \frac{4 - 2x}{1 - 3x - x^2 + x^3} = \sum_{k=0}^\infty h(k) x^k = \sum_{k=0}^\infty b(2k+1) x^k.
\]

\vspace{10pt}

\noindent
Thus, 
\[
\mathcal{B}(x) = \mathcal{G}(x^2) + x \mathcal{H}(x^2) = \frac{1 + 4x + 2x^2 - 2x^3 - x^4}{1 - 3x^2 - x^4 + x^6} = \sum_{n=0}^\infty b(n) x^n.
\]

\vspace{10pt}

\noindent
We also have the generating function
\[
\mathcal{J}(x) = \frac{1}{x} \cdot \left( \frac{1-x}{1 - 3x - x^2 + x^3} - 1 \right) = \frac{2x + x^2 - x^3}{x - 3x^2 - x^3 + x^4} = \sum_{k=0}^\infty w(2k + 1) x^k.
\]

\vspace{10pt}

\noindent
Thus,
\[
\mathcal{W}(x) = \mathcal{G}(x^2) + x \mathcal{J}(x^2) = \frac{1+2x+2x^2+x^3-x^4-x^5}{1-3x^2-x^4+x^6} = \sum_{n=0}^\infty w(n) x^n.
\]

Using Doron Zeilberger's powerful \textit{Cfinite} Maple package \cite{Zeil} to calculate the Hadamard product $\mathcal{B}(x) \odot \mathcal{W}(x)$, we obtain the generating function for $B_3 (n)$, namely
\[
\mathbb{B}_{3}(x) = \frac{-1 - 5x - x^2 + 7x^3 + 5x^4 - x^5 + x^6 - x^7}{-1 + 3x + 2x^3 + 4x^4 - 10x^5 - 2x^6 - x^8 + x^9} = \sum_{n=0}^\infty B_3 (n) x^n.
\]

\begin{theorem} \label{Regular_3xn_B}
For $n \geq 0$, the number of non-attacking bishop positions on a $3 \times n$ chessboard is $B_3 (n) = b(n) \cdot w(n)$. The generating function for $B_3 (n)$ is the Hadamard product $\mathbb{B}_{3}(x) = \mathcal{B}(x) \odot \mathcal{W}(x)$.
\end{theorem}
\begin{proof}
Bishops on white squares cannot attack bishops on black squares. 
\end{proof}

\indent
We now shift our focus to counting the non-attacking king positions on an $m \times n$ chessboard, where $m = 1, 2$ and $3$. The Fibonacci sequence is described by the recurrence relation: $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$, for all $n \geq 2$. For all $n \geq 1$, the number of non-attacking king positions on a $1 \times n$ chessboard is known to be $F_{n+2}$ \cite[p.\ 510, Exercise 26]{Grim}. Let $K_2(n)$ denote the number of non-attacking king positions on a $2 \times n$ chessboard. For the degenerate case ($n = 0$), we set $K_2(0) = 1$. Clearly, $K_2(1) = 3$.

\begin{lemma}\label{reg_2xn_K}
For $n \geq 2$, $K_2 (n) = K_2 (n - 1) + 2 \cdot K_2 (n - 2)$, where $K_2 (0) = 1$ and $K_2 (1) = 3$.
\end{lemma} 
\begin{proof}
Let $n \geq 2$. Every non-attacking king position on a $2 \times n$ chessboard is in one of two cases: there is no king or one king in the last column of the chessboard. See Figure \ref{Fig_k2(n)}. Thus, 
$K_2 (n) = K_2 (n - 1) + 2 \cdot K_2 (n - 2)$.
\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{Fig_k2(n).eps}} \caption{The possible cases for a non-attacking king position on a $2 \times n$ chessboard, where $n \geq 2$.} \label{Fig_k2(n)}
\end{center}
\end{figure}
\end{proof}

\begin{table}[h]
  \[
  \begin{array}{ll} \\
  $$n$$ &\quad $$K_{2} (n)$$\\
  \hline
   0  & \quad \quad $1$ \\
   1  & \quad \quad $3$ \\
   2  & \quad \quad $5$ \\
   3  & \quad \quad $11$ \\
   4  & \quad \quad $21$ \\
   5  & \quad \quad $43$\\
  \hline
\end{array}
  \]
  \medskip
  \caption{The number of non-attacking king positions on a $2 \times n$ chessboard, where $n \geq 0$.}
  \label{TabK_2}
  \end{table}

The sequence $K_2 (n)$ appears as a subsequence of (\seqnum{A001045}) in \cite{Sloane}. See Table \ref{TabK_2}. There, we see the generating function
\[
\mathcal{K}_2(x) = \frac{x}{1 - x - 2x^2} = x + x^2 + 3x^3 + 5x^4 + 11x^5 + 21 x^6 + 43x^7 + 85x^8 + \cdots
\]
Thus, the generating function for $K_2 (n)$ is
\[
\mathbb{K}_2(x) = \frac{1}{x^2} \cdot \left( \frac{x}{1 - x - 2x^2} - x \right) = \frac{1 + 2x}{1 - x - 2x^2} = \sum_{n=0}^\infty K_2 (n) x^n.
\]

\begin{theorem}\label{Sol_K_2}
For $n \geq 0$, the number of non-attacking king positions on a $2 \times n$ chessboard is $K_2 (n) = \frac{1}{3} (2^{n+2} - (-1)^n)$.
\end{theorem}
\begin{proof}
Using Lemma \ref{reg_2xn_K}, we will establish the claim with strong mathematical induction. Let $P(n)$ be the statement: $K_2 (n) = \frac{1}{3} (2^{n+2} - (-1)^n)$ is a solution to the recurrence relation $K_2 (n) = K_2 (n - 1) + 2 \cdot K_2 (n - 2)$, where $K_2 (0) = 1$ and $K_2 (1) = 3$.
\begin{itemize}
\item Base Case. Note that $1 = K_2 (0) = \frac{1}{3} (2^{0+2} - (-1)^0)$. Thus, $P(0)$ is true. 
\item Inductive Step. Assume $P(n)$ is true, for all $n \leq k$. Then,
\begin{align}
K_2 (k+1) &= K_2 (k) + 2 \cdot K_2 (k-1)\notag{}\\
&= \frac{1}{3} (2^{k+2} - (-1)^k) + \frac{2}{3} (2^{k+1} - (-1)^{k-1}) \notag{}\\
&= \frac{1}{3} \cdot 2^{k+2} - \frac{1}{3} (-1)^k + \frac{2}{3} \cdot 2^{k+1} - \frac{2}{3} (-1)^{k-1} \notag{}\\
&= \frac{1}{3} \cdot 2^{k+2} + \frac{1}{3} \cdot 2^{k+2} + \frac{1}{3} (-1)^{k+1} - \frac{2}{3} (-1)^{k+1} \notag{}\\
&= \frac{1}{3} (2 \cdot 2^{k+2} + (-1)^{k+1} - 2(-1)^{k+1}) \notag{}\\
&= \frac{1}{3} (2^{(k+1) + 2} - (-1)^{k+1}). \notag 
\end{align}
\end{itemize}
Hence, $P(n)$ is true, for all $n \geq 0$.
\end{proof}

For $n \geq 1$, an \textit{extended} $3 \times n$ chessboard has an extra square attached (in the horizontal direction) to the lower righthand corner of the board. Let $K_E (n)$ denote the number of non-attacking king positions on an extended $3 \times n$ chessboard. We set $K_E (0) = 2$. Furthermore, let $K_3 (n)$ denote the number of non-attacking king positions on a $3 \times n$ chessboard. We set $K_3 (0) = 1$. A direct calculation yields $K_3 (1) = 5$.

\begin{lemma} \label{ExtendK_3xn}
For $n \geq 1$, $K_E (n) = K_3 (n) + K_E (n-1).$
\end{lemma}
\begin{proof}
Let $n \geq 1$. Every non-attacking king position on an extended $3 \times n$ chessboard is in one of two cases: there is either no king or a king on the extended square of the chessboard. See Figure \ref{Fig_kE(n)}. Thus, 
$K_E (n) = K_3 (n) + K_E (n-1)$.
\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{Fig_kE(n).eps}} \caption{The two cases for a non-attacking king position on an extended $3 \times n$ chessboard, where $n \geq 1$.} \label{Fig_kE(n)}
\end{center}
\end{figure}
\end{proof} 
  
\begin{lemma} \label{K_3xn}
For $n \geq 2$, $K_3 (n) = K_3 (n-1) + 2 \cdot K_3 (n-2) + 2 \cdot K_E (n-2)$.
\end{lemma}
\begin{proof}
Let $n \geq 2$. Every non-attacking king position on a $3 \times n$ chessboard is in one of several cases: there is either no king, one king or two kings in the last column of the chessboard. See Figure \ref{Fig_k3(n)}. Thus, $K_3 (n) = K_3 (n-1) + 2 \cdot K_3 (n-2) + 2 \cdot K_E (n-2)$.
\end{proof}
\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{Fig_k3(n).eps}} \caption{The possible cases for a non-attacking king position on a $3 \times n$ chessboard, where $n \geq 2$.} \label{Fig_k3(n)}
\end{center}
\end{figure} 
  
\indent
The sequence $K_E (n)$ appears as a subsequence of (\seqnum{A046672}) in \cite{Sloane}. See Table \ref{TabK_E}. There, we see the generating function
\[
\mathcal{K}_E(x) = \frac{1}{1 - 2x - 3x^2 + 2x^3} = 1 + 2x + 7x^2 + 18x^3 + 53x^4 + 146x^5 + \cdots
\]
Thus, the generating function for $K_E (n)$ is
\[
\mathbb{K}_E(x) = \frac{1}{x} \cdot \left( \frac{1}{1 - 2x - 3x^3 + 2x^3} - 1 \right) = \frac{2 + 3x - 2x^2}{1 - 2x - 3x^2 + 2x^3} = \sum_{n=0}^\infty K_E (n) x^n.
\]

\begin{table}[h]
  \[
  \begin{array}{ll} \\
  $$n$$ &\quad $$K_{E} (n)$$\\
  \hline
   0  & \quad \quad $2$ \\
   1  & \quad \quad $7$ \\
   2  & \quad \quad $18$ \\
   3  & \quad \quad $53$ \\
   4  & \quad \quad $146$ \\
   5  & \quad \quad $415$\\
  \hline
\end{array}
  \]
  \medskip
  \caption{The number of non-attacking king positions on an extended $3 \times n$ chessboard, where $n \geq 0$.}
  \label{TabK_E}
  \end{table}

\indent
The sequence $K_3 (n)$ appears as a subsequence of (\seqnum{A054854}) in \cite{Sloane}. See Table \ref{TabK_3(n)}. 

\begin{table}[h]
  \[
  \begin{array}{ll} \\
  $$n$$ &\quad $$K_{3} (n)$$\\
  \hline
   0  & \quad \quad $1$ \\
   1  & \quad \quad $5$ \\
   2  & \quad \quad $11$ \\
   3  & \quad \quad $35$ \\
   4  & \quad \quad $93$ \\
   5  & \quad \quad $269$\\
  \hline
\end{array}
  \]
  \medskip
  \caption{The number of non-attacking king positions on a $3 \times n$ chessboard, where $n \geq 0$.}
  \label{TabK_3(n)}
  \end{table}

\noindent
There, we see the generating function
\[
\mathcal{K}_3 (x) = \frac{1-x}{1 - 2x - 3x^2 + 2x^3} = 1 + x + 5x^2 + 11x^3 + 35x^4 + 93x^5 + \cdots
\]
Thus, the generating function for $K_3 (n)$ is
\[
\mathbb{K}_3(x) = \frac{1}{x} \cdot \left( \frac{1-x}{1 - 2x - 3x^3 + 2x^3} - 1 \right) = \frac{1 + 3x - 2x^2}{1 - 2x - 3x^2 + 2x^3} = \sum_{n=0}^\infty K_3 (n) x^n.
\]
  
\begin{theorem} \label{TheoremK_3(n)}
For $n \geq 0$, the number of non-attacking king positions on a $3 \times n$ chessboard is the coefficient of the $x^n$-th term in $\mathbb{K}_3(x)$.
\end{theorem}

\section{Cylindrical chessboards} \label{S:cyl}

Let a \textit{cylindrical} $m \times n$ chessboard be represented by identifying the left and right edges with each other. Hence, $n$ is even. We assume that a black square is in the upper left-hand corner of the board and that the board is fixed in position and orientation. Let $\overline{K}_1(n)$ denote the number of non-attacking king positions on a cylindrical $1 \times n$ chessboard. For the degenerate case ($n = 0$), we set $\overline{K}_1(0) = 1$. 

Recall the Fibonacci sequence described by the recurrence relation: $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$, for all $n \geq 2$.

\begin{lemma}\label{cyl_1xn_K}
For even $n \geq 2$, $\overline{K}_{1} (n) = F_{n-1} + F_{n+1}$.
\end{lemma}
\begin{proof}
Let $K_1(n)$ denote the number of non-attacking king positions on a regular $1 \times n$ chessboard. For all $n \geq 1$, it is known that $K_1(n) = F_{n+2}$ \cite[p.\ 510, Exercise 26]{Grim}. Now, let $n \geq 2$ and even. Every non-attacking king position on a cylindrical $1 \times n$ chessboard is in one of two cases. See Figure \ref{FigCyl_k1(n)}. Thus, 
\begin{align}
\overline{K}_{1} (n) &= K_1 (n-3) + K_1 (n-1)\notag{}\\
&= F_{n-3+2} + F_{n-1+2} \notag{}\\
&= F_{n-1} + F_{n+1}. \notag 
\end{align}
\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{FigCyl_k1(n).eps}} \caption{The possible cases for a non-attacking king position on a cylindrical $1 \times n$ chessboard, where $n \geq 2$ and even.} \label{FigCyl_k1(n)}
\end{center}
\end{figure}
\end{proof}

\begin{table}[h]
  \[
  \begin{array}{ll} \\
  $$n$$ &\quad $$\overline{K}_{1} (n)$$\\
  \hline
   0  & \quad \quad $1$ \\
   2  & \quad \quad $3$ \\
   4  & \quad \quad $7$ \\
   6  & \quad \quad $18$ \\
   8  & \quad \quad $47$ \\
   10  & \quad \quad $123$\\
  \hline
\end{array}
  \]
  \medskip
  \caption{The number of non-attacking king positions on a cylindrical $1 \times n$ chessboard, where $n \geq 0$ and even.}
  \label{Tab5}
  \end{table}
  
The sequence $\overline{K}_{1} (n)$ is connected to (\seqnum{A219233}) in \cite{Sloane}. See Table \ref{Tab5}. Let us find the generating function for $\overline{K}_{1} (n)$, where $n \geq 0$ is even. Mathematica 11 gives the generating function 
\[
\mathcal{F}(x) = \frac{1 - x}{1 - 3x + x^2} = \sum_{k=0}^\infty F_{2k+1} x^k.
\]
Then, 
\[
\mathcal{F}(x^2) = \frac{1 - x^2}{1 - 3x^2 + x^4} = \sum_{k=0}^\infty F_{2k+1} x^{2k}.
\]
Also, 
\[
x^2 \mathcal{F}(x^2) = \frac{x^2(1 - x^2)}{1 - 3x^2 + x^4} = \sum_{k=0}^\infty F_{2k+1} x^{2k+2}.
\]
Thus, 
\begin{align}
\overline{\mathbb{K}}_{1}(x) = &\text{ }\mathcal{F}(x^2) + x^2 \mathcal{F}(x^2) \notag{}\\
= &\text{ }\sum_{k=0}^\infty F_{2k+1} x^{2k} + \sum_{k=0}^\infty F_{2k+1} x^{2k+2} \notag{}\\
= &\text{ }[F_1 x^0 + F_3 x^2 + F_5 x^4 + \cdots] + [F_1 x^2 + F_3 x^4 + F_5 x^6 + \cdots] \notag{}\\
= &\text{ }\sum_{k=0}^\infty \overline{K}_{1}(2k) x^{2k} = \frac{1 - x^4}{1 - 3x^2 + x^4}. \notag \\ \notag
\end{align}

\begin{theorem} \label{TheoremCylK_1(n)}
For even $n \geq 0$, the number of non-attacking king positions on a cylindrical $1 \times n$ chessboard is the coefficient of the $x^n$-th term in $\overline{\mathbb{K}}_1(x)$.
\end{theorem}

For even $n \geq 0$, let $\overline{B}_2(n)$ denote the number of non-attacking bishop positions on a cylindrical $2 \times n$ chessboard. For the degenerate case ($n = 0$), we set $\overline{B}_2(0) = 1$. Using the \textit{Cfinite} Maple package \cite{Zeil}, we calculate the Hadamard product $\overline{\mathbb{K}}_{1}(x) \odot \overline{\mathbb{K}}_{1}(x)$. This gives the generating function for $\overline{B}_{2} (n)$, namely\\
\[
\overline{\mathbb{B}}_{2}(x) = \frac{1 + x^2 - 15x^4 + 3x^6}{1 - 8x^2 + 8x^4 - x^6} = \sum_{k=0}^\infty \overline{B}_{2}(2k) x^{2k}.
\]

\begin{theorem} \label{cyl_2xn_B}
For even $n \geq 0$, the number of non-attacking bishop positions on a cylindrical $2 \times n$ chessboard is $\overline{B}_{2} (n) = (F_{n-1} + F_{n+1})^2$. The generating function for $\overline{B}_{2} (n)$ is the Hadamard product $\overline{\mathbb{B}}_2 (x) = \overline{\mathbb{K}}_{1}(x) \odot \overline{\mathbb{K}}_{1}(x)$.
\end{theorem}
\begin{proof}
The configuration of the black squares is completely symmetric to the configuration of the white squares. Bishops on white squares cannot attack bishops on black squares. The result follows immediately from Lemma \ref{cyl_1xn_K}.
\end{proof}

\begin{table}[h]
  \[
  \begin{array}{ll} \\
  $$n$$ &\quad $$\overline{B}_{2} (n)$$\\
  \hline
   0  & \quad \quad $1$ \\
   2  & \quad \quad $9$ \\
   4  & \quad \quad $49$ \\
   6  & \quad \quad $324$ \\
   8  & \quad \quad $2209$ \\
   10  & \quad \quad $15129$\\
  \hline
\end{array}
  \]
  \medskip
  \caption{The number of non-attacking bishop positions on a cylindrical $2 \times n$ chessboard, where $n \geq 0$ and even.}
  \label{Tab6}
  \end{table}

\noindent
We note that the sequence $\overline{B}_2 (n)$ does not appear in \cite{Sloane}. See Table \ref{Tab6}.\\ 

Let $\overline{B}_{3} (n)$ denote the number of non-attacking bishop positions on a cylindrical $3 \times n$ chessboard, for even $n \geq 2$. We set $\overline{B}_{3} (0) = 1$. For odd $n \geq 3$, a \textit{doubly truncated} $3 \times n$ chessboard has missing black squares in the lower lefthand and lower righthand corners of the board. Let $b_{DT}(n)$, for odd $n \geq 3$, denote the number of non-attacking bishop positions on the black squares of a doubly truncated $3 \times n$ chessboard. In the degenerate case where $n = 1$, we set $b_{DT}(1) = b_T (1) = 2$. 

\begin{lemma}\label{b_DT(n)}
For odd $n \geq 3$, $b_{DT}(n) = w_T(n-1) + b_{DT}(n-2)$. 
\end{lemma}
\begin{proof}
Let $n \geq 3$ and odd. Any non-attacking bishop position on the black squares of a doubly truncated $3 \times n$ chessboard is in one of two cases: there is either no bishop or a bishop in the last column of the chessboard. See Figure \ref{Fig_bDT(n)}. Thus, $b_{DT}(n) = w_T(n-1) + b_{DT}(n-2)$. 
\end{proof}
\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{Fig_bDT(n).eps}} \caption{The possible cases for a non-attacking bishop position on the black squares of a doubly truncated $3 \times n$ chessboard, where $n \geq 3$ and odd.} \label{Fig_bDT(n)}
\end{center}
\end{figure}

\begin{table}[h]
  \[
  \begin{array}{ll} \\
  $$n$$ &\quad $$b_{DT} (n)$$\\
  \hline
   1  & \quad \quad $2$ \\
   3  & \quad \quad $5$ \\
   5  & \quad \quad $15$ \\
   7  & \quad \quad $47$ \\
   9  & \quad \quad $150$ \\  
   11 & \quad \quad $481$\\
   \hline
\end{array}
  \]
  \medskip
  \caption{The number of non-attacking bishop positions on the black squares of a doubly truncated $3 \times n$ chessboard, where $n \geq 1$ and odd.} 
  \label{Tab7}
  \end{table}
  
The sequence $b_{DT}(n)$ does not appear in \cite{Sloane}. See Table \ref{Tab7}. From Lemma \ref{b_DT(n)}, we see that $b_{DT}(n) = 2 + w_T (2) + w_T (4) + \cdots + w_T (n-1)$, for odd $n \geq3$. Using this, along with $\mathcal{W}_T (x^2)$, we obtain the generating function for $b_{DT}(n)$, namely 

\begin{align}
\mathcal{B}_{DT}(x) = &\text{ }x \left( \frac{\mathcal{W}_T (x^2)}{1-x^2} + \frac{1}{1-x^2} - 2 \right) + 2x \notag{}\\
= &\text{ }\frac{-2x + 3x^3 + x^5 - x^7}{-1 + 4x^2 - 2x^4 - 2x^6 + x^8} = \sum_{k=0}^\infty b_{DT} (2k+1) x^{2k+1}.\notag \\ \notag
\end{align}

For even $n \geq 2$, let $\overline{b}_{3} (n)$ denote the number of non-attacking bishop positions on the black squares of a cylindrical $3 \times n$ chessboard. We set $\overline{b}_{3} (0) = 1$. Note that $\overline{b}_{3} (2) = 1 \textnormal{ (zero bishops) } + 3 \textnormal{ (one bishop)} = 4$. For $\overline{b}_{3} (4)$, there are two cases to examine. There is either no bishop or a bishop on the black square in the ``last" column of a cylindrical $3 \times 4$ board. See Figure \ref{FigCyl_b3(4)}. Thus, $\overline{b}_{3} (4) = b(2) + 2 + 2 + 1 \textnormal{ (no bishop)} + 2 \textnormal{ (one bishop)} = 12$. 

\begin{lemma}\label{Thm_cyl_b3xn}
For even $n \geq 6$, $\overline{b}_{3} (n) = b(n-2) + w(n-3) + w(n-5) + 2\cdot b_{DT} (n-3)$.
\end{lemma}
\begin{proof}
Let $n \geq 6$ and even. Any non-attacking bishop position on the black squares of a cylindrical $3 \times n$ chessboard is in one of two cases: there is either no bishop or a bishop in the ``last" column of the chessboard. See Figure \ref{FigCyl_b3(n)}. Thus, $\overline{b}_{3} (n) = b(n-2) + w(n-3) + w(n-5) + 2\cdot b_{DT} (n-3)$.
\end{proof}

\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{FigCyl_b3(4).eps}} \caption{The possible cases for a non-attacking bishop position on the black squares of a cylindrical $3 \times 4$ chessboard.} \label{FigCyl_b3(4)}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{FigCyl_b3(n).eps}} \caption{The possible cases for a non-attacking bishop position on the black squares of a cylindrical $3 \times n$ chessboard, where $n \geq 6$ and even.} \label{FigCyl_b3(n)}
\end{center}
\end{figure}

The sequence $\overline{b}_{3} (n)$ does not appear in \cite{Sloane}. See Table \ref{Tab8}. 

\begin{table}[h]
  \[
  \begin{array}{ll} \\
  $$n$$ &\quad $$\overline{b}_{3} (n)$$\\
  \hline
   0  & \quad \quad $$1$$ \\
   2  & \quad \quad $$4$$ \\
   4  & \quad \quad $$12$$ \\
   6  & \quad \quad $$34$$ \\
   8  & \quad \quad $$108$$ \\  
   10 & \quad \quad $$344$$\\
   \hline
\end{array} 
  \]
  \medskip
  \caption{The number of non-attacking bishop positions on the black squares of a cylindrical $3 \times n$ chessboard, where $n \geq 0$ and even.}
  \label{Tab8}
  \end{table} 

\noindent
Using Lemma \ref{Thm_cyl_b3xn}, along with $\mathcal{G}(x)$, $\mathcal{J}(x)$ and $\mathcal{B}_{DT}(x)$, we obtain the generating function for $\overline{b}_{3} (n)$, namely 

\begin{align}
\overline{b}_{3}(x) = &\text{ }x^2 \mathcal{G}(x^2) + x^3 \cdot x \mathcal{J}(x^2) + x^5 \cdot x \mathcal{J}(x^2) + 2x^3 \mathcal{B}_{DT}(x) + x^4 + 3x^2 + 1 \notag{}\\
= &\text{ }\frac{-1 + 2x^4 + 4x^6 - 3x^8}{-1 + 4x^2 - 2x^4 - 2x^6 + x^8} = \sum_{k=0}^\infty \overline{b}_{3} (2k) x^{2k}.\notag \\ \notag
\end{align}

Using the \textit{Cfinite} Maple package \cite{Zeil}, we calculate the Hadamard product $\overline{b}_{3}(x) \odot \overline{b}_{3}(x)$. This gives the generating function for $\overline{B}_{3} (n)$, namely

\begin{align}
&\overline{\mathbb{B}}_{3} (x) = \notag{}\\
&\frac{-1 - 2x^2 + 45x^4 + 252x^6 - 1090x^8 + 644x^{10} + 802x^{12} - 740x^{14} + 35x^{16} + 86x^{18} - 15x^{20}}{-1 + 14x^2 - 35x^4 - 48x^6 + 198x^8 - 112x^{10} - 78x^{12} + 72x^{14} - 5x^{16} - 6x^{18} + x^{20}}. \notag \\ \notag
\end{align}

\begin{theorem} \label{cyl_3xn_B}
For even $n \geq 0$, the number of non-attacking bishop positions on a cylindrical $3 \times n$ chessboard is $\overline{B}_{3} (n) = (\overline{b}_{3} (n))^2$. The generating function for $\overline{B}_{3} (n)$ is the Hadamard product $\overline{\mathbb{B}}_3 (x) = \overline{b}_{3}(x) \odot \overline{b}_{3}(x)$.
\end{theorem}
\begin{proof}
The configuration of the black squares is completely symmetric to the configuration of the white squares. Bishops on white squares cannot attack bishops on black squares. 
\end{proof}

\begin{table}[h]
  \[
  \begin{array}{ll} \\
  $$n$$ &\quad $$\overline{B}_{3} (n)$$\\
  \hline
   0  & \quad \quad $$1$$ \\
   2  & \quad \quad $$16$$ \\
   4  & \quad \quad $$144$$ \\
   6  & \quad \quad $$1156$$ \\
   8  & \quad \quad $$11664$$ \\  
   10 & \quad \quad $$118336$$\\
   \hline
\end{array}
  \]
  \medskip
  \caption{The number of non-attacking bishop positions on a cylindrical $3 \times n$ chessboard, where $n \geq 0$ and even.} 
  \label{Tab9}
  \end{table}
 
\noindent
We note that the sequence $\overline{B}_3 (n)$ does not appear in \cite{Sloane}. See Table \ref{Tab9}.\\
  
\indent
For even $n \geq 2$, let $\overline{K}_2(n)$ denote the number of non-attacking king positions on a cylindrical $2 \times n$ chessboard. For the degenerate case ($n = 0$), we set $\overline{K}_2(0) = 1$. Clearly, $\overline{K}_2 (2) = 5$.

\begin{lemma}\label{CylK2xn}
For even $n \geq 4$, $\overline{K}_2(n) = K_2(n-1) + 2 \cdot K_2(n-3)$.
\end{lemma}
\begin{proof}
Let $n \geq 4$ and even. Any non-attacking king position on a cylindrical $2 \times n$ chessboard is in one of two cases: there is either no king or a king in the ``last" column of the chessboard. See Figure \ref{FigCyl_k2(n)}. Thus, $\overline{K}_2(n) = K_2(n-1) + 2 \cdot K_2(n-3)$.
\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{FigCyl_k2(n).eps}} \caption{The possible cases for a non-attacking king position on a cylindrical $2 \times n$ chessboard, where $n \geq 4$ and even.} \label{FigCyl_k2(n)}
\end{center}
\end{figure}
\end{proof}

\begin{table}[h]
  \[
  \begin{array}{ll} \\
  $$n$$ &\quad $$\overline{K}_{2} (n)$$\\
  \hline
   0  & \quad \quad $$1$$ \\
   2  & \quad \quad $$5$$ \\
   4  & \quad \quad $$17$$ \\
   6  & \quad \quad $$65$$ \\
   8  & \quad \quad $$257$$ \\  
   10 & \quad \quad $$1025$$\\
   \hline
\end{array}
  \]
  \medskip
  \caption{The number of non-attacking king positions on a cylindrical $2 \times n$ chessboard, where $n \geq 0$ and even.} \label{TableValuesCylK2xn}
  \end{table}

\noindent 
The sequence $\overline{K}_2 (n)$ is a subsequence of (\seqnum{A092896}) in \cite{Sloane}. See Table \ref{TableValuesCylK2xn}.

\begin{theorem}\label{Count_cylK2xn}
For even $n \geq 0$, the number of non-attacking king positions on a cylindrical $2 \times n$ chessboard is $\overline{K}_2 (n) = 2^n + 1$.
\end{theorem}
\begin{proof}
Using Lemma \ref{CylK2xn} and Theorem \ref{Sol_K_2}, we see that

\begin{align}
\overline{K}_2 (n) &= K_2(n-1) + 2 \cdot K_2(n-3) \notag{}\\
&= \frac{1}{3} (2^{n-1+2} - (-1)^{n-1}) + 2 (\frac{1}{3} (2^{n-3+2} - (-1)^{n-3})) \notag{}\\
&= \frac{1}{3} \cdot 2^{n+1} - \frac{1}{3} (-1)^{n-1} + \frac{2}{3} \cdot 2^{n-1} - \frac{2}{3} (-1)^{n-3} \notag{}\\
&= \frac{2}{3} \cdot 2^{n} + \frac{1}{3} \cdot 2^{n} - \frac{1}{3} (-1)^{n-1} - \frac{2}{3} (-1)^{n-3} \notag{}\\
&= 2^{n} + \frac{1}{3} (-1)^{n} + \frac{2}{3} (-1)^{n} \notag{}\\
&= 2^n + (-1)^n \notag{}\\
&= 2^n + 1, \notag 
\end{align}
since $n \geq 2$ is even.
\end{proof}

For $n \geq 1$, a \textit{doubly extended} $3 \times n$ chessboard has an extra square attached (in the horizontal direction) to the lower lefthand and righthand corners of the board. Let $K_{DE} (n)$ denote the number of non-attacking king positions on a doubly extended $3 \times n$ chessboard. We set $K_{DE} (0) = 3$, since a doubly extended $3 \times 0$ chessboard can be viewed as a regular $1 \times 2$ chessboard. Observe that $K_{DE} (1) = 1 \textnormal{ (zero kings}) + 5 \textnormal{ (one king}) + 4 \textnormal{ (two kings}) + 1 \textnormal{ (three kings}) = 11$. See Figure \ref{FigDE_K(1)}.

\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{FigDE_K(1).eps}} \caption{Non-attacking positions with two or three kings on a doubly extended $3 \times 1$ chessboard.} \label{FigDE_K(1)}
\end{center}
\end{figure}

For even $n \geq 2$, let $\overline{K}_3 (n)$ denote the number of non-attacking king positions on a cylindrical $3 \times n$ chessboard. We set $\overline{K}_3 (0) = 1$. Observe that $\overline{K}_3 (2) = 1 \textnormal{ (zero kings}) + 6 \textnormal{ (one king}) + 4 \textnormal{ (two kings}) = 11$. See Figure \ref{FigCyl_K(2)}.

\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{FigCyl_K(2).eps}} \caption{Non-attacking positions with two kings on a cylindrical $3 \times 2$ chessboard.} \label{FigCyl_K(2)}
\end{center}
\end{figure}

\begin{lemma}\label{K_DE(n)}
For $n \geq 2$, $K_{DE} (n) = K_3 (n) + 2 \cdot K_E (n-1) + K_{DE} (n-2)$.
\end{lemma}
\begin{proof}
Let $n \geq 2$. Any non-attacking king position on a doubly extended $3 \times n$ chessboard is in one of several cases: there is either no king, one king or two kings on the extended squares of the chessboard. See Figure \ref{FigDE_K(n)}. Thus, $K_{DE} (n) = K_3 (n) + 2 \cdot K_E (n-1) + K_{DE} (n-2)$.
\end{proof}
\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{FigDE_K(n).eps}} \caption{The possible cases for a non-attacking king position on a doubly extended $3 \times n$ chessboard, where $n \geq 2$.} \label{FigDE_K(n)}
\end{center}
\end{figure}

\begin{table}[h]
  \[
  \begin{array}{ll} \\
  $$n$$ &\quad $$K_{DE} (n)$$\\
  \hline
   0  & \quad \quad $$3$$ \\
   1  & \quad \quad $$11$$ \\
   2  & \quad \quad $$28$$ \\
   3  & \quad \quad $$82$$ \\
   4  & \quad \quad $$227$$ \\  
   5 & \quad \quad $$643$$\\
   \hline
\end{array}
  \]
  \medskip
  \caption{The number of non-attacking king positions on a doubly extended $3 \times n$ chessboard, where $n \geq 0$.} 
  \label{TableValuesK_DE3xn} 
  \end{table}

\indent
The sequence $K_{DE} (n)$ does not appear in \cite{Sloane}. See Table \ref{TableValuesK_DE3xn}. Using Lemma \ref{K_DE(n)} (and generating functions $\mathbb{K}_3 (x)$ and $\mathbb{K}_E (x)$), let us find the generating function for $K_{DE} (n)$. 

\begin{align}
\mathbb{K}_{DE} (x) &= \sum_{n=0}^{\infty} K_{DE} (n) x^n = 3 + 11x + \sum_{n=2}^{\infty} K_{DE} (n) x^n \notag{}\\
&= 3 + 11x + \sum_{n=2}^{\infty} (K_3 (n) + 2 \cdot K_E (n-1) )x^n +  \sum_{n=2}^{\infty} K_{DE} (n-2) x^n \notag{}\\
&= 3 + 11x + \sum_{n=2}^{\infty} (K_3 (n) + 2 \cdot K_E (n-1) )x^n +  \sum_{j = 0}^{\infty} K_{DE} (j) x^{j+2} \notag{}\\
&= 3 + 11x + \sum_{n=2}^{\infty} (K_3 (n) + 2 \cdot K_E (n-1) )x^n +  x^2 \cdot \mathbb{K}_{DE} (x). \notag 
\end{align}

\noindent
Solving for $\mathbb{K}_{DE} (x)$ yields 
\begin{align}
\mathbb{K}_{DE} (x) = \frac{1}{1 - x^2} \cdot \left( 3 + 11x + \sum_{n=2}^{\infty} (K_3 (n) + 2 \cdot K_E (n-1) )x^n \right). \notag
\end{align}

\noindent
Hence, 
\begin{align}
\mathbb{K}_{DE} (x) &= \frac{1}{1 - x^2} \cdot \left( 3 + 11x + (\mathbb{K}_3 (x) - 1 - 5x) + 2 (x \cdot \mathbb{K}_E (x) - 2x) \right) \notag{}\\
&= \frac{-3 - 8x -2x^2 + 4x^3}{-1 + x + 5x^2 + x^3 -2x^4} = \sum_{n=0}^{\infty} K_{DE} (n) x^n. \notag
\end{align}

\begin{lemma}\label{CylK_3(n)}
For even $n \geq 4$, $\overline{K}_3 (n) = K_3 (n-1) + 2 \cdot K_3 (n-3) + 2 \cdot K_{DE} (n-3)$.
\end{lemma}
\begin{proof}
Let $n \geq 4$ and even. Any non-attacking king position on a cylindrical $3 \times n$ chessboard is in one of several cases: there is either no king, one king or two kings in the ``last" column of the chessboard. See Figure \ref{FigCyl_k3(n)}. Thus, $\overline{K}_3 (n) = K_3 (n-1) + 2 \cdot K_3 (n-3) + 2 \cdot K_{DE} (n-3)$.
\end{proof}
\begin{figure}[h]
\begin{center}
\scalebox{.50}{\includegraphics{FigCyl_k3(n).eps}} \caption{The possible cases for a non-attacking king position on a cylindrical $3 \times n$ chessboard, where $n \geq 4$ and even.} \label{FigCyl_k3(n)}
\end{center}
\end{figure}

\begin{table}[h]
  \[
  \begin{array}{ll} \\
  $$n$$ &\quad $$\overline{K}_3 (n)$$\\
  \hline
   0  & \quad \quad $$1$$ \\
   2  & \quad \quad $$11$$ \\
   4  & \quad \quad $$67$$ \\  
   6 & \quad \quad $$503$$\\
   8 & \quad \quad $$3939$$\\
   10 & \quad \quad $$31111$$\\
\hline
\end{array}
  \]
  \medskip
  \caption{The number of non-attacking king positions on a cylindrical $3 \times n$ chessboard, where $n \geq 0$ and even.} 
  \label{TableValuesCylK_3(n)}
  \end{table}

\indent The sequence $\overline{K}_3 (n)$ does not appear in \cite{Sloane}. See Table \ref{TableValuesCylK_3(n)}. Using Lemma \ref{CylK_3(n)} (and generating functions $\mathbb{K}_3 (x)$ and $\mathbb{K}_{DE} (x)$), let us find the generating function for $\overline{K}_3 (n)$.

\begin{align}
\overline{\mathbb{K}}_{3} (x) = \textnormal{}&x \cdot \left( \mathbb{K}_3 (x) \odot \frac{x}{1-x^2} \right) + 2x^3 \cdot \left( \mathbb{K}_3 (x) \odot \frac{x}{1-x^2} \right) + \notag{}\\
&2x^3 \cdot \left( \mathbb{K}_{DE} (x) \odot \frac{x}{1-x^2} \right) + 6x^2 + 1. \notag\\ \notag
\end{align}

\noindent
Using the \textit{Cfinite} Maple package \cite{Zeil}, we see that 
\[
\overline{\mathbb{K}}_3 (x) = \frac{1 - 27x^4 + 42 x^6 - 12x^8}{1 - 11x^2 + 27x^4 - 21x^6 + 4x^8} = \sum_{k = 0}^{\infty} \overline{K}_3 (2k) x^{2k}. 
\]
\begin{theorem} \label{TheoremCylK_3(n)}
For even $n \geq 0$, the number of non-attacking king positions on a cylindrical $3 \times n$ chessboard is the coefficient of the $x^n$-th term in $\overline{\mathbb{K}}_3(x)$.
\end{theorem} 

\section{Concluding remarks} \label{S:remarks}

The \textit{On-line Encyclopedia of Integer Sequences}  \cite{Sloane} is an invaluable resource for mathematicians working in the areas of discrete mathematics and combinatorics. During our research project, we encountered various sequences which we checked in \cite{Sloane}, hoping to gain further insight into our combinatorics problem. Some of these sequences did not appear within \cite{Sloane}. The sequences $B_3 (n)$, $\overline{B}_{2} (n)$, $\overline{B}_{3} (n)$ and $\overline{K}_3 (n)$, along with contextual information, recurrence relations and generating functions, have been submitted for entry into this dynamic database of integer sequences.

For additional information on non-attacking chess pieces and other variants, the interested reader is directed to \cite{Kot}.

\section{Acknowledgments} \label{S:acknow}

The authors thank Stephen C. Locke for his thought-provoking conversations during the course of this research project. We are also grateful to the anonymous referee for his/her valuable comments and suggestions.

\begin{thebibliography}{9}

\bibitem{Grim}
R. P. Grimaldi, \textit{Discrete and Combinatorial Mathematics: An Applied Introduction}, 5th Edition, Addison-Wesley, 2004.

\bibitem{Kot}
V. Kot$\check{\textnormal{e}}$$\check{\textnormal{s}}$ovec, \textit{Non-attacking Chess Pieces}, 6th Edition (digital document). Available at 
	    \url{http://www.kotesovec.cz}

\bibitem{Sloane}
N. J. A. Sloane, 
The On-Line Encyclopedia of Integer Sequences.
Published electronically at \url{http://oeis.org}, 2017.

\bibitem{Stevens}
G. E. Stevens, The bishop's tale: a combinatorial proof of $F_n^2 = 2(F_{n-1}^2 + F_{n-2}^2) - F_{n-3}^2$, \textit{Fibonacci Quart}.~\textbf{45} (2007), 319--321.

\bibitem{Zeil}
D. Zeilberger, The C-finite ansatz, \textit{Ramanujan J}.~\textbf{31} (2013), 23--32.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 \emph{Mathematics Subject Classification:}
Primary 05A19.

\noindent \emph{Keywords:} 
non-attacking bishop, non-attacking king, chess.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A001045},
\seqnum{A030186},
\seqnum{A033505},
\seqnum{A046672},
\seqnum{A054854},
\seqnum{A092896}, and
\seqnum{A219233}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  February 5 2017;
revised version received  May 22 2017.
Published in {\it Journal of Integer Sequences},
June 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}