A140518 Number of simple paths from corner to corner of an n X n grid with king-moves allowed.

1, 5, 235, 96371, 447544629, 22132498074021, 10621309947362277575, 50819542770311581606906543, 2460791237088492025876789478191411, 1207644919895971862319430895789323709778193, 5996262208084349429209429097224046573095272337986011

Offset: 1

Author

Don Knuth, Jul 26 2008

Keywords

• nonn
• walk

Comments

This graph is the "strong product" of P_n with P_n, where P_n is a path of length n. Sequence A007764 is what we get when we restrict ourselves to rook moves of unit length.

Computed using ZDDs (ZDD = "reduced, order, zero-suppressed binary decision diagram").

Examples

			For example, when n=8 this is the number of ways to move a king from a1 to h8 without occupying any cell twice.
		

References

• Donald E. Knuth, The Art of Computer Programming, Vol. 4, fascicle 1, section 7.1.4, p. 117, Addison-Wesley, 2009.

Links

• Jens Weise, Evolutionary Many-Objective Optimisation for Pathfinding Problems, Ph. D. Dissertation, Otto von Guercke Univ., Magdeburg (Germany, 2022), see p. 53.

Crossrefs

Main diagonal of A329118.

Cf. A140519, A158651, A234622, A007764, A038496.

Cf. A220638 (Hosoya index).

Extensions

a(9)-a(11) from Andrew Howroyd, Apr 07 2016