Talk:Permutation

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class High Priority  Field: Basics
One of the 500 most frequently viewed mathematics articles.

---> The algorithm presented in this article doesn't work with set equal or less than 2. Explication are missing about it.

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

[edit] 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

x1, x1, ..., xn.

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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] Accessibility

I arrived planning to make the intro more layman-accessible, but now I'm confused myself. (Combinatoric) permutations can't use all the elements of the set? That's what I'm getting from "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).". What would the, er, thingies 1,2,3, 2,1,3, and 3,2,1, taken from the set (1,2,3) be called, then? BTW, I'm a big proponent of putting a clear, simple example of a common case right up front so as to draw in the non-math types; I'll try to find a correct one once I figure out what's going on myself... Lunkwill 29 June 2005 07:38 (UTC)

What's wrong with the intro?
The term permutation is used in two senses, one more common than the other. Almost all the time when the term permutation is used, the size of the permutation r is the size of the set n (r = n), though an older usage included (r < n). See the counting permutation section. Dysprosia 29 June 2005 08:19 (UTC)

[edit] Encoding

I have a problem I've been trying to solve by encoding a repetitive permutation of three letters into one big number. It would look like this. AAA=1 AAB=2 AAC=3 ..... ABA=27 ABB=28 ABC=29 Is there a mathematical formula or algorithm for this?

Use the Wikipedia:Reference desk next time. There is a trivial solution to the problem. Roughly, treat A = 0, ..., Z = 25, and then the triple of letters as a base-26 number (ie., p+26q+676r, p, q, r being the three numbers corresponding to the letters). Dysprosia 15:06, 6 January 2006 (UTC)
676p+26q+r+1.--Patrick 01:14, 7 January 2006 (UTC)
Whoops ;) If I were doing something like this I'd index at 0 anyway, it's more natural. Dysprosia 01:38, 7 January 2006 (UTC)

[edit] Notation

I've seen other notation, specifically here[1], in the second question, and here[2] in questions 2iii and 2iv. Could someone who understands this a bit better than I do explain it, as it appears to be fairly common. 80.177.1.238 16:43, 8 March 2006 (UTC)

[edit] Notation for Identity

The section does not explain the notation for the identity perm in cyclic form. If all fixed points are omitted, one is lead to the conclusion that the notation for an identity perm. is an empty string. It also fails to point out an ambiguity where the last element is a fixed point (or tail suffix of such). You can't inspect cyclic notation with fixed points omitted to determine the number of elements in the perm. described, whereas without the omission of fixed points, the notation was entirely clear in both regards. MaxEnt 10:07, 17 April 2006 (UTC)

[edit] Error and Confusion with Falling Factorial

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.

I found this passage confusing. The notation is introduced, not defined explicitly (except by implied equiv. to the previous result) and when the notation is defined in the same proximity, it's a contrary definition, plus the final formula surely can't be correct for the rising fact. notation, there must be a sign wrong. The casuaul reader could be easily mislead here. MaxEnt 09:52, 17 April 2006 (UTC)

[edit] Abstract algebra

The "Abstract algebra" paragraph now seems obsolete and could be deleted, am I wrong ?

BTW, there's nothing wrong in defining a permutation of {1...n} once as a bijection from this set into itself, and once as a family (x1,x2,...,xn) of numbers from this set, each occuring once, since the two definition coincide (at least if we agree that such a family is indexed by {1,...,n}).

On the other hand there seems many many articles about the same subject, I try to start a non-exhaustive list:

I think they should be merged (urgently) or identified clearly (in each of the other articles) as the article treating a particular aspect of the thing (which should then not be discussed in any of the others). — MFH:Talk 22:53, 16 October 2006 (UTC)

[edit] Algorithm to generate permutations

The one in the article is by far the shortest I've come across. I've checked its outcome for various sequence lengths n, getting n! different arrangements each time, so conclude that it's valid. It would be nice if there was some explanation of the principle and a reference to its source. 86.132.234.4 13:31, 18 January 2007 (UTC)

Thank you! I've developed the algorithm myself some months ago, so far I didn't publish it. But actually, I did my first investigations on permutations in school, that's some years ago... A. Pichler 17:13, 19 January 2007 (UTC)

It wasn't clear to me initially that the sequence index is 1-based, although looking at it now, the mathematical notation for the sequence does specify. Maybe this could be made clearer in the text? --Lumimies 21:53, 1 May 2007 (UTC)

Yep pretty nice algo, many thanks for that. Using the factoradic on the fly is very good, I just pre-computed the factorial (from 1 to n) outside of the function to avoid recomputing at each call and zooooom...

[edit] Congrats

Very good article. Very helpful. I commend you.

[edit] How do I figure this out?

And perhaps the solution method should be somewhere in the article. For example: The set {1, 2, 3, 4, 5, 6} has 720 different rearrangements (permutations of which n=6 and r=6). If the permutations were all put into matrices (in other words, if they were all in the matrix-esque display in the article), how many of them would apply to the following rules?: "s(x)=1, s(y)=2, s(z)=3, x<y<z" In other words, how many of these permutations would have the numbers 1, 2, and 3 in that order, including ones such as {6, 1, 2, 4, 3, 5} and {4, 1, 5, 2, 6, 3}? -Mr. Random

I found it. Find the number of permutations and divide by the first three numbers. -Mr. Random —The preceding unsigned comment was added by 207.179.172.217 (talk) 11:00, 11 May 2007 (UTC).

The algorithm presented in the article doesn't work with set equal or less than 2. Explication are missing about it.

Please sign your posts on talk pages per Wikipedia:Sign your posts on talk pages. Thanks! Hyacinth 19:56, 13 May 2007 (UTC)