cp's OEIS Frontend

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

%I A215527 #12 Apr 10 2016 02:27:25
%S A215527 1,8,441,23436,3274015,1279624470,1429940707685,4632832974994840,
%T A215527 44016723796115276451,1236712122885961369684270,
%U A215527 103348977536357696768748889161,25793194766828189243602379528079372,19283754194866506189223991782133012219131
%N 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).
%C A215527 Overall there are n*n sectors.
%C A215527 The length of the step is 1. The length of the path varies.
%C A215527 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 A215527 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 A215527 NorthPole NW SW SouthPole
%e A215527 NorthPole NW SW SE SouthPole
%e A215527 NorthPole NW NE SE SouthPole
%e A215527 NorthPole NW NE SE SW SouthPole
%e A215527 NorthPole NE SE SouthPole
%e A215527 NorthPole NE SE SW SouthPole
%e A215527 NorthPole NE NW SW SouthPole
%e A215527 NorthPole NE NW SW SE SouthPole
%e A215527 So a(2)=8.
%o A215527 (C)
%o A215527 #include <stdio.h>  // GCC -O3  // a(7) in ~1.5 hours
%o A215527 char grid[8][8];
%o A215527 long long SIZE;
%o A215527 long long calc_ways(long long x, long long y) {
%o A215527   if (grid[x][y]) return 0;
%o A215527   grid[x][y] = 1;
%o A215527   long long n = calc_ways( x==0? SIZE-1 : x-1, y);  // try West
%o A215527   if (SIZE>2)
%o A215527             n+= calc_ways( x==SIZE-1? 0 : x+1, y);  // East
%o A215527   if (y>0)  n+= calc_ways(x,y-1);  // North
%o A215527   if (y==SIZE-1)  n++;
%o A215527   else      n+= calc_ways(x,y+1);  // South
%o A215527   grid[x][y] = 0;
%o A215527   return n;
%o A215527 }
%o A215527 int main(int argc, char **argv)
%o A215527 {
%o A215527   for (SIZE=1; SIZE<7; ++SIZE) {
%o A215527     memset(grid, 0, sizeof(grid));
%o A215527     printf("%llu, ",calc_ways(0,0)*SIZE);
%o A215527   }
%o A215527   printf("\n      ");
%o A215527   for (SIZE=3; SIZE<9; ++SIZE) {
%o A215527     unsigned long long r;
%o A215527     memset(grid, 0, sizeof(grid));
%o A215527     grid[0][0]=1;
%o A215527     grid[0][1]=1;
%o A215527     r =  calc_ways(0,2)*SIZE;    if (SIZE>6) printf(".");
%o A215527     r += calc_ways(1,1)*SIZE*2;  if (SIZE>6) printf(".");
%o A215527     grid[0][1]=0;
%o A215527     grid[1][0]=1;
%o A215527     r += calc_ways(1,1)*SIZE*2;  if (SIZE>6) printf(".");
%o A215527     r += calc_ways(2,0)*SIZE*2;  printf("%llu, ", r);
%o A215527   }
%o A215527 }
%Y A215527 Cf. A007764, A268894.
%K A215527 nonn,walk
%O A215527 1,2
%A A215527 _Alex Ratushnyak_, Aug 15 2012
%E A215527 a(8)-a(13) from _Andrew Howroyd_, Apr 09 2016