Combinatorics, Algorithm, and Humanity

By Xah Lee. Date:
『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！

a lovely story on combinatorics problem, algorithm, and humanity.

  1. 1
  2. 2
  3. 12
  4. 184
  5. 8512
  6. 1262816
  7. 575780564
  8. 789360053252
  9. 3266598486981642
  10. 41044208702632496804
  11. 1568758030464750013214100
  12. 182413291514248049241470885236
  13. 64528039343270018963357185158482118
  14. 69450664761521361664274701548907358996488

the sequence is “Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid.” , sequence id A007764, see https://oeis.org/A007764

there isn't a closed form formula know so far. We have counted up to f[26].

This problem, seems to be spurred by a computer game named The Witness.

The Witness: Giant Bomb Quick Look

Buy at amazon

[ The Witness (2016 video game) ] [ 2016-03-09 https://en.wikipedia.org/wiki/The_Witness_%282016_video_game%29 ]