Search

A generic rectangulation is a partition of a rectangle into finitely many interior-disjoint rectangles, such that no four rectangles meet in a point. In this work we present a versatile algorithmic framework for exhaustively generating a large variety of different classes of generic rectangulations. Our algorithms work under very mild assumptions, and apply to a large number of rectangulation classes known from the literature, such as generic rectangulations, diagonal rectangulations, 1-sided/area-universal, block-aligned rectangulations, and their guillotine variants, including aspect-ratio-universal rectangulations. They also apply to classes of rectangulations that are characterized by avoiding certain patterns, and in this work we initiate a systematic investigation of pattern avoidance in rectangulations. Our generation algorithms are efficient, in some cases even loopless or constant amortized time, i.e., each new rectangulation is generated in constant time in the worst case or on average, respectively. Moreover, the Gray codes we obtain are cyclic, and sometimes provably optimal, in the sense that they correspond to a Hamilton cycle on the skeleton of an underlying polytope. These results are obtained by encoding rectangulations as permutations, and by applying our recently developed permutation language framework. [ABSTRACT FROM AUTHOR]

Let πn be a uniformly chosen random permutation on [n]. Using an analysis of the probability that two overlapping consecutive k-permutations are order isomorphic, we show that the expected number of distinct consecutive patterns of all lengths k ∈ {1, 2,..., n} in πn is n 2 2 (1 - o (1)) as n → ∞. This exhibits the fact that random permutations pack consecutive patterns near-perfectly. [ABSTRACT FROM AUTHOR]

We define four new shuffling algorithms on permutations. For each algorithm, we characterize and enumerate the sets of permutations that are sorted after k iterations of the algorithm and we determine properties of the corresponding generating functions. For three of the algorithms, the sets of sortable permutations can be seen to be permutation classes for any nonnegative integer k. [ABSTRACT FROM AUTHOR]

We investigate the connections between patterns in permutations and forbidden configurations in restricted elections, first discovered by Lackner and Lackner, in order to enhance the approach initiated by the two mentioned authors. More specifically, our achievements are essentially two. First, we define a new type of domain restriction, called enriched group-separable. Enriched group-separable elections are a subset of group-separable elections, which describe a special, still natural, situation that can arise in the context of group-separability. The exact enumeration of group-separable elections has been very recently determined by Karpov. Here we give a recursive characterization for enriched group-separable elections, from which we are able to find a recurrence relation and a closed formula expressing their number. Our second achievement is a generalization of a result of Lackner and Lackner, concerning the connection between permutation patterns and forbidden configurations with 3 voters. Our result relates forbidden configurations with the strong order on pairs of permutations, a notion which is still largely undeveloped, and suggests a potential approach for the determination of upper bounds for restricted elections whose forbidden configurations contains at least one configuration with 3 voters. [ABSTRACT FROM AUTHOR]

Permutation classes are sets of permutations defined by the absence of certain substructures. In some cases permutation classes can be decomposed as unions of subclasses. We use combinatorial specifications automatically discovered by Combinatorial Exploration: An algorithmic framework for enumeration, Albert et al. 2022, to uniformly generate large random permutations in a permutation class, and apply clustering methods to partition them into interesting subclasses. We seek to automate as much of this process as possible. [ABSTRACT FROM AUTHOR]

We continue our study of a new boundedness condition for affine permutations, motivated by the fruitful concept of periodic boundary conditions in statistical physics. We focus on bounded affine permutations of size N that avoid the monotone decreasing pattern of fixed size m. We prove that the number of such permutations is asymptotically equal to (m - 1) 2 N N (m - 2) / 2 times an explicit constant as N → ∞ . For instance, the number of bounded affine permutations of size N that avoid 321 is asymptotically equal to 4 N (N / 4 π) 1 / 2 . We also prove a permuton-like result for the scaling limit of random permutations from this class, showing that the plot of a typical bounded affine permutation avoiding m ⋯ 1 looks like m - 1 random lines of slope 1 whose y intercepts sum to 0. [ABSTRACT FROM AUTHOR]

