|
%I #25 Oct 17 2019 18:51:45
%S 10,20,46,104,240,544,1256,2848,6576,14912,34432,78080,180288,408832,
%T 944000,2140672,4942848,11208704,25881088,58689536,135515136,
%U 307302400,709566464,1609056256,3715338240,8425127936,19453763584
%N 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 The keypad is of the form:
%C +---+---+---+
%C | 1 | 2 | 3 |
%C +---+---+---+
%C | 4 | 5 | 6 |
%C +---+---+---+
%C | 7 | 8 | 9 |
%C +---+---+---+
%C | * | 0 | # |
%C +---+---+---+
%H Derek Lim, <a href="/A327692/b327692.txt">Table of n, a(n) for n = 1..2500</a>
%F Conjectures from _Colin Barker_, Oct 01 2019: (Start)
%F G.f.: 2*x*(5 + 10*x - 7*x^2 - 8*x^3 + 2*x^4) / (1 - 6*x^2 + 4*x^4).
%F a(n) = 6*a(n-2) - 4*a(n-4) for n>6.
%F (End)
%e For n = 1 the a(1) = 10 numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
%e 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 (Python)
%o def number_dialable(N):
%o reach = ((4,6),(6,8),(7,9),(4,8),(3,9,0),(),(1,7,0),(2,6),(1,3),(2,4))
%o M = [[0] * 10 for _ in range(N)]
%o M[0] = [1]*10
%o for step in range(1,N):
%o for tile in range(10):
%o for nxt in reach[tile]:
%o M[step][nxt] += M[step-1][tile]
%o return [sum(row) for row in M]
%Y Cf. A280594, A169696.
%K nonn
%O 1,1
%A _Derek Lim_, Sep 22 2019
|
