Talk: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? -- Taku 08:21, Nov 19, 2003 (UTC)

Can you give us an example? I don't understand exactly what you mean. 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.

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. -- Taku 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. 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).

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

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.

--Zero 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"? Dysprosia 06:48, 28 Mar 2004 (UTC)

Fine. --Zero 07:00, 28 Mar 2004 (UTC)

Shall I implement it? Or wait till Hfastedge wants to chip in? 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 Hfastedge 03:05, 29 Mar 2004 (UTC)

its been changed 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 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. --Zero 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). 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? 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? 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. --Zero 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. 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." --Zero 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. Kevin Baas 23:00, 5 Apr 2004 (UTC)

Yes it does. The identity relation for permutations is inherited from the identity relation for sequences. --Zero 14:50, 19 Apr 2004 (UTC)

This is not object-orientated programming, nor should it be. 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. Kevin Baas

Contents

1 Permutations as biyections 2 Example before counting 3 Obscelete? 4 bell ringing unclear (no pun) 5 Einstein notation

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? 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. --Zero 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₁, x₁, ..., 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. 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.

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. 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. 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?? Revolver 22:51, 10 Nov 2004 (UTC)

The meaning you mention is essentially obsolete in professional mathematics. The article should reflect that fact. --Zero 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?? 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. :-) 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?

BenFrantzDale 15:07, Feb 2, 2005 (UTC)

Same as "even" and "odd". Do physicists say "positive" and "negative"? I never saw that in mathematics. --Zero 17:54, 2 Feb 2005 (UTC)

It could be a mistake on that page. I don't claim to know :-) —BenFrantzDale 01:05, Feb 3, 2005 (UTC)