We present several completely general diversity metrics to quantify the problem-solving capacity of any public policy decision-making process. These metrics can be used alongside existing policy process analysis methods and capture aspects of the policy process that have not been considered before. This is performed by modelling the policy process using a declarative process paradigm. We introduce a class of traces, called first-passage traces, to represent different executions of the declarative processes. Heuristics of what properties a diversity measure of such processes ought to satisfy are used to derive two different metrics for these processes in terms of the set of first-passage traces. These metrics turn out to have formulations in terms of the entropies of two different random variables on the set of traces of the processes. In addition, we introduce a measure of "goodness" that allows for comparisons of policy processes with respect to the prescribed notion of "goodness". [ABSTRACT FROM AUTHOR]

We enumerate involutions avoiding any single pattern of length three according to the statistic 'number of visible pairs', namely, the number of non-adjacent columns in the bargraph representation of a given permutation that is mutually visible to each other. The proofs are combinatorial and reside on well-known bijections between pattern avoiding involutions and lattice paths. [ABSTRACT FROM AUTHOR]

The notion of a p-Riordan graph generalizes that of a Riordan graph, which, in turn, generalizes the notions of a Pascal graph and a Toeplitz graph. In this paper we introduce the notion of a p-Riordan word, and show how to encode p-Riordan graphs by p-Riordan words. For special important cases of Riordan graphs (the case p = 2 ) and oriented Riordan graphs (the case p = 3 ) we provide alternative encodings in terms of pattern-avoiding permutations and certain balanced words, respectively. As a bi-product of our studies, we provide an alternative proof of a known enumerative result on closed walks in the cube. [ABSTRACT FROM AUTHOR]

For an arbitrary finite permutation group G, subgroup of the symmetric group S ℓ , we determine the permutations involving only members of G as ℓ -patterns, i.e. avoiding all patterns in the set S ℓ \ G . The set of all n-permutations with this property constitutes again a permutation group. We consequently refine and strengthen the classification of sets of permutations closed under pattern involvement and composition that is due to Atkinson and Beals. [ABSTRACT FROM AUTHOR]

We study permutations p such that both p and p 2 avoid a given pattern q. We obtain a generating function for the case of q = 312 (equivalently, q = 231), we prove that if q is monotone increasing, then above a certain length, there are no such permutations, and we prove an upper bound for q = 321. We also present some intriguing questions in the case of q = 132. [ABSTRACT FROM AUTHOR]

After fixing a canonical ordering (or labeling) of the elements of a finite poset, one can associate each linear extension of the poset with a permutation. Some recent papers consider specific families of posets and ask how many linear extensions give rise to permutations that avoid certain patterns. We build off of two of these papers. We first consider pattern avoidance in k-ary heaps, where we obtain a general result that proves a conjecture of Levin, Pudwell, Riehl, and Sandberg in a special case. We then prove some conjectures that Anderson, Egge, Riehl, Ryan, Steinke, and Vaughan made about pattern-avoiding linear extensions of rectangular posets. [ABSTRACT FROM AUTHOR]

A new class of functions with a unique identification minor is introduced: functions determined by content and singletons. Relationships between this class and other known classes of functions with a unique identification minor are investigated. Some properties of functions determined by content and singletons are established, especially concerning invariance groups and similarity. [ABSTRACT FROM AUTHOR]

An important feature of the time series in the real world is that its distribution has different degrees of asymmetry, which is what we call irreversibility. In this paper, we propose a new method named permutation pattern (PP) to calculate the Kullback–Leibler divergence ( D KL ) and the Jensen–Shannon divergence ( D JS ) to explore the irreversibility of time series. Meanwhile, we improve D JS and obtain a complete mean divergence ( D m ) through averaging D KL of a time series and its inverse time series. The variation trend of D m is similar to D JS , but the value of D m is slightly larger and the description of irreversibility is more intuitive. Furthermore, we compare D JS and D m calculated by PP with those calculated by the horizontal visibility graph, and discuss their respective characteristics. Then, we investigate the advantages of D JS and D m through length variation, dynamic time variation, multiscale and so on. It is worth mentioning that we introduce Score and variance to analyze the practical significance of stock irreversibility. [ABSTRACT FROM AUTHOR]

In this paper, some fuzzy nature of a newly constructed an algebraic structure Gp (p ≥ 5 and p is always prime) were been investigated by construction of a modified fuzzy membership function on Gp and it was used to investigate the ∝ - cut lévélof Gp and it was established that the ∝ - cut lévél of Gp is the domain Gp|wp-1, the support(Supp) of Gp was also been investigated and we arrived at a conclusion that, the support of the Gp structure is the entire domain of the structure (Gp). [ABSTRACT FROM AUTHOR]

