Counting Nonattacking Chess Piece Placements: Bishops and Anassas

Eder G. Santos Brazil

                 ederguidsa@gmail.com

Abstract

We derive recurrences and closed-form expressions for counting nonattacking placements of two types of chess pieces with unbounded straight-line moves, namely the bishop (two diagonal moves) and the anassa (one horizontal or vertical move and one diagonal move), placed on a standard square chessboard. Additionally, we obtain explicit expressions for the corresponding quasi-polynomial coefficients. The recurrences are derived by analyzing how nonattacking configurations attack a specific subset of board squares, employing a bijective argument to establish the relations. The main results are simplifications of known expressions for the bishop and a general counting formula for the anassa.

1 Introduction

In a series of papers, Chaiken, Hanusa, and Zaslavsky [2, 3, 4, 5, 6, 7, 11] prove that the counting function for the nonattacking placements of k chess pieces with unbounded straightline moves (also called riders) on a square board of size m is a cyclically repeating sequence of quasi-polynomials Q(m, k) in m of degree 2k, whose coefficients themselves, after a normalization by k!, are polynomials in k. The general form for the counting function constituents is, then,

Q(m, k) = ∑_{d=0}^{2k} c_{d}(k)m^{d},

where the coefficients c_{d}(k) may vary cyclically, depending on m modulo a number t, the period, but not on m itself.

In this paper, we derive explicit formulas for counting the possible nonattacking placements of bishops (two diagonal moves) and anassas (one horizontal or vertical move and one diagonal move) on the square chessboard. The board B_{m} is defined as the set of coordinate pairs of its squares, and each piece type is defined by a set M of basic moves, which are non-zero, non-parallel integral vectors with coprime coordinates. The central ideas of this paper are the following Definition 1 and Theorem 2:

Definition 1 (Collapsibility, Inductive Subset). Let B_{m} be a board of size m, let I_{m} be a suitably chosen subset of B_{m}, and let M_{P} be the set of moves of a specific piece type P. The board B_{m} is said to be collapsible under {M_{P} , I_{m}} if there exists a bijection f : (B_{m} −I_{m}) → B_{m−1} that preserves the neighborhood relations induced by M_{P} on the board squares. In such conditions, we also say I_{m} is an inductive subset of B_{m} under {f, M_{P} }.

Theorem 2. Let P_{B−I}(m, k) and P_{B}(m − 1, k) enumerate the possible nonattacking placements of k pieces P, with move set M_{P}, on the boards B_{m} − I_{m} and B_{m−1}, respectively, where I_{m} ⊂ B_{m} and B_{m} is a board of size m, collapsible under {M_{P} , I_{m}}. Then,

P_{B−I}(m, k) = P_{B}(m − 1, k).

Proof. If B_{m} is collapsible under {M_{P} , I_{m}}, then, by Definition 1, there exists a one to one correspondence between the nonattacking configurations of the k pieces P on boards B_{m}−I_{m} and B_{m−1}. Hence, the respective enumerating functions must be equal.

The general strategy used in this paper is to find a specific inductive subset I_{m} of B_{m} and then analyze how the nonattacking configurations placed on B_{m} − I_{m} attack I_{m}. Then, we apply Theorem 2 in order to derive a recurrence for P_{B}(m, k).

In the following sections, we apply these concepts to nonattacking placements of bishops and anassas on the square chessboard. Throughout this paper, unless otherwise specified, we make use of extended definitions for the binomial coefficients [14] and for the Stirling numbers of both kinds [12, 10, p. 267], allowing their arguments to assume any integer value. We also provide links to relevant entries in the On-Line Encyclopedia of Integer Sequences (OEIS)

[15] and use the following notation:

\left\{{m \atop k}\right\} Stirling number of the second kind (\underline{A008277}).
\left[{m \atop k}\right] Unsigned Stirling number of the first kind (\underline{A132393}).
\begin{aligned}\{ \\ \{ & {m \atop k} & \} \\ & & \} \end{aligned} Associated Stirling number of the second kind (\underline{A008299}).
δ_{ij} Kronecker Delta function, 1 if i = j and 0 otherwise.
π(m) Parity function, 1 if m odd and 0 otherwise.

[m^{d}]Q(m, k) Coefficient of m^{d} in the quasi-polynomial Q(m, k).
⌈x⌉  Ceiling function, min{n | n ≥ x, n integer}.
⌊x⌋  Floor function, max{n | n ≤ x, n integer}.
(m)_{k}  Falling factorial, m(m − 1) ⋯ (m − k + 1), (m)_{0} = 1.

2 The bishop

2.1 Recurrences and closed-form solutions

We provide an alternative proof for the following result, first obtained by Arshon [1] and then refined by Kotěšovec [13, p. 248].

Theorem 3 (Arshon, Kotěšovec). Let B_{S}(m, k) be the number of possible nonattacking configurations of k bishops placed on the square board S_{m}. Then,

B_{S}(m, k) = ∑_{j=0}^{m} ∑_{i=0}^{⌊ \frac{m+1}{2} ⌋} \binom{⌊\frac{m+1}{2}⌋}{i}\left\{{i + ⌊\frac{m}{2}⌋ \atop m − j}\right\} ∑_{l=0}^{⌊ \frac{m}{2} ⌋} \binom{⌊\frac{m}{2}⌋}{l}\left\{{l + ⌊\frac{m+1}{2}⌋ \atop m − k + j}\right\}.

Although this formula is correct, Chaiken, Hanusa, and Zaslavsky [6] state that it is not entirely satisfactory due to the dependency of the summation indices on m, which makes its quasi-polynomial nature unclear. We provide a further refinement to this expression that makes the quasi-polynomial form more evident.

First, we divide the square board into white and black squares, noting that a bishop, once placed on one of the colors, never leaves it. Then, the problem reduces to placing bishops on two independent boards. Table 1 illustrates these boards and their associated square board. In order to simplify the visualization, the diagonals of the square board S_{m} were translated into rows and columns, so that placing rooks on such translated boards corresponds to placing bishops on the respective colors of the square board.

From the point of view of Definition 1, note that the bishop has move set M_{B} = {(1, 1), (−1, 1)}. We choose an inductive subset candidate I_{m} as the shaded squares of Figure 1a, which translate to the boards W_{m} and K_{m} as the leftmost longest columns I_{m}^{W} and I_{m}^{K}, respectively (shaded squares of Figures 1b and 1c). We define a bijection f_{B} : (i, j) ∈ (S_{m} − I_{m}) → (k, l) ∈ S_{m−1} as follows:

