# The number of solutions to Hertzsprung's Problem

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 .

## 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

• Can you simply print all values one by one infinitely like a sequence instead of taking a input? Apr 19 at 15:02
• @mousetail yes that's acceptable Apr 19 at 15:40
• I had this weird dream last night that I wrote a PPCG question based on a men's restroom - each man won't stand directly next to the previous man to arrive because it makes them look like they're a stalker, in which case in how many ways can n men fill n urinals?
– Neil
Apr 19 at 17:02
• The formula is incorrect. Instead of summing from i=0 to k-1, it needs to be from 1 to k-1, with an extra n! added to the whole thing in lieu of the k=0 entry (which works out to 0 as written). See the pinned comment on the Another Roof video. Apr 19 at 17:40
• @MarkReed fixed Apr 19 at 19:35

# Nekomata + -n, 6 bytes

r↕∆A1>


Attempt This Online!

Brute force. Slow for large input.

r↕∆A1>
r↕      Find a permutation of [0..n-1] such that
∆A    the absolute differences of adjacent elements
1>  are all greater than 1


The flag -n count possible solutions.

• Does Nekomata support recursion? I can't find it in docs May 4 at 6:47
• @lesobrod Not yet. May 4 at 6:58

# Jelly, 7 bytes

I almost asked this question after watching Another Roof's video.

Œ!IỊ§¬S


A monadic Link that accepts $$\n\$$ and yields the number of solutions.

Try it online!

### How?

Œ!IỊ§¬S - Link: non-negative integer, n  e.g. 4
Œ!      - all permutations (of [1..n])        [[1,2,3,4],[1,2,4,3],...,[2,4,1,3],...,[3,1,4,2],...,[4,3,2,1]]
I     - forward differences                 [[1,1,1],[1,2,-1],...,[2,-3,2],...,[-2,3,-2],...[-1,-1,-1]]
Ị    - insignificant?                      [[1,1,1],[1,0,1],...,[0,0,0],...,[0,0,0],...[1,1,1]]
§   - sums                                [3,2,...,0,...,0,...3]
¬  - logical NOT                         [0,0,...,1,...,1,...,0]
S - sum                                 2


...yes, it also works if $$\n=0\$$ (the alternative of Œ!IỊ§ċ0 would give $$\0\$$ rather than $$\1\$$).

# 05AB1E (legacy), 7 bytes

Lœ¥Ä≠PO


Port of @alephalpha's Nekomata answer, so also a slow brute-force for larger inputs.

Explanation:

L       # Push a list in the range [1, (implicit) input-integer]
œ      # Get all permutations of this list
¥     # † For each inner permutation-list: get its deltas / forward-differences
Ä    # Get the absolute value of each inner-most difference
≠   # Check for each that it's NOT 1 (so basically >= 2)
P  # Product on each inner list, to check for which all overlapping pairs are >=2
O # Take the sum, to check how many are truthy
# (after which it is output implicitly as result)


† Uses the legacy version of 05AB1E to save 1 byte, because ¥ vectorizes on a list of lists, whereas the new 05AB1E version would give an error, and would require an additional € before the ¥ to accomplish the same thing.

11005:&$:@*3[{:}]&3-:&*-4[{:}]&3-:&*-5[{:}]&2+:&*+:nao&5+40.  Try it Infinitely prints values starting at n=4. Based on the recursive formula pioneered by Arnauld but instead of recursing just keeps previous values pushed to the stack. # Desmos, 69 bytes K=n-k+1 f(n)=n!-∑_{k=2}^n(-1)^kK!∑_{a=1}^k2^anCr(K,a)nCr(k-2,a-1)  Nice. Try It On Desmos! Try It On Desmos! - Prettified # PowerShell, 125 bytes Try it online Golfed Version: function G($i){if($i -lt 4){if($i -lt 2){1}else{0}}else{($i+1)*(G($i-1))-($i-2)*(G($i-2))-($i-5)*(G($i-3))+($i-3)*(G($i-4))}}


Un-Golfed Version:

