Permutations, matrices, and generalized Young tableaux

Donald E. Knuth

Vol. 34 (1970), No. 3, 709–727

DOI: 10.2140/pjm.1970.34.709

Abstract

A generalized Young tableau of “shape” (p₁,p₂,⋯,p_m), where p₁ ≧ p₂ ≧⋯ ≧ p_m ≧ 1, is an array Y of positive integers y_ij, for 1 ≦ j ≦ p_i,1 ≦ i ≦ m, having monotonically nondecreasing rows and strictly increasing columns. By extending a construction due to Robinson and Schensted, it is possible to obtain a one-to-one correspondence between m × 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 + ⋯ + a_in times in Q, and the integer j occurs exactly a_1j + ⋯ + 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.

Mathematical Subject Classification

Primary: 05.30

Milestones

Received: 14 May 1969

Published: 1 September 1970