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,2

Comments

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

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).

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

Example

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}}.

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 *)

Prog

(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
(PARI) a(n)=7*n^2 + 4*n - 3 + 4*sign((n-2)*(n-1)) \\ Charles R Greathouse IV, Feb 09 2017

Crossrefs

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

Sequence in context: A107291 A044466 A022274 * A212679 A204468 A140867

Adjacent sequences: A118309 A118310 A118311 * A118313 A118314 A118315

Keyword

easy,nice,nonn

Author

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

Extensions

Link updated by Tristan Miller, Jun 13 2013

Status

approved