Journal articles: 'Permutation'

1

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

2

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

3

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

4

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

5

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

6

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

7

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

8

KRASILENKO, VLADIMIR, NATALIYA YURCHUK, and DIANA NIKITOVICH. "THE APPLICATION OF ISOMORPHIC MATRIX REPRESENTATIONS FOR MODELING THE PROTOCOL FOR THE FORMATION OF SECRET KEYS-PERMUTATIONS OF HUGE SIZES." HERALD OF KHMELNYTSKYI NATIONAL UNIVERSITY 295, no. 2 (May 2021): 78–88. http://dx.doi.org/10.31891/2307-5732-2021-295-2-78-88.

Full text

Abstract:

A The article considers the peculiarities of the application of isomorphic matrix representations for modeling the protocol of matching secret keys-permutations of significant dimension. The situation is considered when for cryptographic transformations of blocks with a length of 256 * 256 bytes, presented in the form of a matrix of a black-and-white image, it is necessary to rearrange all bytes in accordance with the matrix keys. To generate a basic matrix key and the appearance of the components KeyA and KeyB in the format of two black and white images, a software module using engineering mathematical software Mathcad is proposed. Simulations are performed, for example, with sets of fixed matrix representations. The essence of the protocol of coordination of the main matrix of permutations by the parties is considered. Also shown are software modules in Mathcad for accelerated methods that display the procedure of iterative permutations in a permutation matrix isomorphic to the elevation of the permutation matrix to the desired degree with a certain side, corresponding to specific bits of bits or other code representations of selected random numbers. It is demonstrated that the parties receive new permutation matrices after the first step of the protocol, those sent to the other party, and the identical new permutation matrices received by the parties after the second step of the protocol, ie the secret permutation matrix. Similar qualitative cryptographic transformations have been confirmed using the proposed representations of the permutation matrix based on the results of modeling matrix affine-permutation ciphers and multi-step matrix affine-permutation ciphers for different cases when the components of affine transformations are first executed in different sequences. , and then permutation using the permutation matrix, or vice versa. The model experiments performed in the study demonstrated the adequacy of the functioning of the models proposed by the protocol and methods of generating a permutation matrix and demonstrated their advantages.

APA, Harvard, Vancouver, ISO, and other styles

9

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

10

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

11

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

12

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

13

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

14

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

15

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

16

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

17

Tovstyuk, K. D., C. C. Tovstyuk, and O. O. Danylevych. "The Permutation Group Theory and Electrons Interaction." International Journal of Modern Physics B 17, no. 21 (August 20, 2003): 3813–30. http://dx.doi.org/10.1142/s0217979203021812.

Full text

Abstract:

The new mathematical formalism for the Green's functions of interacting electrons in crystals is constructed. It is based on the theory of Green's functions and permutation groups. We constructed a new object of permutation groups, which we call double permutation (DP). DP allows one to take into consideration the symmetry of the ground state as well as energy and momentum conservation in every virtual interaction. We developed the classification of double permutations and proved the theorem, which allows the selection of classes of associated double permutations (ADP). The Green's functions are constructed for series of ADP. We separate in the DP the convolving columns by replacing the initial interaction between the particles with the effective interaction. In convoluting the series for Green's functions, we use the methods developed for permutation groups schemes of Young–Yamanuti.

APA, Harvard, Vancouver, ISO, and other styles

18

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

19

Niwareeba, Roland, Mitchell A. Cox, and Ling Cheng. "Adaptive-Mode PAPR Reduction Algorithm for Optical OFDM Systems Leveraging Lexicographical Permutations." Electronics 12, no. 13 (June 24, 2023): 2797. http://dx.doi.org/10.3390/electronics12132797.

Full text

Abstract:

In direct current optical orthogonal frequency division multiplexing (DCO-OFDM) systems, the high peak-to-average power ratio (PAPR) has been a significant challenge. Recently, lexicographical symbol position permutation (LSPP) using random permutations has been introduced as an efficient solution to reduce high PAPR. In this paper, we aim to evaluate the effectiveness of LSPP by comparing both adjacent and interleaved lexicographical permutation sequences with random lexicographical permutation sequences. Our findings demonstrate that random permutation yields superior PAPR reduction performance results when compared to adjacent and interleaved permutation. However, in scenarios with a limited number of sub-blocks, the use of adjacent and interleaved permutation becomes more favorable, as they can eliminate the possibility of generating identical permutation sequences, a drawback of random permutation. Additionally, we propose a novel algorithm to determine the optimal number of candidate permutation sequences that can achieve acceptable PAPR reduction performance while adhering to computational complexity constraints defined by the system requirements.

