A390419 Triangle read by rows: T(n,k) is the number of ways to place k non-attacking kings in each row of an n X n board, 0 <= k <= floor((n+1)/4) + [n=1].

1, 1, 1, 1, 2, 1, 16, 1, 184, 1, 2642, 1, 45514, 6, 1, 911642, 1550, 1, 20793594, 988556, 1, 531713286, 587256692, 1, 15059408170, 380941109984, 20, 1, 467843350146, 269426066012742, 263928, 1, 15815643320036, 209984659485901510, 22868187338, 1, 577912024460656, 181134684682770775026, 1034937133971366

Offset

1,5

Comments

The value T(n,k) is an upper bound for A387098(n,k).

The terms are computed via matrix exponentiation. Let S be the set of all valid single-row configurations of k kings on n cells. Let M be the |S| X |S| transition matrix where m_ij = 1 if row configuration j can follow row i. Then T(n,k) is the sum of all entries in M^(n-1).

Links

Sean A. Irvine, Table of n, a(n) for n = 1..199 (rows 1..36 flattened, terms 1..142 from Hamidreza Maleki Tirabadi)

Sean A. Irvine, Java program (github)

Hamidreza Maleki Tirabadi, Kings_Problem_UpperBound_Counter go program.

Formula

T(n,k) = Sum(M^(n-1) * v_1) where v_1 is the all-ones vector of size |S| and M is defined in the comments.

Example

Triangle begins:
  1,            1;
  1;
  1,            2;
  1,           16;
  1,          184;
  1,         2642;
  1,        45514,               6;
  1,       911642,            1550;
  1,     20793594,          988556;
  1,    531713286,       587256692;
  1,  15059408170,    380941109984,     20;
  1, 467843350146, 269426066012742, 263928;
  ...

Prog

(Go) // See Links.

Crossrefs

Columns k=0..7 are A000012, A388004, A389665, A390736, A390782, A390920, A390985, A390984.

Cf. A387098.

Sequence in context: A184232 A074952 A078074 * A016447 A095850 A324610

Adjacent sequences: A390416 A390417 A390418 * A390420 A390421 A390422

Keyword

nonn,tabf

Author

Hamidreza Maleki Tirabadi, Nov 05 2025

Status

approved