function G($i){ if($i -lt 4)
{if($i -lt 2){1} else{0} }else{ ($i+1)*(G($i-1))-($i-2)*(G($i-2))-($i-5)*(G($i-3))+($i-3)*(G($i-4)) } }  Let me know of any improvements! # Aussie++, 136 bytes Tested in commit 9522366. Loses precision for inputs >18, because all numbers are doubles. THE HARD YAKKA FOR a IS(n)<YA RECKON n <2?BAIL 1;YA RECKON n <4?BAIL 0;BAIL(n +1)*a(n -1)-(n -2)*a(n -2)-(n -5)*a(n -3)+(n -3)*a(n -4);>  Aussie++ requires every identifier to be followed by whitespace, a semicolon, a comma, or a paren, so I can't remove the spaces before all the operators. It also doesn't have bitwise operators, and the equivalent to -- is PULL YA HEAD IN, so I can't take the same shortcuts as the JS and C answers. Example test code: G'DAY MATE! THE HARD YAKKA FOR a IS(n)<YA RECKON n <2?BAIL 1;YA RECKON n <4?BAIL 0;BAIL(n +1)*a(n -1)-(n -2)*a(n -2)-(n -5)*a(n -3)+(n -3)*a(n -4);> I RECKON i IS A WALKABOUT FROM [0 TO 18] < GIMME "" + i + ": " + a(i); > CHEERS C***!  # VyxalRl, 36 bits1, 4.5 bytes Ṗ'¯ȧċA  Try it Online! (link is to bitstring) Port of Kevin Cruijssen's 05AB1E answer, which is in turn a port of alephalpha's Nekomata answer. Like those, it is a brute force solution, suffering with the same slowdown on larger inputs. Ṗ # permutations of the range 1..n (due to the R flag) ' # filtered by ¯ȧ # absolute value of the deltas A # are all ċ # not 1 # the length of this filtered list is taken by the l flag # and implicitly output  # PARI/GP, 51 bytes n->Vec(sum(i=0,n,i!*(x*(1-x)/(1+x))^i)+O(x^n++))[n]  Attempt This Online! Based on the generating funtion on the OEIS page. # JavaScript (ES6), 56 bytes Based on the recurrence formula provided on OEIS. f=n=>n<4?n/2^1:-~n--*f(n--)-n*f(n)-(n-3)*f(--n)+n*f(n-1)  Try it online! ### With Bigints, 58 bytes f=n=>n<4?n/2n^1n:-~n--*f(n--)-n*f(n--)-~-~-n*f(n)+n--*f(n)  Try it online! # C (gcc), 60 58 bytes f(n){n=n<4?n<2:-~n--*f(n--)-n*f(n)-(n-3)*f(--n)+n*f(n-1);}  Try it online! Port of Arnauld's JavaScipt answer. Saved 2 bytes thanks to Arnauld • In C, you can just use n<2 instead of n/2^1. (I could do that in JS as well, but that would output Boolean values, which is a bit weird.) Apr 19 at 15:55 • @Arnauld One certainly can - thanks! :D Apr 19 at 16:50 # Raku, 132 bytes Translated the (corrected) formula directly; not particularly golfed, just crunched out all the unnecessary whitespace: ->\n{[*](1..n)+[+]((1..n-1).map: ->\k{(-1)**k*[*](1..n -k)*[+]((1..k).map: ->\r{2**r*combinations(n -k,r)*combinations(k-1,r-1)})})}  Try it online! # Charcoal, 34 bytes Ｆ⁴⊞υ‹ι²ＦＮ⊞υΣ×⮌υ⟦⁺⁵ι±⁺²ι⁻¹ι⊕ι⟧Ｉ§υ±⁴  Attempt This Online! Link is to verbose version of code. Outputs the nth element. Explanation: Ｆ⁴⊞υ‹ι²  Start with the first four values (0-indexed, so 1, 1, 0, 0). ＦＮ⊞υΣ×⮌υ⟦⁺⁵ι±⁺²ι⁻¹ι⊕ι⟧  Use the recurrence relation to calculate n more values. Ｉ§υ±⁴  Output the 4th last value. # Japt-x, 10 bytes õ á Ëäa eÉ  Try it # Scala, 97 bytes Based on the recurrence formula provided by A002464. Golfed version. Try it online! def f(n:Int):Int=if(n<4){if(n<2)1 else 0}else (n+1)*f(n-1)-(n-2)*f(n-2)-(n-5)*f(n-3)+(n-3)*f(n-4)  Ungolfed version. object Main { def f(n: Int): Int = { if (n < 4) { if (n < 2) 1 else 0 } else { (n + 1)*f(n-1) - (n - 2) *f(n-2) - (n - 5) *f(n - 3) + (n - 3)* f(n - 4) } } def main(args: Array[String]): Unit = { val tests = Array(1, 2, 3, 4, 5, 6) val expected = Array(1, 0, 0, 2, 14, 90) val checker = Array("✕", "✓") for (index <- tests.indices) { val t = tests(index) val s = f(t) val e = expected(index) println(s"$t -> $s${checker(if (s == e) 1 else 0)}")
}
}
}