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

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.

Links

Table of n, a(n) for n=0..19.

Formula

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

Example

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.

Sequence in context: A260332 A254999 A364167 * A024486 A052635 A366001

Adjacent sequences: A357600 A357601 A357602 * A357604 A357605 A357606

Keyword

nonn,easy

Author

Janaka Rodrigo, Oct 05 2022

Status

approved