A140518 -id:A140518 - cp's OEIS frontend

A329118 Array read by antidiagonals: T(m, n) is the number of simple paths from corner to diagonally opposite corner on an m X n grid with king moves allowed.

1, 1, 1, 1, 5, 1, 1, 24, 24, 1, 1, 116, 235, 116, 1, 1, 560, 2922, 2922, 560, 1, 1, 2704, 38169, 96371, 38169, 2704, 1, 1, 13056, 494596, 3764367, 3764367, 494596, 13056, 1, 1, 63040, 6375379, 150610151, 447544629, 150610151, 6375379, 63040, 1, 1, 304384, 82191766, 5898799685, 56182569218, 56182569218, 5898799685, 82191766, 304384, 1

Offset: 1

Andrew Howroyd, Nov 05 2019

			Array begins:
===================================================================
m\n | 1     2       3          4             5                6
----+--------------------------------------------------------------
  1 | 1     1       1          1             1                1 ...
  2 | 1     5      24        116           560             2704 ...
  3 | 1    24     235       2922         38169           494596 ...
  4 | 1   116    2922      96371       3764367        150610151 ...
  5 | 1   560   38169    3764367     447544629      56182569218 ...
  6 | 1  2704  494596  150610151   56182569218   22132498074021 ...
  7 | 1 13056 6375379 5898799685 6972159602221 8656506756327178 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..231

Rows 2..6 are A086347, A193168, A193170, A193171, A193172.
Main diagonal is A140518.
Cf. A158651, A272445, A288033.

A272445 Numbers of paths for moving a king from a corner to the opposite one in an n X n chessboard, provided that each cell must be reached exactly once.

Original entry on oeis.org

1, 2, 30, 4942, 5853876, 58039036412, 4458135334234700, 2811002302704446996926, 14204916761279146343474398608, 580077332863329104087361516015280826, 190934226579364879405564404836420471442186330, 507088717315287736410992294230305692212344811974323748

Offset: 1

César Eliud Lozada, Apr 29 2016

			On a 2 X 2 chessboard, the king has 2 paths to go from a corner to the opposite one, standing exactly one time on each cell, so a(2)=2.
On a 3 X 3 chessboard, the king has 30 paths to go from a corner to the opposite one, standing exactly one time on each cell, so a(3)=30.

César Eliud Lozada, Chess king paths
Eric Weisstein's World of Mathematics, King Graph

Cf. A001184, A158651, A140518, A288033.

ChessKingPaths := proc(N, aUsed:=[1])
  local nLast, nPrev,  nNext,  i, j, i1, j1, i2, j2:
  global aPath, nPaths;
if N=1 then
  aPath:=[[1]]; nPaths:=1; return nPaths;
end if:
  if aUsed=[1] then
    aPath:=[]; nPaths:=0;
  end if;
  nLast:=N^(2);   #`opposite corner`
  nPrev := aUsed[-1] ; #actual position
  #Check all possible next cells
  i1:=`if`(floor((nPrev-1)/N)=0,0,-N); i2:=`if`(floor((nPrev-1)/N)=N-1,0,N);
  j1:=`if`((nPrev-1)mod N=0,0,-1); j2:=`if`((nPrev-1) mod N=N-1,0,1);
  for i from i1 to i2 by N do
    for j from j1 to j2 by 1 do
      if i=0 and j=0 then next fi; #`no move`
      nNext:=nPrev+i+j;
      #`out of bounds or already visited`
      if nNext<1 or nNext>nLast or (nNext in aUsed) then next: fi;
      #`nLast must be the last one`
      if (nNext=nLast and nops(aUsed)<>nLast-1) then next fi:
      if nNext=nLast  and nops(aUsed)=nLast-1 then  #`path completed`
        #comment if list is not required. It will consume all memory for N>=5
        aPath:=[op(aPath), [op(aUsed),nNext]];
        nPaths:=nPaths+1;
        break:
      else
        ChessKingPaths(N,[op(aUsed),nNext]) #move and continue
      end if;
    end do:
  end do:
  return nPaths;
end proc:
#For a(n) call this function with parameter n.
#Examples: ChessKingPaths(2), ChessKingPaths(3),...
#The list of paths is stored in variable aPath.

a(5)-a(11) from Andrew Howroyd, Jun 19 2017

a(12) from Ed Wynn, Jul 08 2023

A308129 Number of (undirected) Hamiltonian paths on the n X n king graph.

Original entry on oeis.org

