Journal articles: 'Permutations'

1

Wituła, Roman, Edyta Hetmaniok, and Damian Słota. "On Commutation Properties of the Composition Relation of Convergent and Divergent Permutations (Part I)." Tatra Mountains Mathematical Publications 58, no. 1 (March 1, 2014): 13–22. http://dx.doi.org/10.2478/tmmp-2014-0002.

Full text

Abstract:

Abstract In the paper we present the selected properties of composition relation of the convergent and divergent permutations connected with commutation. We note that a permutation on ℕ is called the convergent permutation if for each convergent series ∑an of real terms, the p-rearranged series ∑ap(n) is also convergent. All the other permutations on ℕ are called the divergent permutations. We have proven, among others, that, for many permutations p on ℕ, the family of divergent permutations q on ℕ commuting with p possesses cardinality of the continuum. For example, the permutations p on ℕ having finite order possess this property. On the other hand, an example of a convergent permutation which commutes only with some convergent permutations is also presented.

APA, Harvard, Vancouver, ISO, and other styles

2

Savchuk, M., and M. Burlaka. "Encoding and classification of permutations bу special conversion with estimates of class power." Bulletin of Taras Shevchenko National University of Kyiv. Series: Physics and Mathematics, no. 2 (2019): 36–43. http://dx.doi.org/10.17721/1812-5409.2019/2.3.

Full text

Abstract:

Scientific articles investigating properties and estimates of the number of so-called complete permutations are surveyed and analyzed. The paper introduces a special S-transform on the set of permutations and determines the permutation properties according to this transform. Classification and coding of permutations by equivalence classes according to their properties with respect to S-transformation is proposed. This classification and permutation properties, in particular, generalize known results for complete permutations regarding determining certain cryptographic properties of substitutions that affect the cryptographic transformations security. The exact values of the number of permutations in equivalence classes for certain permutation sizes are calculated and the estimates of the cardinality of classes with various properties are constructed by statistical modeling. The complete list of permutation classes with the exact values of their sizes for permutations of order n = 11 is presented. The interval estimates for the size of classes with various characteristics for permutations of order n = 11, 26, 30, 31, 32, 33, 45, 55 are obtained. Monte Carlo estimates and bounds of confidence intervals used the approximation of the binomial distribution by the normal and Poisson distributions, as well as the Python programming language package Scipy. Statistical tables have been calculated that can be used for further conclusions and estimates. The classification of permutations by their properties with respect to the introduced transform can be used in constructing high-quality cryptographic transformations and transformations with special features. The classes of complete permutations with their properties are selected as the best for rotary cryptosystems applications. The obtained results can be used, in particular, to search for permutations with certain characteristics and properties, to find the probability that the characteristic of the generated permutation belongs to a collection of given characteristics, to estimate the complexity of finding permutations with certain properties. A statistical criterion of consent, which uses the characteristics of permutations by S-transformation to test the generators of random permutations and substitutions is proposed.

APA, Harvard, Vancouver, ISO, and other styles

3

Adamczak, William. "A Note on the Structure of Roller Coaster Permutations." Journal of Mathematics Research 9, no. 3 (May 24, 2017): 75. http://dx.doi.org/10.5539/jmr.v9n3p75.

Full text

Abstract:

In this paper we consider the structure of a special class of permutations known as roller coaster permutations, first introduced by Ahmed & Snevily (2013). A roller coaster permutation is described as, a permutation that maximizes the total switches from ascending to descending, or visa versa, for the permutation as well as all of its subpermutations, simultaneously. This paper looks at the structure of these permutations, particularly the alternating structure, what the entires of these permutations can look like, we then introduce a notion of a condition stronger than alternating that we shall refer to as recursively alternating.

APA, Harvard, Vancouver, ISO, and other styles

4

Brualdi, Richard A., and Geir Dahl. "Permutation Matrices, Their Discrete Derivatives and Extremal Properties." Vietnam Journal of Mathematics 48, no. 4 (March 24, 2020): 719–40. http://dx.doi.org/10.1007/s10013-020-00392-5.

Full text

Abstract:

AbstractFor a permutation π, and the corresponding permutation matrix, we introduce the notion of discrete derivative, obtained by taking differences of successive entries in π. We characterize the possible derivatives of permutations, and consider questions for permutations with certain properties satisfied by the derivative. For instance, we consider permutations with distinct derivatives, and the relationship to so-called Costas arrays.

APA, Harvard, Vancouver, ISO, and other styles

5

Senashov, Vasily S., Konstantin A. Filippov, and Anatoly K. Shlepkin. "Regular permutations and their applications in crystallography." E3S Web of Conferences 525 (2024): 04002. http://dx.doi.org/10.1051/e3sconf/202452504002.

Full text

Abstract:

The representation of a group G in the form of regular permutations is widely used for studying the structure of finite groups, in particular, parameters like the group density function. This is related to the increased potential of computer technologies for conducting calculations. The work addresses the problem of calculation regular permutations with restrictions on the structure of the degree and order of permutations. The considered regular permutations have the same nontrivial order, which divides the degree of the permutation. Examples of the application of permutation groups in crystallography and crystal chemistry are provided.

APA, Harvard, Vancouver, ISO, and other styles

6

Gao, Alice L. L., Sergey Kitaev, Wolfgang Steiner, and Philip B. Zhang. "On a Greedy Algorithm to Construct Universal Cycles for Permutations." International Journal of Foundations of Computer Science 30, no. 01 (January 2019): 61–72. http://dx.doi.org/10.1142/s0129054119400033.

Full text

Abstract:

