

A240594


Number of lattice paths from NW to SE corner in an Lshaped grid.


0



1, 1, 3, 3, 5, 1, 4, 10, 4, 10, 16, 10, 16, 19, 1, 5, 15, 35, 5, 17, 35, 55, 15, 35, 53, 65, 35, 55, 65, 69, 1, 6, 21, 56, 126, 6, 26, 66, 126, 196, 21, 66, 126, 186, 231, 56, 126, 186, 226, 246, 126, 196, 231, 246, 251
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

This is actually a sequence of square matrices that has been converted to a sequence of numbers. The matrices are:
a[1] = [1]
a[2] = [[1, 3], [3, 5]]
a[3] = [[1, 4, 10], [4, 10, 16], [10, 16, 19]], etc.
The ijth entry of matrix a[N] is defined as follows.
Definition 1: Take an N X N square grid and remove an (N+1i) X (N+1j) rectangle from the northeast corner. Then the ijth entry of a[N] gives the number of lattice paths from the northwest to southeast corner in the resulting Lshaped figure. (Paths may only travel east or south on any step.)
Definition 2: The ijth entry of a[N] gives the number of ways to deal (2N) cards, labeled 1 to 2N, into two separate hands of N cards in such a way that the ith lowest card in hand 1 has a higher face value than the jth highest card in hand 2.
These two definitions are equivalent.
These matrices serve as the objective function in a linear assignment problem solved in reference (1). The problem is to find the N X N permutation matrix M that maximizes the inner product M dot a[N]. In reference (1) the matrices are called P^N and the order of the columns is reversed. See sequence A240567.
A remarkable recursive formula, called the "hooksum formula," computes a[N+1] from a[N]. To obtain the ijth element of a[N+1], first we "augment" a[N] by adding an (N+1)st row and column in which all the elements are the same and equal to (2NchooseN). That is, a[N]_N+1,j = a[N]_i,N+1 = (2NchooseN) for all i and j. Now, for each i and j, add all of the elements in a[N] that lie directly above or directly to the left of a[N]_ij, including a[N]_ij itself. This is called a "hooksum," h[N]_ij. Finally, the elements of a[N+1] are given by a[N+1]_ij = h[N]_ij  h[N]_i1,j1. (If i=1 or j=1, the second term in this formula is zero.)


LINKS

Table of n, a(n) for n=1..55.
D. Mackenzie, Sun Bin's Legacy, 2014.


FORMULA

See comments for recursive definition of a[N] as a sequence of matrices.


EXAMPLE

Start with a 2 X 2 square grid. Delete a 1 X 1 square from the northeast corner to obtain an Lshaped figure with three squares. There are 5 paths from the NW to SE corners: (E, S, E, S), (E, S, S, E), (S, E, E, S), (S, E, S, E), and (S, S, E, E). (Here E means "east" and S means "south".) Thus a[2]_22 = 5. Next, delete a 2 X 1 rectangle from the northeast corner to obtain an Lshaped figure with two squares and a horizontal line segment. Now there are 3 paths from NW to SE: (E, S, S, E), (S, E, S, E), and (S, S, E, E). Thus a[2]_12 = 3. Similarly, a[2]_21 = 3. (Note that all of the a[N] matrices are symmetric.) Finally, delete a 2 X 2 square from the 2 X 2 grid. This leaves only the lefthand edge and bottom edge of the grid intact. Then there is only 1 path from the NW to SE corner, which goes (S, S, E, E). Thus a[2]_11 = 1.


CROSSREFS

As noted above, A240567 describes the solutions of a linear optimization problem with objective matrix given by a[N]. A000984 gives the number of lattice paths in the "vacuous" case where we delete an i X 0 or 0 X j rectangle from the N X N grid.
Sequence in context: A109824 A011399 A205853 * A079887 A131843 A205550
Adjacent sequences: A240591 A240592 A240593 * A240595 A240596 A240597


KEYWORD

nonn


AUTHOR

Dana Mackenzie, Apr 08 2014


STATUS

approved



