|
Layered Permutation
In the mathematics of permutations, a layered permutation is a permutation that reverses contiguous blocks of elements. Equivalently, it is the direct sum of decreasing permutations. One of the earlier works establishing the significance of layered permutations was , which established the Stanley–Wilf conjecture for classes of permutations forbidding a layered permutation, before the conjecture was proven more generally. Example For instance, the layered permutations of length four, with the reversed blocks separated by spaces, are the eight permutations :1 2 3 4 :1 2 43 :1 32 4 :1 432 :21 3 4 :21 43 :321 4 :4321 Characterization by forbidden patterns The layered permutations can also be equivalently described as the permutations that do not contain the permutation patterns 231 or 312. That is, no three elements in the permutation (regardless of whether they are consecutive) have the same ordering as either of these forbidden triples. Enumeration A layered permutation on the nu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order of an ordered set. Permutations differ from combinations, which are selections of some members of a set regardless of order. For example, written as tuples, there are six permutations of the set , namely (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). These are all the possible orderings of this three-element set. Anagrams of words whose letters are different are also permutations: the letters are already ordered in the original word, and the anagram is a reordering of the letters. The study of permutations of finite sets is an important topic in the fields of combinatorics and group theory. Permutations are used in almost every branch of mathematics, and in many other fields of scie ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Skew And Direct Sums Of Permutations
In combinatorics, the skew sum and direct sum of permutations are two operations to combine shorter permutations into longer ones. Given a permutation ''π'' of length ''m'' and the permutation ''σ'' of length ''n'', the skew sum of ''π'' and ''σ'' is the permutation of length ''m'' + ''n'' defined by : (\pi\ominus\sigma)(i) = \begin \pi(i)+n & \text1\le i\le m, \\ \sigma(i-m) & \textm+1\le i\le m+n,\end and the direct sum of ''π'' and ''σ'' is the permutation of length ''m'' + ''n'' defined by : (\pi\oplus\sigma)(i) = \begin \pi(i) & \text1\le i\le m,\\ \sigma(i-m)+m & \textm+1\le i\le m+n.\end Examples The skew sum of the permutations ''π'' = 2413 and ''σ'' = 35142 is 796835142 (the last five entries are equal to ''σ'', while the first four entries come from shifting the entries of ''π'') while their direct sum is 241379586 (the first four entries are equal to ''π'', while the last five come from shifting the entries of ''σ''). Sums of permu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stanley–Wilf Conjecture
The Stanley–Wilf conjecture, formulated independently by Richard P. Stanley and Herbert Wilf in the late 1980s, states that the growth rate of every proper permutation class is singly exponential. It was proved by and is no longer a conjecture. Marcus and Tardos actually proved a different conjecture, due to , which had been shown to imply the Stanley–Wilf conjecture by . Statement The Stanley–Wilf conjecture states that for every permutation ''β'', there is a constant ''C'' such that the number , ''S''''n''(''β''), of permutations of length ''n'' which avoid ''β'' as a permutation pattern is at most ''C''''n''. As observed, this is equivalent to the convergence of the limit :\lim_ \sqrt The upper bound given by Marcus and Tardos for ''C'' is exponential in the length of ''β''. A stronger conjecture of had stated that one could take ''C'' to be , where ''k'' denotes the length of ''β'', but this conjecture was disproved for the permutation by . Indeed, has sho ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Permutation Pattern
In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the permutation to the digit sequence 123...; for instance the digit sequence 213 represents the permutation on three elements that swaps elements 1 and 2. If π and σ are two permutations represented in this way (these variable names are standard for permutations and are unrelated to the number pi), then π is said to ''contain'' σ as a ''pattern'' if some subsequence of the digits of π has the same relative order as all of the digits of σ. For instance, permutation π contains the pattern 213 whenever π has three digits ''x'', ''y'', and ''z'' that appear within π in the order ''x''...''y''...''z'' but whose values are ordered as ''y'' < ''x'' < ''z'', the same as the ordering of the values in the permutation 213. T ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Wilf Equivalence
In the study of permutations and permutation patterns, Wilf equivalence is an equivalence relation on permutation classes. Two permutation classes are Wilf equivalent when they have the same numbers of permutations of each possible length, or equivalently if they have the same generating functions. The equivalence classes for Wilf equivalence are called Wilf classes; they are the combinatorial class In mathematics, a combinatorial class is a countable set of mathematical objects, together with a size function mapping each object to a non-negative integer, such that there are finitely many objects of each size. Counting sequences and isomorphis ...es of permutation classes. The counting functions and Wilf equivalences among many specific permutation classes are known. Wilf equivalence may also be described for individual permutations rather than permutation classes. In this context, two permutations are said to be Wilf equivalent if the principal permutation classes formed by forbid ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Gilbreath Permutation
A Gilbreath shuffle is a way to shuffle a deck of cards, named after mathematician Norman Gilbreath (also known for Gilbreath's conjecture). Gilbreath's principle describes the properties of a deck that are preserved by this type of shuffle, and a Gilbreath permutation is a permutation that can be formed by a Gilbreath shuffle.. Description A Gilbreath shuffle consists of the following two steps: *Deal off any number of the cards from the top of the deck onto a new pile of cards. *Riffle the new pile with the remainder of the deck. It differs from the more commonly used procedure of cutting a deck into two piles and then riffling the piles, in that the first step of dealing off cards reverses the order of the cards in the new pile, whereas cutting the deck would preserve this order. Gilbreath's principle Although seemingly highly random, Gilbreath shuffles preserve many properties of the initial deck. For instance, if the initial deck of cards alternates between black and red card ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Superpattern
In the mathematical study of permutations and permutation patterns, a superpattern or universal permutation is a permutation that contains all of the patterns of a given length. More specifically, a ''k''-superpattern contains all possible patterns of length ''k''. Definitions and example If π is a permutation of length ''n'', represented as a sequence of the numbers from 1 to ''n'' in some order, and ''s'' = ''s''1, ''s''2, ..., ''s''''k'' is a subsequence of π of length ''k'', then ''s'' corresponds to a unique ''pattern'', a permutation of length ''k'' whose elements are in the same order as ''s''. That is, for each pair ''i'' and ''j'' of indexes, the ''i''th element of the pattern for ''s'' should be less than the ''j''the element if and only if the ''i''th element of ''s'' is less than the ''j''th element. Equivalently, the pattern is order-isomorphic to the subsequence. For instance, if π is the permutation 25314, then it has ten subsequences of length three, for ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sorting Number
In mathematics and computer science, the sorting numbers are a sequence of numbers introduced in 1950 by Hugo Steinhaus for the analysis of comparison sort algorithms. These numbers give the worst-case number of comparisons used by both binary insertion sort and merge sort. However there are other algorithms that use fewer comparisons. Formula and examples The nth sorting number is given by the formula :n\,S(n)-2^+1 where :S(n)=\lfloor 1 + \log_2 n \rfloor. The sequence of numbers given by this formula (starting with n=1) is :0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, ... . The same sequence of numbers can also be obtained from the recurrence relation :A(n) = A\bigl(\lfloor n/2\rfloor\bigr)+A\bigl(\lceil n/2\rceil\bigr)+n-1. It is an example of a 2-regular sequence. Asymptotically, the value of the nth sorting number fluctuates between approximately n\log_2 n-n and n\log_2 n-0.915n depending on the ratio between n and the nearest power of two. Application to sorting In ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Insertion Sort
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: * Simple implementation: Jon Bentley shows a three-line C/C++ version that is five lines when optimized. * Efficient for (quite) small data sets, much like other quadratic (i.e., O(''n''2)) sorting algorithms * More efficient in practice than most other simple quadratic algorithms such as selection sort or bubble sort * Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(''kn'') when each element in the input is no more than places away from its sorted position * Stable; i.e., does not change the relative order of elements with equal keys * In-place; i.e., only requires a constant amount O(1) of additional memory space * Online; i.e. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Involution (mathematics)
In mathematics, an involution, involutory function, or self-inverse function is a function that is its own inverse, : for all in the domain of . Equivalently, applying twice produces the original value. General properties Any involution is a bijection. The identity map is a trivial example of an involution. Examples of nontrivial involutions include negation (x \mapsto -x), reciprocation (x \mapsto 1/x), and complex conjugation (z \mapsto \bar z) in arithmetic; reflection, half-turn rotation, and circle inversion in geometry; complementation in set theory; and reciprocal ciphers such as the ROT13 transformation and the Beaufort polyalphabetic cipher. The composition of two involutions ''f'' and ''g'' is an involution if and only if they commute: . Involutions on finite sets The number of involutions, including the identity involution, on a set with elements is given by a recurrence relation found by Heinrich August Rothe in 1800: :a_0 = a_1 = 1 and a_n = a_ + ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stack-sortable Permutation
In mathematics and computer science, a stack-sortable permutation (also called a tree permutation) is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure. The stack-sortable permutations are exactly the permutations that do not contain the permutation pattern 231; they are counted by the Catalan numbers, and may be placed in bijection with many other combinatorial objects with the same counting function including Dyck paths and binary trees. Sorting with a stack The problem of sorting an input sequence using a stack was first posed by , who gave the following linear time algorithm (closely related to algorithms for the later all nearest smaller values problem): *Initialize an empty stack *For each input value ''x'': **While the stack is nonempty and ''x'' is larger than the top item on the stack, pop the stack to the output **Push ''x'' onto the stack *While the stack is nonempty, pop it to the output K ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Separable Permutation
In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums. Separable permutations may be characterized by the forbidden permutation patterns 2413 and 3142;; , Theorem 2.2.36, p. p.58. they are also the permutations whose permutation graphs are cographs and the permutations that realize the series-parallel partial orders. It is possible to test in polynomial time whether a given separable permutation is a pattern in a larger permutation, or to find the longest common subpattern of two separable permutations. Definition and characterization define a separable permutation to be a permutation that has a ''separating tree'': a rooted binary tree in which the elements of the permutation appear (in permutation order) at the leaves of the tree, and in which the descendants of each tree node form a contiguous subset of these elements. Each interior node of the tree is either a positive ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
