Permutations, matrices, and generalized Young tableaux (Q2540557)

A generalized Young tableau of ``shape'' \((p_1,p_2,\ldots,p_m)\), where \(p_1\ge p_2\ge \cdots\ge p_m \ge 1\), is an array \(Y\) of positive integers \(y_{ij}\), for \(1\le j\le p_i\), \(1\le i\le m\), having monotonically nondecreasing rows and strictly increasing columns. By extending a construction due to G. de B. Robinson and C. Schensted, it is possible to obtain a one-to-one correspondence between \(m\times n\) matrices \(A\) of nonnegative integers and ordered pairs \((P,Q)\) of generalized Young tableaux, where \(P\) and \(Q\) have the same shape, the integer \(i\) occurs exactly \(a_{i1} + \ldots + a_{in}\) times in \(Q\), and the integer \(j\) occurs exactly \(a_{1j} + \ldots + a_{mj}\) times in \(P\). A similar correspondence can be given for the case that \(A\) is a matrix of zeros and ones, and the shape of \(Q\) is the transpose of the shape of \(P\). The correspondences have several remarkable properties.