A215527 - OEIS

%I #12 Apr 10 2016 02:27:25

%S 1,8,441,23436,3274015,1279624470,1429940707685,4632832974994840,

%T 44016723796115276451,1236712122885961369684270,

%U 103348977536357696768748889161,25793194766828189243602379528079372,19283754194866506189223991782133012219131

%N 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).

%C Overall there are n*n sectors.

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

%C 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

%e 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:

%e NorthPole NW SW SouthPole

%e NorthPole NW SW SE SouthPole

%e NorthPole NW NE SE SouthPole

%e NorthPole NW NE SE SW SouthPole

%e NorthPole NE SE SouthPole

%e NorthPole NE SE SW SouthPole

%e NorthPole NE NW SW SouthPole

%e NorthPole NE NW SW SE SouthPole

%e So a(2)=8.

%o (C)

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

%o char grid[8][8];

%o long long SIZE;

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

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

%o   grid[x][y] = 1;

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

%o   if (SIZE>2)

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

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

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

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

%o   grid[x][y] = 0;

%o   return n;

%o }

%o int main(int argc, char **argv)

%o {

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

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

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

%o   }

%o   printf("\n      ");

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

%o     unsigned long long r;

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

%o     grid[0][0]=1;

%o     grid[0][1]=1;

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

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

%o     grid[0][1]=0;

%o     grid[1][0]=1;

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

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

%o   }

%o }

%Y Cf. A007764, A268894.

%K nonn,walk

%O 1,2

%A _Alex Ratushnyak_, Aug 15 2012

%E a(8)-a(13) from _Andrew Howroyd_, Apr 09 2016