We consider the number of passes a permutation needs to take through a stack if we only pop the appropriate output values and start over with the remaining entries in their original order. We define a permutation π to be k -pass sortable if π is sortable using k passes through the stack. Permutations that are 1 -pass sortable are simply the stack sortable permutations as defined by Knuth. We define the permutation class of 2 -pass sortable permutations in terms of their basis. We also show all k -pass sortable classes have finite bases by giving bounds on the length of a basis element of the permutation class for any positive integer k. Finally, we define the notion of tier of a permutation π to be the minimum number of passes after the first pass required to sort π. We then give a bijection between the class of permutations of tier t and a collection of integer sequences studied by Parker [The combinatorics of functional composition and inversion, PhD thesis, Brandeis University (1993)]. This gives an exact enumeration of tier t permutations of a given length and thus an exact enumeration for the class of (t + 1) -pass sortable permutations. Finally, we give a new derivation for the generating function in [S. Parker, The combinatorics of functional composition and inversion, PhD thesis, Brandeis University (1993)] and an explicit formula for the coefficients. [ABSTRACT FROM AUTHOR]

Let a1....,an be a permutation of [n]. Two disjoint order-isomorphic subsequences are called twins. We show that every permutation of [n] contains twins of length Ω (n3/5) improving the trivial bound of Ω (n1/2). We also show that a random permutation contains twins of length Ω (n2/3), which is sharp. [ABSTRACT FROM AUTHOR]

This paper examine certain behavior of some permutation statistics on the pattern ωi defined by Garba and Ibrahim ([GI09]). We investigate the permutation statistics that are equidistributed on ωi∈Gp for any prime p≥5. This to a larger extent helped in identifying ωi as an Eulerian distribution. The graph permutation of ωi and the graph of 132-avoiding pattern of ωi were also studied. [ABSTRACT FROM AUTHOR]

We enumerate involutions according to the joint distribution of left-to-right and right-to-left maxima. From this computation we deduce the distribution of the static "number of visible pairs", namely, the number of non-adjacent columns in the bargraph representation of a given permutation that are mutually visible to each other. The corresponding generating functions are expressible in terms of formal continued fractions. We obtain the same distribution over the set of involutions avoiding either the pattern 3412 or 4321. The proofs reside on a well-known bijection between involutions and labeled Motzkin paths. [ABSTRACT FROM AUTHOR]

