A240594 Number of lattice paths from NW to SE corner in an L-shaped grid.

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

Offset: 1

Author

Dana Mackenzie, Apr 08 2014

Keywords

• nonn

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.)

Examples

			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.
		

Links

• D. Mackenzie, Sun Bin's Legacy, 2014.

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.

Formula

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