The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 =  a = [[1, 3], [3, 5]] a = [[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 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 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_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_12 = 3. Similarly, a_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_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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 21 10:25 EST 2022. Contains 350477 sequences. (Running on oeis4.)