Given permutations σ of size k and π of size n with k < n, the permutation pattern matching problem is to decide whether σ occurs in π as an order-isomorphic subsequence. We give a linear-time algorithm in case both π and σ avoid the two size-3 permutations 213 and 231. For the special case where only σ avoids 213 and 231, we present a O(max(kn 2 , n 2 log log n)-time algorithm. We extend our research to bivincular patterns that avoid 213 and 231 and present a O(kn 4)-time algorithm. Finally we look at the related problem of the longest subsequence which avoids 213 and 231.

We develop the technique of reduced word manipulation to give a range of results concerning reduced words and permutations more generally. We prove a broad connection between pattern containment and reduced words, which specializes to our previous work for vexillary permutations. We also analyze general tilings of Elnitsky's polygon and demonstrate that these are closely related to the patterns in a permutation. Building on previous work for commutation classes, we show that reduced word enumeration is monotonically increasing with respect to pattern containment. Finally, we give several applications of this work. We show that a permutation and a pattern have equally many reduced words if and only if they have the same length (equivalently, the same number of 21-patterns) and that they have equally many commutation classes if and only if they have the same number of 321-patterns. We also apply our techniques to enumeration problems of pattern avoidance and give a bijection between 132-avoiding permutations of a given length and partitions of that same size, as well as refinements of these data and a connection to the Catalan numbers. [ABSTRACT FROM AUTHOR]

Consider a finite sequence of permutations of the elements 1, . . . , n with the property that each element changes its position by at most 1 from any permutation to the next. We call such a sequence a tangle, and we define a move of element i to be a maximal subsequence of at least two consecutive permutations during which its positions form an arithmetic progression of common difference +1 or -1. We prove that for any initial and final permutations, there is a tangle connecting them in which each element makes at most 5 moves, and another in which the total number of moves is at most 4n. On the other hand, there exist permutations that require at least 3 moves for some element, and at least 2n - 2 moves in total. If we further require that every pair of elements exchange positions at most once, then any two permutations can be connected by a tangle with at most O(log n) moves per element, but we do not know whether this can be reduced to O(1) per element, or to O(n) in total. A key tool is the introduction of certain restricted classes of tangle that perform pattern-avoiding permutations. [ABSTRACT FROM AUTHOR]

A permutation $σ$ contains the permutation $τ$ if there is a subsequence of $σ$ order isomorphic to $τ$. A permutation $σ$ is $τ$-avoiding if it does not contain the permutation $τ$. For any $n$, the popularity of a permutation $τ$, denoted $A$$n$($τ$), is the number of copies of $τ$ contained in the set of all 132-avoiding permutations of length $n$. Rudolph conjectures that for permutations $τ$ and $μ$ of the same length, $A$$n$($τ$) ≤ $A$$n$($μ$) for all $n$ if and only if the spine structure of $τ$ is less than or equal to the spine structure of $μ$ in refinement order. We prove one direction of this conjecture, by showing that if the spine structure of $τ$ is less than or equal to the spine structure of $μ$, then $A$$n$($τ$) ≤ $A$$n$($μ$) for all $n$. We disprove the opposite direction by giving a counterexample, and hence disprove the conjecture.

In the past decade, the use of ordinal patterns in the analysis of time series and dynamical systems has become an important tool. Ordinal patterns (otherwise known as a permutation patterns) are found in time series by taking $n$ data points at evenly-spaced time intervals and mapping them to a length-$n$ permutation determined by relative ordering. The frequency with which certain patterns occur is a useful statistic for such series. However, the behavior of the frequency of pattern occurrence is unstudied for most models. We look at the frequency of pattern occurrence in random walks in discrete time, and we define a natural equivalence relation on permutations under which equivalent patterns appear with equal frequency, regardless of probability distribution. We characterize these equivalence classes applying combinatorial methods.

The graph of overlapping permutations is defined in a way analogous to the De Bruijn graph on strings of symbols. However, instead of requiring the tail of one permutation to equal the head of another for them to be connected by an edge, we require that the head and tail in question have their letters appear in the same order of size. We give a formula for the number of cycles of length $d$ in the subgraph of overlapping $312$-avoiding permutations. Using this we also give a refinement of the enumeration of $312$-avoiding affine permutations.

In this paper, we study the distribution of the number occurrences of the simplest frame pattern, called the μ pattern, in n -cycles. Given an n -cycle C , we say that a pair 〈 i , j 〉 matches the μ pattern if i < j and as we traverse around C in a clockwise direction starting at i and ending at j , we never encounter a k with i < k < j . We say that 〈 i , j 〉 is a trivial μ -match if j = i + 1 and is a nontrivial μ -match if i + 1 < j . We say that an n -cycle C is incontractible if there is no i such that i + 1 immediately follows i in C . We show that number of incontractible n -cycles in the symmetric group S n is D n − 1 where D n is the number of derangements in S n . We show that number of n -cycles in S n with exactly k nontrivial μ -matches can be expressed as a linear combination of binomial coefficients of the form ( n − 1 i ) where i ≤ 2 k + 1 . We also show that the generating function N T I n , μ ( q ) of q raised to the number of nontrivial μ -matches in C over all incontractible n -cycles in S n is a new q -analogue of D n − 1 which is different from the q -analogues of the derangement numbers that have been studied by Garsia and Remmel and by Wachs. We show that there is a rather surprising connection between the charge statistic on permutations due to Lascoux and Schüzenberger and our polynomials in that the coefficient of the smallest power of q in N T I 2 k + 1 , μ ( q ) is the number of permutations in S 2 k + 1 whose charge path is a Dyck path. Finally, we show that the coefficient of q ( n − 1 2 ) − k in N T I n , μ ( q ) is the number of partitions of k for sufficiently large n . [ABSTRACT FROM AUTHOR]

We study a sorting machine consisting of two stacks in series where the first stack has the added restriction such that entries in the stack must be in decreasing order from top to bottom. We give the basis of the class of permutations that are sortable by this machine which shows that it is enumerated by the Schröder numbers. [ABSTRACT FROM AUTHOR]