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,1

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.

Links

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

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.

Example

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.

Crossrefs

Sequence in context: A149187 A330056 A258900 * A250393 A221627 A160301

Adjacent sequences: A357757 A357758 A357759 * A357761 A357762 A357763

Keyword

nonn

Author

Janaka Rodrigo, Oct 12 2022

Status

approved