Counting fixed-length permutation patterns

MaRDI QIDQ5494778zbMATH OpenFDO

Authors Cheyne Homberger

Publication date 30 July 2014

Full work available at URL https://arxiv.org/abs/1211.7117, http://www.math.rochester.edu/ojac/vol7/Homberger_2012.pdf

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: We consider the problem of packing fixed-length patterns into a permutation, and develop a connection between the number of large patterns and the number of bonds in a permutation. Improving upon a result of Kaplansky and Wolfowitz, we obtain exact values for the expectation and variance for the number of large patterns in a random permutation. Finally, we are able to generalize the idea of bonds to obtain results on fixed-length patterns of any size, and present a construction that maximizes the number of distinct large patterns.

Recommendations

• Dense packing of patterns in a permutation
• Permutations containing many patterns
• On packing densities of permutations
• Colored patterns and their packing densities
• An answer to a question by Wilf on packing distinct patterns in a permutation

Cited in

(12)

• The minimum Manhattan distance and minimum jump of permutations
• Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations
• An answer to a question by Wilf on packing distinct patterns in a permutation
• Finding and counting permutations via CSPs
• Independence of permutation limits at infinitely many scales
• \((a, b)\)-rectangle patterns in permutations and words
• On the topology of the permutation pattern poset
• Prolific permutations and permuted packings: downsets containing many large patterns
• scientific article; zbMATH DE number 2186873 (Why is no real title available?)
• On the sparseness of the downsets of permutations via their number of separators
• A counting scheme and some algebraic properties of a class of special permutation patterns
• Counting king permutations on the cylinder

This page was built for publication: Counting fixed-length permutation patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5494778)