login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

a(n) is the number of different pairs of shortest grid paths joining two opposite corners in opposite order in an n X n X n grid with middle point on the paths as a common point.
2

%I #51 Nov 19 2022 12:46:50

%S 6,1782,163968,145833750,20373051636,24849381916800,4084135317043200,

%T 5797029176271753750,1041061545857195362500,1615355981352350001296532,

%U 306767275482371866616143872,504734657532271646660879497344,99610601729722879962014433236736,170840233187582521064354430462720000

%N a(n) is the number of different pairs of shortest grid paths joining two opposite corners in opposite order in an n X n X n grid with middle point on the paths as a common point.

%C Alternatively, a(n) is the number of ways to meet at the middle point on the paths when two ants at opposite corners of an n X n X n grid try to interchange their positions by starting simultaneously and moving along the shortest paths at the same constant speed.

%F When n is even, a(n) = Sum_{0 <= p <= q <= r <= 2m, p+q+r=3m} k*(((3m)!/(p!*q!*r!))*((3m!)/(x!*y!*z!)))^2 where m=n/2, x=2m-p, y=2m-q, z=2m-r and k=1 if p=q=r, k=3 if exactly two of p,q,r are equal, k=6 otherwise.

%F When n is odd, a(n) = Sum_{0 <= p <= q <= r+c <= 2m+1, p+q+r=3m+1, 0 <= a,b,c <= 1, a+b+c=1} k*(((3m+1)!/(p!*q!*r!))*((3m+1)!/(x!*y!*z!)))^2 where m=(n-1)/2,x=2m+1-p-a,y=2m+1-q-b,z=2m+1-r-c and k=1 if p=q=r, k=3 if exactly two of p,q,r are equal, k=6 otherwise.

%e As an example with n even, let a 2 X 2 X 2 grid be positioned so that the coordinates of two opposite corners are O(0,0,0), P(2,2,2) and consider the shortest paths joining them. There are (3!/(1!*1!*1!))*(3!/(1!*1!*1!)) shortest grid paths joining O to P with (1,1,1) as the middle point on the paths. Therefore there are (((3!/(1!*1!*1!))*(3!/(1!*1!*1!)))^2 = 1296 pairs of shortest grid paths in opposite order (joining O to P and joining P to O) with (1,1,1) as the common point. There are (3!/(0!*1!*2!))*(3!/(2!*1!*0!)) shortest grid paths from O to P with (2,0,1) or (2,1,0) or (1,2,0) or (2,1,0) or (0,1,2) or (0,2,1) as the middle point. Therefore there are 6*(((3!/(0!*1!*2!))*(3!/(2!*1!*0!)))^2 = 486 pairs of shortest grid paths in opposite order which meet at the middle point on the paths. This gives the total as 1296 + 486 = 1782.

%e When n is odd, a(n) is the number of pairs of shortest paths which share the middle segment of their paths because the middle point of the path bisects the middle segment. For example, consider a grid of size 3 X 3 X 3, positioned so that the two opposite corners are at O(0,0,0) and P(3,3,3). The cases in which the middle segment joins (3,1,0) to (3,2,0) or (3,1,1) with 6 permutations give 4992 pairs. The cases in which the middle segment joins (2,1,1) to (2,1,2) or (2,2,1) or (3,1,1) with 3 permutations give 139968 pairs. The cases in which the middle segment joins (2,2,0) to (2,2,1) or (2,3,2) or (3,2,0) with 3 permutations give 19008 pairs. So the total number of pairs is 163968.

%K nonn

%O 1,1

%A _Janaka Rodrigo_, Oct 12 2022