In this thesis, we describe Schensted's algorithm for finding the length of a longest increasing subsequence of a finite sequence. Schensted's algorithm also constructs a bijection between permutations of the first N natural numbers and standard bitableaux of size N. We also describe the Hillman-Grassl algorithm which constructs a bijection between reverse plane partitions and the solutions in natural numbers of a linear equation involving hook lengths. Pascal programs and sample output for both algorithms appear in the appendix. In addition, we describe the operations on standard bitableaux corresponding to the operations of inverting and reversing permutations. Finally, we show that these operations generate the dihedral group D_4
Identifer | oai:union.ndltd.org:unt.edu/info:ark/67531/metadc503902 |
Date | 08 1900 |
Creators | Sutherland, David C. (David Craig) |
Contributors | Kung, Joseph P. S., Lewis, Paul Weldon |
Publisher | North Texas State University |
Source Sets | University of North Texas |
Language | English |
Detected Language | English |
Type | Thesis or Dissertation |
Format | iv, 101 leaves, Text |
Rights | Public, Sutherland, David C. (David Craig), Copyright, Copyright is held by the author, unless otherwise noted. All rights reserved. |
Page generated in 0.0022 seconds