Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Publication
- Publication Type
Articles 1 - 4 of 4
Full-Text Articles in Discrete Mathematics and Combinatorics
The Expected Number Of Patterns In A Random Generated Permutation On [N] = {1,2,...,N}, Evelyn Fokuoh
The Expected Number Of Patterns In A Random Generated Permutation On [N] = {1,2,...,N}, Evelyn Fokuoh
Electronic Theses and Dissertations
Previous work by Flaxman (2004) and Biers-Ariel et al. (2018) focused on the number of distinct words embedded in a string of words of length n. In this thesis, we will extend this work to permutations, focusing on the maximum number of distinct permutations contained in a permutation on [n] = {1,2,...,n} and on the expected number of distinct permutations contained in a random permutation on [n]. We further considered the problem where repetition of subsequences are as a result of the occurrence of (Type A and/or Type B) replications. Our method of enumerating the Type A replications causes double …
Covering Arrays For Equivalence Classes Of Words, Joshua Cassels, Anant Godbole
Covering Arrays For Equivalence Classes Of Words, Joshua Cassels, Anant Godbole
Undergraduate Honors Theses
Covering arrays for words of length t over a d letter alphabet are k × n arrays with entries from the alphabet so that for each choice of t columns, each of the dt t-letter words appears at least once among the rows of the selected columns. We study two schemes in which all words are not considered to be different. In the first case, words are equivalent if they induce the same partition of a t element set. In the second case, words of the same weighted sum are equivalent. In both cases we produce logarithmic upper bounds …
Combinatorial Optimization Of Subsequence Patterns In Words, Matthew R. Just
Combinatorial Optimization Of Subsequence Patterns In Words, Matthew R. Just
Electronic Theses and Dissertations
Packing patterns in words concerns finding a word with the maximum number of a prescribed pattern. The majority of the work done thus far is on packing patterns into permutations. In 2002, Albert, Atkinson, Handley, Holton and Stromquist showed that there always exists a layered permutation containing the maximum number of a layered pattern among all permutations of length n. Consequently, the packing density for all but two (up to equivalence) permutation patterns up to length 4 can be obtained. In this thesis we consider the analogous question for colored patterns and permutations. By introducing the concept of colored blocks …
Packing Densities Of Colored And Non-Colored Patterns, Matthew R. Just
Packing Densities Of Colored And Non-Colored Patterns, Matthew R. Just
GS4 Georgia Southern Student Scholars Symposium
Pattern packing concerns finding an optimal permutation that contains the maximum number of occurrences of a given pattern and computing the corresponding packing density. In many instances such an optimal permutation can be characterized directly and the number of occurrences of the pattern in interest may be enumerated explicitly. In more complicated patterns a direct characterization may be more challenging, however computational results for long permutations can help provide an indirect characterization of the general form of an optimal permutation. Much work has been done on the study of pattern packing in layered patterns, as the optimal permutation of a …