Bibliografie tematiche / Permutations / Articoli di riviste

Segui questo link per vedere altri tipi di pubblicazioni sul tema: Permutations.

Articoli di riviste sul tema "Permutations"

Autore: Grafiati

Pubblicato: 4 giugno 2021

Ultima modifica: 9 giugno 2025

Cita una fonte nei formati APA, MLA, Chicago, Harvard e in molti altri stili

Scegli il tipo di fonte:

Vedi i top-50 articoli di riviste per l'attività di ricerca sul tema "Permutations".

Accanto a ogni fonte nell'elenco di riferimenti c'è un pulsante "Aggiungi alla bibliografia". Premilo e genereremo automaticamente la citazione bibliografica dell'opera scelta nello stile citazionale di cui hai bisogno: APA, MLA, Harvard, Chicago, Vancouver ecc.

Puoi anche scaricare il testo completo della pubblicazione scientifica nel formato .pdf e leggere online l'abstract (il sommario) dell'opera se è presente nei metadati.

Vedi gli articoli di riviste di molte aree scientifiche e compila una bibliografia corretta.

Malyshev, Fedor M. "Realization of even permutations of even degree by products of four involutions without fixed points." Discrete Mathematics and Applications 34, no. 5 (October 1, 2024): 263–76. http://dx.doi.org/10.1515/dma-2024-0023.

Testo completo

Abstract (sommario):

Abstract We consider representations of an arbitrary permutation π of degree 2n, n ⩾ 3, by products of the so-called (2 n )-permutations (any cycle of such a permutation has length 2). We show that any even permutation is represented by the product of four (2 n )-permutations. Products of three (2 n )-permutations cannot represent all even permutations. Any odd permutation is realized (for odd n) by a product of five (2 n )-permutations.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

Savchuk, M., та 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, № 2 (2019): 36–43. http://dx.doi.org/10.17721/1812-5409.2019/2.3.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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

Gli stili APA, Harvard, Vancouver, ISO e altri

Just, Matthew, and Hua Wang. "Note on packing patterns in colored permutations." Online Journal of Analytic Combinatorics, no. 11 (December 31, 2016): 1–9. https://doi.org/10.61091/ojac-1104.

Testo completo

Abstract (sommario):

Packing patterns in permutations concerns finding the permutation with the maximum number of a prescribed pattern. In 2002, Albert, Atkinson, Handley, Holton and Stromquist showed that there always exists a layered permutation containing the maximum number of a layered pattern among all permutations of length n. Consequently the packing density for all but two (up to equivalence) patterns up to length 4 can be obtained. In this note we consider the analogous question for colored patterns and permutations. By introducing the concept of “colored blocks” we characterize the optimal permutations with the maximum number of a given colored pattern when it contains at most three colored blocks. As examples we apply this characterization to find the optimal permutations of various colored patterns and subsequently obtain their corresponding packing densities.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

Malyshev, Fedor Mikhailovich. "Realization of permutations of even degree by products of three fixed-point-free involutions." Sbornik: Mathematics 215, no. 12 (2024): 1720–54. https://doi.org/10.4213/sm10020e.

Testo completo

Abstract (sommario):

We consider representations of a permutation $\pi$ of degree $2n$, $n\geqslant3$, by a product of three so-called pairwise-cycle permutations, all of whose cycles have length $2$. This is a valid question for even permutations if $n$ is even and for odd permutations if $n$ is odd. We prove constructively that for $n\geqslant4$, $n\neq8$, such a representation holds for all permutations $\pi$ of the same parity as $n$, apart from four exceptional conjugacy classes. For $n=8$ there are five exceptional conjugacy classes, and for $n=3$ there is one such class. Bibliography: 32 titles.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

Abba, Sani, Usman Sanusi, and Sulaiman Sani. "Permutation Pattern Avoidance in the Alternating Sign Matrices." UMYU Scientifica 3, no. 4 (December 24, 2024): 386–98. https://doi.org/10.56919/usci.2434.033.

Testo completo

Abstract (sommario):

Study’s Excerpt Aunu permutations (permutations of prime length with their first entry as unity) are explored with a specific focus on involutions. The concept of pattern avoidance is examined using Aunu permutations that avoid the 213 pattern. The results reveal that Catalan numbers count the set of alternating sign matrices. Both bijective and algebraic proofs are provided to support the findings. The study transforms classical ideas, first presented by Abdullahi bin Fodiyo in his book called Da'ulmusalli (light to a worshipper), into modern mathematical science. Full Abstract We represented permutations using matrices. In the alternating sign matrices, the idea of pattern avoidance in permutation matrices with reference to Aunu Permutations is examined. The primary outcome is that the Catalan numbers count the set of alternating sign matrices related to Aunu Permutations that do not follow pattern 213. Both a bijective and an algebraic proof are given.

Gli stili APA, Harvard, Vancouver, ISO e altri

Andreoli, Samuele, Enrico Piccione, Lilya Budaghyan, Pantelimon Stănică, and Svetla Nikova. "On Decompositions of Permutations in Quadratic Functions." Journal of Cryptology 38, no. 3 (June 2, 2025). https://doi.org/10.1007/s00145-025-09547-4.

Testo completo

Abstract (sommario):

Abstract The algebraic degree of a vectorial Boolean function is one of the main parameters driving the cost of its hardware implementation. Thus, finding decompositions of functions into sequences of functions of lower algebraic degrees has been explored to reduce the cost of implementations. In this paper, we consider such decompositions of permutations over $$\mathbb {F}_{2^n}$$ F 2 n . We prove the existence of a decomposition of the inverse using quadratic and linear power permutations for all permutations when $$2^n-1$$ 2 n - 1 is a prime, and we prove the non-existence of such decompositions for power permutations of differential uniformity strictly lower than 16 when 4|n. We also prove that any permutation admits a decomposition into quadratic power permutations and affine permutations of the form $$ax+b$$ a x + b if $$4 \not \mid n$$ 4 ∤ n . Furthermore, we prove that any permutation admits a decomposition into cubic power permutations and affine permutations. Finally, we present a decomposition of the PRESENT S-Box using the power permutation $$x^7$$ x 7 and affine permutations.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

Dimitrov, Alexander, Sebastiyan Georgiev, and Nikolay Yankov. "Programming realization of permutations." Proceedings. College Dobrich X (December 25, 2018). https://doi.org/10.5281/zenodo.10004792.

Testo completo

Abstract (sommario):

We are studying permutations. Algorithms for generating permutations are shown: a naive one, and an algorithm based on the successor of a given permutation. Both algorithms are realized in C++. The second part of this work shows rank and unrank functions for permutation

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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 → ∞.

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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

Gli stili APA, Harvard, Vancouver, ISO e altri

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.

Testo completo

Abstract (sommario):

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

Gli stili APA, Harvard, Vancouver, ISO e altri

Offriamo sconti su tutti i piani premium per gli autori le cui opere sono incluse in raccolte letterarie tematiche. Contattaci per ottenere un codice promozionale unico!