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

6, 1782, 163968, 145833750, 20373051636, 24849381916800, 4084135317043200, 5797029176271753750, 1041061545857195362500, 1615355981352350001296532, 306767275482371866616143872, 504734657532271646660879497344, 99610601729722879962014433236736, 170840233187582521064354430462720000

Offset: 1

Author

Janaka Rodrigo, Oct 12 2022

Keywords

• nonn

Comments

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.

Examples

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

Formula

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.

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.