APA, Harvard, Vancouver, ISO, and other styles

20

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

21

I, Suleiman, Garba A.I, and Mustafa A. "ON SOME NON-DERANGED PERMUTATION: A NEW METHOD OF CONSTRUCTION." International Journal of Research -GRANTHAALAYAH 8, no. 3 (May 26, 2020): 309–14. http://dx.doi.org/10.29121/granthaalayah.v8.i3.2020.162.

Full text

Abstract:

In this paper, we construct a permutation group via a composition operation on some permutations generated from the structure for prime and as defined by [1]. Thus, providing a new method of constructing permutation group from existing ones.

APA, Harvard, Vancouver, ISO, and other styles

22

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

23

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

24

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

25

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

26

Paik, Hyojung, Yongseong Cho, Seong Beom Cho, and Oh-Kyoung Kwon. "MPI-GWAS: a supercomputing-aided permutation approach for genome-wide association studies." Genomics & Informatics 20, no. 1 (March 31, 2022): e14. http://dx.doi.org/10.5808/gi.22001.

Full text

Abstract:

Permutation testing is a robust and popular approach for significance testing in genomic research that has the advantage of reducing inflated type 1 error rates; however, its compu-tational cost is notorious in genome-wide association studies (GWAS). Here, we developed a supercomputing-aided approach to accelerate the permutation testing for GWAS, based on the message-passing interface (MPI) on parallel computing architecture. Our application, called MPI-GWAS, conducts MPI-based permutation testing using a parallel computing approach with our supercomputing system, Nurion (8,305 compute nodes, and 563,740 central processing units [CPUs]). For 107 permutations of one locus in MPI-GWAS, it was calculated in 600 s using 2,720 CPU cores. For 107 permutations of ~30,000–50,000 loci in over 7,000 subjects, the total elapsed time was ~4 days in the Nurion supercomputer. Thus, MPI-GWAS enables us to feasibly compute the permutation-based GWAS within a reason-able time by harnessing the power of parallel computing resources.

APA, Harvard, Vancouver, ISO, and other styles

27

Tsaban, Boaz. "Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation." Journal of Algorithms 47, no. 2 (July 2003): 104–21. http://dx.doi.org/10.1016/s0196-6774(03)00017-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

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

29

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

30

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

31

ATMINAS, AISTIS, VADIM V. LOZIN, SERGEY KITAEV, and ALEXANDR VALYUZHENICH. "UNIVERSAL GRAPHS AND UNIVERSAL PERMUTATIONS." Discrete Mathematics, Algorithms and Applications 05, no. 04 (December 2013): 1350038. http://dx.doi.org/10.1142/s1793830913500389.

Full text

Abstract:

Let X be a family of graphs and Xn the set of n-vertex graphs in X. A graph U(n) containing all graphs from Xn as induced subgraphs is called n-universal for X. Moreover, we say that U(n) is a propern-universal graph for X if it belongs to X. In the present paper, we construct a proper n-universal graph for the class of split permutation graphs. Our solution includes two ingredients: a proper universal 321-avoiding permutation and a bijection between 321-avoiding permutations and symmetric split permutation graphs. The n-universal split permutation graph constructed in this paper has 4n3 vertices, which means that this construction is order-optimal.

APA, Harvard, Vancouver, ISO, and other styles

32

Hultman, Axel. "Permutation statistics of products of random permutations." Advances in Applied Mathematics 54 (March 2014): 1–10. http://dx.doi.org/10.1016/j.aam.2013.10.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Niemenmaa, Markku. "Decomposition of Transformation Groups of Permutation Machines." Fundamenta Informaticae 10, no. 4 (October 1, 1987): 363–67. http://dx.doi.org/10.3233/fi-1987-10403.

Full text

Abstract:

