login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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[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

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

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.

License Agreements, Terms of Use, Privacy Policy. .

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