cp's OEIS Frontend

A327692 Number of length-n phone numbers that can be dialed by a chess knight on a 0-9 keypad that starts on any number and takes n-1 steps.

%I A327692 #41 Apr 22 2024 12:04:39
%S A327692 10,20,46,104,240,544,1256,2848,6576,14912,34432,78080,180288,408832,
%T A327692 944000,2140672,4942848,11208704,25881088,58689536,135515136,
%U A327692 307302400,709566464,1609056256,3715338240,8425127936,19453763584
%N A327692 Number of length-n phone numbers that can be dialed by a chess knight on a 0-9 keypad that starts on any number and takes n-1 steps.
%C A327692 The keypad is of the form:
%C A327692 +---+---+---+
%C A327692 | 1 | 2 | 3 |
%C A327692 +---+---+---+
%C A327692 | 4 | 5 | 6 |
%C A327692 +---+---+---+
%C A327692 | 7 | 8 | 9 |
%C A327692 +---+---+---+
%C A327692 | * | 0 | # |
%C A327692 +---+---+---+
%H A327692 Derek Lim, <a href="/A327692/b327692.txt">Table of n, a(n) for n = 1..2500</a>
%F A327692 Conjectures from _Colin Barker_, Oct 01 2019: (Start)
%F A327692 G.f.: 2*x*(5 + 10*x - 7*x^2 - 8*x^3 + 2*x^4) / (1 - 6*x^2 + 4*x^4).
%F A327692 a(n) = 6*a(n-2) - 4*a(n-4) for n>6. (End)
%F A327692 Comments from _Francesca Arici_, Apr 17 2024: (Start)
%F A327692 The recursive formula a(n) = 6*a(n-2) - 4*a(n-4) also holds for n=6.
%F A327692 It can be proved using results from graph theory. Indeed, if we consider the directed graph associated to the knight dialler problem, then a(n) equals the number of paths in the graph of length n-1 in the graph. This number can be expressed in terms of the grand sum of powers of the incidence matrix A(i,j) of the graph.
%F A327692 Moreover, the matrix A is diagonalizable over the reals, with one zero eigenvalue, say L(0)=0. Combining this with the formula for the grand sum of a diagonalizable matrix in term of its eigenvalues, the above conjecture reduces to checking an algebraic condition on the nonzero eigenvalues L(1), ..., L(8) of A. (End)
%e A327692 For n = 1 the a(1) = 10 numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
%e A327692 For n = 2 the a(2) = 20 numbers are 04, 06, 16, 18, 27, 29, 34, 38, 43, 49, 40, 61, 67, 60, 72, 76, 81, 83, 92, 94.
%o A327692 (Python)
%o A327692 def number_dialable(N):
%o A327692     reach = ((4,6),(6,8),(7,9),(4,8),(3,9,0),(),(1,7,0),(2,6),(1,3),(2,4))
%o A327692     M = [[0] * 10 for _ in range(N)]
%o A327692     M[0] = [1]*10
%o A327692     for step in range(1,N):
%o A327692         for tile in range(10):
%o A327692             for nxt in reach[tile]:
%o A327692                 M[step][nxt] += M[step-1][tile]
%o A327692     return [sum(row) for row in M]
%Y A327692 Cf. A280594, A169696.
%K A327692 nonn
%O A327692 1,1
%A A327692 _Derek Lim_, Sep 22 2019