:''See permutation (music) for the application of this concept to music.'' In mathematics, especially in abstract algebra and related areas, a permutation is a bijection, from a finite set ''X'' onto itself. In combinatorics, the term permutation has a traditional meaning, which is used to include ordered lists without repetition, but not exhaustive (so of less than maximum length). The concept of a permutation expresses the idea that objects that can be distinguished may be arranged in various different orders. For example, in taking two steps forward one may take paces ''left-right'' or ''right-left'', depending on which foot is first. A more complex application occurs in change ringing. There are many different orders in which a collection of six bells, of different notes, may each be rung once. If the bells are numbered 1 to 6, then each possible order makes a list of the numbers, without repetitions. There are a number of ways in which the permutation concept may be defined more formally. A permutation of the alphabet of 26 letters is a literal string of length 26 containing each letter just once; and it is clear that this definition works for any alphabet of ''N'' letters, with strings of length ''N''. That is, a permutation is simply an ordered sequence with no two elements the same, drawn from a fixed set of symbols, and of maximum length. One can therefore point to the essential difference between a ''permutation'' and a set: the elements of a permutation are arranged in a specified order. ==Arrangements and substitutions== Considering the example of bell-ringing more closely, assume we have six fixed ''positions'' in which a bell can be rung (''first'', ''second'', ..., ''sixth''); and also six bells (''A'', ''B'', ..., ''F'' might be the notes of the scale). Then what we mean by an ''arrangement'' is something like :''B''-''A''-''F''-''E''-''D''-''C'', with each bell put in its ordered place. What we mean by a ''substitution'' is a command such as 'change the order in which ''A'' and ''F'' are rung, and the order in which ''E'' and ''D'' are rung'. This would then give a new arrangement :''B''-''F''-''A''-''D''-''E''-''C''. The distinction between ''arrangement'' and ''substitution'' is important. For example, in ringing church bells not all substitutions are possible, from one ringing of the bells to the next arrangement, for practical reasons; and the instructions to the bell-ringers take the form of a list of arrangements, in which only neighbouring bells are interchanged from one 'round' to the next. ''Both'' arrangements and substitutions are commonly called ''permutations''. In mathematics, however, the phrase ''permutation of a set'' always refers to a ''substitution''. == Counting permutations == In this section only, the traditional definition is used: a permutation is an ordered list without repetitions. It is easy to count the number of permutations of size ''r'' when chosen from a set of size ''n'' (obviously with ''r''≤''n''). For example, if we have a total of 10 elements, the integers {1, 2, ..., 10}, a permutation of three elements from this set is (2,3,1). In this case, ''n'' = 10 and ''r'' = 3. So how many ways can this completely be done? #We can pretend to select the first member of all permutations out of ''n'' choices because there are ''n'' distinct elements from the generating set. #Next, since we have used one of the ''n'' elements already, the second member of the permutation has (''n'' − 1) elements to choose from the remaining set. #The third member can be filled in (''n'' − 2) ways since 2 have been used already. #This pattern continues until there are ''r'' members on the permutation. This means that the last member can be filled in (''n'' − ''r'' + 1) ways. Summarizing, we find that a total of :''n''(''n'' − 1)(''n'' − 2) ... (''n'' − ''r'' + 1) different permutations of ''r'' objects, taken from a pool of ''n'' objects, exist. If we denote this number by P(''n'', ''r'') and use the factorial notation, we can write :. In the above example, we have ''n'' = 10 and ''r'' = 3, so to find out how many unique sets, such as the one previously, we can find, we need to calculate P(10,3) = 720. Other, older notations include ''n''P''r'', P''n'',''r'', or ''n''P''r''. A common modern notation is (''n'')''r'' which is called a ''falling factorial''. However, the same notation is used for the ''rising factorial'' (also called ''Pochhammer symbol'') :''n''(''n'' + 1)(''n'' + 2)...(''n'' + ''r'' − 1). In the latter case, the number of permutations is (''n'' + ''r'' − 1)''r''. == Abstract algebra == As explained in a previous section, in abstract algebra and other mathematical fields, the term ''permutation (of a set)'' is now reserved for a bijective (bijection) from a finite set onto itself. The earlier example, of making permutations out of numbers 1 to 10, would be translated as a map from the set {1, ..., 10} to itself. There are two main notations for such permutations. In relation notation, one can just arrange the "natural" ordering of the elements being permuted on a row, and the new ordering on another row: : This means that in the first position, the second element of the set should be placed, in the second position, the fifth element in the set should be placed, and so on. Alternatively, if we have a finite set of elements (which need not be integers), we can firstly create an association between each element and an integer - more precisely, we can create a mapping ν(''s'') : ''S'' -> Z where ν is bijective, and S is our pool of elements. One can then read the above notation as mapping the element ν-1(1) to element ν-1(2), element ν-1(2) to element ν-1(5), and so on. Alternatively, we can write the permutation in terms of how the elements change when the permutation is successively applied. If we look at the above permutation as an example, if we take an element in the first position, the result of applying the permutation is then placed in the second position, the result of applying the permutation again is placed in the fifth position, and if we were to apply the permutation again we see that the element has now returned to the first permutation. We say that the behaviour of such an element is a ''cycle'', and we can write this cycle as (1 2 5), or alternatively as (2 5 1) or (5 1 2), but not as e.g. (1 5 2). The next cycle begins with any other element not considered till now, until every element appears in a cycle. As such, we can write the permutation as a set of cycles. The previous permutation just considered has cycle form (1 2 5)(3 4). The order ''of'' the cycles is not significant (but, as said before, the order of the elements ''within'' a cycle is, up to cyclic change). Thus, the same permutation could be written as e.g (4 3)(2 5 1). The "canonical" form for a permutation places the lowest-numbered position in each cycle first in that cycle and then orders the cycles by increasing first element. This notation often omits fixed points, that is, elements mapped to themselves; thus (1 3)(2)(4 5) can become simply (1 3)(4 5), since a cycle of just one element has no effect. A permutation consisting of one cycle is itself called a ''cycle''. The number of entries of a cycle is called the ''length''. For example, the length of (1 2 5) is three. A special terminology is used to describe cycles of length two - these are ''transpositions'' - since in a length two cycle, the elements are merely transposed. === Special permutations === If we think of a permutation that "changes" the position of the first element to the first element, the second to the second, and so on, we really have not changed the positions of the elements at all. Because of its action, we describe it as the ''identity permutation'' because it acts as an identity function. If we have some permutation called ''P'', the identity permutation ''I'', we can describe a permutation, written ''P''-1, which undoes the action of applying ''P''. In essence, performing P then P-1 is the same as performing the identity permutation. We always have such a permutation since a permutation is a bijective map. Such a permutation is called the ''inverse permutation''. One can define the product of two permutations. If we have two permutations, ''P'' and ''Q'', the action of performing ''P'' and ''Q'' will be the same as performing some other permutation, ''R'', itself. Note that ''R'' could be ''P'' or ''Q''. The product of ''P'' and ''Q'' is defined to be the permutation ''R''. For more, see symmetric group and permutation group. An even permutation is a permutation which can be expressed as the product of an even number of transpositions, and the identity permutation is an even permutation as it equals (1 2)(1 2). An odd permutation is a permutation which can be expressed as the product of an odd number of transpositions. It can be shown that every permutation is either odd or even and can't be both. We can also represent a permutation in matrix form - the resulting matrix is known as a ''permutation matrix''. ==Permutations in computing== Some of the older textbooks do look at permutations as ''assignments'', as mentioned above. In computer science terms, these are assignment operations, with values :1, 2, ..., ''n'' assigned to variables :''x''1, ''x''2, ..., ''x''''n''. Each value should be assigned just once. The assignment/substitution difference is then illustrative of one way in which functional programming and imperative programming differ — pure functional programming has no assignment mechanism. The mathematics ''convention'' is nowadays that permutations are just functions and the operation on them is function composition; functional programmers follow this. In the assignment language a ''substitution'' is an instruction to switch round the values assigned, simultaneously; a well-known problem. == Numbering permutations == Factoradic numbers can be used to assign unique numbers to permutations, such that given a factoradic n, one can quickly find the corresponding permutation. ==See also== *Cyclic permutation *Permutations and combinations *Even and odd permutations *Combinations *Josephus permutation *Symmetric group *Permutation group *Cyclic order *Weak order of permutations *Substitution cipher *Sorting network *Random permutation Abstract algebra Algebra Combinatorics
I heared that inversion occurs when an larger integer precedes a smaller one in a list. Is this in a context of combinations or abstract algebra? -- User:TakuyaMurata 08:21, Nov 19, 2003 (UTC) Can you give us an example? I don't understand exactly what you mean. User:Dysprosia 08:40, 19 Nov 2003 (UTC) Obviously such inversions occur in any permutation, other than the one fixing each integer 1, ..., n. But I'd say that counting the inversions is more of a combinatorics topic. User:Charles Matthews 10:00, 19 Nov 2003 (UTC) :Thanks for reply but more generally, what is inversion? I really couldn't find out the definition of inversion. -- User:TakuyaMurata 03:28, Nov 20, 2003 (UTC) :If you mean an inverse permutation, it's the permutation, call it ''p''-1 when applied to the permutation ''p'' gives you the identity permutation which doesn't change anything. User:Dysprosia 03:37, 20 Nov 2003 (UTC) :From Knuth ''Sorting and Searching'': an inversion of a permutation p is a pair (i,j) with i < j but p(i) > p(j). User:Charles Matthews 07:21, 20 Nov 2003 (UTC) :"Inversion" in this sense is NOT inversion of permutations. A permutation of the linearly ordered finite set { 1, ..., ''n'' } can be identified with a linear ordering of that set. An inversion is simply an instance of a smaller number following a larger one. E.g., in "1, 4, 2, 3, 5" there are two inversions, since 4 preceeds 2 and 4 preceeds 3. User:Michael Hardy 23:00, 17 Nov 2004 (UTC) ---- In the interests of not starting an edit war, I'll make my points on the current state of the article instead, and leave it up to other editors to verify if they have merit or not. * I use the term "significant" in opposition to the meaning of the word "insignificant": in a set, the order is insignificant, whilst in a permutation, the order is significant. * The use of the wording "necessary to record" is slightly misleading - one doesn't write down the ordering seperate from the elements themselves - in writing down the permutation, one writes down the ordering implicitly. * The permutation concept in the "counting" and in the "abstract algebra" sections are not ''two seperate meanings'', but two different ways of thinking about the same concept User:Dysprosia 03:07, 28 Mar 2004 (UTC) The sentence "''Unlike a set, the order of elements is neccessary to record.''" is firstly poor English, and secondly incorrect. One has to specify the order of the elements of a permutation when defining it, but that is a property of the act of definition and does not specify what the permutation ''is''. The sentence of Dysprosia is completely correct, but uses the word "significant" in the way mathematicians use it and so might not be understood by some readers.
The core of the issue is when two permutations are regarded as the same. For two sets to be the same it is necessary and sufficient for them to have the same elements. For two permutations, one must add ''in the same order''. I propose to replace the disputed sentence by: : The difference between a set and a permutation is that the elements of a permutation appear in a specified order. This means that two permutations are regarded as the same only if they have the same elements in the same order. --User:Zero0000 06:38, 28 Mar 2004 (UTC) :: That sentence is very nice, but the use of "order" in the first half of the sentence could be a little confusing as it might suggest the kinds of order as in order theory, though in straight English it would be rather straightforward. Perhaps, in order (no pun intended ;) to remedy that, we could say "elements of a permutation are arranged in a specified order"? User:Dysprosia 06:48, 28 Mar 2004 (UTC) :: Fine. --User:Zero0000 07:00, 28 Mar 2004 (UTC) ::: Shall I implement it? Or wait till Hfastedge wants to chip in? User:Dysprosia 07:08, 28 Mar 2004 (UTC) "signifigant" and "specified" and "matters" are words with no indirect object in the way you all have used them so far. NAMELY , its SIMPLY, precisely and ONLY the definition of permutation itself that makes the order "signifigant" or "specified" or "matter" i hate being repetitve, but this seems to be the only language you speak. i feel the current version is too verbose, more confusing than good and wasteful User:Hfastedge 03:05, 29 Mar 2004 (UTC) its been changed User:Hfastedge 17:59, 31 Mar 2004 (UTC) changed back by zero0000 without discussing http://en.wikipedia.org/w/wiki.phtml?title=Permutation&diff=0&oldid=3000993 User:Hfastedge 23:47, 31 Mar 2004 (UTC) : "recorded" did not have an evident meaning. It is a verb indicating an action, but there is no action here. Nobody did any recording. The present version is better than your version. --User:Zero0000 00:43, 1 Apr 2004 (UTC) I think the page is pretty decent as it stands. Although it can be made more concise (as Hfastedge has suggested), I have no specific qualms. Regarding the words "significant" "specified" and "matter": words of this sort are important and neccessary for meaningful communication. "Significant" says that this information is what is relevant. "Specified" says that this information is established prior. "Matter" says that this information is important and has consequence. These are all very usefull words which convey a lot of information and operate on a single object/subject. (What is meant by "no indirect object"?) In regards, "recording": this method may not be the best way to convey what a permutation is. It provides an extra level of indirection and extraneous concepts which may be confused with the subject. But it is not wrong in the respect that it implies an action. There is always action in mathematics - whether it's solving a differential equation or what have you. The formal set of rules in themselves may be purely logical and therefore devoid of action, but the choice of applying one rule over another to operate on a string (mathematical expression) is action, and mathematics does not - can not - exist independant of such action. Take for example a Turing machine - a Turing machine is neccesarily, regardless of how it is manifested, a dynamical system, and a dynamical system is neccessarily parameterized by a free paramater such as "time". The moment math becomes manifest - which is the momemt that it becomes meaningful - it is inextricably involved in action. Even as a concept it is involved in a dynamical system (the brain). User:Kevin baas 19:55, 1 Apr 2004 (UTC) Kevin's treatment is more intelligent and very complex. anyway, The verb to be. example sentances: the order is specified (by Whom, for what? WELL, BY the follower of the definition, FOR the purpose of following the definition) the order matters/is signifigant (to whom? for what? WELL, to the follower of the definition most importantly.... any other reasons or people that it might matter to make this highly non-neutral, non scientific and subjective) : The problem, Hfastedge, with omitting the "in the most basic sense" is that we have, in the same article, a paragraph that treats permutations ''not'' as a sequence of elements but "a bijective map from a set to itself.", and not just an ordered collection of objects. This fact needs to be distinguished from the former section in that the first description is not the be-all and end-all of permutations. : Your proposed change is good, however, and expresses the desired idea cleanly, but it seems a little overly complex to me? User:Dysprosia 02:55, 5 Apr 2004 (UTC) so i think the intro should go ''from'': In mathematics, in the most basic sense, a permutation is a sequence with no two elements the same. The difference between a permutation and a set is that the elements of a permutation are arranged in a specified order. This means that two permutations are regarded as the same only if they have the same elements in the same order ''to'': In mathematics, in the most basic sense a permutation is a sequence of elements chosen from a set such that no two elements are the same and that the order of elements is unique compared to all other permutations taken from the set. better? User:Hfastedge 02:08, 5 Apr 2004 (UTC) : It is not good for two reasons. One problem (common to both versions) is that "basic sense" should be "broadest sense". If I was in charge of the article I'd actually describe the case r < n as obsolete since as far as I know it is not used in modern (professional) mathematics ''at all''. The main thing wrong with your proposal is that "sequence" already carries the concept of a list of things in a particular order. So the first sentence in the "from" version is already a complete definition with nothing missing. The second and third sentences just emphasise aspects of the definition but don't form part of the definition. This could be emphasised by a paragraph break after the first sentence. The "to" version is bad because it presents the ordering as if it is new but it is actually part of what "sequence" means. --User:Zero0000 06:56, 5 Apr 2004 (UTC) :I prefer the ''to:'' version. The question was "Which of the two is better?", not "Is the second one good?" and definitely not "Is either good?" The above paragraph does not answer the question that was asked. I answer the question in the affirmative: "Yes, the ''to:'' is better than the ''from:''." :With regards to the assesments Zero made: Sequence does imply order, yes. But that does not mean the word order should not be used. Indeed, if the fact that there is a sequence is significant than order should be discussed. With regard to the last sentence, of Zero's paragraph then: No, sequence does not mean permutation. And permutation can not be defined without discussing the particular order of things that are in a sequence. :Personally, I prefer the word "basic" over "broadest". we're trying to make it simple to the reader. Basic says "this is fundmantal", and the reader thinks "Ahhh, i need go no further! ''This'' is what a permutation is, in this small and simply-worded paragraph!" Boradly doesn't imply simplicity, and has a different meaning altogether. User:Kevin baas 20:18, 5 Apr 2004 (UTC) :: Sorry but you are wrong on all counts here. As the new text says correctly, this "basic" sense is actually obsolescent. Also the only difference between "permutation" (in this old sense) and "sequence" is that permutations can't have two elements the same. The ordering aspects of both are identical. Actually, that would be a good way to define it: ''An obsolescent meaning of permutation is that of a sequence without repeated elements." --User:Zero0000 22:16, 5 Apr 2004 (UTC) :::That definition is incomplete because it does not discuss what makes one permutation not the same as another permutation. User:Kevin baas 23:00, 5 Apr 2004 (UTC) :::: Yes it does. The identity relation for permutations is inherited from the identity relation for sequences. --User:Zero0000 14:50, 19 Apr 2004 (UTC) ::::: This is not object-orientated programming, nor should it be. User:Kevin baas 17:29, 19 Apr 2004 (UTC) :::And btw, I fail to see how I am "wrong on all counts". You have not contradicted anything that I have said, and you have only discussed basic vs. broad, and sequence and permutations, in a sense independant of how I have discussed them. I agree with what you say, with the exception that I don't understand the statement regarding obsolescent (admittedly, I don't know the meaning of the word or who considers it obsolescent), but that is a subjective statement, anyways. This does not contradict what I have said. User:Kevin baas ==Permutations as biyections== Funny but I came to the article in order to check whether "permutation is the same as biyection" (at least for finite sets) and there is practically nothing on it... I actually thought it was the simplest way to define them? User:Pfortuny 17:11, 18 Apr 2004 (UTC) : Bijections is what the "Abstract Algebra" section is about (which in my opinion should be the first section since it is the main meaning of ''permutation'' these days). Btw, I removed the following portion of that section which does not belong there. I don't think it belongs in the article at all; if someone disagrees please put it somewhere other than in the middle of the mathematics. --User:Zero0000 14:47, 19 Apr 2004 (UTC) This was cut from the article ----- Some of the older textbooks look at permutations in an alternative way. In computer science terms, they are defined essentially as assignment operations, with values :1, 2, ..., ''n'' assigned to variables :''x''1, ''x''1, ..., ''x''''n''. Each value should be assigned just once. There is here a real if subtle difference, illustrative of one way in which functional programming and imperative programming differ — pure functional programming has no assignment mechanism. The mathematics ''convention'' is nowadays that permutations are just functions and the operation on them is function composition. -----End of cut ::As I understand, permutations belong originally and primarily to combinatorics, probability, and discrete mathematics. I am against the apparent effort on wikipedia to encode everything in terms of abstract algebra as if it was the preeminant code behind all things. I believe that the abstract algebra approach to permutations is valuable, but I do not believe that it should be put first. An understand of abstract algebra should not be prerequisite for an understanding of permutations. Permutations should be put in concrete terms that are easy to relate to and apply to real-world problems. The purpose of this page is to provide access to the idea of a permutation, and the diverse historical and mathematical context thereof, so as to provide the readers with practical tools. I think an accessable and practical discussion should be the dominant goal. User:Kevin baas 17:17, 19 Apr 2004 (UTC) Well, I disagree. I have taught students who have met this kind of definition, for example in Fraleigh's ''Algebra''. It should be mentioned in this article, since it is a possible point of view on permutations. There is a problem, in my view, in taking the abstract algebra point of view as definitive. No doubt this point could be explained better; but it belongs on this page. User:Charles Matthews 15:17, 19 Apr 2004 (UTC) :Yes, when reading the page I realized "oh, this is about the ''combinatorial permutations''" (which I did not have in mind then): this is actually logical. But I think something could be said of the algebraic concept.I'll try to make it up.. It's already there, sorry. Thanks to all of you. User:Pfortuny 19:16, 19 Apr 2004 (UTC)
== Example before counting ==
I think there should be an example that clearly shows (visually) what a permutation is (such as the bells or the matrix in the abstract algebra section), before the section that tells one how to count permutations. User:Kevin baas 17:29, 19 Apr 2004 (UTC)
== Obscelete? ==
Sorry, Charles, I noticed you were the one who put in the comment about permutation being used "without qualification" as meaning a bijection. While I agree with you in principle, I think it's misleading. First of all, I took a combinatorics class in grad school, and we constantly used the term "permutation of r objects from a pool of n objects" or just "permutation" in this traditional sense all the time, usually saying things like "r-permute-n" or something. I admit, usually it's the bijection, but enough times it's used the other way that I don't see how it an be written off. Especially when this meaning is used extensively in one of the sections later on?? User:Revolver 22:51, 10 Nov 2004 (UTC)
: The meaning you mention is essentially obsolete in professional mathematics. The article should reflect that fact. --User:Zero0000 23:45, 10 Nov 2004 (UTC)
== bell ringing unclear (no pun) ==
The bell ringing section doesn't seem to give precise definitions of "arrangement" and "substitution", at least it's not clear to me at all what these are supposed to mean? Can you elaborate?? User:Revolver 23:00, 10 Nov 2004 (UTC)
:Bell ringing section is confusing. In fact, the whole article is surprisingly confusing. I will try to make some sense a bit later.
:Some hints for your question for the bell ringing case, I hope they ring the bell:
:"Substitution" examples there are made of "transpositions". A "substitution" is a bijecive function of a set of (mutually different) obects onto itself. An "arrangement" may be viewed as a bijective function of a set of (mutually different) obects onto the set of available positions. There is a subtle difference between the two functions, although the mathematics is basically the same.
:The view of permutation as an arrangement is convenient for the purposes of combinatorics, while the view of permutation as a substitution is convenient for algebra. For those who knows graph theory, there is a similarity: sometimes it is convenient to see a graph as G(V,E); in other cases it is nothing but a square (0-1)-matrix.
:The most important difference:
:*two "arrangements" are related to each other either through the set of positions or through a "substitution".
:*two "substitutions" are related to each other through a... (guess what?) "substitution".
:So, the set of "substitutions" is, in a sense, self-sufficient for its description.
:Stay tuned. :-) User:Mikkalai 00:48, 18 Nov 2004 (UTC)
== Einstein notation ==
Einstein notation mentions "positive" and "negative" permutations and links here. This page doesn't discuss them. Can someone add a bit on that here and maybe a parenthetical there about this?
User:BenFrantzDale 15:07, Feb 2, 2005 (UTC)
: Same as "even" and "odd". Do physicists say "positive" and "negative"? I never saw that in mathematics. --User:Zero0000 17:54, 2 Feb 2005 (UTC)
::It could be a mistake on that page. I don't claim to know :-) —User:BenFrantzDale 01:05, Feb 3, 2005 (UTC)
See other meanings of words starting from letter:
Words begining with Permutation:
Permutation
Permutation
Permutations
Permutations_and_combinations
Permutations_and_combinations
Permutation_(album)
Permutation_(music)
Permutation_automaton
Permutation_cipher
Permutation_cipher
Permutation_City
Permutation_group
Permutation_groups
Permutation_groups
Permutation_matrices
Permutation_matrix
Permutation_matrix
Permutation_representation
Permutation
:''See permutation (music) for the application of this concept to music.'' In mathematics, especially in abstract algebra and related areas, a permutation is a bijection, from a finite set ''X'' onto itself. In combinatorics, the term permutation has a traditional meaning, which is used to include ordered lists without repetition, but not exhaustive (so of less than maximum length). The concept of a permutation expresses the idea that objects that can be distinguished may be arranged in various different orders. For example, in taking two steps forward one may take paces ''left-right'' or ''right-left'', depending on which foot is first. A more complex application occurs in change ringing. There are many different orders in which a collection of six bells, of different notes, may each be rung once. If the bells are numbered 1 to 6, then each possible order makes a list of the numbers, without repetitions. There are a number of ways in which the permutation concept may be defined more formally. A permutation of the alphabet of 26 letters is a literal string of length 26 containing each letter just once; and it is clear that this definition works for any alphabet of ''N'' letters, with strings of length ''N''. That is, a permutation is simply an ordered sequence with no two elements the same, drawn from a fixed set of symbols, and of maximum length. One can therefore point to the essential difference between a ''permutation'' and a set: the elements of a permutation are arranged in a specified order. ==Arrangements and substitutions== Considering the example of bell-ringing more closely, assume we have six fixed ''positions'' in which a bell can be rung (''first'', ''second'', ..., ''sixth''); and also six bells (''A'', ''B'', ..., ''F'' might be the notes of the scale). Then what we mean by an ''arrangement'' is something like :''B''-''A''-''F''-''E''-''D''-''C'', with each bell put in its ordered place. What we mean by a ''substitution'' is a command such as 'change the order in which ''A'' and ''F'' are rung, and the order in which ''E'' and ''D'' are rung'. This would then give a new arrangement :''B''-''F''-''A''-''D''-''E''-''C''. The distinction between ''arrangement'' and ''substitution'' is important. For example, in ringing church bells not all substitutions are possible, from one ringing of the bells to the next arrangement, for practical reasons; and the instructions to the bell-ringers take the form of a list of arrangements, in which only neighbouring bells are interchanged from one 'round' to the next. ''Both'' arrangements and substitutions are commonly called ''permutations''. In mathematics, however, the phrase ''permutation of a set'' always refers to a ''substitution''. == Counting permutations == In this section only, the traditional definition is used: a permutation is an ordered list without repetitions. It is easy to count the number of permutations of size ''r'' when chosen from a set of size ''n'' (obviously with ''r''≤''n''). For example, if we have a total of 10 elements, the integers {1, 2, ..., 10}, a permutation of three elements from this set is (2,3,1). In this case, ''n'' = 10 and ''r'' = 3. So how many ways can this completely be done? #We can pretend to select the first member of all permutations out of ''n'' choices because there are ''n'' distinct elements from the generating set. #Next, since we have used one of the ''n'' elements already, the second member of the permutation has (''n'' − 1) elements to choose from the remaining set. #The third member can be filled in (''n'' − 2) ways since 2 have been used already. #This pattern continues until there are ''r'' members on the permutation. This means that the last member can be filled in (''n'' − ''r'' + 1) ways. Summarizing, we find that a total of :''n''(''n'' − 1)(''n'' − 2) ... (''n'' − ''r'' + 1) different permutations of ''r'' objects, taken from a pool of ''n'' objects, exist. If we denote this number by P(''n'', ''r'') and use the factorial notation, we can write :. In the above example, we have ''n'' = 10 and ''r'' = 3, so to find out how many unique sets, such as the one previously, we can find, we need to calculate P(10,3) = 720. Other, older notations include ''n''P''r'', P''n'',''r'', or ''n''P''r''. A common modern notation is (''n'')''r'' which is called a ''falling factorial''. However, the same notation is used for the ''rising factorial'' (also called ''Pochhammer symbol'') :''n''(''n'' + 1)(''n'' + 2)...(''n'' + ''r'' − 1). In the latter case, the number of permutations is (''n'' + ''r'' − 1)''r''. == Abstract algebra == As explained in a previous section, in abstract algebra and other mathematical fields, the term ''permutation (of a set)'' is now reserved for a bijective (bijection) from a finite set onto itself. The earlier example, of making permutations out of numbers 1 to 10, would be translated as a map from the set {1, ..., 10} to itself. There are two main notations for such permutations. In relation notation, one can just arrange the "natural" ordering of the elements being permuted on a row, and the new ordering on another row: : This means that in the first position, the second element of the set should be placed, in the second position, the fifth element in the set should be placed, and so on. Alternatively, if we have a finite set of elements (which need not be integers), we can firstly create an association between each element and an integer - more precisely, we can create a mapping ν(''s'') : ''S'' -> Z where ν is bijective, and S is our pool of elements. One can then read the above notation as mapping the element ν-1(1) to element ν-1(2), element ν-1(2) to element ν-1(5), and so on. Alternatively, we can write the permutation in terms of how the elements change when the permutation is successively applied. If we look at the above permutation as an example, if we take an element in the first position, the result of applying the permutation is then placed in the second position, the result of applying the permutation again is placed in the fifth position, and if we were to apply the permutation again we see that the element has now returned to the first permutation. We say that the behaviour of such an element is a ''cycle'', and we can write this cycle as (1 2 5), or alternatively as (2 5 1) or (5 1 2), but not as e.g. (1 5 2). The next cycle begins with any other element not considered till now, until every element appears in a cycle. As such, we can write the permutation as a set of cycles. The previous permutation just considered has cycle form (1 2 5)(3 4). The order ''of'' the cycles is not significant (but, as said before, the order of the elements ''within'' a cycle is, up to cyclic change). Thus, the same permutation could be written as e.g (4 3)(2 5 1). The "canonical" form for a permutation places the lowest-numbered position in each cycle first in that cycle and then orders the cycles by increasing first element. This notation often omits fixed points, that is, elements mapped to themselves; thus (1 3)(2)(4 5) can become simply (1 3)(4 5), since a cycle of just one element has no effect. A permutation consisting of one cycle is itself called a ''cycle''. The number of entries of a cycle is called the ''length''. For example, the length of (1 2 5) is three. A special terminology is used to describe cycles of length two - these are ''transpositions'' - since in a length two cycle, the elements are merely transposed. === Special permutations === If we think of a permutation that "changes" the position of the first element to the first element, the second to the second, and so on, we really have not changed the positions of the elements at all. Because of its action, we describe it as the ''identity permutation'' because it acts as an identity function. If we have some permutation called ''P'', the identity permutation ''I'', we can describe a permutation, written ''P''-1, which undoes the action of applying ''P''. In essence, performing P then P-1 is the same as performing the identity permutation. We always have such a permutation since a permutation is a bijective map. Such a permutation is called the ''inverse permutation''. One can define the product of two permutations. If we have two permutations, ''P'' and ''Q'', the action of performing ''P'' and ''Q'' will be the same as performing some other permutation, ''R'', itself. Note that ''R'' could be ''P'' or ''Q''. The product of ''P'' and ''Q'' is defined to be the permutation ''R''. For more, see symmetric group and permutation group. An even permutation is a permutation which can be expressed as the product of an even number of transpositions, and the identity permutation is an even permutation as it equals (1 2)(1 2). An odd permutation is a permutation which can be expressed as the product of an odd number of transpositions. It can be shown that every permutation is either odd or even and can't be both. We can also represent a permutation in matrix form - the resulting matrix is known as a ''permutation matrix''. ==Permutations in computing== Some of the older textbooks do look at permutations as ''assignments'', as mentioned above. In computer science terms, these are assignment operations, with values :1, 2, ..., ''n'' assigned to variables :''x''1, ''x''2, ..., ''x''''n''. Each value should be assigned just once. The assignment/substitution difference is then illustrative of one way in which functional programming and imperative programming differ — pure functional programming has no assignment mechanism. The mathematics ''convention'' is nowadays that permutations are just functions and the operation on them is function composition; functional programmers follow this. In the assignment language a ''substitution'' is an instruction to switch round the values assigned, simultaneously; a well-known problem. == Numbering permutations == Factoradic numbers can be used to assign unique numbers to permutations, such that given a factoradic n, one can quickly find the corresponding permutation. ==See also== *Cyclic permutation *Permutations and combinations *Even and odd permutations *Combinations *Josephus permutation *Symmetric group *Permutation group *Cyclic order *Weak order of permutations *Substitution cipher *Sorting network *Random permutation Abstract algebra Algebra Combinatorics
Permutation
I heared that inversion occurs when an larger integer precedes a smaller one in a list. Is this in a context of combinations or abstract algebra? -- User:TakuyaMurata 08:21, Nov 19, 2003 (UTC) Can you give us an example? I don't understand exactly what you mean. User:Dysprosia 08:40, 19 Nov 2003 (UTC) Obviously such inversions occur in any permutation, other than the one fixing each integer 1, ..., n. But I'd say that counting the inversions is more of a combinatorics topic. User:Charles Matthews 10:00, 19 Nov 2003 (UTC) :Thanks for reply but more generally, what is inversion? I really couldn't find out the definition of inversion. -- User:TakuyaMurata 03:28, Nov 20, 2003 (UTC) :If you mean an inverse permutation, it's the permutation, call it ''p''-1 when applied to the permutation ''p'' gives you the identity permutation which doesn't change anything. User:Dysprosia 03:37, 20 Nov 2003 (UTC) :From Knuth ''Sorting and Searching'': an inversion of a permutation p is a pair (i,j) with i < j but p(i) > p(j). User:Charles Matthews 07:21, 20 Nov 2003 (UTC) :"Inversion" in this sense is NOT inversion of permutations. A permutation of the linearly ordered finite set { 1, ..., ''n'' } can be identified with a linear ordering of that set. An inversion is simply an instance of a smaller number following a larger one. E.g., in "1, 4, 2, 3, 5" there are two inversions, since 4 preceeds 2 and 4 preceeds 3. User:Michael Hardy 23:00, 17 Nov 2004 (UTC) ---- In the interests of not starting an edit war, I'll make my points on the current state of the article instead, and leave it up to other editors to verify if they have merit or not. * I use the term "significant" in opposition to the meaning of the word "insignificant": in a set, the order is insignificant, whilst in a permutation, the order is significant. * The use of the wording "necessary to record" is slightly misleading - one doesn't write down the ordering seperate from the elements themselves - in writing down the permutation, one writes down the ordering implicitly. * The permutation concept in the "counting" and in the "abstract algebra" sections are not ''two seperate meanings'', but two different ways of thinking about the same concept User:Dysprosia 03:07, 28 Mar 2004 (UTC) The sentence "''Unlike a set, the order of elements is neccessary to record.''" is firstly poor English, and secondly incorrect. One has to specify the order of the elements of a permutation when defining it, but that is a property of the act of definition and does not specify what the permutation ''is''. The sentence of Dysprosia is completely correct, but uses the word "significant" in the way mathematicians use it and so might not be understood by some readers.
The core of the issue is when two permutations are regarded as the same. For two sets to be the same it is necessary and sufficient for them to have the same elements. For two permutations, one must add ''in the same order''. I propose to replace the disputed sentence by: : The difference between a set and a permutation is that the elements of a permutation appear in a specified order. This means that two permutations are regarded as the same only if they have the same elements in the same order. --User:Zero0000 06:38, 28 Mar 2004 (UTC) :: That sentence is very nice, but the use of "order" in the first half of the sentence could be a little confusing as it might suggest the kinds of order as in order theory, though in straight English it would be rather straightforward. Perhaps, in order (no pun intended ;) to remedy that, we could say "elements of a permutation are arranged in a specified order"? User:Dysprosia 06:48, 28 Mar 2004 (UTC) :: Fine. --User:Zero0000 07:00, 28 Mar 2004 (UTC) ::: Shall I implement it? Or wait till Hfastedge wants to chip in? User:Dysprosia 07:08, 28 Mar 2004 (UTC) "signifigant" and "specified" and "matters" are words with no indirect object in the way you all have used them so far. NAMELY , its SIMPLY, precisely and ONLY the definition of permutation itself that makes the order "signifigant" or "specified" or "matter" i hate being repetitve, but this seems to be the only language you speak. i feel the current version is too verbose, more confusing than good and wasteful User:Hfastedge 03:05, 29 Mar 2004 (UTC) its been changed User:Hfastedge 17:59, 31 Mar 2004 (UTC) changed back by zero0000 without discussing http://en.wikipedia.org/w/wiki.phtml?title=Permutation&diff=0&oldid=3000993 User:Hfastedge 23:47, 31 Mar 2004 (UTC) : "recorded" did not have an evident meaning. It is a verb indicating an action, but there is no action here. Nobody did any recording. The present version is better than your version. --User:Zero0000 00:43, 1 Apr 2004 (UTC) I think the page is pretty decent as it stands. Although it can be made more concise (as Hfastedge has suggested), I have no specific qualms. Regarding the words "significant" "specified" and "matter": words of this sort are important and neccessary for meaningful communication. "Significant" says that this information is what is relevant. "Specified" says that this information is established prior. "Matter" says that this information is important and has consequence. These are all very usefull words which convey a lot of information and operate on a single object/subject. (What is meant by "no indirect object"?) In regards, "recording": this method may not be the best way to convey what a permutation is. It provides an extra level of indirection and extraneous concepts which may be confused with the subject. But it is not wrong in the respect that it implies an action. There is always action in mathematics - whether it's solving a differential equation or what have you. The formal set of rules in themselves may be purely logical and therefore devoid of action, but the choice of applying one rule over another to operate on a string (mathematical expression) is action, and mathematics does not - can not - exist independant of such action. Take for example a Turing machine - a Turing machine is neccesarily, regardless of how it is manifested, a dynamical system, and a dynamical system is neccessarily parameterized by a free paramater such as "time". The moment math becomes manifest - which is the momemt that it becomes meaningful - it is inextricably involved in action. Even as a concept it is involved in a dynamical system (the brain). User:Kevin baas 19:55, 1 Apr 2004 (UTC) Kevin's treatment is more intelligent and very complex. anyway, The verb to be. example sentances: the order is specified (by Whom, for what? WELL, BY the follower of the definition, FOR the purpose of following the definition) the order matters/is signifigant (to whom? for what? WELL, to the follower of the definition most importantly.... any other reasons or people that it might matter to make this highly non-neutral, non scientific and subjective) : The problem, Hfastedge, with omitting the "in the most basic sense" is that we have, in the same article, a paragraph that treats permutations ''not'' as a sequence of elements but "a bijective map from a set to itself.", and not just an ordered collection of objects. This fact needs to be distinguished from the former section in that the first description is not the be-all and end-all of permutations. : Your proposed change is good, however, and expresses the desired idea cleanly, but it seems a little overly complex to me? User:Dysprosia 02:55, 5 Apr 2004 (UTC) so i think the intro should go ''from'': In mathematics, in the most basic sense, a permutation is a sequence with no two elements the same. The difference between a permutation and a set is that the elements of a permutation are arranged in a specified order. This means that two permutations are regarded as the same only if they have the same elements in the same order ''to'': In mathematics, in the most basic sense a permutation is a sequence of elements chosen from a set such that no two elements are the same and that the order of elements is unique compared to all other permutations taken from the set. better? User:Hfastedge 02:08, 5 Apr 2004 (UTC) : It is not good for two reasons. One problem (common to both versions) is that "basic sense" should be "broadest sense". If I was in charge of the article I'd actually describe the case r < n as obsolete since as far as I know it is not used in modern (professional) mathematics ''at all''. The main thing wrong with your proposal is that "sequence" already carries the concept of a list of things in a particular order. So the first sentence in the "from" version is already a complete definition with nothing missing. The second and third sentences just emphasise aspects of the definition but don't form part of the definition. This could be emphasised by a paragraph break after the first sentence. The "to" version is bad because it presents the ordering as if it is new but it is actually part of what "sequence" means. --User:Zero0000 06:56, 5 Apr 2004 (UTC) :I prefer the ''to:'' version. The question was "Which of the two is better?", not "Is the second one good?" and definitely not "Is either good?" The above paragraph does not answer the question that was asked. I answer the question in the affirmative: "Yes, the ''to:'' is better than the ''from:''." :With regards to the assesments Zero made: Sequence does imply order, yes. But that does not mean the word order should not be used. Indeed, if the fact that there is a sequence is significant than order should be discussed. With regard to the last sentence, of Zero's paragraph then: No, sequence does not mean permutation. And permutation can not be defined without discussing the particular order of things that are in a sequence. :Personally, I prefer the word "basic" over "broadest". we're trying to make it simple to the reader. Basic says "this is fundmantal", and the reader thinks "Ahhh, i need go no further! ''This'' is what a permutation is, in this small and simply-worded paragraph!" Boradly doesn't imply simplicity, and has a different meaning altogether. User:Kevin baas 20:18, 5 Apr 2004 (UTC) :: Sorry but you are wrong on all counts here. As the new text says correctly, this "basic" sense is actually obsolescent. Also the only difference between "permutation" (in this old sense) and "sequence" is that permutations can't have two elements the same. The ordering aspects of both are identical. Actually, that would be a good way to define it: ''An obsolescent meaning of permutation is that of a sequence without repeated elements." --User:Zero0000 22:16, 5 Apr 2004 (UTC) :::That definition is incomplete because it does not discuss what makes one permutation not the same as another permutation. User:Kevin baas 23:00, 5 Apr 2004 (UTC) :::: Yes it does. The identity relation for permutations is inherited from the identity relation for sequences. --User:Zero0000 14:50, 19 Apr 2004 (UTC) ::::: This is not object-orientated programming, nor should it be. User:Kevin baas 17:29, 19 Apr 2004 (UTC) :::And btw, I fail to see how I am "wrong on all counts". You have not contradicted anything that I have said, and you have only discussed basic vs. broad, and sequence and permutations, in a sense independant of how I have discussed them. I agree with what you say, with the exception that I don't understand the statement regarding obsolescent (admittedly, I don't know the meaning of the word or who considers it obsolescent), but that is a subjective statement, anyways. This does not contradict what I have said. User:Kevin baas ==Permutations as biyections== Funny but I came to the article in order to check whether "permutation is the same as biyection" (at least for finite sets) and there is practically nothing on it... I actually thought it was the simplest way to define them? User:Pfortuny 17:11, 18 Apr 2004 (UTC) : Bijections is what the "Abstract Algebra" section is about (which in my opinion should be the first section since it is the main meaning of ''permutation'' these days). Btw, I removed the following portion of that section which does not belong there. I don't think it belongs in the article at all; if someone disagrees please put it somewhere other than in the middle of the mathematics. --User:Zero0000 14:47, 19 Apr 2004 (UTC) This was cut from the article ----- Some of the older textbooks look at permutations in an alternative way. In computer science terms, they are defined essentially as assignment operations, with values :1, 2, ..., ''n'' assigned to variables :''x''1, ''x''1, ..., ''x''''n''. Each value should be assigned just once. There is here a real if subtle difference, illustrative of one way in which functional programming and imperative programming differ — pure functional programming has no assignment mechanism. The mathematics ''convention'' is nowadays that permutations are just functions and the operation on them is function composition. -----End of cut ::As I understand, permutations belong originally and primarily to combinatorics, probability, and discrete mathematics. I am against the apparent effort on wikipedia to encode everything in terms of abstract algebra as if it was the preeminant code behind all things. I believe that the abstract algebra approach to permutations is valuable, but I do not believe that it should be put first. An understand of abstract algebra should not be prerequisite for an understanding of permutations. Permutations should be put in concrete terms that are easy to relate to and apply to real-world problems. The purpose of this page is to provide access to the idea of a permutation, and the diverse historical and mathematical context thereof, so as to provide the readers with practical tools. I think an accessable and practical discussion should be the dominant goal. User:Kevin baas 17:17, 19 Apr 2004 (UTC) Well, I disagree. I have taught students who have met this kind of definition, for example in Fraleigh's ''Algebra''. It should be mentioned in this article, since it is a possible point of view on permutations. There is a problem, in my view, in taking the abstract algebra point of view as definitive. No doubt this point could be explained better; but it belongs on this page. User:Charles Matthews 15:17, 19 Apr 2004 (UTC) :Yes, when reading the page I realized "oh, this is about the ''combinatorial permutations''" (which I did not have in mind then): this is actually logical. But I think something could be said of the algebraic concept.
See other meanings of words starting from letter:
P
PA | PB | PC | PD | PE | PF | PG | PH | PI | PJ | PK | PL | PM | PN | PO | PR | PS | PT | PU | PW | PX | PY | PZ |Words begining with Permutation:
Permutation
Permutation
Permutations
Permutations_and_combinations
Permutations_and_combinations
Permutation_(album)
Permutation_(music)
Permutation_automaton
Permutation_cipher
Permutation_cipher
Permutation_City
Permutation_group
Permutation_groups
Permutation_groups
Permutation_matrices
Permutation_matrix
Permutation_matrix
Permutation_representation
These materials are based on Wikipedia and licensed under the GNU FDL
YouTube.com videos better site than Turbo Tax 2007
