A169696 -id:A169696 - cp's OEIS frontend

A169774 Number of open knight's tour diagrams of a 3 X n chessboard that are symmetric under 180-degree rotation and have "type F": the endpoints occur in different columns and agree in color with the cells in the nearest corner.

2, 0, 0, 4, 12, 20, 28, 120, 104, 304, 384, 1304, 1680, 4936, 5908, 18304, 21412, 63440, 76920, 233248, 281284, 833720, 990104, 2993016, 3523740, 10485472, 12432392, 37485424, 44184884, 131430320, 154630088, 465106072, 544994604, 1622783328, 1904647128

Offset: 4

N. J. A. Sloane, May 10 2010, based on a communication from Don Knuth, Apr 28 2010

nonn

D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, to appear, 2010.

George Jelliss, Open knight's tours of three-rank boards, Knight's Tour Notes, note 3a (21 October 2000).
George Jelliss, Closed knight's tours of three-rank boards, Knight's Tour Notes, note 3b (21 October 2000).
D. E. Knuth Generating functions for A169770-A169777 and A169696.

Cf. A070030, A169696, A169764-A169777.

a(31)-a(38) from Andrew Howroyd, Jul 01 2017

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.

Original entry on oeis.org

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

Derek Lim, Sep 22 2019

nonn

The keypad is of the form:
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 7 | 8 | 9 |
+---+---+---+
| * | 0 | # |
+---+---+---+

			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.

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

Cf. A280594, A169696.

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]

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)

A347363 Number of self-avoiding knight's paths from the lower left corner to the lower right corner of a 3 X n chessboard.

Original entry on oeis.org

1, 0, 2, 8, 32, 156, 871, 5292, 28702, 154162, 845532, 4662014, 25579463, 140098348, 767973001, 4212065280, 23097682805, 126643657272, 694390484065, 3807499106946, 20877386149018, 114474503105178, 627683328355315, 3441701959286326, 18871492466212538

Offset: 1

Andrzej Kukla, Aug 29 2021

If we enumerate the squares in the 3 X n board like this:
------------------------------------
| 1 | 4 | 7 | 10 | 13 | ... | 3n-2 |
------------------------------------
| 2 | 5 | 8 | 11 | 14 | ... | 3n-1 |
------------------------------------
| 3 | 6 | 9 | 12 | 15 | ... |  3n  |
------------------------------------
then a(n) is the number of self-avoiding knight's paths on such a board from square 3 to square 3n.

			For n = 4 we have exactly 8 self-avoiding paths starting at square 3 and ending at square 12:
  3,  4,  9, 10,  5, 12;
  3,  4,  9,  2,  7, 12;
  3,  8,  1,  6,  7, 12;
  3,  4, 11,  6,  7, 12;
  3,  8,  1,  6, 11,  4,  9,  2,  7, 12;
  3,  4, 11,  6,  7,  2,  9, 10,  5, 12;
  3,  8,  1,  6,  7,  2,  9, 10,  5, 12;
  3,  8,  1,  6, 11,  4,  9, 10,  5, 12;

Cf. A118067, A169696, A212715.

a(8)-a(15) from Pontus von Brömssen, Aug 30 2021

Terms a(16) and beyond from Andrew Howroyd, Nov 19 2021

cp's OEIS Frontend

A169774 Number of open knight's tour diagrams of a 3 X n chessboard that are symmetric under 180-degree rotation and have "type F": the endpoints occur in different columns and agree in color with the cells in the nearest corner.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A347363 Number of self-avoiding knight's paths from the lower left corner to the lower right corner of a 3 X n chessboard.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions