Enumeration of n-Permutations Avoiding a Given k-Permutation

This thesis is a survey of the research on enumerations of n-permutations that avoid a given k-permutation. It contains proofs for the nth Catalan number and there bijections between permutations that avoid a given 3-permutation and Dyck paths, allowing us to conclude that the number of n-permutations that avoid a given 3-permutation is 1/(n+1) (2n)Cn and that L(π) = 4 when π is a 3-permutation. This is followed by proving that L(123...k) = (k − 1). Marcus and Tardos' original proof of the Stanley-Wilf conjecture is explored, followed by contributions made to the field since the Stanley-Wilf conjecture was proven and a discussion of related open problems.