A378590 Total number of ways to place k nonattacking bishops on an n X n chess board. Triangle T(n,k) read by rows (0 <= k <= 2*n-[n>0]-[n>1]).

1, 1, 1, 1, 4, 4, 1, 9, 26, 26, 8, 1, 16, 92, 232, 260, 112, 16, 1, 25, 240, 1124, 2728, 3368, 1960, 440, 32, 1, 36, 520, 3896, 16428, 39680, 53744, 38368, 12944, 1600, 64, 1, 49, 994, 10894, 70792, 282248, 692320, 1022320, 867328, 389312, 81184, 5792, 128

Offset

0,5

Comments

The sequence counts every possible nonattacking configuration of k bishops on an n x n chess board.

Links

Table of n, a(n) for n=0..50.

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(6): 1407-1433, 2020; see also arXiv preprint, arXiv:1609.00853 [math.CO], 2016-2020.

Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 234-259.

Eder G. Santos, Counting non-attacking chess pieces placements: Bishops and Anassas, arXiv:2411.16492 [math.CO], 2024.

Formula

T(n,k) = Sum_{j=0..k} (Sum_{i=0..j} binomial(floor(n/2),i) * Stirling2(n-i,n-j)) * (Sum_{l=0..k-j} binomial(ceiling(n/2),l) * Stirling2(n-l,n-k+j)).

T(n,2*n-2+delta(n,1)+2*delta(n,0)) = A000079(n)-delta(n,1).

Example

Triangle begins:
  1;
  1  1;
  1  4   4;
  1  9  26    26     8;
  1 16  92   232   260    112     16;
  1 25 240  1124  2728   3368   1960     440     32;
  1 36 520  3896 16428  39680  53744   38368  12944   1600    64;
  1 49 994 10894 70792 282248 692320 1022320 867328 389312 81184 5792 128;
  ...
For example, for n = 2, k=2, the T(2,2)=4 nonattacking configurations are:
  +---+---+   +---+---+   +---+---+   +---+---+
  | B | B |   | B |   |   |   | B |   |   |   |
  +---+---+ , +---+---+ , +---+---+ , +---+---+
  |   |   |   | B |   |   |   | B |   | B | B |
  +---+---+   +---+---+   +---+---+   +---+---+

Prog

(SageMath) def stirling2_negativek(n, k):
  if k < 0: return 0
  else: return stirling_number2(n, k)
print([sum([sum([binomial(floor(n/2), i)*stirling2_negativek(n-i, n-j)*sum([binomial(ceil(n/2), l)*stirling2_negativek(n-l, n-k+j) for l in [0..k-j]]) for i in [0..j]]) for j in [0..k]]) for n in [0..10] for k in [0..2*n-2+kronecker_delta(n, 1)+2*kronecker_delta(n, 0)]])

Crossrefs

Columns k=0-1 give: A000012, A000290.

Columns k=2-10 for n>=1 give: A172123, A172124, A172127, A172129, A176886, A187239, A187240, A187241, A187242.

Main diagonal T(n,n) gives A002465.

Row sums give A201862.

Cf. A000079.

Sequence in context: A080721 A123588 A373504 * A289710 A243594 A360707

Adjacent sequences: A378587 A378588 A378589 * A378591 A378592 A378593

Keyword

nonn,easy,tabf

Author

Eder G. Santos, Dec 01 2024

Status

approved