By a permutation machine we mean a triple (Q,S,F), where Q and S are finite sets and F is a function Q × S → Q which defines a permutation on Q for every element from S. These permutations generate a permutation group G and by considering the structure of G we can obtain efficient ways to decompose the transformation group (Q,G). In this paper we first consider the situation where G is half-transitive and after this we show how to use our result in the general non-transitive case.

APA, Harvard, Vancouver, ISO, and other styles

34

Suleiman I., Suleiman I., and Ejima O. Ejima O. "Semi-Magic Permutation: A Composition Study on the Structure ωi." Academic Journal of Applied Mathematical Sciences, no. 510 (May 15, 2019): 136–39. http://dx.doi.org/10.32861/ajams.510.136.139.

Full text

Abstract:

In this paper we propose a definition for a semi-magic permutation and study the composition function behavior between the magic, semi-magic and non-magic permutation using the structure defined as: (figure) Where p is a prime greater than or less than five. We equally observed that no permutations for is magic or semi-magic.

APA, Harvard, Vancouver, ISO, and other styles

35

Bischoff, M. "A remark about the anomalies of cyclic holomorphic permutation orbifolds." International Journal of Mathematics 31, no. 10 (July 31, 2020): 2050080. http://dx.doi.org/10.1142/s0129167x20500809.

Full text

Abstract:

Using a result of Longo and Xu, we show that the anomaly arising from a cyclic permutation orbifold of order 3 of a holomorphic conformal net [Formula: see text] with central charge [Formula: see text] depends on the “gravitational anomaly” [Formula: see text]. In particular, the conjecture that holomorphic permutation orbifolds are non-anomalous and therefore a stronger conjecture of Müger about braided crossed [Formula: see text]-categories arising from permutation orbifolds of completely rational conformal nets are wrong. More generally, we show that cyclic permutations of order [Formula: see text] are non-anomalous if and only if [Formula: see text] or [Formula: see text]. We also show that all cyclic permutation gaugings of [Formula: see text] arise from conformal nets.

APA, Harvard, Vancouver, ISO, and other styles

36

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

37

Burns, J. M., B. Goldsmith, B. Hartley, and R. Sandling. "On quasi-permutation representations of finite groups." Glasgow Mathematical Journal 36, no. 3 (September 1994): 301–8. http://dx.doi.org/10.1017/s0017089500030901.

Full text

Abstract:

In [6], Wong defined a quasi-permutation group of degree n to be a finite group G of automorphisms of an n-dimensional complex vector space such that every element of G has non-negative integral trace. The terminology derives from the fact that if G is a finite group of permutations of a set ω of size n, and we think of G as acting on the complex vector space with basis ω, then the trace of an element g ∈ G is equal to the number of points of ω fixed by g. In [6] and [7], Wong studied the extent to which some facts about permutation groups generalize to the quasi-permutation group situation. Here we investigate further the analogy between permutation groups and quasipermutation groups by studying the relation between the minimal degree of a faithful permutation representation of a given finite group G and the minimal degree of a faithful quasi-permutation representation. We shall often prefer to work over the rational field rather than the complex field.

APA, Harvard, Vancouver, ISO, and other styles

38

ELRIFAI, E. A., and M. ANIS. "POSITIVE PERMUTATION BRAIDS AND PERMUTATION INVERSIONS WITH SOME APPLICATIONS." Journal of Knot Theory and Its Ramifications 21, no. 10 (July 11, 2012): 1250101. http://dx.doi.org/10.1142/s0218216512501015.

Full text

Abstract:

In this paper we constructed an isomorphic group of binary matrices to a finite symmetric group. Our method is based on the inversion of permutations. Using this embedding we find an algorithm for writing down a standard braid word representation for each positive permutation braid. Also an algorithm for writing basis of Hecke algebra Hn+1 from such basis of Hn is given.

APA, Harvard, Vancouver, ISO, and other styles

39

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

40

Brändén, Petter, and Anders Claesson. "Mesh Patterns and the Expansion of Permutation Statistics as Sums of Permutation Patterns." Electronic Journal of Combinatorics 18, no. 2 (March 15, 2011). http://dx.doi.org/10.37236/2001.

Full text

Abstract:

Any permutation statistic $f:{\mathfrak{S}}\to{\mathbb C}$ may be represented uniquely as a, possibly infinite, linear combination of (classical) permutation patterns: $f= \Sigma_\tau\lambda_f(\tau)\tau$. To provide explicit expansions for certain statistics, we introduce a new type of permutation patterns that we call mesh patterns. Intuitively, an occurrence of the mesh pattern $p=(\pi,R)$ is an occurrence of the permutation pattern $\pi$ with additional restrictions specified by $R$ on the relative position of the entries of the occurrence. We show that, for any mesh pattern $p=(\pi,R)$, we have $\lambda_p(\tau) = (-1)^{|\tau|-|\pi|}{p}^{\star}(\tau)$ where ${p}^{\star}=(\pi,R^c)$ is the mesh pattern with the same underlying permutation as $p$ but with complementary restrictions. We use this result to expand some well known permutation statistics, such as the number of left-to-right maxima, descents, excedances, fixed points, strong fixed points, and the major index. We also show that alternating permutations, André permutations of the first kind and simsun permutations occur naturally as permutations avoiding certain mesh patterns. Finally, we provide new natural Mahonian statistics.

APA, Harvard, Vancouver, ISO, and other styles

41

Bean, Christian, Émile Nadeau, and Henning Ulfarsson. "Enumeration of Permutation Classes and Weighted Labelled Independent Sets." Discrete Mathematics & Theoretical Computer Science 22 no. 2, Permutation..., Special issues (March 29, 2021). http://dx.doi.org/10.46298/dmtcs.5995.

Full text

Abstract:

In this paper, we study the staircase encoding of permutations, which maps a permutation to a staircase grid with cells filled with permutations. We consider many cases, where restricted to a permutation class, the staircase encoding becomes a bijection to its image. We describe the image of those restrictions using independent sets of graphs weighted with permutations. We derive the generating function for the independent sets and then for their weighted counterparts. The bijections we establish provide the enumeration of permutation classes. We use our results to uncover some unbalanced Wilf-equivalences of permutation classes and outline how to do random sampling in the permutation classes. In particular, we cover the classes $\mathrm{Av}(2314,3124)$, $\mathrm{Av}(2413,3142)$, $\mathrm{Av}(2413,3124)$, $\mathrm{Av}(2413,2134)$ and $\mathrm{Av}(2314,2143)$, as well as many subclasses. Comment: Final formatting for publication in DMTCS

APA, Harvard, Vancouver, ISO, and other styles

42

Dutta, Avijit, Mridul Nandi, and Suprita Talnikar. "Permutation Based EDM: An Inverse Free BBB Secure PRF." IACR Transactions on Symmetric Cryptology, June 11, 2021, 31–70. http://dx.doi.org/10.46586/tosc.v2021.i2.31-70.

Full text

Abstract:

In CRYPTO 2019, Chen et al. have initiated an interesting research direction in designing PRF based on public permutations. They have proposed two beyond the birthday bound secure n-bit to n-bit PRF constructions, i.e., SoEM22 and SoKAC21, which are built on public permutations, where n is the size of the permutation. However, both of their constructions require two independent instances of public permutations. In FSE 2020, Chakraborti et al. have proposed a single public permutation based n-bit to n-bit beyond the birthday bound secure PRF, which they refer to as PDMMAC. Although the construction is minimal in the number of permutations, it requires the inverse call of its underlying permutation in their design. Coming up with a beyond the birthday bound secure public permutation based n-bit to n-bit PRF with a single permutation and two forward calls was left as an open problem in their paper. In this work, we propose pEDM, a single permutation based n-bit to n-bit PRF with two calls that do not require invertibility of the permutation. We have shown that our construction is secured against all adaptive information-theoretic distinguishers that make roughly up to 22n/3 construction and primitive queries. Moreover, we have also shown a matching attack with similar query complexity that establishes the tightness of our security bound.

APA, Harvard, Vancouver, ISO, and other styles

43

Ramdas, Aaditya, Rina Foygel Barber, Emmanuel J. Candès, and Ryan J. Tibshirani. "Permutation Tests Using Arbitrary Permutation Distributions." Sankhya A, June 3, 2023. http://dx.doi.org/10.1007/s13171-023-00308-8.

Full text

Abstract:

