A272445 -id:A272445 - 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.

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

A350729 Array read by antidiagonals: T(m,n) is the number of (undirected) Hamiltonian paths in the m X n king graph.

Original entry on oeis.org

1, 1, 1, 1, 12, 1, 1, 48, 48, 1, 1, 208, 392, 208, 1, 1, 768, 4678, 4678, 768, 1, 1, 2752, 43676, 171592, 43676, 2752, 1, 1, 9472, 406396, 4743130, 4743130, 406396, 9472, 1, 1, 32000, 3568906, 132202038, 364618672, 132202038, 3568906, 32000, 1

Offset: 1

Andrew Howroyd, Jan 16 2022

			Array begins:
===========================================================
m\n | 1    2      3         4           5             6 ...
----+------------------------------------------------------
  1 | 1    1      1         1           1             1 ...
  2 | 1   12     48       208         768          2752 ...
  3 | 1   48    392      4678       43676        406396 ...
  4 | 1  208   4678    171592     4743130     132202038 ...
  5 | 1  768  43676   4743130   364618672   28808442502 ...
  6 | 1 2752 406396 132202038 28808442502 6544911081900 ...
     ...

Andrew Howroyd, Table of n, a(n) for n = 1..231
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, King Graph

Rows 1..5 are A000012, A339760, A339761, A339762, A339763.
Main diagonal is A308129.
Cf. A272445, A307026, A329118, A339098, A339190.

T(m,n) = T(n,m).

A272469 Numbers of n-step paths of a king moving on an n X n chessboard, starting at a corner and not visiting any cell twice.

Original entry on oeis.org

0, 6, 50, 322, 1874, 10558, 58716, 325758, 1808778, 10068548, 56213606, 314785072, 1767660604, 9951449844, 56151698716, 317484868212, 1798343124800, 10203031413894

Offset: 1

César Eliud Lozada, Apr 30 2016

			On an n X n chessboard, a king in a corner is allowed to have n moves. For n=2, let's name the cells A1,A2,B1,B2 with the king at A1. Two moves, without repeating cells, can be done in the following 6 different ways: {A1-A2-B1, A1-A2-B2, A1-B1-A2, A1-B1-B2, A1-B2-A2, A1-B2-B1}. So a(2)=6.

Cf. A272445.

pathCount := proc (N)
local g1, g2, nStep, gg, nCells, nPrev, i1, i2, j1, j2, i, j, nNext;
    nCells := N^2; g1 := [[1]];
    if N = 1 then return nops(g1) fi; #forced value for N=0
    for nStep to N do
        g2 := [];
        for gg in g1 do
            nPrev := gg[-1];
            i1 := `if`(floor((nPrev-1)/N) = 0, 0, -N);
            i2 := `if`(floor((nPrev-1)/N) = N-1, 0, N);
            j1 := `if`(`mod`(nPrev-1, N) = 0, 0, -1);
            j2 := `if`(`mod`(nPrev-1, N) = N-1, 0, 1);
            for i from i1 by N to i2 do
                for j from j1 to j2 do
                    if i = 0 and j = 0 then next fi;
                    nNext := nPrev+i+j;
                    if nNext < 0 or nCells < nNext or (nNext in gg) then next fi;
                    g2 := [op(g2), [op(gg), nNext]]
                end do
            end do
        end do;
        g1 := g2
    end do;
    return nops(g1);
end proc:
[seq(pathCount(n), n = 1 .. 6)];

a(9)-a(16) from Alois P. Heinz, May 01 2016

a(17)-a(18) from Bert Dobbelaere, Jan 08 2019

A351110 Triangle read by rows: T(m,n) is the number of paths for a Racetrack car (using Moore neighborhood) with initial velocity zero, going from one corner to the diagonally opposite corner on an m X n grid, such that all positions are visited exactly once, 1 <= n <= m.

Original entry on oeis.org

1, 1, 0, 1, 1, 6, 1, 0, 15, 2, 1, 1, 70, 289, 9436, 1, 0, 294, 191, 128020

Offset: 1

Pontus von Brömssen, Feb 01 2022

For a Racetrack car using von Neumann neighborhood (see A351042), there are no such paths if 2 <= n <= m, because the car will never be able to leave a corner of the grid (except the corner where it starts).

			Triangle begins:
  m\n| 1  2   3   4      5  6
  ---+-----------------------
  1  | 1
  2  | 1  0
  3  | 1  1   6
  4  | 1  0  15   2
  5  | 1  1  70 289   9436
  6  | 1  0 294 191 128020  ?

Wikipedia, Racetrack

Cf. A000012 (column n=1), A000035 (column n=2), A272445, A351041, A351042, A351106, A351111 (main diagonal).

A351111 Number of 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, such that all positions are visited exactly once.

Original entry on oeis.org

1, 0, 6, 2, 9436

Offset: 1

Pontus von Brömssen, Feb 01 2022

			For n = 4 the following path and its reflection in the diagonal are the only solutions, so a(4) = 2.
   _   _
  | | |_
  |_ \  |
   _| |_|

Wikipedia, Racetrack

Main diagonal of A351110.

Cf. A272445, A351041, A351107.

A338426 a(n) is the number of paths a chess king can take from (0,0) to (n+1,0) touching each point in {-1,0,1} X {1,2,...,n} exactly once.

Original entry on oeis.org

1, 2, 28, 154, 1206, 8364, 60614, 432636, 3104484, 22235310, 159360540, 1141875800, 8182608226, 58634396372, 420162632840, 3010793013534, 21574706493988, 154599722419136, 1107828637412194, 7938463325113516, 56885333141857872, 407628148378295190

Offset: 0

Peter Kagey, Oct 25 2020

			For n = 1, the a(1) = 2 paths are (0,0)->(1,1)->(1,0)->(1,-1)->(2,0) and (0,0)->(1,-1)->(1,0)->(1,1)->(2,0).
An example of one of the a(2) = 28 paths is (0,0)->(1,1)->(2,1)->(2,0)->(1,-1)->(1,0)->(2,-1)->(3,0).

Peter Kagey, Table of n, a(n) for n = 0..1000
Code Golf Stack Exchange user Bubbler, Counting King's Hamiltonian Paths through 3-by-N grid

Cf. A140518, A158651, A193168, A272445.

a(n) = 7*a(n-1) + 6*a(n-2) - 39*a(n-3) + 29*a(n-4) + 28*a(n-5) - 26*a(n-6) - 10*a(n-7) + 6*a(n-8) for n >= 8.

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

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A350729 Array read by antidiagonals: T(m,n) is the number of (undirected) Hamiltonian paths in the m X n king graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A272469 Numbers of n-step paths of a king moving on an n X n chessboard, starting at a corner and not visiting any cell twice.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Extensions

A351110 Triangle read by rows: T(m,n) is the number of paths for a Racetrack car (using Moore neighborhood) with initial velocity zero, going from one corner to the diagonally opposite corner on an m X n grid, such that all positions are visited exactly once, 1 <= n <= m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A351111 Number of 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, such that all positions are visited exactly once.

Views

Author

Keywords

Examples

Links

Crossrefs

A338426 a(n) is the number of paths a chess king can take from (0,0) to (n+1,0) touching each point in {-1,0,1} X {1,2,...,n} exactly once.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula