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!)
A340005 Number of self-avoiding paths along the edges of a grid with nXn square cells, which do not pass above the diagonal. The paths start at the lower left corner and finish at the upper right corner. 2
1, 1, 2, 7, 40, 369, 5680, 150707, 6993712, 567670347, 80294818098, 19750798800833, 8447500756620198, 6286515496550185699, 8145835634791919637646, 18387066260739625200447575, 72319765957232441125506763756, 495718308213370458738098777141317 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

LINKS

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

EXAMPLE

3X3 square cells

  *---*---*---E

  |   |   |   |

  *---*---*---*

  |   |   |   |

  *---*---*---*

  |   |   |   |

  S---*---*---*

a(3) = A000108(3) + 2 = 7;

              E              E              E

              |              |              |

              *              *          *---*

              |              |          |

              *      *---*---*      *---*

              |      |              |

  S---*---*---*  S---*          S---*

              E              E

              |              |

              *          *---*

              |          |

          *---*          *

          |              |

  S---*---*      S---*---*

              E              E

              |              |

              *          *---*

              |          |

      *---*   *          *---*

      |   |   |              |

  S---*   *---*  S---*---*---*

PROG

(Python)

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

CROSSREFS

Row sum of A340043.

Cf. A000108, A007764.

Sequence in context: A006455 A130715 A317723 * A325061 A215207 A106871

Adjacent sequences:  A340002 A340003 A340004 * A340006 A340007 A340008

KEYWORD

nonn

AUTHOR

Seiichi Manyama, Dec 26 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 September 23 20:42 EDT 2021. Contains 347617 sequences. (Running on oeis4.)