(k, l) = \begin{cases}(i − 1, j), & if 2 ≤ i ≤ m and i > j; \\ (i, j − 1), & if 3 ≤ j ≤ m and j > i + 1. \end{cases}

Bijection f_{B} can be interpreted as a one-unit downward translation of the upper part of S_{m} − I_{m} followed by a one-unit leftward translation of the lower part of S_{m} − I_{m}, in order to build S_{m−1}. Then, it is straightforward to verify that S_{m} is collapsible under {M_{B}, I_{m}}, because all diagonal neighborhood relations induced by M_{B} are preserved by f_{B}. Bijection

m Square Board (S_{m}) White Board (W_{m}) Black Board (K_{m})
0  ∅  ∅  ∅

1  ∅

2

3

4

5

6

Table 1: The sequences of boards (S_{m})_{m≥0}, (W_{m})_{m≥0}, and (K_{m})_{m≥0} up to m = 6, corresponding to the square board and the associated white and black boards. The diagonals of S_{m} are translated into rows and columns, so that placing bishops on S_{m} is equivalent to placing rooks on W_{m} and on K_{m}.

6 5 4 3 2 1 1 2 3 4 5 6 (a)  (b)  (c)

Figure 1: (a) Board S_{6} with I_{6} shaded. (b) White board W_{6} with I_{6}^{W} shaded. (c) Black board K_{6} with I_{6}^{K} shaded.

f_{B} is equivalent to a horizontal joining of both parts of W_{m} − I_{m}^{W}, in order to build W_{m−1}, and similarly for K_{m} − I_{m}^{K}, in order to build K_{m−1}.

Theorem 4. Let R_{W}(m, k) be the number of possible nonattacking configurations of k rooks placed on W_{m}. Similarly, let R_{K}(m, k) be the number of possible nonattacking configurations of k rooks placed on K_{m}. Then,

R_{W}(m, k) = R_{W}(m − 1, k) + (m − k + π(m))R_{W}(m − 1, k − 1),  (1)
R_{K}(m, k) = R_{K}(m − 1, k) + (m − k + 1 − π(m))R_{K}(m − 1, k − 1),  (2)

with initial conditions R_{W}(m, 0) = R_{K}(m, 0) = 1 and R_{W}(0, k) = R_{K}(0, k) = δ_{k0}. These recurrences have the following closed-form solutions:

R_{W}(m, k) = ∑_{j=0}^{k} \binom{⌈\frac{m}{2}⌉}{j}\left\{{m − j \atop m − k}\right\},  (3)

R_{K}(m, k) = ∑_{j=0}^{k} \binom{⌊\frac{m}{2}⌋}{j}\left\{{m − j \atop m − k}\right\},  (4)

valid for all integers m, k ≥ 0.

Proof. First, note that I_{m}^{W} has m − 1 + π(m) squares and each nonattacking rook placed on W_{m} −I_{m}^{W} attacks I_{m}^{W} on exactly one distinct square. Thus, we have two disjoint possibilities for placing k nonattacking rooks on W_{m}:

Case 1. Place all of them on W_{m} − I_{m}^{W}. This can be done in R_{W−I^{W}}(m, k) = R_{W}(m − 1, k) ways, using Theorem 2.

Case 2. Place k − 1 of them on W_{m} − I_{m}^{W} and then place the remaining rook on one of the m − 1 + π(m) − (k − 1) = m − k + π(m) unattacked squares of I_{m}^{W}. This can be done in (m − k + π(m))R_{W−I^{W}}(m, k − 1) = (m − k + π(m))R_{W}(m − 1, k − 1) ways, using Theorem 2.

These cases establish Equation (1). The initial conditions are consequences of an empty board, due either to the absence of squares (m = 0) or to the absence of pieces (k = 0). In order to prove the validity of the closed-form solution, first check the initial conditions, using the identity \left\{{−j \atop −k}\right\} = \left[{k \atop j}\right],

R_{W}(m, 0) = \binom{⌈\frac{m}{2}⌉}{0}\left\{{m \atop m}\right\} = 1,

R_{W}(0, k) = ∑_{j=0}^{k} \binom{0}{j}\left\{{−j \atop −k}\right\} = \left[{k \atop 0}\right] = δ_{k0}.

Then, replace (3) in (1) and use the identities m − 1 + π(m − 1) = m − π(m), \left\{{m−j \atop m−k}\right\} = \left\{{m−1−j \atop m−1−k}\right\} + (m − k)\left\{{m−1−j \atop m−k}\right\}, and \binom{\frac{1}{2} (m−π(m))}{j} + π(m)\binom{\frac{1}{2} (m−π(m))}{j−1} = \binom{\frac{1}{2} (m+π(m))}{j} in order to prove that the recurrence holds:

R_{W}(m − 1, k) + (m − k + π(m))R_{W}(m − 1, k − 1) =

= ∑_{j=0}^{k} \binom{\frac{1}{2}(m − 1 + π(m − 1))}{j}\left\{{m − 1 − j \atop m − 1 − k}\right\}+

+ (m − k + π(m)) ∑_{j=0}^{k−1} \binom{\frac{1}{2}(m − 1 + π(m − 1))}{j}\left\{{m − 1 − j \atop m − k}\right\}

= \binom{\frac{1}{2}(m − π(m))}{k} + ∑_{j=0}^{k−1} \binom{\frac{1}{2}(m − π(m))}{j} (\left\{{m − j \atop m − k}\right\} + π(m)\left\{{m − 1 − j \atop m − k}\right\})

= ∑_{j=0}^{k} \binom{\frac{1}{2}(m − π(m))}{j}\left\{{m − j \atop m − k}\right\} + π(m) ∑_{j=1}^{k} \binom{\frac{1}{2}(m − π(m))}{j − 1}\left\{{m − j \atop m − k}\right\}

= \left\{{m \atop m − k}\right\} + ∑_{j=1}^{k} (\binom{\frac{1}{2}(m − π(m))}{j} + π(m)\binom{\frac{1}{2}(m − π(m))}{j − 1}) \left\{{m − j \atop m − k}\right\}

