A389766 Number of ways to place 2 non-attacking kings in each row and column of an n X n board.

2, 664, 146510, 31197434, 6798881226, 1567979086356, 390673279156006, 106280659533411296, 31714093249071901942

Offset

8,1

Comments

This sequence is part of a family of sequences for k kings per row and column. This entry corresponds to the k=2 case.

A significant empirical discovery is a structural law for this family of problems: for a given k, the first nonzero term appears at n = 4k, where a(4k) = 2. This has been computationally verified for k from 1 to 100.

This problem is a generalization of Hertzsprung's problem (A002464), which corresponds to the k=1 case.

Links

Table of n, a(n) for n=8..16.

Sean A. Irvine, Java program (github)

Hamidreza Maleki Tirabadi, Go program for enumeration

Formula

The number of valid single-row configurations for n cells and k=2 kings is given by binomial(n-1, 2).

No simple recurrence is currently known.

Example

a(8) = 2. This is the first nonzero term for k=2, occurring at n = 4k = 8. The two solutions are highly structured and symmetric.
One of the two configurations can be represented in ASCII form as follows, where '*' marks the positions of kings:
  Row 1: [1 3]  ->  . * . * . . . .
  Row 2: [5 7]  ->  . . . . . * . *
  Row 3: [1 3]  ->  . * . * . . . .
  Row 4: [5 7]  ->  . . . . . * . *
  Row 5: [0 2]  ->  * . * . . . . .
  Row 6: [4 6]  ->  . . . . * . * .
  Row 7: [0 2]  ->  * . * . . . . .
  Row 8: [4 6]  ->  . . . . * . * .
Each row contains exactly two kings, and each column contains exactly two kings, with no two kings touching, even diagonally.

Prog

(Go) // See Links.

Crossrefs

Column k=2 of A387098.

Cf. A002464 (the k=1 case).

Cf. A061995.

Sequence in context: A046856 A156938 A285221 * A079195 A120123 A140014

Adjacent sequences: A389763 A389764 A389765 * A389767 A389768 A389769

Keyword

nonn,more

Author

Hamidreza Maleki Tirabadi, Oct 14 2025

Extensions

a(16) from Sean A. Irvine, Oct 30 2025

Status

approved