Hertzprung's Problem (OEIS A002464) is the number of solutions to a variant of the Eight Queens Puzzle, where instead of placing \$n\$ queens, you place \$n\$ rook-king fairy pieces (can attack like both a rook and a king); in other words, it's how many possible positions you can place \$n\$ rook-kings on an \$n \times n\$ board such that each piece does not occupy a neighboring square (both vertically, horizontally, and diagonally).
Challenge
Write the shortest function or full program that will output the number of solutions to Hertzprung's Problem.
You may either:
- output just \$\operatorname{A002464}(n)\$, given a positive integer \$n > 0\$, or
- output all terms of \$\operatorname{A002464}(k) \text{ where } 0 < k < \infty\$ as a sequence.
Notes
- A formula is derived in this video: $$ \operatorname{A002464}(n) = n! + \sum_{k=1}^{n-1} (-1)^k(n-k)!\sum_{r=1}^k 2^r \binom{n-k}{r} \binom{k-1}{r-1} $$
Test Cases
1: 1
2: 0
3: 0
4: 2
5: 14
6: 90
23: 3484423186862152966838
n
men filln
urinals? \$\endgroup\$