= ∑_{j=0}^{k} \binom{\frac{1}{2}(m + π(m))}{j}\left\{{m − j \atop m − k}\right\} = R_{W}(m, k).

For the black board, note that I_{m}^{K} has m−π(m) squares and follow similar steps to obtain (2). Then, use a similar reasoning to check the validity of the closed-form solution (4).

Remark 5. In fact, the approach used to solve recurrence (1), for instance, is more natural if we consider R_{W}(m, m − k), using the boundary condition R_{W}(m, m) = δ_{m1} + δ_{m0}. By solving for some small k, the reader may correctly guess and check the following closed-form solution:

R_{W}(m, m − k) = ∑_{j=0}^{k} \binom{k}{j}\frac{(−1)^{k−j}(j + 1)^{\frac{1}{2} (m+π(m))}j^{\frac{1}{2} (m−π(m))}}{k!} .

This was essentially the expression found by Arshon [1], as stated by Kotěšovec [13, pp. 242–248]. By expanding (j + 1)^{\frac{1}{2} (m+π(m))} using the binomial theorem, rearranging summation indices and using the identity \left\{{m \atop k}\right\} = ∑_{j=0}^{k} \binom{k}{j} \frac{(−1)^{k−j}j^{m}}{k!} , Kotěšovec was able to refine Arshon’s result, obtaining

R_{W}(m, k) = ∑_{j=0}^{\frac{1}{2} (m+π(m))} \binom{\frac{1}{2}(m + π(m))}{j}\left\{{j + \frac{1}{2}(m − π(m)) \atop m − k}\right\}.

However, this can be further simplified by noting that

R_{W}(2m, k) = ∑_{j=m−k}^{m} \binom{m}{j}\left\{{j + m \atop 2m − k}\right\} = ∑_{j=0}^{k} \binom{m}{j}\left\{{2m − j \atop 2m − k}\right\},

R_{W}(2m − 1, k) = ∑_{j=m−k}^{m} \binom{m}{j}\left\{{j + m − 1 \atop 2m − 1 − k}\right\} = ∑_{j=0}^{k} \binom{m}{j}\left\{{2m − 1 − j \atop 2m − 1 − k}\right\}.

Combining both equations results in (3). A similar approach yields (4).

Theorem 6. Let B_{S}(m, k) be the number of possible nonattacking configurations of k bishops placed on the square board S_{m}. Then,

B_{S}(m, k) = ∑_{j=0}^{k} ∑_{i=0}^{j} \binom{⌊\frac{m}{2}⌋}{i}\left\{{m − i \atop m − j}\right\} ∑_{l=0}^{k−j} \binom{⌈\frac{m}{2}⌉}{l}\left\{{m − l \atop m − k + j}\right\},  (5)

for all integers m, k ≥ 0.

Proof. Replace Equations (4) and (3) in the following:

B_{S}(m, k) = ∑_{j=0}^{k} R_{K}(m, j)R_{W}(m, k − j).  (6)

Equation (5) makes the quasi-polynomial nature of B_{S}(m, k) evident and gives an upper bound for the period t = 2. Regarding the exact period, a deeper analysis is needed because there may be cancellations in the sums. Take, for example, the case k = 1, B_{S}(m, 1) = \frac{m^{2}+π(m)}{2} + \frac{m^{2}−π(m)}{2} = m^{2}, or the case k = 2, B_{S}(m, 2) = 12\binom{m}{4} + 14\binom{m}{3} + 4\binom{m}{2}, both having period t = 1. The exact period t = 2 for all k ≥ 3 was rigorously proven by Chaiken, Hanusa, and Zaslavsky [7, Thm. 1.1].

Theorems 4 and 6 led to the submission of a new sequence, \underline{A378590}, to the OEIS database, along with updates to the sequences \underline{A274105} and \underline{A274106}.

Remark 7. Another aspect mentioned by Chaiken, Hanusa, and Zaslavsky [6] is the possibility of retrieving the number of combinatorial types of the nonattacking configurations for the piece by setting m = −1 in the counting formulas. They showed [2, Thm. 5.8] that this number is k! for all pieces with exactly two unbounded straight-line moves. Indeed, setting m = −1 in Equation (5) yields

B_{S}(−1, k) = ∑_{j=0}^{k} ∑_{i=0}^{j} \binom{⌊−\frac{1}{2}⌋}{i}\left\{{−1 − i \atop −1 − j}\right\} ∑_{l=0}^{k−j} \binom{⌈−\frac{1}{2}⌉}{l}\left\{{−1 − l \atop −1 − k + j}\right\}

= ∑_{j=0}^{k}(k − j)! ∑_{i=0}^{j}(−1)^{i}\left[{j + 1 \atop i + 1}\right] = k!,

where the following identities were used:

(a) \binom{⌊− \frac{1}{2} ⌋}{i} = (−1)^{i};

(b) \binom{⌈− \frac{1}{2} ⌉}{l} = δ_{l0};

(c) \left\{{−m \atop −k}\right\} = \left[{k \atop m}\right];

(d) \left[{k+1 \atop 1}\right] = k!; and

(e) ∑_{i=0}^{j}(−1)^{i}\left[{j+1 \atop i+1}\right] = δ_{j0}.

2.2 Quasi-polynomial coefficients for the bishop

In order to proceed to explicit calculation of the quasi-polynomial coefficients for the bishop using Equation (5), two results are needed.

Lemma 8. Let m and k be nonnegative integers. Then,

\left\{{m \atop m − k}\right\} = ∑_{p=0}^{k}\begin{aligned}\{ \\ \{ & {k + p \atop p} & \} \\ & & \} \end{aligned}\binom{m}{k + p}.  (7)

An interesting property [8] of the numbers \begin{aligned}\{ \\ \{ & {m \atop k} & \} \\ & & \} \end{aligned} is that they follow the recurrence

\begin{aligned}\{ \\ \{ & {m \atop k} & \} \\ & & \} \end{aligned} = k\begin{aligned}\{ \\ \{ & {m − 1 \atop k} & \} \\ & & \} \end{aligned} + (m − 1)\begin{matrix}\{ \\ \{ & {m − 2 \atop k − 1} & \} \\ & & \} \end{matrix},

