A007764 -id:A007764 - cp's OEIS frontend

A376606 a(n) is the numerator of the expected number of moves to reach a position outside an nXn chessboard, starting in one of the corners, when performing a random walk with unit steps on the square lattice.

1, 2, 11, 10, 99, 122, 619, 4374, 187389, 482698, 11031203, 33386106, 32723853563, 139832066, 150236161755, 633573154269934, 5755694771977, 189378719187729770, 509943025510535499, 6031948951257694364778, 1044408374351599765540157091, 27891966006517951087819226666

Offset: 1

Ruediger Jehn and Hugo Pfoertner, Oct 03 2024

The moves are that of chess rook with moves of unit length or of a chess king restricted to the Von Neumann 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, 2, 11/4, 10/3, 99/26, 122/29, 619/136, 4374/901, 187389/36562, 482698/89893, ...
Approximately 1, 2, 2.75, 3.333, 3.808, 4.207, 4.551, 4.855, 5.125, 5.370, 5.593, ...

Hugo Pfoertner, Table of n, a(n) for n = 1..45
Hugo Pfoertner, Plot of A376606(n)/A376607(n) vs n, using Plot 2.

A376607 are the corresponding denominators.
A376609 and A376610 are similar for a chess king visiting the Moore neighborhood.
A376736 and A376737 are similar for a chess knight.
Cf. A001263, A007764, A272763.

droprob(n,moves=[[1,0],[0,1],[0,-1],[-1,0]], nmoves=4) = {my(np=n^2+1, M=matrix(np), P=1/nmoves); for(t=1, nmoves, for( i=1, n, my(ti=i+moves[t][1]); for(j=1,n,my(tj=j+moves[t][2]); my(m=(i-1)*n+j); if(ti<1 || ti>n || tj<1 || tj>n, M[m,np]+=P, my(mt=(ti-1)*n+tj); M[m,mt]+=P)))); vecsum((1/(matid(np)-M))[,1])};
a376606(n) = numerator(droprob(n))

A333323 Number of self-avoiding closed paths on an n X n grid which pass through NW and SE corners.

Original entry on oeis.org

1, 3, 42, 1799, 232094, 92617031, 115156685746, 442641690778179, 5224287477491915786, 188825256606226776728029, 20879416139356164466643759334, 7057757437924198729598570424130207, 7287699030020917172151307665469211016474, 22973720258279267139936821063450448822110219653

Offset: 2

Seiichi Manyama, Mar 23 2020

nonn

			a(2) = 1;
   +--*
   |  |
   *--+
a(3) = 3;
   +--*--*   +--*--*   +--*
   |     |   |     |   |  |
   *--*  *   *     *   *  *--*
      |  |   |     |   |     |
      *--+   *--*--+   *--*--+

Anthony J. Guttmann and Iwan Jensen, Table of n, a(n) for n = 2..27
Anthony J. Guttmann and Iwan Jensen, Self-avoiding walks and polygons crossing a domain on the square and hexagonal lattices, arXiv:2208.06744 [math-ph], Aug 13 2022, Table D2 (with offset 1).
Anthony J. Guttmann and Iwan Jensen, The gerrymander sequence, or A348456, arXiv:2211.14482 [math.CO], 2022.

Cf. A007764, A333246, A333247, A333466.

Cf. A121785, A356610-A356616, A354511.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333323(n):
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles().including(1).including(n * n)
    return cycles.len()
print([A333323(n) for n in range(2, 10)])

a(11) from Seiichi Manyama, Apr 07 2020

a(10) and a(12)-a(15) from Vaclav Kotesovec, Aug 16 2022 (computed by Anthony Guttmann)

A064297 Triangle of self-avoiding rook paths joining opposite corners of n X k board.

Original entry on oeis.org

1, 1, 2, 1, 4, 12, 1, 8, 38, 184, 1, 16, 125, 976, 8512, 1, 32, 414, 5382, 79384, 1262816, 1, 64, 1369, 29739, 752061, 20562673, 575780564, 1, 128, 4522, 163496, 7110272, 336067810, 16230458696, 789360053252, 1, 256, 14934, 896476, 67005561