AbstractPermutation tests date back nearly a century to Fisher’s randomized experiments, and remain an immensely popular statistical tool, used for testing hypotheses of independence between variables and other common inferential questions. Much of the existing literature has emphasized that, for the permutation p-value to be valid, one must first pick a subgroup G of permutations (which could equal the full group) and then recalculate the test statistic on permuted data using either an exhaustive enumeration of G, or a sample from G drawn uniformly at random. In this work, we demonstrate that the focus on subgroups and uniform sampling are both unnecessary for validity—in fact, a simple random modification of the permutation p-value remains valid even when using an arbitrary distribution (not necessarily uniform) over any subset of permutations (not necessarily a subgroup). We provide a unified theoretical treatment of such generalized permutation tests, recovering all known results from the literature as special cases. Thus, this work expands the flexibility of the permutation test toolkit available to the practitioner.

APA, Harvard, Vancouver, ISO, and other styles

44

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

45

Cooper, Joshua N. "A Permutation Regularity Lemma." Electronic Journal of Combinatorics 13, no. 1 (March 14, 2006). http://dx.doi.org/10.37236/1048.

Full text

Abstract:

We introduce a permutation analogue of the celebrated Szemerédi Regularity Lemma, and derive a number of consequences. This tool allows us to provide a structural description of permutations which avoid a specified pattern, a result that permutations which scatter small intervals contain all possible patterns of a given size, a proof that every permutation avoiding a specified pattern has a nearly monotone linear-sized subset, and a "thin deletion" result. We also show how one can count sub-patterns of a permutation with an integral, and relate our results to permutation quasirandomness in a manner analogous to the graph-theoretic setting.

APA, Harvard, Vancouver, ISO, and other styles

46

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

47

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

48

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

49

Adam Kabela, Daniel Král', Jonathan A. Noel, and Théo Pierron. "Density Maximizers of Layered Permutations." Electronic Journal of Combinatorics 29, no. 3 (September 9, 2022). http://dx.doi.org/10.37236/10781.

Full text

Abstract:

A permutation is layered if it contains neither $231$ nor $312$ as a pattern.It is known that, if $\sigma$ is a layered permutation, then the density of $\sigma$ in a permutation of order $n$ is maximized by a layered permutation. Albert, Atkinson, Handley, Holton and Stromquist [Electron. J. Combin. 9 (2002), #R5] claimed that the density of a layered permutation with layers of sizes $(a,1,b)$ where $a,b\geq2$ is asymptotically maximized by layered permutations with a bounded number of layers, and conjectured that the same holds if a layered permutation has no consecutive layers of size one and its first and last layers are of size at least two. We show that, if $\sigma$ is a layered permutation whose first layer is sufficiently large and second layer is of size one, then the number of layers tends to infinity in every sequence of layered permutations asymptotically maximizing the density of $\sigma$. This disproves the conjecture and the claim of Albert et al. We complement this result by giving sufficient conditions on a layered permutation to have asymptotic or exact maximizers with a bounded number of layers.

APA, Harvard, Vancouver, ISO, and other styles

50

Kitaev, Sergey, and Jeffrey Remmel. "Place-Difference-Value Patterns: A Generalization of Generalized Permutation and Word Patterns." Integers 10, no. 1 (January 2010). http://dx.doi.org/10.1515/integ.2010.011.

Full text

Abstract:

AbstractMotivated by the study of Mahonian statistics, in 2000, Babson and Steingrímsson [Sém. Lothar. Comb] introduced the notion of a “generalized permutation pattern” (GP) which generalizes the concept of “classical” permutation pattern introduced by Knuth in 1969. The invention of GPs led to a large number of publications related to properties of these patterns in permutations and words. Since the work of Babson and Steingrímsson, several further generalizations of permutation patterns have appeared in the literature, each bringing a new set of permutation or word pattern problems and often new connections with other combinatorial objects and disciplines. For example, Bousquet-Mélou et al. [J. Comb. Theory A] introduced a new type of permutation pattern that allowed them to relate permutation patterns theory to the theory of partially ordered sets.In this paper we introduce yet another, more general definition of a pattern, called place-difference-value patterns (PDVP) that covers all of the most common definitions of permutation and/or word patterns that have occurred in the literature. PDVPs provide many new ways to develop the theory of patterns in permutations and words. We shall give several examples of PDVPs in both permutations and words that cannot be described in terms of any other pattern conditions that have been introduced previously. Finally, we discuss several bijective questions linking our patterns to other combinatorial objects.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Permutation'

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