with initial conditions \begin{aligned}\{ \\ \{ & {0 \atop k} & \} \\ & & \} \end{aligned} = δ_{k0}, \begin{aligned}\{ \\ \{ & {1 \atop k} & \} \\ & & \} \end{aligned} = 0 and \begin{aligned}\{ \\ \{ & {m \atop 0} & \} \\ & & \} \end{aligned} = δ_{m0}. Written in the form \begin{aligned}\{ \\ \{ & {m+k \atop k} & \} \\ & & \} \end{aligned}, these numbers are also referenced as the Ward numbers (\underline{A134991}). The related OEIS sequences assume k > 0 and m ≥ 2, but here we have trivially extended the definition of \begin{aligned}\{ \\ \{ & {m \atop k} & \} \\ & & \} \end{aligned} in order to account for the cases k = 0 and 0 ≤ m < 2 as well. Lemma 8 is a well-known result and may be proven by induction.

Lemma 9. Let p and q be nonnegative integers, and let x and z be arbitrary complex numbers. Then,

\binom{2x + z − q}{p}\binom{x}{q} = ∑_{i=0}^{p+q} β_{i}(p, q, z)\binom{2x + z}{i},  (8)

where

β_{i}(p, q, z) = \frac{1}{2^{2q}} ∑_{b=max(0,i−p)}^{q} 2^{b}\binom{2q − b}{q} ∑_{a=0}^{b} \binom{p + b − q − z}{a}\binom{q + z}{b − a}\binom{a − q}{p + b − i}. (9)

Proof. We begin with two combinatorial identities, listed by Gould and Quaintance [9, identities (1.40) and (1.42)]. Let x be an arbitrary complex number and let q be a nonnegative integer. Then,

(−1)^{q}2^{2q}\binom{x}{q} = ∑_{b=0}^{q} \binom{−q − 1}{q − b}\binom{2q − 2x − 1}{b}2^{b}.  (10)

Now, let p be a nonnegative integer and let z be an arbitrary complex number. Use the identity \binom{−x}{q} = (−1)^{q}\binom{x+q−1}{q} and multiply \binom{2x+z−q}{p} on both sides of (10) to obtain

\binom{2x + z − q}{p}\binom{x}{q} = \frac{1}{2^{2q}} ∑_{b=0}^{q} 2^{b}\binom{2q − b}{q}\binom{2x + z − q}{p}\binom{2x − 2q + b}{b}.  (11)

We also have the following result [9, identity (6.81)] for arbitrary complex numbers w and y and nonnegative integers m and n:

\binom{w}{m}\binom{y}{n} = ∑_{k=0}^{n} \binom{m − w + y}{k}\binom{n + w − y}{n − k}\binom{w + k}{m + n}.  (12)

Making w = 2x + z − q, m = p, y = 2x − 2q + b, n = b, and expanding the binomial product in (11) yields

\binom{2x + z − q}{p}\binom{x}{q} = \frac{1}{2^{2q}} ∑_{b=0}^{q} 2^{b}\binom{2q − b}{q} ∑_{a=0}^{b} \binom{p + b − q − z}{a}\binom{q + z}{b − a}\binom{2x + z − q + a}{p + b}.

Then, use the generalized version of the Vandermonde Convolution [9, identity (6.9)] to write

\binom{2x + z − q + a}{p + b} = ∑_{i=0}^{p+b} \binom{2x + z}{i}\binom{a − q}{p + b − i}.

The final step is to rearrange the summation indices in order to obtain (8) and (9). Theorem 10. The quasi-polynomial coefficients of R_{W}(m, k), R_{K}(m, k) and B_{S}(m, k) are, respectively,

[m^{d}]R_{W}(m, k) = ∑_{i=d}^{2k} \frac{(−1)^{i−d}}{i!} \left[{i \atop d}\right] ∑_{p=max(0,i−k)}^{k} ∑_{j=p}^{k}\begin{aligned}\{ \\ \{ & {p + j \atop p} & \} \\ & & \} \end{aligned}β_{i}(p + j, k − j, −π(m)), (13)
[m^{d}]R_{K}(m, k) = ∑_{i=d}^{2k} \frac{(−1)^{i−d}}{i!} \left[{i \atop d}\right] ∑_{p=max(0,i−k)}^{k} ∑_{j=p}^{k}\begin{aligned}\{ \\ \{ & {p + j \atop p} & \} \\ & & \} \end{aligned}β_{i}(p + j, k − j, π(m)),  (14)
[m^{d}]B_{S}(m, k) = ∑_{j=0}^{k} ∑_{i=0}^{d} ([m^{i}]R_{W}(m, j)) ([m^{d−i}]R_{K}(m, k − j)) ,  (15)

for 0 ≤ d ≤ 2k. Proof. From Equation (3) and Lemma 8

R_{W}(2m, k) = ∑_{j=0}^{k} \binom{m}{j}\left\{{2m − j \atop 2m − k}\right\} = ∑_{j=0}^{k} ∑_{p=0}^{k−j}\begin{aligned}\{ \\ \{ & {p + k − j \atop p} & \} \\ & & \} \end{aligned}\binom{2m − j}{p + k − j}\binom{m}{j},
R_{W}(2m − 1, k) = ∑_{j=0}^{k} \binom{m}{j}\left\{{2m − 1 − j \atop 2m − 1 − k}\right\} = ∑_{j=0}^{k} ∑_{p=0}^{k−j}\begin{aligned}\{ \\ \{ & {p + k − j \atop p} & \} \\ & & \} \end{aligned}\binom{2m − 1 − j}{p + k − j}\binom{m}{j}.

Now relabel j to k − j, use Lemma 9, and rearrange the summation indices to obtain

R_{W}(2m, k) = ∑_{i=0}^{2k} ∑_{p=max(0,i−k)}^{k} ∑_{j=p}^{k}\begin{aligned}\{ \\ \{ & {p + j \atop p} & \} \\ & & \} \end{aligned}β_{i}(p + j, k − j, 0)\binom{2m}{i},
R_{W}(2m − 1, k) = ∑_{i=0}^{2k} ∑_{p=max(0,i−k)}^{k} ∑_{j=p}^{k}\begin{aligned}\{ \\ \{ & {p + j \atop p} & \} \\ & & \} \end{aligned}β_{i}(p + j, k − j, −1)\binom{2m − 1}{i}.

