A086349 On a 3 X 3 board, the number of n-move paths for a chess king.

1, 9, 40, 200, 952, 4624, 22272, 107648, 519552, 2509056, 12113920, 58492928, 282425344, 1363677184, 6584401920, 31792332800, 153506906112, 741197021184, 3578815578112, 17280050659328, 83435464425472

Offset: 0

Author

Zak Seidov, Jul 17 2003

Keywords

• easy
• nonn
• changed

Examples

			a(1)=9 because there are 9 cells in the 3 X 3 board;
a(2)=40 because from each of 4 corner cells, king can move to 3 cells, this gives 4*3=12 moves, from each of 4 side cells, king can move to 5 cells, this gives 4*5=20 moves and from the central cell, king can move to 8 cells, this gives 8 moves and the total is 12+20+8=40.
		

Links

• Mike Oakes, KingMovesForPrimes.
• Zak Seidov, KingMovesForPrimes.
• Zak Seidov et al., New puzzle? King moves for primes, digest of 28 messages in primenumbers group, Jul 13 - Jul 23, 2003. [Cached copy]
• Sleephound, KingMovesForPrimes.

Crossrefs

Cf. A086346, A086347, A086348.

Formula

a(n) = 4*A086346(n) + 4*A086347(n) + A086349(n).

a(n) = 2*a(n-1)+12*a(n-2)+8*a(n-3) for n>3. G.f.: (1+x)*(1+6*x+4*x^2)/((1+2*x)*(1-4*x-4*x^2)). - Colin Barker, Apr 12 2012

Extensions

Edited by Johannes W. Meijer, Jul 15 2010