login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 4
1, 2, 10, 124, 4620, 536360, 189313340, 201653395768, 651683788574786 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

LINKS

Table of n, a(n) for n=1..9.

EXAMPLE

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.

PROG

(Python)

# 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)])

(Ruby)

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)

CROSSREFS

Cf. A000108, A007764.

Sequence in context: A005321 A339934 A092645 * A334555 A202950 A144835

Adjacent sequences:  A333452 A333453 A333454 * A333456 A333457 A333458

KEYWORD

nonn,more

AUTHOR

Seiichi Manyama, Mar 22 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 28 06:59 EST 2021. Contains 340490 sequences. (Running on oeis4.)