The final step is to use the identity \binom{x}{i} = ∑_{d=0}^{i} \frac{(−1)^{i−d}}{i!} \left[{i \atop d}\right]x^{d} and rearrange the summation indices again. Here, L(i, k) = max(0, i − k):

R_{W}(2m, k) = ∑_{d=0}^{2k} ∑_{i=d}^{2k} \frac{(−1)^{i−d}}{i!} \left[{i \atop d}\right] ∑_{p=L(i,k)}^{k} ∑_{j=p}^{k}\begin{aligned}\{ \\ \{ & {p + j \atop p} & \} \\ & & \} \end{aligned}β_{i}(p + j, k − j, 0)(2m)^{d},
R_{W}(2m − 1, k) = ∑_{d=0}^{2k} ∑_{i=d}^{2k} \frac{(−1)^{i−d}}{i!} \left[{i \atop d}\right] ∑_{p=L(i,k)}^{k} ∑_{j=p}^{k}\begin{aligned}\{ \\ \{ & {p + j \atop p} & \} \\ & & \} \end{aligned}β_{i}(p + j, k − j, −1)(2m − 1)^{d}.

Combining both results yields (13). A similar approach, using R_{K}(2m, k) and R_{K}(2m+1, k), results in (14). A trivial manipulation in (6) yields (15).

3 The anassa

3.1 Recurrence and closed-form solution

In this paper, without any loss of generality, anassas are considered to be pieces with move set M_{A} = {(0, 1), (1, 1)}, as shown in Figure 2a. We choose Λ_{m} = V_{m} ∪ D_{m} (Figure 2b) as the inductive subset and define a bijection f_{A} : (i, j) ∈ (S_{m} − Λ_{m}) → (k, l) ∈ S_{m−1} as follows:

(k, l) = \begin{cases}(i, j − 1), & if i < j < m; \\ (i, j), & if j < i < m. \end{cases}

Bijection f_{A} can be interpreted as a one-unit downward translation of the upper part of S_{m} − Λ_{m}, in order to build S_{m−1}. Then, it is straightforward to verify that S_{m} is collapsible under {M_{A}, Λ_{m}} because all right diagonal and vertical neighborhood relations induced by M_{A} are preserved by f_{A}.

\begin{aligned}6 \\ 5 \\ 4 & & & • \\ 3 \\ 2 \\ 1 \\ & 1 & 2 & 3 & 4 & 5 & 6 \end{aligned} ; (a)  6 5 4 3 2 1 1 2 3 4 5 6 (b)

Figure 2: (a) Illustration of the attacks of an anassa placed on square (3, 4). (b) Sets Λ_{6} (light and dark shaded squares), V_{6} (only dark shaded squares) and D_{6} (only light shaded squares).

Here, the number of attacked squares in Λ_{m} depends essentially on how many pieces are placed below and above Λ_{m}, since every nonattacking configuration placed on S_{m}−Λ_{m}, with p pieces below Λ_{m} and k − p pieces above Λ_{m}, attacks Λ_{m} on exactly 2p + (k − p) = k + p distinct squares, with k attacked squares in D_{m} and p attacked squares in V_{m}. Thus, a natural choice is to count the nonattacking configurations with exactly p pieces placed strictly below the main diagonal of S_{m}.

Theorem 11. Let A_{S}(m, k, p) be the number of possible nonattacking configurations of k anassas placed on the square board S_{m} such that exactly p of them are placed strictly below the board’s main diagonal. Then,

A_{S}(m, k, p) = A_{S}(m − 1, k, p) + (m − k + 1)A_{S}(m − 1, k − 1, p)+
+(m − p)A_{S}(m − 1, k − 1, p − 1) + (m − p)(m − k + 1)A_{S}(m − 1, k − 2, p − 1), (16)

with initial conditions A_{S}(0, k, p) = δ_{k0}δ_{p0}, A_{S}(m, 0, p) = δ_{p0}, A_{S}(m, 1, p) = \left\{{m+1 \atop m}\right\}δ_{p0} + \left\{{m \atop m−1}\right\}δ_{p1} and A_{S}(m, k, 0) = \left\{{m+1 \atop m−k+1}\right\}. This recurrence has the following closed-form solution:

A_{S}(m, k, p) = ∑_{j=0}^{p}(m − k + j)_{j}\binom{k − p − 1}{j}\binom{k − j}{k − p}\left\{{m + 1 \atop m − k + j + 1}\right\},  (17)

valid for all integers m, k, p ≥ 0.

Proof. We have the following disjoint possibilities for the placement of k nonattacking anassas on S_{m} such that p of them are placed strictly below the board’s main diagonal:

Case 1. Place all of them on S_{m} − Λ_{m}, while keeping p of them below Λ_{m}. This can be done in A_{S}(m − 1, k, p) ways.

Case 2. Place k − 1 of them on S_{m} − Λ_{m}, while keeping p of them below Λ_{m}, and then place the remaining anassa on one of the m − k + 1 unattacked squares of D_{m}. This can be done in (m − k + 1)A_{S}(m − 1, k − 1, p) ways.

Case 3. Place k − 1 of them on S_{m} − Λ_{m}, while keeping p − 1 of them below Λ_{m}, and then place the remaining anassa on one of the m − 1 − (p − 1) = m − p unattacked squares of V_{m}. This can be done in (m − p)A_{S}(m − 1, k − 1, p − 1) ways.

Case 4. Place k − 2 of them on S_{m} − Λ_{m}, while keeping p − 1 of them below Λ_{m}, then place the first remaining anassa on one of the m − 1 − (p − 1) = m − p unattacked squares of V_{m} and then place the other remaining anassa on one of the m − k + 1 unattacked squares of D_{m}. This can be done in (m − p)(m − k + 1)A_{S}(m − 1, k − 2, p − 1) ways.

These cases establish recurrence (16). The first two initial conditions are consequences of an empty board, due either to the absence of squares (m = 0) or to the absence of pieces (k = 0). The last two initial conditions are consequences of the well-known result that states that \left\{{m+1 \atop m−k+1}\right\} enumerates the nonattacking configurations of k rooks (or k anassas, due to the board symmetry) placed on a staircase board, in the shape of a right isosceles triangle, with m squares in its longest row.

In order to prove the validity of the closed-form solution, first check the initial conditions

A_{S}(0, k, p) = ∑_{j=0}^{p}(−k + j)_{j}\binom{k − p − 1}{j}\binom{k − j}{k − p}\left\{{1 \atop −k + j + 1}\right\}