A universal cycle for permutations of length [Formula: see text] is a cyclic word or permutation, any factor of which is order-isomorphic to exactly one permutation of length [Formula: see text], and containing all permutations of length [Formula: see text] as factors. It is well known that universal cycles for permutations of length [Formula: see text] exist. However, all known ways to construct such cycles are rather complicated. For example, in the original paper establishing the existence of the universal cycles, constructing such a cycle involves finding an Eulerian cycle in a certain graph and then dealing with partially ordered sets. In this paper, we offer a simple way to generate a universal cycle for permutations of length [Formula: see text], which is based on applying a greedy algorithm to a permutation of length [Formula: see text]. We prove that this approach gives a unique universal cycle [Formula: see text] for permutations, and we study properties of [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

7

Vidybida, Alexander K. "Calculating Permutation Entropy without Permutations." Complexity 2020 (October 22, 2020): 1–9. http://dx.doi.org/10.1155/2020/7163254.

Full text

Abstract:

A method for analyzing sequential data sets, similar to the permutation entropy one, is discussed. The characteristic features of this method are as follows: it preserves information about equal values, if any, in the embedding vectors; it is exempt from combinatorics; and it delivers the same entropy value as does the permutation method, provided the embedding vectors do not have equal components. In the latter case, this method can be used instead of the permutation one. If embedding vectors have equal components, this method could be more precise in discriminating between similar data sets.

APA, Harvard, Vancouver, ISO, and other styles

8

Steingrı́msson, Einar. "Permutation Statistics of Indexed Permutations." European Journal of Combinatorics 15, no. 2 (March 1994): 187–205. http://dx.doi.org/10.1006/eujc.1994.1021.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

ZHOU, YINGCHUN, and MURAD S. TAQQU. "APPLYING BUCKET RANDOM PERMUTATIONS TO STATIONARY SEQUENCES WITH LONG-RANGE DEPENDENCE." Fractals 15, no. 02 (June 2007): 105–26. http://dx.doi.org/10.1142/s0218348x07003526.

Full text

Abstract:

Bucket random permutations (shuffling) are used to modify the dependence structure of a time series, and this may destroy long-range dependence, when it is present. Three types of bucket permutations are considered here: external, internal and two-level permutations. It is commonly believed that (1) an external random permutation destroys the long-range dependence and keeps the short-range dependence, (2) an internal permutation destroys the short-range dependence and keeps the long-range dependence, and (3) a two-level permutation distorts the medium-range dependence while keeping both the long-range and short-range dependence. This paper provides a theoretical basis for investigating these claims. It extends the study started in Ref. 1 and analyze the effects that these random permutations have on a long-range dependent finite variance stationary sequence both in the time domain and in the frequency domain.

APA, Harvard, Vancouver, ISO, and other styles

10

Mansour, Toufik, Howard Skogman, and Rebecca Smith. "Passing through a stack k times." Discrete Mathematics, Algorithms and Applications 11, no. 01 (February 2019): 1950003. http://dx.doi.org/10.1142/s1793830919500034.

Full text

Abstract:

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 [Formula: see text] to be [Formula: see text]-pass sortable if [Formula: see text] is sortable using [Formula: see text] passes through the stack. Permutations that are [Formula: see text]-pass sortable are simply the stack sortable permutations as defined by Knuth. We define the permutation class of [Formula: see text]-pass sortable permutations in terms of their basis. We also show all [Formula: see text]-pass sortable classes have finite bases by giving bounds on the length of a basis element of the permutation class for any positive integer [Formula: see text]. Finally, we define the notion of tier of a permutation [Formula: see text] to be the minimum number of passes after the first pass required to sort [Formula: see text]. We then give a bijection between the class of permutations of tier [Formula: see text] 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 [Formula: see text] permutations of a given length and thus an exact enumeration for the class of [Formula: see text]-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.

APA, Harvard, Vancouver, ISO, and other styles

11

Recchia, Gabriel, Magnus Sahlgren, Pentti Kanerva, and Michael N. Jones. "Encoding Sequential Information in Semantic Space Models: Comparing Holographic Reduced Representation and Random Permutation." Computational Intelligence and Neuroscience 2015 (2015): 1–18. http://dx.doi.org/10.1155/2015/986574.

Full text

Abstract:

Circular convolution and random permutation have each been proposed as neurally plausible binding operators capable of encoding sequential information in semantic memory. We perform several controlled comparisons of circular convolution and random permutation as means of encoding paired associates as well as encoding sequential information. Random permutations outperformed convolution with respect to the number of paired associates that can be reliably stored in a single memory trace. Performance was equal on semantic tasks when using a small corpus, but random permutations were ultimately capable of achieving superior performance due to their higher scalability to large corpora. Finally, “noisy” permutations in which units are mapped to other units arbitrarily (no one-to-one mapping) perform nearly as well as true permutations. These findings increase the neurological plausibility of random permutations and highlight their utility in vector space models of semantics.

APA, Harvard, Vancouver, ISO, and other styles

12

Drakakis, Konstantinos. "On the Measurement of the (Non)linearity of Costas Permutations." Journal of Applied Mathematics 2010 (2010): 1–14. http://dx.doi.org/10.1155/2010/149658.

Full text

Abstract:

We study several criteria for the (non)linearity of Costas permutations, with or without the imposition of additional algebraic structure in the domain and the range of the permutation, aiming to find one that successfully identifies Costas permutations as more nonlinear than randomly chosen permutations of the same order.

APA, Harvard, Vancouver, ISO, and other styles

13

QI, XINGQIN, GUOJUN LI, JICHANG WU, and BINGQIANG LIU. "SORTING SIGNED PERMUTATIONS BY FIXED-LENGTH REVERSALS." International Journal of Foundations of Computer Science 17, no. 04 (August 2006): 933–48. http://dx.doi.org/10.1142/s0129054106004194.

Full text

Abstract:

A signed n-permutation is a permutation on {1,2,…,n} in which each element is labelled by a positive or negative sign. Here we consider the problem of sorting signed permutations by fixed-length reversals. Indeed, limiting the transformations to reversals of length exactly k can be very restrictive, for example, (+1,+3,+2,+4,…,+n) can never be sorted to (+1,+2,+3,+4,…,+n) by 2-reversals. That is, for given two signed permutations it is not obvious whether they can be sorted to each other by k-reversals. Thus in 1996, Chen and Skiena gave the following open problem: what is the connectedness of signed permutations under fixed-length reversals? In this paper, we resolve this open problem when "fixed-length" is even, and give a characterization of the connectedness of signed n-permutations under 2l-reversal, for both linear and circular permutations.

APA, Harvard, Vancouver, ISO, and other styles

14

Choi, Wonseok, Jooyoung Lee, and Yeongmin Lee. "Building PRFs from TPRPs: Beyond the Block and the Tweak Length Bounds." IACR Transactions on Symmetric Cryptology 2024, no. 1 (March 1, 2024): 35–70. http://dx.doi.org/10.46586/tosc.v2024.i1.35-70.

Full text

Abstract:

A secure n-bit tweakable block cipher (TBC) using t-bit tweaks can be modeled as a tweakable uniform random permutation, where each tweak defines an independent random n-bit permutation. When an input to this tweakable permutation is fixed, it can be viewed as a perfectly secure t-bit random function. On the other hand, when a tweak is fixed, it can be viewed as a perfectly secure n-bit random permutation, and it is well known that the sum of two random permutations is pseudorandom up to 2n queries.A natural question is whether one can construct a pseudorandom function (PRF) beyond the block and the tweak length bounds using a small number of calls to the underlying tweakable permutations. A straightforward way of constructing a PRF from tweakable permutations is to xor the outputs from two tweakable permutations with c bits of the input to each permutation fixed. Using the multi-user security of the sum of two permutations, one can prove that the (t + n − c)-to-n bit PRF is secure up to 2n+c queries.In this paper, we propose a family of PRF constructions based on tweakable permutations, dubbed XoTPc, achieving stronger security than the straightforward construction. XoTPc is parameterized by c, giving a (t + n − c)-to-n bit PRF. When t < 3n and c = t/3 , XoTPt/3 becomes an (n + 2t/3 )-to-n bit pseudorandom function, which is secure up to 2n+2t/3 queries. It provides security beyond the block and the tweak length bounds, making two calls to the underlying tweakable permutations. In order to prove the security of XoTPc, we extend Mirror theory to q ≫ 2n, where q is the number of equations. From a practical point of view, our construction can be used to construct TBC-based MAC finalization functions and CTR-type encryption modes with stronger provable security compared to existing schemes.

APA, Harvard, Vancouver, ISO, and other styles

15

SMYCZYŃSKI, SEBASTIAN. "CONSTANT-MEMORY ITERATIVE GENERATION OF SPECIAL STRINGS REPRESENTING BINARY TREES." International Journal of Foundations of Computer Science 23, no. 02 (February 2012): 375–87. http://dx.doi.org/10.1142/s0129054112400187.

Full text

Abstract:

The shapes of binary trees can be encoded as permutations having a very special property. These permutations are tree permutations, or equivalently they avoid subwords of the type 231. The generation of binary trees in natural order corresponds to the generation of these special permutations in the lexicographic order. In this paper we use a stringologic approach to the generation of these special permutations: decompositions of essential parts into the subwords having staircase shapes. A given permutation differs from the next one with respect to its tail called here the working suffix. Some new properties of such working suffixes are discovered in the paper and used to design effective algorithms transforming one tree permutation into its successor or predecessor in the lexicographic order. The algorithms use a constant amount of additional memory and they look only at those elements of the permutation which belong to the working suffix. The best-case, average-case and worst-case time complexities of the algorithms are O(1), O(1), and O(n) respectively. The advantages of our stringologic approach are constant time and iterative generation, while other known algorithms are usually recursive or not constant-memory ones. In this paper we also present a new compact non-recursive linear time algorithm solving a related problem of decoding the shape of a binary tree from its corresponding tree permutation.

APA, Harvard, Vancouver, ISO, and other styles

16

Bean, Christian, Émile Nadeau, Jay Pantone, and Henning Ulfarsson. "Using large random permutations to partition permutation classes." Pure Mathematics and Applications 30, no. 1 (June 1, 2022): 31–36. http://dx.doi.org/10.2478/puma-2022-0006.

Full text

Abstract:

Abstract 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.

APA, Harvard, Vancouver, ISO, and other styles

17

BLOCK, LOUIS, ALEXANDER M. BLOKH, and ETHAN M. COVEN. "ZERO ENTROPY PERMUTATIONS." International Journal of Bifurcation and Chaos 05, no. 05 (October 1995): 1331–37. http://dx.doi.org/10.1142/s0218127495001009.

Full text

Abstract:

The entropy of a permutation is the (topological) entropy of the "connect-the-dots" map determined by it. We give matrix- and graph-theoretic, geometric, and dynamical characterizations of zero entropy permutations, as well as a procedure for constructing all of them. We also include some information about the number of zero entropy permutations.

APA, Harvard, Vancouver, ISO, and other styles

18

Cioni, Lapo, and Luca Ferrari. "Sorting with a popqueue." RAIRO - Theoretical Informatics and Applications 58 (2024): 13. http://dx.doi.org/10.1051/ita/2024010.

Full text

Abstract:

We introduce a new sorting device for permutations, which we call popqueue. It consists of a special queue, having the property that any time one wants to extract elements from the queue, actually all the elements currently in the queue are poured into the output. We illustrate two distinct optimal algorithms, called Min and Cons, to sort a permutation using such a device, which allow us also to characterize sortable permutations in terms of pattern avoidance. We next investigate what happens by making two passes through a popqueue, showing that the set of sortable permutations is not a class for Min, whereas it is for Cons. In the latter case we also explicitly find the basis of the class of sortable permutations. Finally, we study preimages under Cons (by means of an equivalent version of the algorithm), and find a characterization of the set of preimages of a given permutation. We also give some enumerative results concerning the number of permutations having k preimages, for k = 1, 2, 3, and we conclude by observing that there exist permutations having k preimages for any value of k ≥ 0.

APA, Harvard, Vancouver, ISO, and other styles

19

Mishin, Dmitry V., Anatoly A. Gladkikh, Vladislav I. Kutuzov, and Aqeel Latif Khudair. "Research of cognitive data processing in radio communication systems with permutation decoding." Physics of Wave Processes and Radio Systems 27, no. 1 (March 29, 2024): 103–12. http://dx.doi.org/10.18469/1810-3189.2024.27.1.103-112.

Full text

Abstract:

Background. The need to use permutation decoding tools in radio communication systems is explained by the increased error correction capabilities of this method. In this case, complex matrix calculations during the search for equivalent codes according to the classical scheme of permutation decoding are replaced by a list of ready-made solutions. These solutions are calculated a priori and entered into the cognitive cards of the decoder processor, which makes the method a convenient tool in the procedure for ensuring information reliability when controlling, for example, unmanned vehicles via radio channels. In fact, matrix calculations on board are replaced by searching the list of cognitive maps for the right solution corresponding in real time to the current permutation of reliable character numerators. However, data processing in the decoder’s cognitive map requires a special description. Aim. The study of methods for identifying permutations of character numerators of code vectors in order to effectively transform them in a system of cognitive maps of a permutation decoder. Methods. The paper reveals the subtle structure of cognitive maps of productive and unproductive permutations of numerators, which allows on a regular basis to obtain an alternative solution for switching to a set of productive permutations when the receiver receives an unproductive permutation, thereby excluding the use of trial and error. Results. The efficiency of the permutation decoder increases due to the implementation of permutations that were originally included in a set of solutions introduced into the cognitive map of unproductive permutations. Conclusion. A family of microcontrollers is proposed to implement the principle of interaction of cognitive maps with a system of alternative solutions.

APA, Harvard, Vancouver, ISO, and other styles

20

Liu, Mengyu, and Huilan Li. "A Hopf Algebra on Permutations Arising from Super-Shuffle Product." Symmetry 13, no. 6 (June 4, 2021): 1010. http://dx.doi.org/10.3390/sym13061010.

Full text

Abstract:

In this paper, we first prove that any atom of a permutation obtained by the super-shuffle product of two permutations can only consist of some complete atoms of the original two permutations. Then, we prove that the super-shuffle product and the cut-box coproduct on permutations are compatible, which makes it a bialgebra. As this algebra is graded and connected, it is a Hopf algebra.

APA, Harvard, Vancouver, ISO, and other styles

21

GNEDIN, ALEXANDER, ALEXANDER IKSANOV, and ALEXANDER MARYNYCH. "A Generalization of the Erdős–Turán Law for the Order of Random Permutation." Combinatorics, Probability and Computing 21, no. 5 (July 3, 2012): 715–33. http://dx.doi.org/10.1017/s0963548312000247.

Full text

Abstract:

We consider random permutations derived by sampling from stick-breaking partitions of the unit interval. The cycle structure of such a permutation can be associated with the path of a decreasing Markov chain on n integers. Under certain assumptions on the stick-breaking factor we prove a central limit theorem for the logarithm of the order of the permutation, thus extending the classical Erdős–Turán law for the uniform permutations and its generalization for Ewens' permutations associated with sampling from the PD/GEM(θ)-distribution. Our approach is based on using perturbed random walks to obtain the limit laws for the sum of logarithms of the cycle lengths.

APA, Harvard, Vancouver, ISO, and other styles

22

KING, DEBORAH M. "Maximal entropy of permutations of even order." Ergodic Theory and Dynamical Systems 17, no. 6 (December 1997): 1409–17. http://dx.doi.org/10.1017/s0143385797086367.

Full text

Abstract:

A finite invariant set of a continuous map of an interval induces a permutation called its type. If this permutation is a cycle, it is called its orbit type. It has been shown by Geller and Tolosa that Misiurewicz–Nitecki orbit types of period $n$ congruent to $1$ (mod 4) and their generalizations to orbit types of period $n$ congruent to $3$ (mod 4) have maximal entropy among all orbit types of odd period $n$, and indeed among all permutations of period $n$. We further generalize this family to permutations of even period $n$ and show that they again attain maximal entropy amongst $n$-permutations.

APA, Harvard, Vancouver, ISO, and other styles

23

Hajnal, Péter. "A short note on Layman permutations." Acta Universitatis Sapientiae, Mathematica 14, no. 2 (December 1, 2022): 231–38. http://dx.doi.org/10.2478/ausm-2022-0015.

Full text

Abstract:

Abstract A permutation p of [k] = {1, 2, 3, …, k} is called Layman permutation iff i + p(i) is a Fibonacci number for 1 ≤ i ≤ k. This concept is introduced by Layman in the A097082 entry of the Encyclopedia of Integers Sequences, that is the number of Layman permutations of [n]. In this paper, we will study Layman permutations. We introduce the notion of the Fibonacci complement of a natural number, that plays a crucial role in our investigation. Using this notion we prove some results on the number of Layman permutations, related to a conjecture of Layman that is implicit in the A097083 entry of OEIS.

APA, Harvard, Vancouver, ISO, and other styles

24

Wocjan, Paweł, and Michał Horodecki. "Characterization of Combinatorially Independent Permutation Separability Criteria." Open Systems & Information Dynamics 12, no. 04 (December 2005): 331–45. http://dx.doi.org/10.1007/s11080-005-4483-2.

Full text

Abstract:

The so-called permutation separability criteria are simple operational conditions that are necessary for separability of mixed states of multipartite systems: (1) permute the indices of the density matrix and (2) check if the trace norm of at least one of the resulting operators is greater than one. If it is greater than one then the state is necessarily entangled. A shortcoming of the permutation separability criteria is that many permutations give rise to equivalent separability criteria. Therefore, we introduce a necessary condition for two permutations to yield independent criteria called combinatorial independence. This condition basically means that the map corresponding to one permutation cannot be obtained by concatenating the map corresponding to the second permutation with a norm-preserving map. We characterize completely combinatorially independent criteria, and determine simple permutations that represent all independent criteria. The representatives can be visualized by means of a simple graphical notation. They are composed of three basic operations: partial transpose, and two types of so-called reshufflings. In particular, for a four-partite system all criteria except one are composed of partial transpose and only one type of reshuffling; the exceptional one requires the second type of reshuffling. Furthermore, we show how to obtain efficiently a simple representative for every permutation. This method allows to check easily if two permutations are combinatorially equivalent or not.

APA, Harvard, Vancouver, ISO, and other styles

25

Donets, G. A., and V. I. Biletskyi. "On the Problem of a Linear Function Localization on Permutations." Cybernetics and Computer Technologies, no. 2 (July 24, 2020): 14–18. http://dx.doi.org/10.34229/2707-451x.20.2.2.

Full text

Abstract:

Combinatorial optimization problems and methods of their solution have been a subject of numerous studies, since a large number of practical problems are described by combinatorial optimization models. Many studies consider approaches to and describe methods of solution for combinatorial optimization problems with linear or fractionally linear target functions on combinatorial sets such as permutations and arrangements. Studies consider solving combinatorial problems by means of well-known methods, as well as developing new methods and algorithms of searching a solution. We describe a method of solving a problem of a linear target function localization on a permutation set. The task is to find those locally admissible permutations on the permutation set, for which the linear function possesses a given value. In a general case, this problem may have no solutions at all. In the article, we propose a newly developed method that allows us to obtain a solution of such a problem (in the case that such solution exists) by the goal-oriented seeking for locally admissible permutations with a minimal enumeration that is much less than the number of all possible variants. Searching for the solution comes down to generating various permutations and evaluating them. Evaluation of each permutation includes two steps. The first step consists of function decreasing by transposing the numbers in the first n – 3 positions, and the second step is evaluation of the permutations for the remaining three numbers. Then we analyze the correlation (which is called balance) to define whether the considered permutation is the solution or not. In our article, we illustrate the localization method by solving the problem for n = 5. Keywords: localization, linear function, permutation, transposition, balance, position.

APA, Harvard, Vancouver, ISO, and other styles

26

Cao, Xiwang, Lei Hu, and Zhengbang Zha. "Constructing permutation polynomials from piecewise permutations." Finite Fields and Their Applications 26 (March 2014): 162–74. http://dx.doi.org/10.1016/j.ffa.2013.12.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Faure, Emil, Anatoly Shcherba, Mykola Makhynko, Bohdan Stupka, Joanna Nikodem, and Ruslan Shevchuk. "Permutation-Based Block Code for Short Packet Communication Systems." Sensors 22, no. 14 (July 19, 2022): 5391. http://dx.doi.org/10.3390/s22145391.

Full text

Abstract:

This paper presents an approach to the construction of block error-correcting code for data transmission systems with short packets. The need for this is driven by the necessity of information interaction between objects of machine-type communication network with a dynamically changing structure and unique system of commands or alerts for each network object. The codewords of a code are permutations with a given minimum pairwise Hamming distance. The purpose of the study is to develop a statistical method for constructing a code, in contrast to known algebraic methods, and to investigate the code size. An algorithm for generating codewords has been developed. It can be implemented both by enumeration of the full set of permutations, and by enumeration of a given number of randomly selected permutations. We have experimentally determined the dependencies of the average and the maximum values of the code size on the size of a subset of permutations used for constructing the code. A technique for computing approximation quadratic polynomials for the determined code size dependencies has been developed. These polynomials and their corresponding curves estimate the size of a code generated from a subset of random permutations of such a size that a statistically significant experiment cannot be performed. The results of implementing the developed technique for constructing a code based on permutations of lengths 7 and 11 have been presented. The prediction relative error of the code size did not exceed the value of 0.72% for permutation length 11, code distance 9, random permutation subset size 50,000, and permutation statistical study range limited by 5040.

APA, Harvard, Vancouver, ISO, and other styles

28

Burov, Dmitry A. "Subgroups of direct products of groups invariant under the action of permutations on factors." Discrete Mathematics and Applications 30, no. 4 (August 26, 2020): 243–55. http://dx.doi.org/10.1515/dma-2020-0021.

Full text

Abstract:

AbstractWe study subgroups of the direct product of two groups invariant under the action of permutations on factors. An invariance criterion for the subdirect product of two groups under the action of permutations on factors is put forward. Under certain additional constraints on permutations, we describe the subgroups of the direct product of a finite number of groups that are invariant under the action of permutations on factors. We describe the subgroups of the additive group of vector space over a finite field of characteristic 2 which are invariant under the coordinatewise action of inversion permutation of nonzero elements of the field.

APA, Harvard, Vancouver, ISO, and other styles

29

WANG, LI-YUAN, and HAI-LIANG WU. "APPLICATIONS OF LERCH’S THEOREM TO PERMUTATIONS OF QUADRATIC RESIDUES." Bulletin of the Australian Mathematical Society 100, no. 3 (July 10, 2019): 362–71. http://dx.doi.org/10.1017/s000497271900073x.

Full text

Abstract:

Let $n$ be a positive integer and $a$ an integer prime to $n$. Multiplication by $a$ induces a permutation over $\mathbb{Z}/n\mathbb{Z}=\{\overline{0},\overline{1},\ldots ,\overline{n-1}\}$. Lerch’s theorem gives the sign of this permutation. We explore some applications of Lerch’s result to permutation problems involving quadratic residues modulo $p$ and confirm some conjectures posed by Sun [‘Quadratic residues and related permutations and identities’, Preprint, 2018, arXiv:1809.07766]. We also study permutations involving arbitrary $k$th power residues modulo $p$ and primitive roots modulo a power of $p$.

APA, Harvard, Vancouver, ISO, and other styles

30

AKL, SELIM G., and IVAN STOJMENOVIĆ. "A SIMPLE OPTIMAL SYSTOLIC ALGORITHM FOR GENERATING PERMUTATIONS." Parallel Processing Letters 02, no. 02n03 (September 1992): 231–39. http://dx.doi.org/10.1142/s0129626492000362.

Full text

Abstract:

We describe a simple parallel algorithm for generating all permutations of n elements. The algorithm is designed to be executed on a linear array of n processors, each having constant size memory and each being responsible for producing one element of a given permutation. There is a constant delay per permutation, leading to an O (n!) time solution. The algorithm is cost-optimal, assuming the time to output the permutations is counted.

APA, Harvard, Vancouver, ISO, and other styles

31

Cioni, Lapo. "Preimages under a popqueue-sorting algorithm." Pure Mathematics and Applications 30, no. 1 (June 1, 2022): 63–67. http://dx.doi.org/10.2478/puma-2022-0010.

Full text

Abstract:

Abstract Following the footprints of what has been done with other sorting devices, we study a popqueue and define an optimal sorting algorithm, called Cons. Our results include a description of the set of all the preimages of a given permutation, an enumeration of the set of the preimages of permutations with some specific properties and, finally, the exact enumeration of permutations having 0, 1 and 2 preimages, respectively, with a characterization of permutations having 3 preimages.

APA, Harvard, Vancouver, ISO, and other styles

32

Miranda, Guilherme Henrique Santos, Alexsandro Oliveira Alexandrino, Carla Negri Lintzmayer, and Zanoni Dias. "Approximation Algorithms for Sorting λ-Permutations by λ-Operations." Algorithms 14, no. 6 (June 1, 2021): 175. http://dx.doi.org/10.3390/a14060175.

Full text

Abstract:

Understanding how different two organisms are is one question addressed by the comparative genomics field. A well-accepted way to estimate the evolutionary distance between genomes of two organisms is finding the rearrangement distance, which is the smallest number of rearrangements needed to transform one genome into another. By representing genomes as permutations, one of them can be represented as the identity permutation, and, so, we reduce the problem of transforming one permutation into another to the problem of sorting a permutation using the minimum number of rearrangements. This work investigates the problems of sorting permutations using reversals and/or transpositions, with some additional restrictions of biological relevance. Given a value λ, the problem now is how to sort a λ-permutation, which is a permutation whose elements are less than λ positions away from their correct places (regarding the identity), by applying the minimum number of rearrangements. Each λ-rearrangement must have size, at most, λ, and, when applied to a λ-permutation, the result should also be a λ-permutation. We present algorithms with approximation factors of O(λ2), O(λ), and O(1) for the problems of Sorting λ-Permutations by λ-Reversals, by λ-Transpositions, and by both operations.

APA, Harvard, Vancouver, ISO, and other styles

33

Lengyel, Tamás. "The Distribution of the Size of the Union of Cycles for Two Types of Random Permutations." International Journal of Combinatorics 2010 (October 24, 2010): 1–10. http://dx.doi.org/10.1155/2010/751861.

Full text

Abstract:

We discuss some problems and permutation statistics involving two different types of random permutations. Under the usual model of random permutations, we prove that the shifted coverage of the elements of , 2, , of a random permutation over , 2, , ; that is, the size of the union of the cycles containing these elements, excluding these elements themselves, follows a negative hypergeometric distribution. This fact gives a probabilistic model for the coverage via the canonical cycle representation. For a different random model, we determine some random permutation statistics regarding the problem of the lost boarding pass and its variations.

APA, Harvard, Vancouver, ISO, and other styles

34

Haliuk, Serhii, Oleh Krulikovskyi, and Vitalii Vlasenko. "STUDYING THE PROPERTIES OF PIXELS PERMUTATIONS BASED ON DISCRETIZED STANDARD MAP." Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Środowiska 10, no. 1 (March 30, 2020): 48–51. http://dx.doi.org/10.35784/iapgos.907.

Full text

Abstract:

In this article, we described specifics of pixels permutations based on the discretized, two-dimensional Chirikov standard map. Some properties of the discretized Chirikov map can be used by an attacker to recover the original images that are studied. For images with dimensions N ´ N the vulnerability of permutations allows for brute force attacks, and shown is the ability of an intruder to restore the original image without setting the value of keys permutations. Presented is also, successful cryptographic attack on the encrypted image through permutation of pixels. It is found that for images with dimension N ´ N the maximum number of combinations is equal to NN-1. A modified Chirikov map was proposed with improved permutation properties, due to the use of two nonlinearities, that increase the keys space to N2!.

APA, Harvard, Vancouver, ISO, and other styles

35

Lintzmayer, Carla Negri, Guillaume Fertin, and Zanoni Dias. "Sorting permutations by prefix and suffix rearrangements." Journal of Bioinformatics and Computational Biology 15, no. 01 (February 2017): 1750002. http://dx.doi.org/10.1142/s0219720017500020.

Full text

Abstract:

Some interesting combinatorial problems have been motivated by genome rearrangements, which are mutations that affect large portions of a genome. When we represent genomes as permutations, the goal is to transform a given permutation into the identity permutation with the minimum number of rearrangements. When they affect segments from the beginning (respectively end) of the permutation, they are called prefix (respectively suffix) rearrangements. This paper presents results for rearrangement problems that involve prefix and suffix versions of reversals and transpositions considering unsigned and signed permutations. We give 2-approximation and ([Formula: see text])-approximation algorithms for these problems, where [Formula: see text] is a constant divided by the number of breakpoints (pairs of consecutive elements that should not be consecutive in the identity permutation) in the input permutation. We also give bounds for the diameters concerning these problems and provide ways of improving the practical results of our algorithms.

APA, Harvard, Vancouver, ISO, and other styles

36

Ayyer, Arvind, and Beáta Bényi. "Toppling on Permutations with an Extra Chip." Electronic Journal of Combinatorics 28, no. 4 (November 5, 2021). http://dx.doi.org/10.37236/10420.

Full text

Abstract:

The study of toppling on permutations with an extra labeled chip was initiated by the first author with D. Hathcock and P. Tetali (arXiv:2010.11236), where the extra chip was added in the middle. We extend this to all possible locations $p$ as well as values $r$ of the extra chip and give a complete characterization of permutations which topple to the identity. Further, we classify all permutations which are outcomes of the toppling process in this generality, which we call resultant permutations. Resultant permutations turn out to be certain decomposable permutations. The number of configurations toppling to a given resultant permutation is shown to depend purely on the number of left-to-right maxima (or records) of the permutation to the left of $p$ and the number of right-to-left minima to the right of $p$. The number of permutations toppling to a given resultant permutation (identity or otherwise) is shown to be the binomial transform of a poly-Bernoulli number of type B.

APA, Harvard, Vancouver, ISO, and other styles

37

Kobayashi, Masato. "Bijection Between Bigrassmannian Permutations Maximal below a Permutation and its Essential Set." Electronic Journal of Combinatorics 17, no. 1 (May 20, 2010). http://dx.doi.org/10.37236/476.

Full text

Abstract:

Bigrassmannian permutations are known as permutations which have precisely one left descent and one right descent. They play an important role in the study of Bruhat order. Fulton introduced the essential set of a permutation and studied its combinatorics. As a consequence of his work, it turns out that the essential set of bigrassmannian permutations consists of precisely one element. In this article, we generalize this observation for essential sets of arbitrary permutations. Our main theorem says that there exists a bijection between bigrassmanian permutations maximal below a permutation and its essential set. For the proof, we make use of two equivalent characterizations of bigrassmannian permutations by Lascoux-Schützenberger and Reading.

APA, Harvard, Vancouver, ISO, and other styles

38

Burstein, Alexander, and Niklas Eriksen. "Combinatorial properties of permutation tableaux." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AJ,..., Proceedings (January 1, 2008). http://dx.doi.org/10.46298/dmtcs.3615.

Full text

Abstract:

International audience We give another construction of a permutation tableau from its corresponding permutation and construct a permutation-preserving bijection between $1$-hinge and $0$-hinge tableaux. We also consider certain alignment and crossing statistics on permutation tableaux that have previously been shown to be equidistributed by mapping them to patterns in related permutations. We give two direct maps on tableaux that prove the equidistribution of those statistics by exchanging some statistics and preserving the rest. Finally, we enumerate some sets of permutations that are restricted both by pattern avoidance and by certain parameters of their associated permutation tableaux. Nous donnons une nouvelle construction d'un tableau de permutation à partir de la permutation correspondante. Nous construisons ensuite une permutation qui préserve la bijection entre un tableau charnière $1$ et tableau charnière $0$. Nous considérons également certaines statistiques sur les alignements et croisements dans les tableaux de permutations. L'équidistribution de ces données statistiques est connue, et donnée par le biais d'une application très compliquée associant les alignements et croisements des tableaux a des motifs des permutations correspondantes. Nous construisons deux involutions définies sur les tableaux qui démontrent l'équidistribution des statistiques en échangeant certaines données tout en préservant d'autres. Enfin, nous dénombrons quelques ensembles de permutations définis non seulement par l'absence de certains motifs mais aussi par certains paramètres issus des tableaux de permutations.

APA, Harvard, Vancouver, ISO, and other styles

39

Khovanova, Tanya, and Eric Zhang. "Limit Densities of Patterns in Permutation Inflations." Electronic Journal of Combinatorics 28, no. 1 (January 29, 2021). http://dx.doi.org/10.37236/8234.

Full text

Abstract:

Call a permutation $k$-inflatable if the sequence of its tensor products with uniform random permutations of increasing lengths has uniform $k$-point pattern densities. Previous work has shown that nontrivial $k$-inflatable permutations do not exist for $k \geq 4$. In this paper, we derive a general formula for the limit densities of patterns in the sequence of tensor products of a fixed permutation with each permutation from a convergent sequence. By applying this result, we completely characterize $3$-inflatable permutations and find explicit examples of $3$-inflatable permutations with various lengths, including the shortest examples with length $17$.

APA, Harvard, Vancouver, ISO, and other styles

40

Cho, Soojin, and Kyoungsuk Park. "Alignments, crossings, cycles, inversions, and weak Bruhat order in permutation tableaux of type $B$." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings, 27th..., Proceedings (January 1, 2015). http://dx.doi.org/10.46298/dmtcs.2484.

Full text

Abstract:

International audience Alignments, crossings and inversions of signed permutations are realized in the corresponding permutation tableaux of type $B$, and the cycles of signed permutations are understood in the corresponding bare tableaux of type $B$. We find the relation between the number of alignments, crossings and other statistics of signed permutations, and also characterize the covering relation in weak Bruhat order on Coxeter system of type $B$ in terms of permutation tableaux of type $B$. De nombreuses statistiques importantes des permutations signées sont réalisées dans les tableaux de permutations ou ”bare” tableaux de type $B$ correspondants : les alignements, croisements et inversions des permutations signées sont réalisés dans les tableaux de permutations de type $B$ correspondants, et les cycles des permutations signées sont comprises dans les ”bare” tableaux de type $B$ correspondants. Cela nous mène à relier le nombre d’alignements et de croisements avec d’autres statistiques des permutations signées, et aussi de caractériser la relation de couverture dans l’ordre de Bruhat faible sur des systèmes de Coxeter de type $B$ en termes de tableaux de permutations de type $B$.

APA, Harvard, Vancouver, ISO, and other styles

41

Blitvić, Natasha. "SIF Permutations and Chord-Connected Permutations." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AT,..., Proceedings (January 1, 2014). http://dx.doi.org/10.46298/dmtcs.2443.

Full text

Abstract:

International audience A stabilized-interval-free (SIF) permutation on [n], introduced by Callan, is a permutation that does not stabilize any proper interval of [n]. Such permutations are known to be the irreducibles in the decomposition of permutations along non-crossing partitions. That is, if $s_n$ denotes the number of SIF permutations on [n], $S(z)=1+\sum_{n\geq1} s_n z^n$, and $F(z)=1+\sum_{n\geq1} n! z^n$, then $F(z)= S(zF(z))$. This article presents, in turn, a decomposition of SIF permutations along non-crossing partitions. Specifically, by working with a convenient diagrammatic representation, given in terms of perfect matchings on alternating binary strings, we arrive at the \emphchord-connected permutations on [n], counted by $\{c_n\}_{n\geq1}$, whose generating function satisfies $S(z)= C(zS(z))$. The expressions at hand have immediate probabilistic interpretations, via the celebrated moment-cumulant formula of Speicher, in the context of the free probability theory of Voiculescu. The probability distributions that appear are the exponential and the complex Gaussian.

APA, Harvard, Vancouver, ISO, and other styles

42

Avgustinovich, Sergey, Sergey Kitaev, and Anna Taranenko. "On Five Types of Crucial Permutations with Respect to Monotone Patterns." Electronic Journal of Combinatorics 30, no. 1 (February 24, 2023). http://dx.doi.org/10.37236/11500.

Full text

Abstract:

A crucial permutation is a permutation that avoids a given set of prohibitions, but any of its extensions, in an allowable way, results in a prohibition being introduced. In this paper, we introduce five natural types of crucial permutations with respect to monotone patterns, notably quadracrucial permutations that are linked most closely to Erdős-Szekeres extremal permutations. The way we define right-crucial and bicrucial permutations is consistent with the definition of respective permutations studied in the literature in the contexts of other prohibitions. For each of the five types, we provide its characterization in terms of Young tableaux via the Robinson-Schensted correspondence. Moreover, we use the characterizations to prove that the number of such permutations of length $n$ is growing when $n\to\infty$, and to enumerate minimal crucial permutations in all but one case. We also provide other enumerative results.

APA, Harvard, Vancouver, ISO, and other styles

43

Claesson, Anders, Vít Jelínek, Eva Jelínková, and Sergey Kitaev. "Pattern avoidance in partial permutations (extended abstract)." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AN,..., Proceedings (January 1, 2010). http://dx.doi.org/10.46298/dmtcs.2818.

Full text

Abstract:

International audience Motivated by the concept of partial words, we introduce an analogous concept of partial permutations. A $\textit{partial permutation of length n with k holes}$ is a sequence of symbols $\pi = \pi_1 \pi_2 \cdots \pi_n$ in which each of the symbols from the set $\{1,2,\ldots,n-k\}$ appears exactly once, while the remaining $k$ symbols of $\pi$ are "holes''. We introduce pattern-avoidance in partial permutations and prove that most of the previous results on Wilf equivalence of permutation patterns can be extended to partial permutations with an arbitrary number of holes. We also show that Baxter permutations of a given length $k$ correspond to a Wilf-type equivalence class with respect to partial permutations with $(k-2)$ holes. Lastly, we enumerate the partial permutations of length $n$ with $k$ holes avoiding a given pattern of length at most four, for each $n \geq k \geq 1$. Nous introduisons un concept de permutations partielles. $\textit{Une permutation partielle de longueur n avec k trous}$ est une suite finie de symboles $\pi = \pi_1 \pi_2 \cdots \pi_n$ dans laquelle chaque nombre de l'ensemble $\{1,2,\ldots,n-k\}$ apparaît précisément une fois, tandis que les $k$ autres symboles de $\pi$ sont des "trous''. Nous introduisons l'étude des permutations partielles à motifs exclus et nous montrons que la plupart des résultats sur l'équivalence de Wilf peuvent être généralisés aux permutations partielles avec un nombre arbitraire de trous. De plus, nous montrons que les permutations de Baxter d'une longueur donnée $k$ forment une classe d'équivalence du type Wilf par rapport aux permutations partielles avec $(k-2)$ trous. Enfin, nous présentons l'énumération des permutations partielles de longueur $n$ avec $k$ trous qui évitent un motif de longueur $\ell \leq 4$, pour chaque $n \geq k \geq 1$.

APA, Harvard, Vancouver, ISO, and other styles

44

Lipson, Mark. "Completion of the Wilf-Classification of 3-5 Pairs Using Generating Trees." Electronic Journal of Combinatorics 13, no. 1 (April 4, 2006). http://dx.doi.org/10.37236/1057.

Full text

Abstract:

A permutation $\pi$ is said to avoid the permutation $\tau$ if no subsequence in $\pi$ has the same order relations as $\tau$. Two sets of permutations $\Pi_1$ and $\Pi_2$ are Wilf-equivalent if, for all $n$, the number of permutations of length $n$ avoiding all of the permutations in $\Pi_1$ equals the number of permutations of length $n$ avoiding all of the permutations in $\Pi_2$. Using generating trees, we complete the problem of finding all Wilf-equivalences among pairs of permutations of which one has length 3 and the other has length 5 by proving that $\{123,32541\}$ is Wilf-equivalent to $\{123,43251\}$ and that $\{123,42513\}$ is Wilf-equivalent to $\{132, 34215\}$. In addition, we provide generating trees for fourteen other pairs, among which there are two examples of pairs that give rise to isomorphic generating trees.

APA, Harvard, Vancouver, ISO, and other styles

45

Eriksson, Kimmo, and Svante Linusson. "The size of Fulton's essential set." Electronic Journal of Combinatorics 2, no. 1 (April 3, 1995). http://dx.doi.org/10.37236/1200.

Full text

Abstract:

The essential set of a permutation was defined by Fulton as the set of southeast corners of the diagram of the permutation. In this paper we determine explicit formulas for the average size of the essential set in the two cases of arbitrary permutations in $S_n$ and $321$-avoiding permutations in $S_n$. Vexillary permutations are discussed too. We also prove that the generalized Catalan numbers ${r+k-1\choose n}-{r+k-1\choose n-2}$ count $r\times k$-matrices dotted with $n$ dots that are extendable to $321$-avoiding permutation matrices.

APA, Harvard, Vancouver, ISO, and other styles

46

Timashev, Aleksandr N. "On the probability of coincidence of cycle lengths for independent random permutations with given number of cycles." Discrete Mathematics and Applications 25, no. 6 (January 1, 2015). http://dx.doi.org/10.1515/dma-2015-0036.

Full text

Abstract:

AbstractFrom the set of all permutations of the degree n with a given number N ≤ n of cycles two permutations are choosed randomly, uniformly and independently. The cycles of each permutation are numbered in some of N! possible ways. We study the coincidence probability of the cycle lengths of permutations for a given numbering. This probability up to a suitably selected renumbering of cycles of the first permutation equals to the probability of similarity of these permutations. The asymptotic estimates of the coincidence probability of the cycle lengths are obtained for five types of relations between N, n → ∞.

APA, Harvard, Vancouver, ISO, and other styles

47

Claesson, Anders, Vít Jelínek, Eva Jelínková, and Sergey Kitaev. "Pattern Avoidance in Partial Permutations." Electronic Journal of Combinatorics 18, no. 1 (January 26, 2011). http://dx.doi.org/10.37236/512.

Full text

Abstract:

Motivated by the concept of partial words, we introduce an analogous concept of partial permutations. A partial permutation of length $n$ with $k$ holes is a sequence of symbols $\pi=\pi_1\pi_2\dotsb\pi_n$ in which each of the symbols from the set $\{1,2,\dotsc,n-k\}$ appears exactly once, while the remaining $k$ symbols of $\pi$ are "holes". We introduce pattern-avoidance in partial permutations and prove that most of the previous results on Wilf equivalence of permutation patterns can be extended to partial permutations with an arbitrary number of holes. We also show that Baxter permutations of a given length $k$ correspond to a Wilf-type equivalence class with respect to partial permutations with $(k-2)$ holes. Lastly, we enumerate the partial permutations of length $n$ with $k$ holes avoiding a given pattern of length at most four, for each $n\ge k\ge 1$.

APA, Harvard, Vancouver, ISO, and other styles

48

Pan, Ran, and Jeffrey B. Remmel. "Asymptotics for minimal overlapping patterns for generalized Euler permutations, standard tableaux of rectangular shape, and column strict arrays." Discrete Mathematics & Theoretical Computer Science Vol. 18 no. 2, Permutation..., Permutation Patterns (May 20, 2016). http://dx.doi.org/10.46298/dmtcs.1315.

Full text

Abstract:

A permutation $\tau$ in the symmetric group $S_j$ is minimally overlapping if any two consecutive occurrences of $\tau$ in a permutation $\sigma$ can share at most one element. B\'ona \cite{B} showed that the proportion of minimal overlapping patterns in $S_j$ is at least $3 -e$. Given a permutation $\sigma$, we let $\text{Des}(\sigma)$ denote the set of descents of $\sigma$. We study the class of permutations $\sigma \in S_{kn}$ whose descent set is contained in the set $\{k,2k, \ldots (n-1)k\}$. For example, up-down permutations in $S_{2n}$ are the set of permutations whose descent equal $\sigma$ such that $\text{Des}(\sigma) = \{2,4, \ldots, 2n-2\}$. There are natural analogues of the minimal overlapping permutations for such classes of permutations and we study the proportion of minimal overlapping patterns for each such class. We show that the proportion of minimal overlapping permutations in such classes approaches $1$ as $k$ goes to infinity. We also study the proportion of minimal overlapping patterns in standard Young tableaux of shape $(n^k)$. Comment: Accepted by Discrete Math and Theoretical Computer Science. Thank referees' for their suggestions

APA, Harvard, Vancouver, ISO, and other styles

49

Vatter, Vincent. "An Erd\H{o}s--Hajnal analogue for permutation classes." Discrete Mathematics & Theoretical Computer Science Vol. 18 no. 2, Permutation..., Permutation Patterns (March 24, 2016). http://dx.doi.org/10.46298/dmtcs.1328.

Full text

Abstract:

Let $\mathcal{C}$ be a permutation class that does not contain all layered permutations or all colayered permutations. We prove that there is a constant $c$ such that every permutation in $\mathcal{C}$ of length $n$ contains a monotone subsequence of length $cn$.

APA, Harvard, Vancouver, ISO, and other styles

50

Linman, Julie, and Michael Pinsker. "Permutations on the Random Permutation." Electronic Journal of Combinatorics 22, no. 2 (June 22, 2015). http://dx.doi.org/10.37236/4910.

Full text

Abstract:

The random permutation is the Fraïssé limit of the class of finite structures with two linear orders. Answering a problem stated by Peter Cameron in 2002, we use a recent Ramsey-theoretic technique to show that there exist precisely 39 closed supergroups of the automorphism group of the random permutation, and thereby expose all symmetries of this structure. Equivalently, we classify all structures which have a first-order definition in the random permutation.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Permutations'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles