2012/11/29 by Cheyne Homberger, Homberger, Cheyne
Biochemistry, Genetics and Molecular Biology · Engineering · #Combinatorics (math.CO) #FOS: Mathematics #Genome Rearrangement Algorithms #Optimization and Packing Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1211.7117
openalex publication_date 2012/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.