= δ_{k0} ∑_{j=0}^{p}(j)_{j}\binom{−p − 1}{j}\binom{−j}{−p}\left\{{1 \atop j + 1}\right\} = δ_{k0}δ_{p0},

A_{S}(m, 0, p) = ∑_{j=0}^{p}(m + j)_{j}\binom{−p − 1}{j}\binom{−j}{−p}\left\{{m + 1 \atop m + j + 1}\right\} = δ_{p0},
A_{S}(m, 1, p) = ∑_{j=0}^{p}(m − 1 + j)_{j}\binom{−p}{j}\binom{1 − j}{1 − p}\left\{{m + 1 \atop m + j}\right\}

= (m − 1)_{0}\binom{−p}{0}\binom{1}{1 − p}\left\{{m + 1 \atop m}\right\} + (m)_{1}\binom{−p}{1}\binom{0}{1 − p}\left\{{m + 1 \atop m + 1}\right\}

= (δ_{p1} + δ_{p0})\left\{{m + 1 \atop m}\right\} − mδ_{p1} = δ_{p0}\left\{{m + 1 \atop m}\right\} + δ_{p1}\left\{{m \atop m − 1}\right\},

A_{S}(m, k, 0) = ∑_{j=0}^{0}(m − k + j)_{j}\binom{k − 1}{j}\binom{k − j}{k}\left\{{m + 1 \atop m − k + j + 1}\right\} = \left\{{m + 1 \atop m − k + 1}\right\}.

Then, in order to replace (17) in (16), note that (m − p)A_{S}(m − 1, k − 1, p − 1) =

= (m − p) ∑_{j=0}^{p}(m − k + j)_{j}\binom{k − p − 1}{j}\binom{k − j − 1}{k − p}\left\{{m \atop m − k + j + 1}\right\},  (18a)

(m − k + 1)A_{S}(m − 1, k − 1, p) =

= (m − k + 1) ∑_{j=0}^{p}(m − k + j)_{j}\binom{k − p − 2}{j}\binom{k − j − 1}{k − p − 1}\left\{{m \atop m − k + j + 1}\right\},  (18b)

(m − p)(m − k + 1)A_{S}(m − 1, k − 2, p − 1) =

= (m − p)(m − k + 1) ∑_{j=0}^{p−1}(m − k + j + 1)_{j}\binom{k − p − 2}{j}\binom{k − j − 2}{k − p − 1}\left\{{m \atop m − k + j + 2}\right\}

= (m − p) ∑_{j=1}^{p}(m − k + j)_{j}\binom{k − p − 2}{j − 1}\binom{k − j − 1}{k − p − 1}\left\{{m \atop m − k + j + 1}\right\}.  (18c)

Now, sum Equations (18a) to (18c), simplify the binomial coefficients, and use the recurrence for the Stirling numbers of the second kind to obtain

(m − p)A_{S}(m − 1, k − 1, p − 1) + (m − k + 1)A_{S}(m − 1, k − 1, p)+ + (m − p)(m − k + 1)A_{S}(m − 1, k − 2, p − 1) =

= ∑_{j=0}^{p}(m − k + j + 1)(m − k + j)_{j}\binom{k − p − 1}{j}\binom{k − j}{k − p}\left\{{m \atop m − k + j + 1}\right\}+

+ ∑_{j=0}^{p}(j + 1)(m − k + j)_{j}\binom{k − p − 1}{j + 1}\binom{k − j − 1}{k − p}\left\{{m \atop m − k + j + 1}\right\}

= ∑_{j=0}^{p}(m − k + j + 1)(m − k + j)_{j}\binom{k − p − 1}{j}\binom{k − j}{k − p}\left\{{m \atop m − k + j + 1}\right\}+

+ ∑_{j=1}^{p} j(m − k + j − 1)_{j−1}\binom{k − p − 1}{j}\binom{k − j}{k − p}\left\{{m + 1 \atop m − k + j + 1}\right\}−

− ∑_{j=1}^{p} j(m − k + j − 1)_{j−1}(m − k + j + 1)\binom{k − p − 1}{j}\binom{k − j}{k − p}\left\{{m \atop m − k + j + 1}\right\}. (19)

Then, use the Stirling numbers recurrence again to write

A_{S}(m − 1, k, p) = ∑_{j=0}^{p}(m − k + j − 1)_{j}\binom{k − p − 1}{j}\binom{k − j}{k − p}\left\{{m \atop m − k + j}\right\} =

= ∑_{j=0}^{p}(m − k + j − 1)_{j}\binom{k − p − 1}{j}\binom{k − j}{k − p}\left\{{m + 1 \atop m − k + j + 1}\right\}−

− ∑_{j=0}^{p}(m − k + j + 1)(m − k + j − 1)_{j}\binom{k − p − 1}{j}\binom{k − j}{k − p}\left\{{m \atop m − k + j + 1}\right\}. (20)

Now, sum (19) and (20) and use the identity (r)_{s} = (r − 1)_{s} + s(r − 1)_{s−1} to retrieve A_{S}(m, k, p), proving that recurrence (16) holds. Remark 12. We may verify that, for p = k, Equation (17) is a telescoping sum, resulting in

A_{S}(m, k, k) = ∑_{j=0}^{k}(−1)^{j}(m − k + j)_{j}\left\{{m + 1 \atop m − k + j + 1}\right\}

= ∑_{j=0}^{k}(−1)^{j} ((m − k + j)_{j}\left\{{m \atop m − k + j}\right\} + (m − k + j + 1)_{j+1}\left\{{m \atop m − k + j + 1}\right\})

= \left\{{m \atop m − k}\right\}.

This result is expected, since \left\{{m \atop m−k}\right\} enumerates the nonattacking configurations of k anassas placed on a staircase board of size m − 1.

Theorem 13. Let A_{S}(m, k) be the number of possible nonattacking configurations of k anassas placed on the square board S_{m}. Then,

A_{S}(m, k) = ∑_{j=0}^{⌈ \frac{k}{2} ⌉}(m − k + j)_{j}\left\{{m \atop m − k + j}\right\}2^{k−2j} (\binom{k − j}{j − 1} + \binom{k − j + 1}{j}) ,  (21)

for all integers m, k ≥ 0.

