Vol. 34, No. 3, 1970

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Vol. 321: 1  2
Online Archive
The Journal
Editorial Board
Submission Guidelines
Submission Form
Policies for Authors
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author Index
To Appear
Other MSP Journals
Permutations, matrices, and generalized Young tableaux

Donald E. Knuth

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

A generalized Young tableau of “shape” (p1,p2,,pm), where p1 p2 pm 1, is an array Y of positive integers yij, for 1 j pi,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 ai1 + + ain times in Q, and the integer j occurs exactly a1j + + amj 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
Received: 14 May 1969
Published: 1 September 1970
Donald E. Knuth