|
%I #9 Mar 24 2017 00:47:56
%S 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,
%T 35,55,65,69,1,6,21,56,126,6,26,66,126,196,21,66,126,186,231,56,126,
%U 186,226,246,126,196,231,246,251
%N Number of lattice paths from NW to SE corner in an L-shaped grid.
%C This is actually a sequence of square matrices that has been converted to a sequence of numbers. The matrices are:
%C a[1] = [1]
%C a[2] = [[1, 3], [3, 5]]
%C a[3] = [[1, 4, 10], [4, 10, 16], [10, 16, 19]], etc.
%C The ij-th entry of matrix a[N] is defined as follows.
%C 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.)
%C 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.
%C These two definitions are equivalent.
%C 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.
%C 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.)
%H D. Mackenzie, <a href="http://arxiv.org/abs/1404.1093">Sun Bin's Legacy</a>, 2014.
%F See comments for recursive definition of a[N] as a sequence of matrices.
%e 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.
%Y 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.
%K nonn
%O 1,3
%A _Dana Mackenzie_, Apr 08 2014
|
