Results 1 to 10 of about 37 (37)
Enumerating two permutation classes by the number of cycles [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 We enumerate permutations in the two permutation classes $\text{Av}_n(312, 4321)$ and $\text{Av}_n(321, 4123)$ by the number of cycles each permutation admits. We also refine this enumeration with respect to several statistics.
Kassie Archer
doaj +1 more source
Two examples of Wilf-collapse [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 Two permutation classes, the X-class and subpermutations of the increasing oscillation are shown to exhibit an exponential Wilf-collapse. This means that the number of distinct enumerations of principal subclasses of each of these classes grows much more
Michael Albert +2 more
doaj +1 more source
Enumeration of Stack-Sorting Preimages via a Decomposition Lemma [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 We give three applications of a recently-proven "Decomposition Lemma," which allows one to count preimages of certain sets of permutations under West's stack-sorting map $s$.
Colin Defant
doaj +1 more source
Enumeration of Dumont permutations avoiding certain four-letter patterns [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 In this paper, we enumerate Dumont permutations of the fourth kind avoiding or containing certain permutations of length 4. We also conjecture a Wilf-equivalence of two 4-letter patterns on Dumont permutations of the first kind.
Alexander Burstein, Opel Jones
doaj +1 more source
The number of distinct adjacent pairs in geometrically distributed words [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 A sequence of geometric random variables of length $n$ is a sequence of $n$ independent and identically distributed geometric random variables ($\Gamma_1, \Gamma_2, \dots, \Gamma_n$) where $\mathbb{P}(\Gamma_j=i)=pq^{i-1}$ for $1~\leq~j~\leq~n$ with $p+q=
Margaret Archibald +5 more
doaj +1 more source
Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 Defant, Engen, and Miller defined a permutation to be uniquely sorted if it has exactly one preimage under West's stack-sorting map. We enumerate classes of uniquely sorted permutations that avoid a pattern of length three and a pattern of length four by
Hanna Mularczyk
doaj +1 more source
Certificate complexity and symmetry of nested canalizing functions [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 Boolean nested canalizing functions (NCFs) have important applications in molecular regulatory networks, engineering and computer science. In this paper, we study their certificate complexity.
Yuan Li, Frank Ingram, Huaming Zhang
doaj +1 more source
Snow Leopard Permutations and Their Even and Odd Threads [PDF]
Discrete Mathematics & Theoretical Computer Science, 2016 Caffrey, Egge, Michel, Rubin and Ver Steegh recently introduced snow leopard permutations, which are the anti-Baxter permutations that are compatible with the doubly alternating Baxter permutations. Among other things, they showed that these permutations
Eric S. Egge, Kailee Rubin
doaj +1 more source
Equivalence classes of mesh patterns with a dominating pattern [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 Two mesh patterns are coincident if they are avoided by the same set of permutations, and are Wilf-equivalent if they have the same number of avoiders of each length.
Murray Tannock, Henning Ulfarsson
doaj +1 more source
Flip-sort and combinatorial aspects of pop-stack sorting [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 Flip-sort is a natural sorting procedure which raises fascinating combinatorial questions. It finds its roots in the seminal work of Knuth on stack-based sorting algorithms and leads to many links with permutation patterns. We present several structural,
Andrei Asinowski +2 more
doaj +1 more source