|
| |
|
|
A240594
|
|
Number of lattice paths from NW to SE corner in an L-shaped 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 ij-th entry of matrix a[N] is defined as follows.
Definition 1: Take an N X N square grid and remove an (N+1-i) X (N+1-j) rectangle from the northeast corner. Then the ij-th entry of a[N] gives the number of lattice paths from the northwest to southeast corner in the resulting L-shaped figure. (Paths may only travel east or south on any step.)
Definition 2: The ij-th 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 i-th lowest card in hand 1 has a higher face value than the j-th 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 "hook-sum formula," computes a[N+1] from a[N]. To obtain the ij-th 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 (2N-choose-N). That is, a[N]_N+1,j = a[N]_i,N+1 = (2N-choose-N) 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 "hook-sum," h[N]_ij. Finally, the elements of a[N+1] are given by a[N+1]_ij = h[N]_ij - h[N]_i-1,j-1. (If i=1 or j=1, the second term in this formula is zero.)
|
|
|
LINKS
|
|
|
|
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 L-shaped 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 L-shaped 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 left-hand 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.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
