Find results with:

Add another field

Search by date

to

Searching collections:

Dartmouth Dissertations

Add or remove collections

Home Dartmouth Dissertations Page 1

Reference URL

To link to the entire object, paste this link in email, IM or document

To embed the entire object, paste this HTML in website

To link to this page, paste this link in email, IM or document

To embed this page, paste this HTML in website

Pattern avoiding permutations & rook placements / by Jonathan S. Bloom.

you wish to report:

Your comment:

Your Name:

Submit

Cancel

...

Back to top

Powered by CONTENTdm®

Author	Bloom, Jonathan S.
Title	Pattern avoiding permutations & rook placements / by Jonathan S. Bloom.
Date	2014
Abstract	In Chapter 2 we look at the distribution of permutation statistics in the context of pattern-avoiding permutations. The first part of this chapter deals with a recursively defined bijection of Robertson [37] between 123- and 132-avoiding permutations. We introduce the general notion of permutation templates and pivots in order to give a non-recursive pictorial reformulation of Robertson's bijection. This new description in turn makes it obvious that this bijection preserves the number of fixed points and exceedances of a permutation. This confirms a conjecture of Robertson from the 2003 Integers conference. In the last part of Chapter 2 we consider a conjecture of Sagen [23] involving the distribution of descents and patterns of length 4. In particular, we introduce an explicit bijection between 2413- and 1423-avoiding permutations that preserves descents as well as many other permutation statistics. This work generalizes and simplifies Stankova's bijection in [45] which is fundamental to the classification of Wilf-equivalence classes for patterns of length 4. In Chapter 3 we shift focus and consider an important bijection, due to Backlin, West, and Xin [3], in the context of pattern avoiding rook placements. Using the notion of pivots from Chapter 2, we prove that this bijection has an equivalent, yet far from obvious, definition in terms of Fomin's growth diagrams. Armed with this new characterization, it becomes clear that this bijection commutes with inverses. This answers a question first posed by Bousquet-M?lou and Steingr?msson [15] and later by Krattentahler [33]. Continuing our study of pattern avoiding rook placements, we study shape-Wilf-equivalence in Chapter 4. Although Stankova and West in [43] first established that 231 and 312 are shape-Wilf-equivalent, their proof is nonbijective and somewhat complicated. Here we give a bijective and elucidating proof of this result, that, besides its simplicity, yields many important enumerative results that we explore in Chapter 5. In the context of matchings and set partitions we prove several new enumerative results. In particular, we define a notion of pattern-avoiding matchings and set partitions that not only extends the well studied idea of k-crossings and k-nestings but also plays nicely with the concept of shape-Wilf-equivalence. Although 123-avoiding matchings had previously been counted [18] we provide the first enumeration of 231-avoiding matchings and set partitions using the main idea from Chapter 4. Using similar enumerative techniques we also provide a new and simpler proof of B?na's celebrated formula for the generating function of 2314-avoiding permutations.
Description	vii, 158 leaves : ill.
Format	application/pdf
College	Dartmouth College. Department of Mathematics.
Issuing Body	Dartmouth Dissertations are made available through the Dartmouth Digital Library.
Degree	Thesis (Ph.D.)--Dartmouth College.
Copyright	All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means without permission in writing from the author.
DOI	http://dx.doi.org/10.1349/ddlp.1260

Title	Page 1
Full Text	PATTERN AVOIDING PERMUTATIONS & ROOK PLACEMENTS A Thesis Submitted to the Faculty in partial ful llment of the requirements for the degree of Doctor of Philosophy in Mathematics by Jonathan S. Bloom DARTMOUTH COLLEGE Hanover, New Hampshire May 2014 Examining Committee: Sergi Elizalde, Chair Rosa Orellana Vince Vatter Peter Winkler F. Jon Kull, Ph.D. Dean of Graduate Studies

Find results with:

Searching collections:

Home Dartmouth Dissertations Page 1

Pattern avoiding permutations & rook placements / by Jonathan S. Bloom.

Object Description

Description

Pattern avoiding permutations & rook placements / by...

Pattern avoiding permutations & rook placements / by...

	All
	Pages Enter page numbers or page ranges separated by commas. For example: 1,3,5-12