Proof. First, we use the recurrence for the Stirling numbers of the second kind and manipulate the binomial coefficients to rewrite (17) as

A_{S}(m, k, p) = ∑_{j=0}^{p}(m − k + j)_{j}\binom{k − p − 1}{j}\binom{k − j}{k − p}\left\{{m \atop m − k + j}\right\}+

+ ∑_{j=1}^{p+1}(m − k + j)_{j}\binom{k − p − 1}{j − 1}\binom{k − j + 1}{k − p}\left\{{m \atop m − k + j}\right\}

= ∑_{j=0}^{p+1}(m − k + j)_{j} (\binom{k − j}{k − p}\binom{k − p}{j} + \binom{k − j}{k − p − 1}\binom{k − p − 1}{j − 1}) \left\{{m \atop m − k + j}\right\}

= ∑_{j=0}^{p+1}(m − k + j)_{j} (\binom{k − j}{j}\binom{k − 2j}{p − j} + \binom{k − j}{j − 1}\binom{k − 2j + 1}{p − j + 1}) \left\{{m \atop m − k + j}\right\}. (22)

We also have

A_{S}(m, k) = ∑_{p=0}^{k} A_{S}(m, k, p).  (23)

Then, replace (22) in (23) and rearrange the summation indices to obtain

A_{S}(m, k) = ∑_{j=0}^{k+1}(m − k + j)_{j}\left\{{m \atop m − k + j}\right\}\binom{k − j}{j} ∑_{p=j}^{k} \binom{k − 2j}{p − j}+

+ ∑_{j=1}^{k+1}(m − k + j)_{j}\left\{{m \atop m − k + j}\right\}\binom{k − j}{j − 1} ∑_{p=j−1}^{k} \binom{k − 2j + 1}{p − j + 1}.

Now, use the identity ∑_{p=j}^{k} \binom{k−2j}{p−j} = 2^{k−2j} and simplify the binomial coefficients. The upper summation limit can be reduced to ⌈\frac{k}{2}⌉, as indicated by the remaining binomial coefficients. These manipulations result in (21).

Remark 14. As done in Remark 7, setting m = −1 in (21) leads to

A_{S}(−1, k) = ∑_{j=0}^{⌈ \frac{k}{2} ⌉}(−1 − k + j)_{j}\left\{{−1 \atop −1 − k + j}\right\}2^{k−2j} (\binom{k − j}{j − 1} + \binom{k − j + 1}{j})

= ∑_{j=0}^{⌈ \frac{k}{2} ⌉}(−1)^{j}(k)_{j}(k − j)!2^{k−2j} (\binom{k − j}{j − 1} + \binom{k − j + 1}{j})

= k! ∑_{j=0}^{⌈ \frac{k}{2} ⌉}(−1)^{j}2^{k−2j} (\binom{k − j}{j − 1} + \binom{k − j + 1}{j})

= k! ∑_{j=0}^{⌈ \frac{k}{2} ⌉}(−1)^{j} (2^{k+1−2j}\binom{k + 1 − j}{k + 1 − 2j} − 2^{k−2j}\binom{k − j}{k − 2j}) .

But, by Gould and Quaintance [9, identity (1.69)], we have

∑_{j=0}^{⌈ \frac{k}{2} ⌉}(−1)^{j}2^{k−2j}\binom{k − j}{k − 2j} = k + 1.

Then, as predicted by Chaiken, Hanusa, and Zaslavsky [2, Thm. 5.8],

A_{S}(−1, k) = k!(k + 2 − k − 1) = k!.

Remark 15. Kotěšovec [13, p. 716] provided two expressions for the anassa (“semi-rook + semi-bishop”) when k = m. Here, his expressions are trivially extended to account for the case m = 0 as well:

A_{S}(m, m) = ∑_{j=0}^{m} \binom{m + 1}{j}\left\{{m \atop j}\right\}\frac{j!}{2^{j}} = \frac{1}{2^{m+1}} ∑_{j=0}^{m+1} \binom{m + 1}{j}j^{m}.

Using (21), this result implies the identity

∑_{j=0}^{m} \binom{m + 1}{j}\left\{{m \atop j}\right\}\frac{j!}{2^{j}} = 2^{m} ∑_{j=0}^{⌈ \frac{m}{2} ⌉}\left\{{m \atop j}\right\}\frac{j!}{2^{2j}} (\binom{m − j}{j − 1} + \binom{m − j + 1}{j}) .

However, we could not find a direct simplification for the right-hand side that could prove this result.

We highlight that Theorem 13 led to the submission of a new sequence, \underline{A378561}, to the OEIS database.

3.2 Quasi-polynomial coefficients for the anassa

As for the bishop, an explicit expression for the quasi-polynomial coefficients of A_{S}(m, k) can be obtained by using Lemma 8 and some binomial identities.

Theorem 16. The quasi-polynomial coefficients of A_{S}(m, k) are

[m^{d}]A_{S}(m, k) =

= ∑_{i=d}^{2k} \frac{(−1)^{i−d}}{i!} \left[{i \atop d}\right] ∑_{j=0}^{U(i,k)} α(k, j) ∑_{p=L(i,k)}^{k−j}\begin{aligned}\{ \\ \{ & {p + k − j \atop p} & \} \\ & & \} \end{aligned} ∑_{b=0}^{j} \binom{p}{b}\binom{k}{j − b}\binom{b}{k + p − i}, (24)

for 0 ≤ d ≤ 2k, where α(k, j) = 2^{k−2j} (\binom{k−j}{j−1} + \binom{k−j+1}{j}) j!, U(i, k) = min(⌈\frac{k}{2}⌉, 2k − i), and L(i, k) = max(0, i − k).

Proof. First, use Lemma 8 to expand the Stirling numbers of the second kind in (21), obtaining

A_{S}(m, k) = ∑_{j=0}^{⌈ \frac{k}{2} ⌉} α(k, j) ∑_{p=0}^{k−j}\begin{aligned}\{ \\ \{ & {p + k − j \atop p} & \} \\ & & \} \end{aligned}\binom{m}{p + k − j}\binom{m − k + j}{j}.

Then, use identity (12) to expand the binomial product

A_{S}(m, k) = ∑_{j=0}^{⌈ \frac{k}{2} ⌉} α(k, j) ∑_{p=0}^{k−j}\begin{aligned}\{ \\ \{ & {p + k − j \atop p} & \} \\ & & \} \end{aligned} ∑_{b=0}^{j} \binom{p}{b}\binom{k}{j − b}\binom{m + b}{k + p},

