Vol. 34, No. 3, 1970

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 269: 1
Vol. 268: 1  2
Vol. 267: 1  2
Vol. 266: 1  2
Vol. 265: 1  2
Vol. 264: 1  2
Vol. 263: 1  2
Vol. 262: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Editorial Board
Officers
Special Issues
Submission Guidelines
Submission Form
Subscriptions
Contacts
Author Index
To Appear
 
ISSN: 0030-8730
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” (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
Milestones
Received: 14 May 1969
Published: 1 September 1970
Authors
Donald E. Knuth