Offset: 1

Henry Bottomley, Sep 05 2001

			Triangle starts
1,
1, 2,
1, 4, 12,
1, 8, 38, 184,
1, 16, 125, 976, 8512,
1, 32, 414, 5382, 79384, 1262816,
1, 64, 1369, 29739, 752061, 20562673, 575780564,
1, 128, 4522, 163496, 7110272, 336067810, ...

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 331-339.

Ruben Grønning Spaans, Triangle of rows 1 to 20, flattened
Steven R. Finch, Self-Avoiding Walks of a Rook on a Chessboard [From Steven Finch, Apr 20 2019]
Steven R. Finch, Self-Avoiding Walks of a Rook [From Steven Finch, Apr 20 2019; mentioned in Finch's "Gammel" link above]
Steven R. Finch, Table of Non-Overlapping Rook Paths [From Steven Finch, Apr 20 2019; mentioned in Finch's "Gammel" link above]
Ruben Grønning Spaans, C program

Half of A064298.
Row/column combinations include A000012, A000079, A006192, A007786, A007787, A145403.
Right hand column is A007764.
Cf. A271465.

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

A288032 Number of (undirected) paths in the n X n grid graph.

Original entry on oeis.org

0, 12, 322, 14248, 1530196, 436619868, 343715004510, 766012555199052, 4914763477312679808, 91781780911712980966236, 5028368533802124263609489682, 813124448051069045700905179168520

Offset: 1

Eric W. Weisstein, Jun 04 2017

Paths of length zero are not counted here. - Andrew Howroyd, Jun 10 2017

Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A288518.

Cf. A236753, A288033, A288148, A007764, A121785, A120443.

a(6)-a(12) from Andrew Howroyd, Jun 10 2017

A333455 Number of self-avoiding walks from NW to SE corners on an n X n grid which pass through all points on the diagonal connecting NW and SE corners.

Original entry on oeis.org

1, 2, 10, 124, 4620, 536360, 189313340, 201653395768, 651683788574786

Offset: 1

Seiichi Manyama, Mar 22 2020

a(11) = 191874208353355680763886. - Seiichi Manyama, Apr 07 2020

			a(2) = 2;
   S--*   S
      |   |
      E   *--E
a(3) = 10;
   S--*--*   S--*--*   S--*
         |         |      |
      +--*   *--+--*      +--*
      |      |               |
      *--E   *--*--E         E
   S--*      S--*      S  *--*
      |         |      |  |  |
      +      *--+      *  +  *
      |      |         |  |  |
      *--E   *--*--E   *--*  E
   S  *--*   S         S
   |  |  |   |         |
   *--+  *   *  +--*   *--+--*
         |   |  |  |         |
         E   *--*  E         E
   S
   |
   *--+
      |
      *--E
a(4) = 124;
   S--*--*--*   S--*--*--*   S--*--*--*
            |            |            |
   *--+--*  *   *--+--*  *   *--+  *--*
   |     |  |   |     |  |   |  |  |
   *--*  +--*   *     +--*   *  *--+
      |         |            |
      *--*--E   *--*--*--E   *--*--*--E
   ... and so on.

Cf. A000108, A007764.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333455(n):
    if n == 1: return 1
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, n * n
    paths = GraphSet.paths(start, goal)
    for i in range(n - 1):
        paths = paths.including((n + 1) * i + 1)
    return paths.len()
print([A333455(n) for n in range(1, 10)])

def search(x, y, n, used)
  return 0 if x < 0 || n <= x || y < 0 || n <= y || used[x + y * n]
  return 1 if x == n - 1 && y == n - 1 && (0..n - 2).all?{|i| used[(n + 1) * i] == true}
  cnt = 0
  used[x + y * n] = true
  @move.each{|mo|
    cnt += search(x + mo[0], y + mo[1], n, used)
  }
  used[x + y * n] = false
  cnt
end
def A(n)
  @move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
  used = Array.new(n * n, false)
  search(0, 0, n, used)
end
def A333455(n)
  (1..n).map{|i| A(i)}
end
p A333455(6)

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

A059783 Number of paths (without loops) in graph of n-dimensional hypercube starting at point (0,0,0,...,0) and ending at (1,1,1,...,1).

Original entry on oeis.org

1, 2, 18, 6432, 18651552840

Offset: 1

Avi Peretz (njk(AT)netvision.net.il), Feb 22 2001

Terms up to a(5)=18651552840 confirmed by independent computation. [Joerg Arndt, Aug 07 2012]

			a(2) = 2 because there are 2 paths: 00,01,11 and 00,10,11

J. Berestycki, É. Brunet, and Z. Shi, Accessibility percolation with backsteps, arXiv preprint arXiv:1401.6894 [math.PR], 2014.
Higher Dimensions Number of simple paths in a tesseract [From _Dmitry Kamenetsky_, Aug 28 2009]

Cf. A007764.

Cf. A091299, A006069, A006070, A003042, A066037, A091302.

Added a(5), based on http://teamikaria.com/4dforum/viewtopic.php?f=5&t=1211 Dmitry Kamenetsky, Aug 28 2009

Corrected offset Alex Ratushnyak, Aug 07 2012

A333464 Number of self-avoiding walks from NW to SE corners on an n X n grid which pass through all points on the diagonal connecting NE and SW corners.

Original entry on oeis.org

1, 0, 2, 20, 752, 84008, 29145982, 30795358024, 99417240957788

Offset: 1

Seiichi Manyama, Mar 22 2020

a(11) = 29262010991555584566654. - Seiichi Manyama, Apr 07 2020

			a(3) = 2;
   S--*--+   S  *--+
         |   |  |  |
   *--+--*   *  +  *
   |         |  |  |
   +--*--E   +--*  E
a(4) = 20;
   S--*--*--+   S--*--*--+   S--*--*--+
            |            |            |
   *--*--+--*   *--*--+--*   *--*  +--*
   |            |            |  |  |
   *  +--*      *  +--*--*   *  +--*
   |  |  |      |  |     |   |
   +--*  *--E   +--*     E   +--*--*--E
   S--*--*--+   S--*--*--+   S--*--*--+
            |            |            |
      *--+--*      *--+--*      *--+  *
      |            |            |  |  |
   *--+  *--*   *--+         *--+  *--*
   |     |  |   |            |
   +--*--*  E   +--*--*--E   +--*--*--E
   S--*--*--+   S--*  *--+   S--*  *--+
            |      |  |  |      |  |  |
         +--*   *--*  +  *      *--+  *
         |      |     |  |            |
   *--+--*      *  +--*  *   *--+--*--*
   |            |  |     |   |
   +--*--*--E   +--*     E   +--*--*--E
   S--*  *--+   S  *--*--+   S  *--*--+
      |  |  |   |  |     |   |  |     |
      *  +  *   *--*  +--*   *  *--+  *
      |  |  |         |      |     |  |
   *--+  *  *   *--+--*      *  +--*  *
   |     |  |   |            |  |     |
   +--*--*  E   +--*--*--E   +--*     E
   S  *--*--+   S  *--*--+   S     *--+
   |  |     |   |  |     |   |     |  |
   *  *  +--*   *  *  +--*   *--*--+  *
   |  |  |      |  |  |               |
   *  +  *      *  +  *--*   *--+--*--*
   |  |  |      |  |     |   |
   +--*  *--E   +--*     E   +--*--*--E
   S     *--+   S     *--+   S     *--+
   |     |  |   |     |  |   |     |  |
   *--*  +  *   *  *--+  *   *  *--+  *
      |  |  |   |  |     |   |  |     |
   *--+  *  *   *  +--*  *   *  +  *--*
   |     |  |   |     |  |   |  |  |
   +--*--*  E   +--*--*  E   +--*  *--E
   S     *--+   S     *--+
   |     |  |   |     |  |
   *  *--+  *   *     +  *
   |  |     |   |     |  |
   *  +     *   *  +--*  *
   |  |     |   |  |     |
   +--*     E   +--*     E

Cf. A007764, A333455.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333464(n):
    if n == 1: return 1
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, n * n
    paths = GraphSet.paths(start, goal)
    for i in range(n):
        paths = paths.including((n - 1) * (i + 1) + 1)
    return paths.len()
print([A333464(n) for n in range(1, 10)])

def search(x, y, n, used)
  return 0 if x < 0 || n <= x || y < 0 || n <= y || used[x + y * n]
  return 1 if x == n - 1 && y == n - 1 && (0..n - 1).all?{|i| used[(n - 1) * (i + 1)] == true}
  cnt = 0
  used[x + y * n] = true
  @move.each{|mo|
    cnt += search(x + mo[0], y + mo[1], n, used)
  }
  used[x + y * n] = false
  cnt
end
def A(n)
  return 1 if n == 1
  @move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
  used = Array.new(n * n, false)
  search(0, 0, n, used)
end
def A333464(n)
  (1..n).map{|i| A(i)}
end
p A333464(6)

A340005 Number of self-avoiding paths along the edges of a grid with n X n square cells, which do not pass above the diagonal. The paths start at the lower left corner and finish at the upper right corner.

Original entry on oeis.org

1, 1, 2, 7, 40, 369, 5680, 150707, 6993712, 567670347, 80294818098, 19750798800833, 8447500756620198, 6286515496550185699, 8145835634791919637646, 18387066260739625200447575, 72319765957232441125506763756, 495718308213370458738098777141317

Offset: 0

Seiichi Manyama, Dec 26 2020

nonn

			3 X 3 square cells
  *---*---*---E
  |   |   |   |
  *---*---*---*
  |   |   |   |
  *---*---*---*
  |   |   |   |
  S---*---*---*
a(3) = A000108(3) + 2 = 7;
              E              E              E
              |              |              |
              *              *          *---*
              |              |          |
              *      *---*---*      *---*
              |      |              |
  S---*---*---*  S---*          S---*
              E              E
              |              |
              *          *---*
              |          |
          *---*          *
          |              |
  S---*---*      S---*---*
              E              E
              |              |
              *          *---*
              |          |
      *---*   *          *---*
      |   |   |              |
  S---*   *---*  S---*---*---*

Siqi Wang, Table of n, a(n) for n = 0..31

Row sum of A340043.

Cf. A000108, A007764.

# Using graphillion
from graphillion import GraphSet
def make_stairs(n):
    s = 1
    grids = []
    for i in range(n + 1, 1, -1):
        for j in range(i - 1):
            a, b, c = s + j, s + j + 1, s + i + j
            grids.extend([(a, b), (a, c)])
        s += i
    return grids
def A340005(n):
    if n == 0: return 1
    universe = make_stairs(n)
    GraphSet.set_universe(universe)
    start, goal = n + 1, (n + 1) * (n + 2) // 2
    paths = GraphSet.paths(start, goal)
    return paths.len()
print([A340005(n) for n in range(15)])

cp's OEIS Frontend

A376606 a(n) is the numerator of the expected number of moves to reach a position outside an nXn chessboard, starting in one of the corners, when performing a random walk with unit steps on the square lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A333323 Number of self-avoiding closed paths on an n X n grid which pass through NW and SE corners.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Extensions

A064297 Triangle of self-avoiding rook paths joining opposite corners of n X k board.

Views

Author

Keywords

Examples

References

Links

Crossrefs

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

A288032 Number of (undirected) paths in the n X n grid graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A333455 Number of self-avoiding walks from NW to SE corners on an n X n grid which pass through all points on the diagonal connecting NW and SE corners.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Ruby

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

A059783 Number of paths (without loops) in graph of n-dimensional hypercube starting at point (0,0,0,...,0) and ending at (1,1,1,...,1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A333464 Number of self-avoiding walks from NW to SE corners on an n X n grid which pass through all points on the diagonal connecting NE and SW corners.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs