A357603 a(n) is the number of different pairs of shortest paths in an n X n lattice going between opposite corners in opposite directions and not meeting at their middle point.

0, 2, 18, 236, 3090, 42252, 589932, 8383608, 120720402, 1756863020, 25789460268, 381298472568, 5671808350572, 84807208655288, 1273785187835640, 19207311526394736, 290631247129611282, 4411188317020786668, 67137528193253129484, 1024357917198436543800

Offset: 0

Author

Janaka Rodrigo, Oct 05 2022

Keywords

• nonn
• easy

Comments

Equivalently, a(n) is the number of different ways to interchange the positions of two men standing at opposite corners of an n X n lattice without meeting each other.

The two men start to move simultaneously at the same constant speed; one always moves to the right or upward, the other always moves to the left or downward.

All terms are even.

Examples

			Let the lattice points of a lattice of size 2 X 2 be labeled 1,2,3,4,5,6,7,8,9, and let men A and B start at points 1 and 9, respectively.
                          man B
                          starts
             7---8---9 <-- here
             |   |   |
   man A     4---5---6
   starts    |   |   |
    here --> 1---2---3
.
The lattice paths available for A are 14789, 14589, 14569, 12589, 12569, 12369 and those available for B are 98741, 98541, 98521, 96541, 96521, 96321.
A002894(2) = 36 is the number of different ways to exchange positions, that is, 6 X 6 or (C(4,2))^2.
The different ways they can meet halfway on their paths are as follows:
If A selects 14789, B must select 98741. If A selects one of 14589, 14569, 12589, 12569, B must select one of 98541, 98521, 96541, 96521. If A selects 12369, B must select 96321.
Therefore the total number of choices available is 1 + 4*4 + 1 = 18 and this is given by A005260(2) = (C(2,0))^4 + (C(2,1))^4 + (C(2,2))^4 = 18.
Therefore the total number of such different pairs is a(2) = 36 - 18 = 18.
		

Crossrefs

Cf. A005260, A002894.

Formula

a(n) = A002894(n) - A005260(n).