Talk:Permutation
Permutation has been listed as a level4 vital article in Mathematics. If you can improve it, please do. This article has been rated as BClass. 
WikiProject Mathematics  (Rated Bclass, Highimportance)  


Daily pageviews of this article 
Archives 

Threads older than 12 months may be archived by Lowercase sigmabot III. 
Major Problem with Notation[edit]
If I am not mistaken (mistakenness is always possible) there is a huge split in the way people write permutations.
A mere notational divergence in itself would not be a big deal. There are many different kinds of notations used to describe many different mathematical objects. Generally they can portray and let portray. A mixed situation may not be ideal, but it is certainly no catastrophe.
What (I claim) makes the split in permutation notation rather more serious is that the two kinds of notation are indistinguishable, yet mean different things. In fact, we have not two different notations, but two different interpretations of the same notation. This confuses and disturbs me.
I speak, of course, of the popular doubleline notation (or, equivalently, the singleline notation) for specifying a permutation. One group of practitioners uses a sequence of numbers to refer to positions in the permutation. I will call this the Address Method. The other group uses a sequence of numbers to refer to the values contained in those positions. I will call this the Value Method.
An example follows.
1 2 3 4 5      3 5 1 2 4
Suppose one sets out to use the abovenotated permutation to reorder the sequence {5, 2, 4, 3, 1}.
Here is what happens when one applies the two different interpretations.
Using the Address Method, we understand the second line to be a picture of the first line after it has been operated on by the permutation. Thus we interpret the permutation to direct us as follows: "send the contents of position 3 to position 1; send the contents of position 5 to position 2; send the contents of position 1 to position 3; send the contents of position 2 to position 4, and send the contents of position 4 to position 5.
The result is {4, 1, 5, 2, 3}.
Using the Value Method, we understand the second line as a mapping of the values in the first line. Thus we interpret the permutation to direct us thus: "change each 1 to a 3, each 2 to a 5, each 3 to a 1, each 4 to a 2 and each 5 to a 4."
The result is {4, 5, 2, 1, 3}  entirely different from the result of using the Address Method.
This same split is, amazingly, also present in Cycle Notation, where, for example, the cycle {1, 2, 5} may again refer to addresses or to values. The results then differ just as they do when applying doubleline notation.
As far as I know, both systems produce working models of, say, a Symmetric Group. The problem lies not in any failure of theory, but only in a failure to produce the same written results from the same starting materials. I would hope such a problem would not affect people trying to grasp the rudiments of group theory by studying Wikipedia. (No, Wikipedia is not an ideal textbook, but it may very well serve as such for a while in some circumstances. And if it is useless, what's the point of writing this stuff?)
I am not neutral on this point. I favor the Address Method. I have several (I think) compelling reasons for that preference, but in order to keep this message short, I will save the details for a continuing exchange.
The Value Method is in use in the article under discussion here, namely Permutations. In the case of this particular article, changing the notation would require some rewriting, since there are verbal descriptions associated with the Value Method.
Already breaking my promise to wait before making an argument, I offer here one reason to consider changing the notation in the article. Consider the results below, copied from a Mathematica session.
?Permute Permute[expr, perm] permutes the elements of expr according to the permutation perm. In[1]:= Permute[{5,2,4,3,1},{3,5,1,2,4}] Out[1]= {4, 1, 5, 2, 3}
And Mathematica is far from the only reason to consider a change.
I am discussing this here because I am reluctant to jump in and make (what seem to me) significant edits without consulting the community. Please help me by following up on this.
Thank you Dratman (talk) 00:56, 26 August 2011 (UTC)
 Yes, there is an inherent and unavoidable ambiguity with oneline, twoline and cycle notations for permutations. (Though in my experience, I think the problem does not exist "in the wild" for cycle notation  I've never seen anyone use cycle notation to represent moving addresses, rather than values.)
 First look at http://www.scientificamerican.com/media/inline/200807/puzzles/m12.html
 and then at http://www.scientificamerican.com/article.cfm?id=thecyclenotationandm12 . This puzzle illustrates why the "address" method makes more sense, if not everywhere (though I think so), at least in a number of familiar situations. Think about the Rubik's cube. Do you describe moves as functions of color?
 For anther, independent example, see http://mathcircle.berkeley.edu/BMC3/perm/node3.html
 Dratman (talk) 18:39, 26 August 2011 (UTC)
 This is equivalent to the problem of whether we multiply permutations on the left or right. In fact, the two possible conventions are interchangeable by taking inverses of permutations (which exchanges values and positions, as well as the order of multiplication). It really doesn't seem possible to make a compelling case that one of these notations is preferable, since they literally carry exactly the same information and the use of both is widespread.
 I think in this situation that the sensible thing to do to preserve consistency of notation throughout as the main goal. This suggests to me that mucking around with the notation is a bad idea.
 Incidentally, the Mathematica description seems to me to be compatible with both notations because of the ambiguity about whether "according to the permutation perm" means that perm acts on the left or the right. Joel B. Lewis (talk) 02:17, 26 August 2011 (UTC)
 Yes, there exist different conventions for what is meant by permuting (more than two conventions, as will be clear below), but the description of the problem by Dratman is confused. One thing there is NO confusion about is which permutation (in the sense of a bijection) is meant by a twoline notation or by a cycle notation: it is the map that sends any value in the first line to the value directly below it in the second line, respectively that sends any value in a cycle notation to the next value (wrapping to the start of the cycle if necessary).
 Also, in case the twoline form is reduced to a single line (as is done in the discussion above) then this is only done in case of permutations of a set [n]:={1,2,...,n}, and the reduction is then obtained by writing the twoline form with "1 2 ... n" as first line (as is most common, though not obligatory for a twoline form) and then dropping that first line.
 The next thing to worry about is composing permutations: here indeed there are two schools (see Permutation#Product and inverse). What I've seen most, and this article uses, is the convention that permutations compose as functions (which they are) do, so f∘g denotes the map x↦f(g(x)), in other words the permutation on the right "sees the argument first". The other school prefers the opposite order, and has the left permutation see the argument first; this would be natural is functions were written to the right of their arguments, but I don't think adherents of that school would normally do that (for one thing Knuth composes permutations lefttoright while writing functions to the left; this would give a mess when permutations are used as functions, but I guess he simply never does that). But I don't think this dichotomy is what Dratman asks about, so I will assume the righttoleft composition convention to get this issue out of the way.
 I "prefer" the righttoleft convention when I write f(g(x)). That notation is unambiguous! I prefer the lefttoright convention when I write A ∘ B, as in group theory (where it is disputed) or in the "syntactic sugar" first layer parser of any nonLisptype computer language (where it is not disputed). I am well aware that many people are strongly in favor of using the righttoleft convention everywhere. But the problem, I repeat, is not that there are two conventions. The problem, which (I claim) is serious, is that they are indistinguishable.Dratman (talk) 19:17, 26 August 2011 (UTC)
 Finally, and most to the point, there is the question about what permuting, or acting by a permutation, means. There are many sets that a permutation group can act upon, and the action could be defined in a arbitrarily complicated way. However there are two classes of "natural" ways for permutations to act: for sets "builtup" from [n] (such as [n] itself, or the set [n]^{2} of ordered pairs, or the set of kcombinations taken from [n]), the natural action is to apply the permutation (as a function) to each of the components; this is the "value" point of view signalled above. There is little confusion about this kind of action: one gets a left action by applying the permutation itself (rather than its inverse). In symbolic notation this action, in the case of [n]^{2}, looks like
 .
 Finally, and most to the point, there is the question about what permuting, or acting by a permutation, means. There are many sets that a permutation group can act upon, and the action could be defined in a arbitrarily complicated way. However there are two classes of "natural" ways for permutations to act: for sets "builtup" from [n] (such as [n] itself, or the set [n]^{2} of ordered pairs, or the set of kcombinations taken from [n]), the natural action is to apply the permutation (as a function) to each of the components; this is the "value" point of view signalled above. There is little confusion about this kind of action: one gets a left action by applying the permutation itself (rather than its inverse). In symbolic notation this action, in the case of [n]^{2}, looks like
 But in practice the other natural class of actions is more important: the actions on sets of the form X^{n}, i.e., of ntuples taken from some set X, or on invariant subsets thereof. The action is by permuting the positions, so that each component of the ntuple becomes a component of the result, at a position determined by the permutation. If one wants a leftaction of the permutation group, then a permutation σ will send a component at position i to the position σ(i). While there is no inverse in this description, it will be present in a symbolic notation, which looks as follows
 ,
 because to know the first component of the result, one must search for a component that is sent to the first position, and that is the one originally at position σ^{−1}(1). I am personally comfortable with this way of interpreting permuting of ntuples, but one could prefer (maybe in view of the somewhat awkward symbolic notation) to define a rightaction instead: then permutation by σ will send a component at position σ(i) to the position i, and in symbolic notation one gets (writing the permutation at the right, as is appropriate for a right action)
 ;
 this is I guess what is called the "Address Method" above (which reads the twoline notation from bottom to top: "send the contents of position 5 to position 2" (because 5 is below 2)). I also suppose this is what Mathematica does, which example would have looked much clearer if it had been given as follows (but it is just my guess that Mathematica would do this, as I don't have it to try; also I find the braces particularly disturbing since normally order is ignored inside a set):
 But in practice the other natural class of actions is more important: the actions on sets of the form X^{n}, i.e., of ntuples taken from some set X, or on invariant subsets thereof. The action is by permuting the positions, so that each component of the ntuple becomes a component of the result, at a position determined by the permutation. If one wants a leftaction of the permutation group, then a permutation σ will send a component at position i to the position σ(i). While there is no inverse in this description, it will be present in a symbolic notation, which looks as follows
In[1]:= Permute[(e,b,d,c,a),{3,5,1,2,4}] Out[1]= (d, a, e, b, c)
 Yes, that is exactly the result given by Mathematica.
 Sadly, Mathematica uses "{...}" as list delimiters, to enclose any nonatomic object whatsoever. It is definitely not set notation.
 That bothered me until I realized it's just like Lisp's "(...)": the language has no grammar below that level, so one set of delimiters has to be universal. Dratman (talk) 18:00, 26 August 2011 (UTC)
 This is consistent with the fact that the Permute function takes the permutation as its second (right) rather than its first (left) argument.
 If one wants to act on the set P of "permutations in oneline form", namely the set of ntuples with n distinct components taken from [n] , then one finds oneself on the intersection of the two classes: P is both builtup from [n], and an invariant (under permuting) subset of [n]^{n}. So this is the most confusing case possible, where several "natural" actions of permutations compete (it would have been different if ntuples with n distinct components taken from any other nelement set were considered, in which case only permutation of positions would be possible). So we have (at least) three such ways to act by a permutation σ on a oneline form p: two left actions which are (1) apply σ to each component (the Value Method), and (2) send each component at position i to the position σ(i) (the "left Address Method"), and one rightaction (3) send (x_{1},...,x_{n}) to (x_{σ(1)},...,x_{σ(n)}) (the "Address Method"). Denoting the fact that p is the oneline notation for a permutation π as p=ol(π), these three methods can also be described as sending this ol(π) respectively to (1) ol(σ∘π), to (2) ol(π∘σ^{−1}), and to (3) ol(π∘σ). I think the real root of confusion is that in the very particular case that p=(1,2,...,n) (so π is identity), the results of (1) and (3) are the same (though the actions are quite different) since σ∘π=π∘σ when π is identity. So saying that σ is the permutation that sends p=(1,2,...,n) to ol(σ) does not tell you whether leftaction (1) or rightaction (3) were used. Moral: it is a bad idea to think of permutations as defined by the way they transform oneline forms;
 Exactly. That is how this ambiguity came into existence. One should not define a function of certain positive integers as "(4, 7, 2, 1, 8)" when one means f(1) = 4, f(2)= 7, f(3) = 2, f(4) = 1, f(5) = 8. Use any notation you like, but make it clear what you mean Dratman (talk) 19:47, 26 August 2011 (UTC)
 they are just bijections [n]→[n], and as such there is no ambiguity. And the definition of the twoline notation uses the Value Method, since the permutation used throughout the example above could be written not only as
 If one wants to act on the set P of "permutations in oneline form", namely the set of ntuples with n distinct components taken from [n] , then one finds oneself on the intersection of the two classes: P is both builtup from [n], and an invariant (under permuting) subset of [n]^{n}. So this is the most confusing case possible, where several "natural" actions of permutations compete (it would have been different if ntuples with n distinct components taken from any other nelement set were considered, in which case only permutation of positions would be possible). So we have (at least) three such ways to act by a permutation σ on a oneline form p: two left actions which are (1) apply σ to each component (the Value Method), and (2) send each component at position i to the position σ(i) (the "left Address Method"), and one rightaction (3) send (x_{1},...,x_{n}) to (x_{σ(1)},...,x_{σ(n)}) (the "Address Method"). Denoting the fact that p is the oneline notation for a permutation π as p=ol(π), these three methods can also be described as sending this ol(π) respectively to (1) ol(σ∘π), to (2) ol(π∘σ^{−1}), and to (3) ol(π∘σ). I think the real root of confusion is that in the very particular case that p=(1,2,...,n) (so π is identity), the results of (1) and (3) are the same (though the actions are quite different) since σ∘π=π∘σ when π is identity. So saying that σ is the permutation that sends p=(1,2,...,n) to ol(σ) does not tell you whether leftaction (1) or rightaction (3) were used. Moral: it is a bad idea to think of permutations as defined by the way they transform oneline forms;
1 2 3 4 5      3 5 1 2 4
 but also (as is allowed, see Permutation#Notation) as
5 2 4 3 1      4 5 2 1 3
 (the same columns in a different order). You'll see that its second line is now obtained from the first one only by the Value Method, not by the Address Method. I hope this settles your question. Marc van Leeuwen (talk) 10:24, 26 August 2011 (UTC)
 In my experience, the majority of people who study finite permutation groups use action on the right, that is gh maps x onto h(g(x)). Zero^{talk} 11:29, 26 August 2011 (UTC)
 Whether or not you're right about the majority of people, I think the proper way to say this is defining composition so that the natural action of permutations on the base set [n] is a right action, although it is written on the left (personally I find using that combination of conventions somewhat masochistic). But that action is not the main topic of the initial question, which is about permutation actions (however changing the convention about composition does make everything one says about actions come out differently, which is why I wanted to fix composition first). Marc van Leeuwen (talk) 12:25, 26 August 2011 (UTC)
See also: Talk:Cayley_graph#Order_of_compositions
There the conclusion was, that ab stands for first do a, than do b, because that's how function composition is written by almost everyone. The article f.c. states the same. Watchduck (talk) 12:31, 26 August 2011 (UTC)
 Grmpf... even more confusion. Quoting from function composition:
 Thus one obtains a composite function g ∘ f: X → Z defined by (g ∘ f)(x) = g(f(x)) for all x in X. The notation g ∘ f is read as "g circle f", or "g composed with f", "g after f", "g following f", or just "g of f".
 Now where in that sentence does it suggest the the left factor g in the composition gets applied before the right factor f?? Also the Cayley graph talk page and article are somewhat confusing: in the article it says "For any the vertices corresponding to the elements and are joined by a directed edge of colour " but in the illustration there is an edge between (for instance) a node labelled 'a' and one labelled 'ba' (or 'cb' and 'bcb' in another illustration) which I cannot get by any sensible values for g and s in the cited sentence. And this problem is independent of how one defines elements of the group to act.
 To mitigate what I said before a bit, one can without too much confusion define the product permutation g.h as h∘g (apply h after g), provided one takes care to always distinguish 'dot' (or juxtaposition) from 'circle' (probably never using the latter), and to avoid writing g(x) (using something like x.g or x^{g} instead for "the image of x by g"). Marc van Leeuwen (talk) 14:42, 26 August 2011 (UTC)
Grmpf ... sorry, I meant to write: "that ab stands for first do b, than do a"
In short: h∘g = h after g = h(g(identity))
Everything else seems to be very unusual, and should just be mentioned, but not used in the article. Watchduck (talk) 15:07, 26 August 2011 (UTC)
 Let me amend my comments to note that I agree with Marc van Leeuwen that I don't think the ambiguity for twoline notation exists in the wild, either, except to the extent that it's equivalent to the ambiguity about which side we multiply permutations on. I also would like to reiterate my opinion that it's a very bad idea to try to change the notation in the article. Joel B. Lewis (talk) 19:43, 26 August 2011 (UTC)
I believe I have shown that both interpretations can, in fact, be found "in the wild." In case you missed the evidence, please see a reply I added, including 3 URLs, near the top of this section. Nevertheless, since several people here are strongly opposed to the idea, it appears we should not change the notation used in the article. Next question: can we clarify any ambiguities without excessively disturbing the flow of the article? I would like to ensure that a reader new to this area of math knows exactly which algorithm is intended. That should not be difficult to do. We just need to add a few definite indications as to how the method works, such as f(1) =, f(2) =, and so forth, along with some related indications of what, specifically, is supposed to happen. It would, however, be absolutely necessary to decide whether, in this article, permutations operate "on the right" or "on the left"  a question about which there seems to be a good bit more uncertainty. Dratman (talk) 23:13, 26 August 2011 (UTC)
 I think that what is exactly meant by "both interpretations" has not been clearly indicated, which makes discussing difficult. However, having looked at the examples given, I'm understanding better the point of view that causes difficulty with the text of the current article. It is vital to make a clear distinction between a "permutation" (a bijection of a set to itself) and the act of permuting an ntuple. One can discuss permutations without considering the act of permuting; most of the current article does that. On the other hand one can be interested in acts of permuting but not in considering bijections of a set; when studying the Rubik's cube one would be in such a situation, and the cited texts from the Scientific American and Berkeley take this point of view. I think the original question was posed from the latter "permuting" perspective, although it is not explicitly mentioned. In any case, from this perspective any permutations considered would be bijections on the set of positions (not of the values sitting in those positions, for instance colours in the case of Rubik's cube) so this is an Address interpretation of permutations.
 As I have mentioned above, there are two possible ways to associate an act of permuting to a given permutation σ: what I called (2) above, which sends the contents of position i to position σ(i), and (3) which takes the new value of position i to be the old value of σ(i); from the permuting perspective the question is in the opposite direction of associating a permutation to an act of permuting, but the two possibilities are still present. From the given examples I conclude that in popular texts (2) is most used, and this is psychologically understandable (σ goes in the direction of the movement of objects), so I'll stick to this convention. However in the permuting perspective one is not even really interested in associating a permutation to an act of permuting, but just to have a notation to write down that act. A natural choice, clearly made in the Scientific American, is to write down the result of permuting an standard initial ntuple , (1,2,...,n). Now the sad fact of life is that the result of permuting (1,2,...,n) according to σ is not the second line of the twoline notation for σ, but of that of its inverse. So this convention uses an alternative "oneline notation" for σ that is not related to the twoline notation for σ by taking the second line. One can get this alternative notation by reordeing the twoline form so that its second line is increasing, and then taking the first line. The confusing comes in part from the fact that this convention is seldom made explicit. Maybe this is the reason that mathematical texts hardly ever introduce the one line form for permutations, it is too confusing.
 However I restate: there is no ambiguity in the meaning of the twoline or cycle notations as designating a bijection (please prove examples if you contest this). So this article can stay as it is, maybe adding a note about permuting. Marc van Leeuwen (talk) 06:00, 30 August 2011 (UTC)
 I now agree that the article should not be changed, except possibly to clarify (briefly and unobtrusively) exactly what the manipulations used in the article mean and what they specifically do.
 With respect to any more realworld ambiguity in the use of the twoline or cycle notations as designating a bijection, my question has always been, DO they refer to a bijection, and exactly how is such a bijection being specified? To this I now want to add the question, do they refer to a "left action" or to a "right action"? These details are all relevant when one tries to work out examples. I will present any additional findings after further study.
Here is another typical instance of the problem, from Mathworld:
 A permutation cycle is a subset of a permutation whose elements trade places with one another. Permutations cycles are called "orbits" by Comtet (1974, p. 256). For example, in the permutation group , (143) is a 3cycle and (2) is a 1cycle. Here, the notation (143) means that starting from the original ordering [1,2,3,4], the first element is replaced by the fourth, the fourth by the third, and the third by the first, i.e., 1>4>3>1.
Here the author unambiguously uses the notion of moving items from one position (what I've called a slot) to another, but then unfortunately starts from [1,2,3,4], from which both methods have the same effect! Dratman (talk) 04:38, 20 November 2011 (UTC)
 In trying to learn how to convert 2line to cycle notation, it was not obvious that (by definition) an application of a kcycle must change the positions of all k of its elements. Talking instead of editing in case I overlooked its mention elsewhere. Also, does this imply that kcycles always have sign of (1)^(k1)? — Preceding unsigned comment added by 74.129.169.64 (talk) 15:33, 8 April 2018 (UTC)
I would like to add that the Mathematica examples above might be misleading.
By default Permute[{5,2,4,3,1},{3,5,1,2,4}]
= {4,3,5,1,2}
and Permute[{e,b,d,c,a},{3,5,1,2,4}]
= {d,c,e,a,b}
.
Only when the Combinatorica package is used (Needs["Combinatorica`"]
) it changes to the cited results {4,1,5,2,3}
and {d,a,e,b,c}
.
At least these are the results I got in a trial version of Mathematica Online.
I have created v:Permutation notation to come to terms with the problems described in this section. There is also a section on Wolfram. Watchduck (quack) 23:07, 6 December 2016 (UTC)
Proposed Merge[edit]
I believe that Cycle notation should be merged into this article, Permutation. First of all, the treatment of cycle notation in this article is more extensive that of its own article. The definition of cycle there is incomplete and the language used to describe the cycle decomposition is at too high a level for the topic. It would take major effort to bring that article up to snuff and in the end it would only be a repeat of what is already here. The only salvageable piece of that article is the example of S_{4} which I propose to merge here. Bill Cherowitzo (talk) 23:01, 10 April 2014 (UTC)
 It probably makes sense to merge here, though it would be nice to have a toplevel notation section devoted to notation of permutations. There may be scope for then splitting off the content of this section, or not, but even if it was split off, I'd think that it should deal with notation of permutations, not only with cyclic notation. The merge would serve to make the material cohesive and eliminate excess duplication. —Quondum 16:56, 7 June 2014 (UTC)
 I think the cycle notation should be divorced from under the heading of Permutations_in_group_theory for it is used in other contexts too. The group theory part has interesting things to say about permutations in cycle notation (e.g. conjugates etc.), but it's not the only angle on cycle notation, e.g. Foata's transition lemma is practically never mentioned in group theory books. 86.127.138.67 (talk) 10:12, 4 April 2015 (UTC)
 I also agree with the merge. I've added some material (here) on the conversion between notations. It would make little sense to add it to the short article because it doesn't define the oneline notation etc. 86.127.138.67 (talk) 09:38, 4 April 2015 (UTC)
 There is one fly in the ointment concerning a merge which I object to very strongly. The original cycle notation article was in fact very informative. In addition, the talk/discussion tab contained some very informative discussion that clarified many of the main points of that article. Merging may be a reasonable idea, but the original page and talk/discussion should be included in the history of the Permutation article that the original cycle notation article has been merged into. As it stands now, the content of the original article and talk/discussion is completely disappeared (or at least inaccessible). For those of us who wish to refresh on it, this complete purging of the content is completely unfair. Please either restore the original article and talk/discussion or include it as part of the history of the Permutation article into which it was merged. At least this way, the original material is available to those of us who wish to review it occasionally. — Preceding unsigned comment added by 2602:306:BD4D:6920:21B:77FF:FE9D:A6DA (talk) 22:12, 27 December 2016 (UTC)
Annoyingly bad presentations in several books[edit]
Alas the stuff I've added is a bit less than satisfactory. Bona's presentation is somewhat confusing in that in his fascination with Foata's transformation he doesn't separately present the properties of the canonical cycle form. I thought I found a good fix to this by reading/using Aigner's book, but it also has problems. For example he says (p. 25):
Conversely, from any npermutation a1a2 . . .an we may uniquely recover the cycle decomposition: (a1a2 . . .) (ai . . .)(aj . . .) . . ., where ai is the first entry larger than a1, aj is the first entry after ai larger than ai, and so on. Thus, the number of cycles determined in this way equals the number of lefttoright maxima of the word a1a2 . . .an.
The only problem with this is that there may be no ai greater than a1, e.g. if the oneline/word is 321 (Appologies for the lack of TeXing but I feel rather pissed right now and not in the mood for more formatting.) 86.127.138.67 (talk) 13:28, 4 April 2015 (UTC)
So, how I can calculate the number (or position) of a given permutation?[edit]
If I got a permutations of the numbers 1…16, e.g. (10,4,8,11,3,16,9,6,14,1,15,7,2,13,5,12), how can I calculate efficiently the position of this permutation in the lexicographicalordered list of all permutations from (1,2,3,…,14,15,16) to (16,15,14,…,3,2,1)? I can't get the algorithm from the formulae given in the article. :( RokerHRO (talk) 08:52, 19 August 2015 (UTC)
 This page is not a helpdesk. Try https://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Mathematics instead. JBL (talk) 12:49, 19 August 2015 (UTC)
Unnecessary confusion caused by inconsistent notation[edit]
The section on other uses of the word 'permutation' explains kpermutation of n ″arrangements of a fixed length k of elements taken from a given set of size n" and I can only assume this refers to n number of items within a set being arranged into groups of length k.
Why, then, does the very proceeding section dealing with permutations with repetition refer to "arrangements of the elements of a set S of length n ... the set S has k elements" which seems to be referring to exactly the same basic mathematical concept (the number of groups of a given length from a fixed set of items) but is instead referring to k number of items being arranged into groups of length n. This strikes me as a pointless inversion and will only confuse readers further.
Can someone please explain why this is this way? I do not know enough about the underlying mathematics to comment on the correctness of the equations themselves in regards to one another.
Somerandompersonwithabrain (talk) 17:16, 13 February 2016 (UTC)
 This topic has been around for a long time and has been frequently rediscovered in many disparate fields. The terminology is just not uniform due to that. We are supposed to be reporting on what is in the literature, and if that literature is inconsistent then so will our reporting of it be. If I were writing all of this stuff myself, as in a book or published article, then I could make the notation I use consistent. But the best we can hope for on Wikipedia is that we use the notations that are the most common in the literature, and this will lead to the problems you see. Trying to do otherwise will get shot down as being WP:OR.Bill Cherowitzo (talk) 22:39, 13 February 2016 (UTC)
The difference between Permutation and Combination[edit]
The difference between Permutation(NPr) and Combination(NCr) is as simple as that, in combination it is just that it is commutative but not associative. NPr  Permutation covers all the possibilities.
Commutative, Associative terms are generic in Mathematics, Vector, Algebra, Linear Algebra and also Modern Algebra.
—Dev Anand Sadasivam^{t@lk} 05:55, 6 April 2016 (UTC)
Paren notation in intro is misleading[edit]
Hello, not a regular editor so I'll just post my concern here. In the intro it says "... there are six permutations of the set {1,2,3}, namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1)."
The paren notation is misleading in this context. The remainder of the article clearly and correctly identifies the standard twoline mapping notation and the oneline cycle notation. Once a student has learned those, (1, 2, 3) is forever understood as cycle notation.
If someone is new to this material, the incorrect use of the parens is confusing and counterproductive to learning. Far better to use [1,2, 3] or <1, 2, 3> IMO. You don't need to explain this choice or call attention to it, since the intro is implicitly invoking the reader's intuition and they'll understand this just as well as with parens.
But later when they get to the twoline and cycle notations, they will not be confused by the earlier use of parens with a different meaning.
189.222.170.79 (talk) 04:36, 17 January 2017 (UTC)
 In a perfect world everyone would use the same notations and ambiguity would never occur. Alas! While I personally only use the two forms you mentioned, I know that the oneline version is the preferred notation among computer scientists and some combinatorialists. This has a lot to do with how you are representing or using permutations. For these individuals, cyclic notation is useless and twoline notation is cumbersome. While your suggestions are good, they are not wide spread and Wikipedia only reports what is in the literature and does not try to "make things right". Bill Cherowitzo (talk) 05:10, 17 January 2017 (UTC)
Recent edits[edit]
I've spent some time renovating the article. But I think I'll stop here to give everyone else a chance. There is still some duplicated content in the article and I'd like to excise the section "Other uses ..." since it isn't about permutations per se and is likely to confuse the reader. ImTheIP (talk) 14:40, 29 October 2018 (UTC)
 While I'm generally happy with the edits you've been making, a word of caution is in order. It seems clear to me that you are writing for a mathematical audience with an occasional nod toward other readers. This may cause problems. Consider some of the remarks given earlier on this talk page. There was a time when "a permutation is a bijection" did not even appear on the page and you are moving in the direction of turning that on its head. Several readers come to this page only with the elementary concept of arrangement and a confusion between permutations and combinations; talking about bijections will not help these folk. I think a balance has to be struck between the mathematically correct and the historically useful approaches to the topic. I would definitely not excise the "Other uses ..." section since it is only "not about permutations" from only one point of view. Also, please be a little more careful in proofreading. Most of my corrections have been fixing blatant errors and I'd be happy to discuss my reasons for any more substantial changes. Bill Cherowitzo (talk) 23:46, 29 October 2018 (UTC)
 I share this concern. In particular, it is not universally true that a permutation is a bijection: it is trueish in the context of modern research mathematics, but not in the historical usage of the term nor in its current usage in some elementary contexts. Even in the modern setting it is not necessarily true that a permutation is a bijection: in many contexts a permutation is actually a word or actually a matrix, for example. (Of course these things are naturally in correspondence with each other, but it is not true that one of them is uniquely privileged over the others.) JBL (talk) 10:29, 30 October 2018 (UTC)
 I don't think that anyone is advocating removing bijective functions from the discourse, and if you got that impression from my comments, that's my bad! What I am advocating is raising the level of the passive interpretation of permutations so that it is comparable to the group theoretic approach (which your edits have clearly improved). The old first paragraph made a reasonable attempt to do this and I will put that back in along with some other tweaks to bring more of a balanced view to the article.Bill Cherowitzo (talk) 17:48, 31 October 2018 (UTC)
What is the idea behind having some books in the Further reading list and others in the Bibliography? ImTheIP (talk) 13:56, 5 November 2018 (UTC)
 According to WP:FURTHER and Wikipedia:Further reading sources that are not directly used as references, but for which some editors feel are still valuable resources for readers, should be put in a Further reading section. I find this guideline particularly useful in keeping down the clutter when Harvard style referencing is being used. Bill Cherowitzo (talk) 19:31, 5 November 2018 (UTC)
Edit request[edit]
This edit request by an editor with a conflict of interest has now been answered. 
After being informed by MrOllie about a potential conflict of interest, I am now formally requesting to make the following additions to the page. The Combinatorial Object Server is a collection of open source software tools I frequently use to create this kind of illustrations, and to which I am a frequent contributor.
Extended content


A: Add the following paragraph to the Subsection "Generation with minimal changes": The following figure shows the output of all three aforementioned algorithms for generating all permutations of length , and of six additional algorithms described in the literature. 1: Lexicographic ordering; 2: SteinhausJohnsonTrotter algorithm; 3: Heap's algorithm; 4: Ehrlich's startransposition algorithm (see ^{[2]}): in each step, the first entry of the permutation is exchanged with a later entry; 5: Zaks' prefix reversal algorithm^{[3]}: in each step, a prefix of the current permutation is reversed to obtain the next permutation; 6: SawadaWilliams' algorithm^{[4]}: each permutation differs from the previous one either by a cyclic leftshift by one position, or an exchange of the first two entries; 7: Corbett's algorithm^{[5]}: each permutation differs from the previous one by a cyclic leftshift of some prefix by one position; 8: Singletrack ordering^{[6]}: each column is a cyclic shift of the other columns; 9: Singletrack Gray code^{[6]}: each column is a cyclic shift of the other columns, plus any two consecutive permutations differ only in one or two transpositions. B: Add the following external link: References

Torsten Mütze (talk) 19:07, 29 May 2019 (UTC)
 Per my concerns at the bottom of Talk:Gray code (Special:PermanentLink/899583820#tbfobjection2019), I object to the addition of the external link (B). I have no opinion on part A. ~ ToBeFree (talk) 23:45, 30 May 2019 (UTC)
 If this edit is done, I would change "SteinhausJohnsonTrotter" to "Steinhaus–Johnson–Trotter" (with an endash rather than a hyphen), per WP:MOS, and where it says "red=1" I would instead write "red = 1" (and similarly with the other colors, of course), since that is the standard format.
 Contrast:
 SteinhausJohnsonTrotter
 Steinhaus–Johnson–Trotter
 red=1
 red = 1
 Michael Hardy (talk) 21:16, 31 May 2019 (UTC)
 Done All proposed edits and suggested modifications for (A) have been implemented. The proposed additional links to the EL section (B) were declined. Thank you to everyone for their input. Regards, Spintendo 15:59, 9 June 2019 (UTC)
 Wikipedia level4 vital articles in Mathematics
 Wikipedia BClass vital articles in Mathematics
 Wikipedia BClass level4 vital articles
 Mathematics articles related to basic mathematics
 Frequently viewed mathematics articles
 BClass mathematics articles
 HighPriority mathematics articles
 Implemented requested edits