A Central Limit Theorem for Repeating Patterns

2012/04/13 by Abrams, Aaron, Babson, Eric, Landau, Henry +2
#05A16 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1204.2872

Abstract

We prove a central limit theorem for the length of the longest subsequence of a random permutation which follows one of a class of repeating patterns. This class includes every fixed pattern of ups and downs having at least one of each, such as the alternating case considered by Stanley in arXiv:math/0511419 and Widom in arXiv:math/0511533. In every case considered the convergence in the limit of long permutations is to normal with mean and variance linear in the length of the permutation.

Related

• On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation
• A central limit theorem for a new statistic on permutations
• Longest subsequence for certain repeated up/down patterns in random permutations avoiding a pattern of length three
• Patterns in random permutations avoiding some sets of multiple patterns
• Longest increasing subsequences of random colored permutations