and use the Vandermonde convolution followed by a rearrangement of the summation indices to obtain

A_{S}(m, k) = ∑_{j=0}^{⌈ \frac{k}{2} ⌉} α(k, j) ∑_{p=0}^{k−j}\begin{aligned}\{ \\ \{ & {p + k − j \atop p} & \} \\ & & \} \end{aligned} ∑_{b=0}^{j} \binom{p}{b}\binom{k}{j − b} ∑_{i=0}^{k+p} \binom{m}{i}\binom{b}{k + p − i}

= ∑_{i=0}^{2k} \binom{m}{i} ∑_{j=0}^{min(⌈ \frac{k}{2} ⌉,2k−i)} α(k, j) ∑_{p=max(0,i−k)}^{k−j}\begin{aligned}\{ \\ \{ & {p + k − j \atop p} & \} \\ & & \} \end{aligned} ∑_{b=0}^{j} \binom{p}{b}\binom{k}{j − b}\binom{b}{k + p − i}.

The final step is to use the identity \binom{m}{i} = ∑_{d=0}^{i} \frac{(−1)^{i−d}}{i!} \left[{i \atop d}\right]m^{d} and rearrange the summation indices again, giving the result.

Remark 17. Chaiken, Hanusa, and Zaslavsky [6, section 5.4] conjectured that all quasipolynomials for the anassa have a factor of (m)_{k}. This conjecture can be proved using Equation (21) and Lemma 8:

A_{S}(m, k) = ∑_{j=0}^{⌈ \frac{k}{2} ⌉} 2^{k−2j} (\binom{k − j}{j − 1} + \binom{k − j + 1}{j}) ∑_{p=0}^{k−j}\begin{aligned}\{ \\ \{ & {p + k − j \atop p} & \} \\ & & \} \end{aligned}\frac{(m)_{p+k−j}(m − k + j)_{j}}{(p + k − j)!} .

It is straightforward to verify that (m)_{p+k−j}(m − k + j)_{j} = (m)_{k}(m − k + j)_{p} and hence

A_{S}(m, k) = (m)_{k} ∑_{j=0}^{⌈ \frac{k}{2} ⌉} 2^{k−2j} (\binom{k − j}{j − 1} + \binom{k − j + 1}{j}) ∑_{p=0}^{k−j}\begin{aligned}\{ \\ \{ & {p + k − j \atop p} & \} \\ & & \} \end{aligned}\frac{(m − k + j)_{p}}{(p + k − j)!} .

4 Conclusion

Theorem 2 provides a way to establish recurrences for the number of possible nonattacking placements of bishops and anassas on the square board. The closed-form solutions to these recurrences are the quasi-polynomials (5) and (21), for bishops and anassas, respectively. These expressions answer some of the questions raised by Chaiken, Hanusa, and Zaslavsky [6] and allow the derivation of explicit formulas for the quasi-polynomial coefficients, results proved in Theorems 10 and 16.

5 Acknowledgments

I am grateful to God Almighty, for of Him, and through Him, and to Him, are all things.

References

[1] S. E. Arshon, Reshenie odnoĭ kombinatorornoĭ zadachi, Matematicheskoe Prosveshche-

    nie 8 (1936), 24–29, https://www.mathnet.ru/eng/mp694.

[2] S. Chaiken, C. R. H. Hanusa, and T. Zaslavsky, A q-queens problem. I. General theory, Electron. J. Combin. 21 (2014), article #P3.33.

[3] S. Chaiken, C. R. H. Hanusa, and T. Zaslavsky, A q-queens problem. II. The square board, J. Algebraic Combin. 41 (2015), 619–642.

[4] S. Chaiken, C. R. H. Hanusa, and T. Zaslavsky, A q-queens problem. III. Nonattacking partial queens, Australas. J. Combin. 74 (2019), 305–331.

[5] S. Chaiken, C. R. H. Hanusa, and T. Zaslavsky. A q-queens problem. IV. Attacking configurations and their denominators, Discrete Math. 343 (2020), article 111649.

[6] S. Chaiken, C. R. H. Hanusa, and T. Zaslavsky, A q-queens problem. V. Some of our favorite pieces: Queens, bishops, rooks, and nightriders, J. Korean Math. Soc. 57 (2020), 1407–1433.

[7] S. Chaiken, C. R. H. Hanusa, and T. Zaslavsky, A q-queens problem. VI. The bishops’ period, Ars Math. Contemp. 16 (2019), 549–561.

[8] A. E. Fekete, Apropos two notes on notation, Amer. Math. Monthly 101 (1994), 771– 778.

[9] H. W. Gould and J. Quaintance, Combinatorial identities: Table I: Intermediate techniques for summing finite series. From the seven unpublished manuscripts of H. W. Gould. Edited and compiled by Jocelyn Quaintance, 2010, https://math.wvu.edu/

    ~hgould/Vol.4.PDF.

[10] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd Edition, 1994.

[11] C. R. H. Hanusa and T. Zaslavsky, A q-queens problem. VII. Combinatorial types of nonattacking chess riders, Australas. J. Combin. 77 (2020), 326–335.

[12] D. E. Knuth, Two notes on notation, Amer. Math. Monthly 99 (1992), 403–422.

[13] V. Kotěšovec, Non-Attacking Chess Pieces (Chess and Mathematics), self-published

    online book, 6th Edition, 2013, http://www.kotesovec.cz/math.htm.

[14] M. J. Kronenburg, The binomial coefficient for negative arguments, arxiv preprint arXiv:1105.3689 [math.CO], 2015. Available at https://arxiv.org/abs/1105.3689.

[15] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2024. Published electronically at https://oeis.org.

2020 Mathematics Subject Classification: Primary 05A15; Secondary 00A08. Keywords: bishop, anassa, nonattacking placement.

(Concerned with sequences \underline{A008277}, \underline{A008299}, \underline{A132393}, \underline{A134991}, \underline{A274105}, \underline{A274106}, \underline{A378561}, and \underline{A378590}.)

Received January 22 2025; revised versions received January 30 2025; April 28 2025. Published in Journal of Integer Sequences, December 15 2025.

Return to Journal of Integer Sequences home page.