PATTERNS IN PERMUTATIONS AND INVOLUTIONS, A …

PATTERNS IN PERMUTATIONS AND INVOLUTIONS, A STRUCTURAL AND ENUMERATIVE APPROACH

By CHEYNE HOMBERGER

A DISSERTATION PRESENTED TO THE GRADUATE SCHOOL OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT

OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY UNIVERSITY OF FLORIDA 2014

c 2014 Cheyne Homberger 2

To Carol and Fred Gropper, my grandparents 3

ACKNOWLEDGMENTS First and foremost I'd like to thank my advisor, Miklo? s Bo? na, for his guidance and encouragement throughout the research process, and for his patience and understanding during my meandering course through graduate school. I also thank Vince Vatter, whose long discussions, advice, and friendship have been instrumental in my development as an academic. Thanks also to Michael Albert for his support and suggestions during our collaborations, and to the remainder of my supervisory committee: Andrew Vince, Meera Sitharam, and Kevin Keating, each of whom have helped me to become a more well-rounded researcher. This dissertation is a product of the combined support of those around me, each of whom have left a profound impact both on this work and on my time in graduate school. The graduate student community, with its many seminars and happy hours, has made the last five years more fun than it should have been. I am grateful for all of my friends and colleagues, both for their support during the busy times and for their distractions during the slow. My time at the University of Florida has been marked with frequent diversions -- organizing seminars and serving on administrative committees has kept me busy and interested, and I am thankful for all of the coworkers and friends I've met along the way. Special thanks to Margaret, Connie, and the rest of the math department staff for helping me to find more travel funding than any graduate student deserves. Finally, I am thankful for my students, who taught me to never stop looking for a simpler way to present a problem. I am grateful for my wonderfully supportive family, who have always always encouraged me in every endevour, fostered every interest, and listened to me long before I had anything to say. Finally, thank you to my best friend and favorite travel partner Elizabeth, for her support, editing skills, and understanding during the last five years, and for pushing me to be better in every way.

4

TABLE OF CONTENTS

page

ACKNOWLEDGMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

CHAPTER

1 PRELIMINARIES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.1 Permutation Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.1.1 Permutations and Patterns . . . . . . . . . . . . . . . . . . . . . . . 13 1.1.2 Wilf-Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.1.3 Geometric Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.2 Dyck Paths and the Catalan Numbers . . . . . . . . . . . . . . . . . . . . 22 1.2.1 Paths on the Integer Lattice . . . . . . . . . . . . . . . . . . . . . . 22 1.2.2 Enumerating Dyck Paths . . . . . . . . . . . . . . . . . . . . . . . . 23 1.2.3 The Catalan Numbers . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.3 Four Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.3.1 Permutations Avoiding 132 . . . . . . . . . . . . . . . . . . . . . . 26 1.3.2 Permutations Avoiding 123 . . . . . . . . . . . . . . . . . . . . . . 30 1.3.3 Permutations Avoiding 123 and 231 . . . . . . . . . . . . . . . . . 32 1.3.4 Ascents in 132-Avoiding Permutations . . . . . . . . . . . . . . . . 34

2 PATTERN EXPECTATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.1 Pattern Occurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.1.1 Pattern Expectation . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.1.2 Background and Data . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.2 123-avoiding Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.2.1 Class Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.2.2 Patterns of Length 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.2.3 Patterns of Length 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.2.4 Larger Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3 PATTERN AVOIDING INVOLUTIONS . . . . . . . . . . . . . . . . . . . . . . . 53

3.1 Definitions and Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.1.1 Previous Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.1.2 Simple Involutions . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

3.2 Simple 123-Avoiding Permutations . . . . . . . . . . . . . . . . . . . . . . 55 3.2.1 The Staircase Decomposition . . . . . . . . . . . . . . . . . . . . . 55 3.2.2 Iterative Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download