
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
789 < here
  
man A 456
starts   
here > 123
.
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.
