cp's OEIS Frontend

The problem of extracting this cube root pitted an abacus salesman against Nobel Prize winning physicist Richard Feynman one afternoon in Rio de Janeiro.

An algebraic number of degree 3 and denominator 10; minimal polynomial 100x^3 - 172903. - Charles R Greathouse IV, Apr 20 2016

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

A precise definition of a(n) is as follows. Let p^n_ij denote the number of ways to deal 2n cards into two hands (n cards per hand) such that the i-th lowest card in hand 1 is greater than the j-th lowest card in hand 2. Let P^n denote the n X n matrix whose ij-th entry is p^n_ij. Let M denote the n X n permutation matrix that has the maximum inner product with P^n. As proved in Mackenzie (2014), provided n is sufficiently large, the optimal permutation matrix M consists of a(n) 1's on the "anti-main diagonal" in the first a(n) rows, followed by (n-a(n)) 1's that all lie on the a(n)-th diagonal below the main diagonal. The following exact formula holds for all n less than 60 and for all n greater than 10 million:

a(n) = max{k: (n-choose-k)^2 + sum_{j=0..(n-k)} (2n-choose-j) >= (2n-choose-n)}.

The formula is conjectured to hold for all n between 60 and 10 million, as well.

Note: a(1) and a(2) are undefined, so the first number given is a(3).