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.

10, 20, 46, 104, 240, 544, 1256, 2848, 6576, 14912, 34432, 78080, 180288, 408832, 944000, 2140672, 4942848, 11208704, 25881088, 58689536, 135515136, 307302400, 709566464, 1609056256, 3715338240, 8425127936, 19453763584

Offset

1,1

Comments

The keypad is of the form:

+---+---+---+

| 1 | 2 | 3 |

+---+---+---+

| 4 | 5 | 6 |

+---+---+---+

| 7 | 8 | 9 |

+---+---+---+

| * | 0 | # |

+---+---+---+

Links

Derek Lim, Table of n, a(n) for n = 1..2500

Formula

Conjectures from Colin Barker, Oct 01 2019: (Start)

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

a(n) = 6*a(n-2) - 4*a(n-4) for n>6. (End)

Comments from Francesca Arici, Apr 17 2024: (Start)

The recursive formula a(n) = 6*a(n-2) - 4*a(n-4) also holds for n=6.

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.

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)

Example

For n = 1 the a(1) = 10 numbers are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
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.

Prog

(Python)
def number_dialable(N):
    reach = ((4, 6), (6, 8), (7, 9), (4, 8), (3, 9, 0), (), (1, 7, 0), (2, 6), (1, 3), (2, 4))
    M = [[0] * 10 for _ in range(N)]
    M[0] = [1]*10
    for step in range(1, N):
        for tile in range(10):
            for nxt in reach[tile]:
                M[step][nxt] += M[step-1][tile]
    return [sum(row) for row in M]

Crossrefs

Cf. A280594, A169696.

Sequence in context: A048063 A007927 A284991 * A269234 A160517 A072081

Adjacent sequences: A327689 A327690 A327691 * A327693 A327694 A327695

Keyword

nonn,changed

Author

Derek Lim, Sep 22 2019

Status

approved