bibkey: barker2019a327692 authors: Colin Barker year: 2019 title: “OEIS 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” doi: null url: https://oeis.org/A327692 claim: “Conjectures from Colin Barker, Oct 01 2019: (Start) G.f.: 2x(5 + 10x - 7x^2 - 8x^3 + 2x^4) / (1 - 6x^2 + 4x^4). a(n) = 6a(n-2) - 4a(n-4) for n>6. (End)” strata_touched:

• D5/S3/Combinatorics/KnightDiallerRecurrence license: citation-only triage: anchor

OEIS A327692

The entry counts the digit sequences of length n that a chess knight can dial on the keypad

1 2 3
4 5 6
7 8 9
* 0 #

starting anywhere and taking n - 1 knight steps, the blank cells * and # not being dialable. Its terms begin 10, 20, 46, 104, 240, 544, 1256, 2848, 6576, 14912, ….

Verified locator

• URL: https://oeis.org/A327692
• Locator: FORMULA, “Conjectures from Colin Barker, Oct 01 2019: (Start) G.f.: 2x(5 + 10x - 7x^2 - 8x^3 + 2x^4) / (1 - 6x^2 + 4x^4). a(n) = 6a(n-2) - 4a(n-4) for n>6. (End)”
• Revision read: #41, Apr 22 2024. The formula line still carries the word Conjectures and records no proof.

Reading of the statement

The recurrence asserted is a(n) = 6*a(n-2) - 4*a(n-4), for n > 6 in Barker’s own range. A later comment by Francesca Arici, dated Apr 17 2024, adds that the recurrence also holds at n = 6, and sketches a route: the count is the grand sum of a power of the adjacency matrix, that matrix is diagonalisable over the reals with one zero eigenvalue, and the assertion then “reduces to checking an algebraic condition on the nonzero eigenvalues”. The sketch stops there; the algebraic condition is not checked and the entry was not reclassified.

Natural subtraction would silently change the statement, so the recorded form is additive: writing dial n for the count of sequences with n knight steps, so that dial n is the entry’s a(n+1), the assertion is

dial (n+5) + 4 * dial (n+1) = 6 * dial (n+3)   for every n.

That is exactly a(m) = 6*a(m-2) - 4*a(m-4) for every m >= 6, which is Barker’s conjecture together with the extension to m = 6 that Arici reports.

Scope of the recorded answer

The assertion holds for every n, and the reason is a single dead key.

Let u n be the vector whose entry at digit d is the number of dialable sequences of n steps starting at d, so u 0 is all ones, u (n+1) is the knight transfer step applied to u n, and dial n is the sum of the entries of u n. The transfer step is linear, so it carries the identity forward: if u (n+5) + 4 * u (n+1) = 6 * u (n+3) holds entrywise at one place, it holds at the next.

The base case is an evaluation. In matrix language the residual of the recurrence applied to the all-ones vector is not zero,

(A^4 - 6A^2 + 4I) · 1 = (0,0,0,0,0,4,0,0,0,0),

the whole residual sitting on the digit 5; one further step kills it, because 5 is the one key a knight can never leave, both of its knight images being the blank cells. Concretely

u 1 = (2,2,2,2,3,0,3,2,2,2)
u 3 = (12,10,10,10,16,0,16,10,10,10)
u 5 = (64,52,52,52,84,0,84,52,52,52)

and u 5 + 4 * u 1 = (72,60,60,60,96,0,96,60,60,60) = 6 * u 3.

The same reading explains the exponent bookkeeping exactly. Summing the residual over all starting digits gives 4 at m = 5, so the recurrence fails there: a(5) + 4*a(1) = 280 against 6*a(3) = 276. It first holds at m = 6, which is the range the entry’s later comment reports.

No eigenvalues, no diagonalisability and no real spectrum enter, so the route is shorter than the one the entry sketches.

Bounded prior-resolution evidence

The entry was read in full at revision #41 and records no proof: the formula line still says Conjectures, and the later comment ends at a reduction. Its cross-references A280594 and A169696 carry no proof of this recurrence. Searches for a published proof return knight-dialler programming material, which counts paths from a fixed start rather than the grand sum and does not address the closed recurrence. Citation indices were not exhaustively reachable, so this is a bounded negative finding and no worldwide priority claim is made.