login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A215527 Number of nonintersecting (or self-avoiding) rook paths joining opposite poles of a sphere with n horizontal sectors and n vertical sectors (demarcated by longitudes and latitudes). 2
1, 8, 441, 23436, 3274015, 1279624470, 1429940707685, 4632832974994840, 44016723796115276451, 1236712122885961369684270, 103348977536357696768748889161, 25793194766828189243602379528079372, 19283754194866506189223991782133012219131 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Overall there are n*n sectors.

The length of the step is 1. The length of the path varies.

Equivalently, the number of directed paths in the graph C_n X P_n that start at any one of the n vertices on one side of the cylinder and terminate at any of the n vertices on the opposite side.  - Andrew Howroyd, Apr 09 2016

LINKS

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

EXAMPLE

With n=2 there are four sectors: North-Western, North-Eastern, South-Western, South Eastern. Eight nonintersecting (self-avoiding) rook paths joining opposite poles exist:

NorthPole NW SW SouthPole

NorthPole NW SW SE SouthPole

NorthPole NW NE SE SouthPole

NorthPole NW NE SE SW SouthPole

NorthPole NE SE SouthPole

NorthPole NE SE SW SouthPole

NorthPole NE NW SW SouthPole

NorthPole NE NW SW SE SouthPole

So a(2)=8.

PROG

(C)

#include <stdio.h>  // GCC -O3  // a(7) in ~1.5 hours

char grid[8][8];

long long SIZE;

long long calc_ways(long long x, long long y) {

  if (grid[x][y]) return 0;

  grid[x][y] = 1;

  long long n = calc_ways( x==0? SIZE-1 : x-1, y);  // try West

  if (SIZE>2)

            n+= calc_ways( x==SIZE-1? 0 : x+1, y);  // East

  if (y>0)  n+= calc_ways(x, y-1);  // North

  if (y==SIZE-1)  n++;

  else      n+= calc_ways(x, y+1);  // South

  grid[x][y] = 0;

  return n;

}

int main(int argc, char **argv)

{

  for (SIZE=1; SIZE<7; ++SIZE) {

    memset(grid, 0, sizeof(grid));

    printf("%llu, ", calc_ways(0, 0)*SIZE);

  }

  printf("\n      ");

  for (SIZE=3; SIZE<9; ++SIZE) {

    unsigned long long r;

    memset(grid, 0, sizeof(grid));

    grid[0][0]=1;

    grid[0][1]=1;

    r =  calc_ways(0, 2)*SIZE;    if (SIZE>6) printf(".");

    r += calc_ways(1, 1)*SIZE*2;  if (SIZE>6) printf(".");

    grid[0][1]=0;

    grid[1][0]=1;

    r += calc_ways(1, 1)*SIZE*2;  if (SIZE>6) printf(".");

    r += calc_ways(2, 0)*SIZE*2;  printf("%llu, ", r);

  }

}

CROSSREFS

Cf. A007764, A268894.

Sequence in context: A231102 A231824 A069442 * A240320 A013457 A012740

Adjacent sequences:  A215524 A215525 A215526 * A215528 A215529 A215530

KEYWORD

nonn,walk

AUTHOR

Alex Ratushnyak, Aug 15 2012

EXTENSIONS

a(8)-a(13) from Andrew Howroyd, Apr 09 2016

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 November 22 05:55 EST 2019. Contains 329388 sequences. (Running on oeis4.)