Involutions in the symmetric group : containment properties and parallels to general permutations / Aaron D. Jaggard.

Format:

Book

Manuscript

Microformat

Thesis/Dissertation

Author/Creator:

Jaggard, Aaron D.

Contributor:

Wilf, Herbert S., 1931-2012, advisor.

University of Pennsylvania.

Language:

English

Subjects (All):

Penn dissertations--Mathematics.

Mathematics--Penn dissertations.

Local Subjects:

Penn dissertations--Mathematics.

Mathematics--Penn dissertations.

Physical Description:

x, 100 pages : illustrations ; 29 cm

Production:

2003.

Summary:

We investigate different types of permutation containment, principally by involutions. We give an exact count of the n-involutions which contain as a subsequence a given k-permutation. This allows us to improve an asymptotic result recently given by McKay, Morse, and Wilf and to define a related notion of equivalence for permutations. We examine questions related to this equivalence. One of these leads to a new proof of a result of Sagan and Stanley which gives the number of standard Young tableaux which contain a given subtableau. We then give some exact and asymptotic results for subsequence containment of permutations by fixed-point-free involutions and asymptotic results for subsequence containment by cyclic permutations.

We then turn to questions of pattern containment and avoidance by involutions. We show that the patterns 12tau and 21tau are equally restrictive, as are the patterns 123tau and 321tau. These imply many of the known results for involutions avoiding a single pattern and also give new results. The second of these results implies a conjecture of Guibert and thus completes the classification of permutations of length 4 according to pattern avoidance by involutions. We adapt techniques which Babson and West used to prove similar results for pattern avoidance by permutations.

Our work was initially motivated by parallels between involutions and general permutations shown by McKay, Morse, and Wilf in the context of subsequence containment. In addition to sharpening some of their results, we show that there are parallels between involutions and permutations in the context of pattern avoidance. These resemblances between involutions and all permutations suggest areas for future work.

Notes:

Adviser: Herbert S. Wilf.

Thesis (Ph.D. in Mathematics) -- University of Pennsylvania, 2003.

Includes bibliographical references.

Local Notes:

University Microfilms order no.: 3087414.

OCLC:

244972945