A118312 Number of squares on infinite chessboard that a knight can reach in n moves from a fixed square.

1, 8, 33, 76, 129, 196, 277, 372, 481, 604, 741, 892, 1057, 1236, 1429, 1636, 1857, 2092, 2341, 2604, 2881, 3172, 3477, 3796, 4129, 4476, 4837, 5212, 5601, 6004, 6421, 6852, 7297, 7756, 8229, 8716, 9217, 9732, 10261, 10804, 11361, 11932, 12517, 13116, 13729, 14356, 14997, 15652

Offset: 0

Author

Anton Chupin (chupin(AT)icmm.ru), May 14 2006

Keywords

• easy
• nice
• nonn

Comments

Related to A018842: a(n) = A018842(n) + A018842(n-2) + A018842(n-4) + ... .

Examples

			a(2)=33 because knight in 2 moves from square (0,0) can reach one of the following squares: {{0,0}, {-4,-2}, {-4,0}, {-4,2}, {-3,-3}, {-3,-1}, {-3,1}, {-3,3}, {-2,-4}, {-2,0}, {-2,4}, {-1,-3}, {-1,-1}, {-1,1}, {-1,3}, {0,-4}, {0,-2}, {0,2}, {0,4}, {1,-3}, {1,-1}, {1,1}, {1,3}, {2,-4}, {2,0}, {2,4}, {3,-3}, {3,-1}, {3,1}, {3,3}, {4,-2}, {4,0}, {4,2}}.
		

References

• M. Petkovic, Mathematics and Chess, Dover Publications (2003), Problem 3.11.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Mordechai Katzman, Knight's moves on an infinite board
• Mordechai Katzman, Counting monomials, arXiv:math/0504113 [math.AC], 2005.
• Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Crossrefs

Cf. A005892, A018842 (squares in EXACTLY n moves), A018836 (squares in <=n moves).

Programs

Magma

I:=[1, 8, 33, 76, 129, 196, 277]; [n le 7 select I[n] else 3*Self(n-1)-3*Self(n-2)+Self(n-3): n in [1..50]]; // Vincenzo Librandi, Jul 09 2012

Mathematica

Table[ -3 + 4*n + 7*n^2 + 4*Sign[(n - 2)(n - 1)], {n, 0, 100}]
CoefficientList[Series[(1+5*x+12*x^2-8*x^4+4*x^5)/(1-x)^3,{x,0,50}],x] (* Vincenzo Librandi, Jul 09 2012 *)
Join[{1,8,33},LinearRecurrence[{3,-3,1},{76,129,196},50]] (* Harvey P. Dale, Dec 05 2014 *)

PARI

a(n)=7*n^2 + 4*n - 3 + 4*sign((n-2)*(n-1)) \\ Charles R Greathouse IV, Feb 09 2017

Formula

a(n) = -3 + 4*n + 7*n^2 + 4*sign((n-2)*(n-1)).

G.f.: (1 + 5*x + 12*x^2 - 8*x^4 + 4*x^5)/(1 - x)^3.

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3). - Vincenzo Librandi, Jul 09 2012

For n >= 3, a(n) = A005892(n).

E.g.f.: exp(x)*(1 + 11*x + 7*x^2) - 2*x*(x + 2). - Stefano Spezia, Jul 27 2022

Extensions

Link updated by Tristan Miller, Jun 13 2013