1, 12, 392, 171592, 364618672, 6544911081900, 829555065360355292, 817534730458899350635436, 6154392250018061759082363305112, 360916610325065945171647827293872547848, 165298493343313203241690299664254975948394404072

Offset: 1

Eric W. Weisstein, May 14 2019

Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, King Graph

Main diagonal of A350729.

Cf. A140518, A158651, A272445, A288033.

a(n) = A158651(n)/2 for n > 1.

a(1) corrected by Andrew Howroyd, Jan 16 2022

A212715 Number of nonintersecting (or self-avoiding) knight paths joining opposite corners of an n X n grid.

Original entry on oeis.org

1, 0, 2, 138, 88920, 752404294

Offset: 1

Alex Ratushnyak, May 24 2012

			When n=3 this is the number of ways to move a knight from a1 to c3 without occupying any cell twice. Only two paths: a1-b3-c1-a2-c3 and a1-c2-a3-b1-c3.
When n=8 this is the number of ways to move a knight from a1 to h8 without occupying any cell twice.

Cf. A007764 : rook paths (with moves of unit length).
Cf. A038496 : bishop paths (with moves of unit length).
Cf. A140518 : king paths.

#include 
int WIDTH, HEIGHT;
char grid[16][16];
int calc_ways(int x, int y) {
    if (!((unsigned)x

A376609 a(n) is the numerator of the expected number of random moves of a chess king to reach a position outside an nXn chessboard, starting in one of the corners.

Original entry on oeis.org

1, 8, 72, 46, 23747, 94968, 12161644, 158536576, 165181795263, 1779861954248, 60921563004721184, 136512657826472304, 38548316743830620183051, 581371653539561314, 2630585854108441990301102856, 120104329127347395409698056, 5092493809189909792181005355935991197, 6666722670813237580783418910187983288

Offset: 1

Hugo Pfoertner, Oct 03 2024

The king visits the Moore neighborhood (see A272763). The piece does not pay attention to its position and will fall off the board if it makes a move beyond the edge of the board.

			1, 8/5, 72/35, 46/19, 23747/8723, 94968/31879, 12161644/3797647, 158536576/46627015, 165181795263/46174521031, ...
Approximately 1, 1.6, 2.057, 2.421, 2.722, 2.979, 3.202, 3.400, 3.577, 3.738, ...

Hugo Pfoertner, Table of n, a(n) for n = 1..45
Hugo Pfoertner, Plot of A376609(n)/A376610(n) vs n, using Plot 2.
Hugo Pfoertner, Results of a simulation of 10^9 walks on the 8X8 board.

A376610 are the corresponding denominators.
A376606 and A376607 are similar for a rook walk with unit steps.
A376736 and A376737 are similar for a chess knight.
Cf. A140518, A272763, A323140, A323561, A323562.

\\ Uses function droprob from A376606
kingmoves = [[1, 0], [0, 1], [0, -1], [-1, 0], [-1, -1], [-1, 1], [1, -1], [1, 1]];
a376609(n) = numerator(droprob(n,kingmoves,8))

A038496 Number of self-avoiding paths with diagonal steps from corner to opposite corner of n X n grid.

Original entry on oeis.org

1, 1, 1, 3, 9, 53, 465, 9815, 288601, 19609857, 1719287011, 340800846539, 88312098753293, 52527897517470365, 41335202747219808853, 74965326513925821171199, 179806473914469748125175893, 992651698460472155144461591193

Offset: 1

David W. Wilson, based on a suggestion of Felice Russo

			Illustration of a(4)=3:
.  o   o         o   o         o   o
.   \             \ / \         \
.    o   o         o   o         o   o
.     \               /         /
.  o   o         o   o         o   o
.       \             \         \ / \
.    o   o         o   o         o   o

Andrew Howroyd, Table of n, a(n) for n = 1..25

Cf. A140518, A007764.

a(11)-a(12) from R. H. Hardin, Jul 31 2008

a(13)-a(18) from Andrew Howroyd, Apr 07 2016

A193168 Number of simple paths from (1, 1) to (n, 3) on an n X 3 grid with king moves allowed.

Original entry on oeis.org

1, 24, 235, 2922, 38169, 494596, 6375379, 82191766, 1059980385, 13670322763, 176299392634, 2273637717194, 29321902354841, 378149186319554, 4876791443282017, 62893416210079645, 811103334429880838, 10460373436120693109, 134901938876902858230, 1739759409373842739031

Offset: 1

Matías Benzo, Jul 17 2011

Simple paths are self-avoiding walks.
Note: Number of paths from (1, 1) to (n, 2) on a n X 2 grid matches the sequence A086347.
Example: a(2) = 24 paths from (1, 1) to (2, 3)
[(1, 1), (2, 1), (1, 2), (1, 3), (2, 3)]
[(1, 1), (2, 2), (1, 3), (2, 3)]
[(1, 1), (2, 2), (2, 1), (1, 2), (2, 3)]
[(1, 1), (1, 2), (2, 1), (2, 2), (1, 3), (2, 3)]
[(1, 1), (2, 2), (2, 1), (1, 2), (1, 3), (2, 3)]
[(1, 1), (1, 2), (2, 2), (1, 3), (2, 3)]
[(1, 1), (1, 2), (1, 3), (2, 3)]
[(1, 1), (2, 2), (1, 3), (1, 2), (2, 3)]
[(1, 1), (2, 2), (2, 3)]
[(1, 1), (1, 2), (2, 3)]
[(1, 1), (2, 2), (1, 2), (1, 3), (2, 3)]
[(1, 1), (2, 1), (2, 2), (1, 3), (2, 3)]
[(1, 1), (2, 1), (2, 2), (1, 2), (2, 3)]
[(1, 1), (2, 1), (1, 2), (1, 3), (2, 2), (2, 3)]
[(1, 1), (1, 2), (2, 1), (2, 2), (2, 3)]
[(1, 1), (2, 1), (2, 2), (1, 3), (1, 2), (2, 3)]
[(1, 1), (2, 1), (1, 2), (2, 3)]
[(1, 1), (1, 2), (2, 2), (2, 3)]
[(1, 1), (1, 2), (1, 3), (2, 2), (2, 3)]
[(1, 1), (2, 1), (2, 2), (1, 2), (1, 3), (2, 3)]
[(1, 1), (2, 2), (1, 2), (2, 3)]
[(1, 1), (2, 1), (2, 2), (2, 3)]
[(1, 1), (2, 1), (1, 2), (2, 2), (2, 3)]
[(1, 1), (2, 1), (1, 2), (2, 2), (1, 3), (2, 3)]

Andrew Howroyd, Table of n, a(n) for n = 1..200

Row 3 of A329118.

Cf. A086347, A140518.

Conjectures from Andrew Howroyd, Nov 05 2019: (Start)
a(n) = 12*a(n-1) + 6*a(n-2) + 50*a(n-3) + 300*a(n-4) - 194*a(n-5) - 833*a(n-6) + 352*a(n-7) + 661*a(n-8) - 84*a(n-9) - 219*a(n-10) + 72*a(n-11) + 54*a(n-12) for n > 12.
G.f.: x*(1 + 12*x - 59*x^2 - 92*x^3 + 195*x^4 + 280*x^5 + 102*x^6 - 178*x^7 - 67*x^8 + 109*x^9 - 75*x^10 - 54*x^11)/((1 + x + 9*x^2 + 24*x^3 + 9*x^4)*(1 - 13*x - 2*x^2 + 45*x^3 - 24*x^4 - 22*x^5 + 9*x^6 + 8*x^7 - 6*x^8)).
(End)

Offset changed and more terms from Andrew Howroyd, Nov 05 2019

A351107 Number of simple paths for a Racetrack car (using Moore neighborhood) with initial velocity zero, going from one corner to the diagonally opposite corner on an n X n grid.

Original entry on oeis.org

1, 3, 23, 1470, 914525

Offset: 1

Pontus von Brömssen, Feb 01 2022

			For n = 3 the following paths exist (up to reflection in the diagonal). The numbers give the positions of the car after successive steps.
  ..2  ..3  ..3  ..3  ..4  ..4  .34  .56  456  548  678  678
  .1.  ..2  .2.  .12  ..3  .23  .2.  .43  32.  673  543  512
  0..  01.  01.  0..  012  01.  01.  012  01.  012  012  043
Of these, only the first path is symmetric with respect to the diagonal, so the other 11 give rise to 2 paths each. In total, there are a(3) = 1 + 2*11 = 23 possible paths.

Wikipedia, Racetrack

Main diagonal of A351106.

Cf. A140518, A351041, A351109, A351111.

A236690 Number of simple directed paths on an n X n king graph.

Original entry on oeis.org

1, 64, 10305, 12029640, 115066382913, 9913814758253424, 7908201732771623795865, 59973177127583169531861733624, 4374964523946648320195747609012311225, 3101392210136336400751621092299022481429113152

Offset: 1

Jaimal Ichharam, Jan 30 2014

This is the number (assuming each character is unique) of strings that are possible in an n X n Boggle grid.

This sequence gives the number of directed paths. Paths may start and end on any vertex and may be of any length. Paths of length zero are counted here. - Andrew Howroyd, May 12 2017

Eric Weisstein's World of Mathematics, King Graph

Cf. A236753 for a simpler version of the problem without diagonal edges.

Cf. A288033, A140518, A158651.

a(n) = 2*A288033(n) + n^2. - Andrew Howroyd, Jun 10 2017

a(5) from Jaimal Ichharam, Feb 12 2014

Named edited and a(6)-a(10) from Andrew Howroyd, May 12 2017

A378902 a(n) is the number of paths of a chess king on square a1 to reach a position outside an 8 X 8 chessboard after n steps.

Original entry on oeis.org

5, 6, 39, 156, 922, 5060, 31165, 196605, 1301490, 8844147, 61504902, 434181564, 3098427480, 22270496859, 160854381441, 1165549608378, 8463549600999, 61543303627788, 447926999731974, 3262077526200660, 23765765966223849, 173189189528260281, 1262299887268848702, 9201356346994752339

Offset: 1

Hugo Pfoertner, Dec 10 2024

The king visits the Moore neighborhood, and the 8 possible moves relative to its current position are E, NE, N, NW, W, SW, S, and SE.

			a(1) = 5: only the 3 moves E, NE, and N end on target squares on the chessboard, the other 5 leave the board.
a(2) = 6: the 6 combinations of step directions leaving the board in exactly 2 moves are [E,SW], [E,S], [E,SE], [N,NE], [N,E], and [N,SE].

Ruediger Jehn, Table of n, a(n) for n = 1..100

Cf. A140518, A376609, A376610, A377018.

LinearRecurrence[{9, 9, -159, -108, 810, 900, -513, -729, -27, 81}, {5, 6, 39, 156, 922, 5060, 31165, 196605, 1301490, 8844147}, 25] (* Hugo Pfoertner, May 17 2025 *)

from numpy import ones, array
P = ones((11,11),dtype=int) # transition matrix, a1=0, b1=1, c1=2, d1=3, b2=4, c2=5, d2=6, c3=7, d3=8, d4=9, off board=10
P = [[0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 5, ],
     [1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 3, ],
     [0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 3, ],
     [0, 0, 1, 1, 0, 1, 2, 0, 0, 0, 3, ],
     [1, 2, 2, 0, 0, 2, 0, 1, 0, 0, 0, ],
     [0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, ],
     [0, 0, 1, 2, 0, 1, 1, 1, 2, 0, 0, ],
     [0, 0, 0, 0, 1, 2, 2, 0, 2, 1, 0, ],
     [0, 0, 0, 0, 0, 1, 2, 1, 2, 2, 0, ],
     [0, 0, 0, 0, 0, 0, 0, 1, 4, 3, 0, ],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ]]
pop = array([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], dtype=object) # king starts in a1
cycle = 100  # simulation period
for i in range(cycle):
    pop = pop @ P
    print(i+1, pop[10]) # Ruediger Jehn, May 17 2025

a(16) and beyond from Ruediger Jehn, May 17 2025

cp's OEIS Frontend

A329118 Array read by antidiagonals: T(m, n) is the number of simple paths from corner to diagonally opposite corner on an m X n grid with king moves allowed.

Views

Author

Keywords

Examples

Links

Crossrefs

A272445 Numbers of paths for moving a king from a corner to the opposite one in an n X n chessboard, provided that each cell must be reached exactly once.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Extensions

A308129 Number of (undirected) Hamiltonian paths on the n X n king graph.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A212715 Number of nonintersecting (or self-avoiding) knight paths joining opposite corners of an n X n grid.

Views

Author

Keywords

Examples

Crossrefs

Programs

C

A376609 a(n) is the numerator of the expected number of random moves of a chess king to reach a position outside an nXn chessboard, starting in one of the corners.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A038496 Number of self-avoiding paths with diagonal steps from corner to opposite corner of n X n grid.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A193168 Number of simple paths from (1, 1) to (n, 3) on an n X 3 grid with king moves allowed.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A351107 Number of simple paths for a Racetrack car (using Moore neighborhood) with initial velocity zero, going from one corner to the diagonally opposite corner on an n X n grid.

Views

Author

Keywords

Examples

Links

Crossrefs

A236690 Number of simple directed paths on an n X n king graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A378902 a(n) is the number of paths of a chess king on square a1 to reach a position outside an 8 X 8 chessboard after n steps.

Views

Author