Talk:Permutation/Archive 1

Archive 1

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 April 2004 (UTC)

Permutations as bijections

Funny but I came to the article in order to check whether "permutation is the same as bijection" (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 April 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 April 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 April 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 April 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 April 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 November 2004 (UTC)

The meaning you mention is essentially obsolete in professional mathematics. The article should reflect that fact. --Zero 23:45, 10 November 2004 (UTC)

Comments

---> 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, 19 November 2003 (UTC)

Can you give us an example? I don't understand exactly what you mean. Dysprosia 08:40, 19 November 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 November 2003 (UTC)

Thanks for reply but more generally, what is inversion? I really couldn't find out the definition of inversion. -- Taku 03:28, 20 November 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 November 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 November 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 November 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 March 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 March 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 March 2004 (UTC)

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

Shall I implement it? Or wait till Hfastedge wants to chip in? Dysprosia 07:08, 28 March 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 March 2004 (UTC)

its been changed Hfastedge 17:59, 31 March 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 March 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 April 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 April 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 April 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 April 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 April 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 April 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 April 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 April 2004 (UTC)

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

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

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 November 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 November 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, 2 February 2005 (UTC)

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

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

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)

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)

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)

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)

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:

• permutation
• permutation group
• symmetric group
• cycle (mathematics)
• cycles and fixed points

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)

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)

permutation

in how many ways can the result of twelve soccer matches be arranged with either a win , draw or loss41.210.20.124 (talk) 18:12, 1 April 2009 (UTC)

calculators

The derivative page has five calculators in the external links and is rated higher than this page. Seems that makes for a better page. This is just not paper put to a Web page.

Warren Van Wyck (talk) 01:40, 21 October 2009 (UTC)

Please read the external links policy and WP:LINKFARM. Links should elaborate on the topic; those that provide a service based on that topic belong in a web directory such as dmoz. (BTW: I've removed those calculators from the derivate page.) Mindmatrix 13:41, 21 October 2009 (UTC)

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)

This page is very inaccessible to laymen trying to learn something new. The introduction jumps right into numerous complex terms. Why not just explain what a permutation is in plain English, provide a simple example, then get into the shop talk on the technical paragraphs? I'm sure it makes sense to egg heads, but then this article wouldn't be telling them anything they don't already know. —Preceding unsigned comment added by 24.35.121.92 (talk) 12:29, 23 February 2010 (UTC)

Introduction digresses.

The introduction is too long (WP:Lead). The historical information and quotation are obviously out of place. The remaining text should be trimmed down if possible. —Preceding unsigned comment added by NOrbeck (talk • contribs) 20:35, 19 August 2010 (UTC)

Agreed and so tagged. The opening needs to be accessible, and simple but useful formulas (like the number of permutations with and without repetition) should be easy for students to find. -- Beland (talk) 14:58, 20 August 2010 (UTC)

Also agreed. I've removed a large amount of content, some of which should probably find a new home elsewhere in the article. It is copied below for reference. --71.233.44.242 (talk) 03:13, 14 January 2011 (UTC)

In algebra and particularly in group theory, a permutation of a set S is defined as a bijection from S to itself (i.e., a map S → S for which every element of S occurs exactly once as image value). To such a map f is associated the rearrangement of S in which each element s takes the place of its image f(s). In combinatorics, a permutation of a finite set S is defined as an ordering of its elements into a list. In this sense, the permutations of S differ precisely by a rearrangement of their elements. For a set S that is given with an initial ordering, such as S={1,2,3,...,n}, these two meanings can be almost identified: applying a permutation in the first sense to this initial ordering gives an alternative ordering of the elements, which is a permutation in the second sense.

The term permutation is also used less formally to designate the act of rearranging parts of an object, or the result thereof. Thus one might define an anagram of a word as a permutation of its letters, or say that X³Y+7+Y²Z is (obtained by) a permutation of the terms of the polynomial X³Y+Y²Z+7. The act of permuting can also refer to substitution of symbols, for instance when saying that Y³Z+Z²X+7 is obtained from X³Y+Y²Z+7 by a (cyclic) permutation of the variables X, Y, Z. These statements can be given a precise meaning by considering an appropriate symmetric group action.

In combinatorics the second sense of "permutation" is sometimes broadened. In elementary combinatorics, the name "permutations and combinations" refers to two related problems, both counting possibilities to select k distinct elements from a set of n elements, where for k-permutations the order of selection is taken into account, but for k-combinations it is ignored. In fact counting k-permutations is used as a step towards counting the number ${\tbinom {n}{k}}$ of k-combinations, and also towards computing the number n! of permutations of the set (in either of the two meanings mentioned above). However k-permutations do not correspond to such permutations unless k = n, that is, unless the selection involves all available elements. In a different broadening of the notion of permutation, one can start, rather than with a set S, with a finite multiset M in which some values may occur more than once. A (multiset) permutation of M is a sequence of elements of M in which each of them occurs exactly as often as it occurs in M. Thus for M=[1,1,1,2,3,3], the sequence [3,1,2,1,1,3] is a multiset permutation of M, but [3,1,2,1,2,3,1] is not.

Permutations occur, in more or less prominent ways, in almost any domain of mathematics. They often arise when different orderings on certain finite sets are considered, possibly only because one wants to ignore such orderings and needs to know how many configurations are thus identified. For similar reasons permutations arise in the study of sorting algorithms in computer science. In algebra, an entire subject is dedicated to the detailed study of permutations, through the notion of symmetric group. The key to its structure is the possibility to compose permutations: by performing two given rearrangements in succession, the combination defines a third rearrangement.

The rule to determine the number of permutations of n objects was known in Hindu culture at least as early as around 1150: the Lilavati by the Indian mathematician Bhaskara II contains a passage that translates to

The product of multiplication of the arithmetical series beginning and increasing by unity and continued to the number of places, will be the variations of number with specific figures.

A first case where at first sight unrelated mathematical questions are studied with the help of permutations occurs around 1770, when Joseph Louis Lagrange, in the study of polynomial equations, observed that properties of the permutations of the roots of an equation are related to the possibilities to solve it. The development that came forth from this work ultimately resulted, through the work of Évariste Galois, in Galois theory, which gives a complete description of what is possible and impossible with respect to solving polynomial equations (in one unknown) by radicals. In modern mathematics there are many similar situations, where understanding a problem requires studying certain permutations related to it.

References

Permutations in statistics?

I have a feeling that there might be some statistical tests (say, nonparametric, just using ranks) that use facts from permutation.

A question, for example: If I draw from two distributions and order them in a single list, what is the probability that the observed permutation is at random (versus sufficiently disordered)? I know a Wilcoxon rank-sum test is a paired version. What about unpaired?

My point is it would be nice to work these references into the permutations article, or at least provide a cross-ref.

dfrankow (talk) 21:16, 30 April 2009 (UTC)

Can you guys make thins simple to understand. Wiki pages on some topics are too obscure to understand. —Preceding unsigned comment added by 180.149.49.125 (talk) 17:34, 19 March 2011 (UTC)

Symmetry between Permutation and Combination

Could someone please re-mention the symmetry between decoding unique factoradic integer k for Permutations (Variable Bit Decoding) and Combinations (Constant Bit Decoding) since ite got nuked. Michael.Pohoreski (talk) 17:02, 22 October 2010 (UTC) e.g. * http://en.wikipedia.org/w/index.php?title=Permutation&oldid=342103380#Encoding_and_decoding

There is some relation between the factorial number system and the combinatorial number system (and both articles refer to one another), but this does not directly relate to the subject of this article in any way. What is unclear to me is what exactly is Variable bit decoding and Constant bit decoding. As for the program code, that is hardly every relevant on a wikipedia page, even one that discusses an algorithm, as algorithms are best described in a programming language independent fashion. In any case wikipedia is not a repository of computer programs. Marc van Leeuwen (talk) 18:51, 19 March 2011 (UTC)

nPr notation

my calculator has a nPr button is this a common notation for purmutations? — Preceding unsigned comment added by 136.159.16.7 (talk) 17:14, 22 September 2011 (UTC)

See the section Permutation#In_combinatorics Joel B. Lewis (talk) 17:21, 22 September 2011 (UTC)

Permutation of an empty set

The lead section states in part:

The number of permutations of n distinct objects is n×(n − 1)×(n − 2)×...×2×1, which number is called "n factorial" and written "n!".

Although this is mathematically correct, neither this nor the rest of the article make it clear to me for which n a permutation of a set of n objects is defined. I do not see any restriction on n in the article. I do not see n defined to be an integer, a natural number, etc. Specifically, does it make sense to speak of a permutation of an empty set? Would an expert on the subject of permutations please clarify these issues in the article? Thank you! — Anita5192 (talk) 02:50, 28 February 2012 (UTC)

Given the context of introduction "n distinct objects", it is clear that n is a natural number. It can be any such number, including 0, why shouldn't it be allowed? There is exactly 0! = 1 permutation of the empty set, which happens to be the empty function ∅ → ∅. Marc van Leeuwen (talk) 18:02, 28 February 2012 (UTC)

As a mathematician, I never assume anything that I do not have to. What you just described is what I already guessed, but mathematics should be clear and should leave nothing to guesswork. Since this issue was not clear to me, how can it be clear to the average nonmathematician? If n is a natural number, I think this should be stated explicitly for anyone not already familiar with the phrase, "n distinct objects." There is also some disagreement as to whether natural numbers or whole numbers include zero. — Anita5192 (talk) 00:19, 29 February 2012 (UTC)

Ball illustration confusing

The illustration with the balls is kind of confusing. They should be separated so that the reader can see that the six sets are independent and not part of some sort of matrix of balls. — Preceding unsigned comment added by 71.239.6.227 (talk) 02:58, 14 March 2012 (UTC)

Permutations in cryptography?

Permutations is linked from cryptography pages, but it is not clear which definition applies. It would be nice if there was a more explicitate explanation of what a "permutation" is in the context of cryptography. 23.25.179.162 (talk) 16:03, 3 October 2012 (UTC)

A new method of finding sequence of permutation and converting this permutation into number and number into arrangement of object as well i.e. its converse.

I have done extensive research on permutation and combination and found consistent result in my research. this result I have found is written in a book known as junction. To see my research result then log in to my sight https://sites.google.com/site/junctionslpresentation/home or e-mail me at Softlaws4095@gmail.com — Preceding unsigned comment added by 14.97.116.20 (talk) 18:34, 24 April 2012 (UTC)

Now I have attached some microsoft word documents which gives some of the proofs of junctions on which I have done research. Please accept my research work this will enable for the convinient study of combination and permutation.

https://sites.google.com/site/junctionslpresentation/ — Preceding unsigned comment added by 27.5.177.192 (talk) 14:50, 20 May 2012 (UTC)

Unfortunately, Wikipedia is not a suitable venue for publication of original research. Please see WP:OR for our policies on this matter. --JBL (talk) 13:48, 8 October 2012 (UTC)

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

I really think the algorithm should be changed to 0-based. Throughout other articles with array-processing algorithms, such as the Fisher–Yates shuffle, implementations are zero based. Zero-based arrays seem to very common in the field of computer science, and the algorithm should reflect that. I have attempted to change it on my own, but I have run into several bugs, especially when the length of the array given is 2. I think everyone would appreciate it if the algorithm was modified. Jessemv (talk) 05:37, 20 November 2009 (UTC)

I was able to convert this algorithm to zero-based as follows: Have k run from 1 to n! inclusive. Then change the swap index calculation to s[k mod (j+1)], and have j run from 1 to (length(s)-1). The other swap index remains s[j] and the k update formula remains k/j (integer division with decimal truncation). Note you don't get the same permutations for the same values of k, nor is the order of permutations the same between these two versions. Let me know if you find an error or have a better zero-based index version. I don't have any bugs for s lengths of one or two with either version though. When I initially implemented this algorithm in C I made the mistake of not giving the algorithm the original s string for each value of k, so watch out for that. If you need an iterative permutation algorithm that gives the output in lexicographic order you can find one in the text Discrete Mathematics By Richard Johnsonbaugh. He also has source code posted here: http://condor.depaul.edu/~rjohnson/source/perm.c Qatux (talk) 18:45, 20 November 2009 (UTC)

I have implemented your code in Java, and found that it works perfectly if you create and pass the array to the algorithm for each value of k. Nice job. I think this should be listed in the article. My algorithm is more efficient in the case where a program has to find all rearrangements of an array, and it relies on the previous permutations, since the algorithm modifies the in-memory array and does not create a new array and then modify it. Thus, you make an array, and then run through all the values of k, passing the array to the algorithm each time. I will get to the lexicographical order algorithm in a while, but I posted my algorithm in the web at http://www.jessevictors.com/files/code.txt Jessemv (talk) 02:40, 23 November 2009 (UTC)

I tried using the algorithm to generate lexicographic permutations as described in this section. I was confused by the statement Since k + 1 is such an index, l is well defined and satisfies k < l in step 2 of the algorithm. It is true that l = k + 1 on the first permutation, but after the first permutation l can be equivalent to k + 2 or k + 3 ... etc. I thought having such a statement that is not applicable to all cases of permutation in the description of the actual algorithm was unnecessary and confusing. I added a walk through example of the algorithm in action as a contribution.--James Lingford (talk) 09:46, 7 August 2013 (UTC)

sequence versus ordered arrangement

I recently converted the descriptor "sequence" for permutations to "ordered arrangement". This was reverted and I just re-reverted. My reasons for doing this are twofold. First, as I mentioned in my original edit, the term "sequence" is not quite correct, the proper term would be "sequence without repetition". If one were required to use this entire phrase, the appeal of this descriptor would soon vanish. One could say, early in the article, that for this article "sequence shall mean sequence without repetition", but this is a long article and readers do not always start at the top and read everything, so may fail to see that disclaimer. A further problem arises (and this is problem was never addressed) when permutations are applied to actual sequences and the term "sequence" had two meanings within the same sentence. Secondly, the term "sequence" is never used, outside of WP and its derivatives, except by a small cadre of computer scientists. The vastly predominant term is "ordered arrangement" and this can be found in high school texts, combinatorics texts and other elementary mathematics texts. By WP:Commonname this should be the term used in the article. We may or may not like the choice, but that is not our call to make. Note that in the later sections that deal exclusively with the computer science aspects of the topic, I left the sequence terminology in place with only a brief transitional comment about it. Bill Cherowitzo (talk) 15:45, 9 June 2014 (UTC)

Number of permutations with repetitions

Article doesn't contain formula for case of permutations with repeated elements. http://www.vitutor.com/statistics/combinatorics/permutations_repetition.html

In some sources it denoted as variations with repetitions but Wikipedia seems to equate terms "variation" and "permutation". http://www.emathematics.net/combinavrepeticion.php LiberalDemocrat (talk) 12:22, 28 December 2014 (UTC)

Most likely due to the fact that these are not permutations. The article does contain a section on permutations of multisets, which are also not permutations, but what you are asking for has no restriction on the number of repeats of an element. These are properly called n-tuples, and perhaps a brief mention should be made of them, with an appropriate link, when other non-permutations are talked about. The "variations with repetition" terminology is not widespread in English and usually appears in translation from non-English sources or authors. The disambiguation page Variation does separate the two cases (with and without repetition) sending one to permutation and the other to tuple. Bill Cherowitzo (talk) 17:44, 28 December 2014 (UTC)

I've edited the article with respect to the above remarks. Bill Cherowitzo (talk) 20:55, 28 December 2014 (UTC)

Honestly I'm a bit confused. How exactly n-tuples contradict permutations? Permutation by definition results in ordered lists of n elements which is ... n-tuples. Although this doesn't look like reputable source(I only tried google search) formula for combinations with repetitions match Wikipedia formula and I suspect the same is true for permutations with repetitions. http://www.mathsisfun.com/combinatorics/combinations-permutations.html

LiberalDemocrat (talk) 10:53, 29 December 2014 (UTC)

The definition of permutation, as given in this article and as found in the reliable sources, is that it is a bijection of a set onto itself. In particular, this means that there are no repeated elements (the one-to-one property of a bijection). n-tuples allow repeated elements, so only those n-tuples which do not have repeated elements can represent permutations. This is modern terminology. Unfortunately, some elementary treatments of this material (such as the MathIsFun page) persist in using the nineteenth century versions of the definition of a permutation which is equivalent to just saying an ordered arrangement of some of the elements of a set with repeats allowed. This is no longer acceptable in mathematical circles. Bill Cherowitzo (talk) 16:54, 29 December 2014 (UTC)

I think I've found the place of confusion. It's permutation article by Encyclopedia of Mathematics. Here it is understood as "an arrangement of elements without repetition". However this definition is taken from V.N. Sachkov "Combinatorial methods in discrete mathematics" where unlike in English sources notion of "permutation" and "variation" differs(permutation doesn't allow repetition, variation allows). The second English source J. Riordan "An introduction to combinational analysis" contradicts this. In page 1 after definition of permutation as ordered arrangement of n elements author writes:

"A few points about these should be noted. First, in either case, nothing is said of the features of the n things; they may be all of one kind, some of one kind, others of others kind, or all unlike." And then he lists all these cases including case of permutation with repetetion witn n^r formula on page 4.

Arturo Magidin, associate professor of Department of Mathematics in University of Louisiana, writes:

"In "permutations", the order matters. In "combinations", the order does not matter... Permutations with repetitions allowed: If you have n objects, and you want to count how many permutations of length m there are: there are n possibilities for the first term, n for the second term, n for the third term, etc. So the total number is n^m." http://math.stackexchange.com/questions/128048/what-is-the-correct-terminology-for-permutation-combination-formulae-that-allo LiberalDemocrat (talk) 11:49, 4 January 2015 (UTC)

The first overview sentence does not make sense

Since participating at some length in this discussion four years ago, I've realized there is an even more fundamental problem here. The very first sentence of the article is as follows:

In mathematics, the notion of permutation relates to the act of rearranging, or permuting, all the members of a set into some sequence or order (...).

For a reader who knows the definition of set, this should fail to make sense. For a set has no initial order. A set is intrinsically unordered. How then can it be rearranged? It cannot be rearranged or, in common parlance, "permuted."

If for example you try to rearrange the set {pig, horse, duck} into, say, {horse, duck, pig}, you have merely shown an equivalent representation. Given that the notation {...} denotes a set, I insist without qualification that {horse, duck, pig} = {pig, horse,duck}.

If I must arrange the elements of a set, I am evidently forced to replace the set with an ordered tuple incorporating the same elements as the set. Thus the set {pig, horse, duck} must be replaced with a 3-tuple such as (pig, horse, duck), or (horse, duck, pig) before it can undergo a reordering operation. And as one more stroke of personal confusion, I find that I do not see how to specify a mapping between an arbitrary finite set and a tuple with the same number of elements as the set. For any specific set I can readily indicate such a mapping, but without having the elements of the set specified in advance, I am at a loss. Dratman (talk) 00:26, 22 June 2015 (UTC)

Your point is well taken. I believe that I have corrected the problem. Bill Cherowitzo (talk) 04:49, 22 June 2015 (UTC)

Thank you Wcherowi. I find your change very clarifying. It seems to solve the problem I raised, at least at this point in the article.— Preceding unsigned comment added by Dratman (talk • contribs)

Please sign your posts.

Also, I disagree strenuously with the premise of your complaint: the fact that something is a set does not mean that it lacks an order or arrangement, as you suggest. Rather, to call something a set merely does not guarantee that it has an order, and so it is perfectly acceptable to say "rearrange a set" where the word "rearrange" itself conveys the information that there is an existing arrangement. Wikipedia math articles are not exercises in formal axiomatic logic, particularly not lead sentences of articles on high school mathematics topics.

JBL, those are good and interesting points, which I want to think about before replying at length. For now I will say that my hope is that this article will achieve accuracy, not rigor or formality. My reason for objecting to the unqualified use of the term "set" is not perfectionism. Dratman (talk) 21:05, 22 June 2015 (UTC)

Permutations are not a "high school mathematics topic." Please read the table of contents of the article. Permutations are at the foundation of group theory, which plays a part in almost every branch of mathematics. Dratman (talk) 12:13, 23 June 2015 (UTC)

All that said, I don't have any objection to Bill Cherowitzo's edit. --JBL (talk) 14:44, 22 June 2015 (UTC)

Congrats

Very good article. Very helpful. I commend you. — Preceding unsigned comment added by W1k13rh3nry (talk • contribs) 23:58, 9 March 2007 (UTC)

THat?

$f(n,k)=\sum _{k_{n-1}}^{k}f(n-1,k_{n-1})$

— Preceding unsigned comment added by 201.255.142.74 (talk) 22:23, 15 July 2009 (UTC)

So, how I can calculate the number (or position) of a given permutation?

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 lexicographical-ordered 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 help-desk. 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

The section on other uses of the word 'permutation' explains k-permutation 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

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)

Proposed Merge

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₄ 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 top-level 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 one-line 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

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 n-permutation 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 left-to-right 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 one-line/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)

This is not a problem: "and so on" means you stop when you can't go on; if a1=n you stop with a single cycle. What's the problem?--JBL (talk) 13:38, 4 April 2015 (UTC)

Paren notation in intro is misleading

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 two-line mapping notation and the one-line 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 two-line 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 one-line 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 two-line 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)

Major Problem with Notation

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 double-line notation (or, equivalently, the single-line 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 above-notated 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 double-line 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 one-line, two-line 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/2008-07/puzzles/m12.html

and then at http://www.scientificamerican.com/article.cfm?id=the-cycle-notation-and-m12 . 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 two-line 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).

If only that were the case -- if no confusion existed -- we could close this issue immediately, and I would merely be wrong. I would not mind! Dratman (talk) 19:02, 26 August 2011 (UTC)

Also, in case the two-line 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 two-line form with "1 2 ... n" as first line (as is most common, though not obligatory for a two-line 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 left-to-right 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 right-to-left composition convention to get this issue out of the way.

I "prefer" the right-to-left convention when I write f(g(x)). That notation is unambiguous! I prefer the left-to-right convention when I write A ∘ B, as in group theory (where it is disputed) or in the "syntactic sugar" first layer parser of any non-Lisp-type computer language (where it is not disputed). I am well aware that many people are strongly in favor of using the right-to-left 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 "built-up" from [n] (such as [n] itself, or the set [n]² of ordered pairs, or the set of k-combinations 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]², looks like

$\sigma .(x,y)=(\sigma (x),\sigma (y))\,$.

But in practice the other natural class of actions is more important: the actions on sets of the form Xⁿ, i.e., of n-tuples taken from some set X, or on invariant subsets thereof. The action is by permuting the positions, so that each component of the n-tuple becomes a component of the result, at a position determined by the permutation. If one wants a left-action 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

$\sigma .(x_{1},x_{2},\ldots ,x_{n})=(x_{\sigma ^{-1}(1)},x_{\sigma ^{-1}(2)},\ldots ,x_{\sigma ^{-1}(n)})$,

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). I am personally comfortable with this way of interpreting permuting of n-tuples, but one could prefer (maybe in view of the somewhat awkward symbolic notation) to define a right-action 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)

$(x_{1},x_{2},\ldots ,x_{n}).\sigma =(x_{\sigma (1)},x_{\sigma (2)},\ldots ,x_{\sigma (n)})\,$;

this is I guess what is called the "Address Method" above (which reads the two-line 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):

     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 non-atomic 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 one-line form", namely the set of n-tuples with n distinct components taken from [n] , then one finds oneself on the intersection of the two classes: P is both built-up from [n], and an invariant (under permuting) subset of [n]ⁿ. So this is the most confusing case possible, where several "natural" actions of permutations compete (it would have been different if n-tuples with n distinct components taken from any other n-element 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 one-line 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 right-action (3) send (x₁,...,x_n) to (x_σ(1),...,x_σ(n)) (the "Address Method"). Denoting the fact that p is the one-line 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(π∘σ⁻¹), 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 left-action (1) or right-action (3) were used. Moral: it is a bad idea to think of permutations as defined by the way they transform one-line 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 two-line notation uses the Value Method, since the permutation used throughout the example above could be written not only as

     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 $g\in G,s\in S,$ the vertices corresponding to the elements $g$ and $gs$ are joined by a directed edge of colour $c_{s}$" 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 two-line 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 n-tuple. 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 n-tuple , (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 two-line notation for σ, but of that of its inverse. So this convention uses an alternative "one-line notation" for σ that is not related to the two-line notation for σ by taking the second line. One can get this alternative notation by reordeing the two-line 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 two-line 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 real-world ambiguity in the use of the two-line 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 3-cycle and (2) is a 1-cycle. 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 2-line to cycle notation, it was not obvious that (by definition) an application of a k-cycle 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 k-cycles always have sign of (-1)^(k-1)? — 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)

Recent edits

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 proof-reading. 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 true-ish 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)

Thanks for your critique! Personally I don't see how the permutation concept can be described without referencing bijective functions, but I'm open to ideas. Also, it is not my article so you can do the changes you see fit. ImTheIP (talk) 13:34, 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

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 $n=4$, and of six additional algorithms described in the literature. Ordering of all permutations of length $n=4$ generated by different algorithms. The permutations are color-coded, where 1=red, 2=yellow, 3=green, 4=blue. 1: Lexicographic ordering; 2: Steinhaus-Johnson-Trotter algorithm; 3: Heap's algorithm; 4: Ehrlich's star-transposition algorithm (see ): in each step, the first entry of the permutation is exchanged with a later entry; 5: Zaks' prefix reversal algorithm: in each step, a prefix of the current permutation is reversed to obtain the next permutation; 6: Sawada-Williams' algorithm: each permutation differs from the previous one either by a cyclic left-shift by one position, or an exchange of the first two entries; 7: Corbett's algorithm: each permutation differs from the previous one by a cyclic left-shift of some prefix by one position; 8: Single-track ordering: each column is a cyclic shift of the other columns; 9: Single-track Gray code: 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: Permutation generation algorithms on the Combinatorial Object Server References

Torsten Mütze (talk) 19:07, 29 May 2019 (UTC)

Per my concerns at the bottom of Talk:Gray code (Special:PermanentLink/899583820#tbf-objection-2019), 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 "Steinhaus-Johnson-Trotter" to "Steinhaus–Johnson–Trotter" (with an en-dash 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:

Steinhaus-Johnson-Trotter

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)

Permutations with repetitions

In permutations with repetitions it has to be stated at least Tuple#n-tuples_of_m-sets as the word tuples alone is only the plural of tuple (ordered set or list) so ordered sets or lists and permutations without repetitions refers to a scalar number

It has to be clarified Tuples at least as Tuple#n-tuples_of_m-sets as Tuples alone is only the plural of Tuple and Permutations without repetition is a scalar number. Orendona (talk) 20:42, 1 November 2020 (UTC)

I see from your edits that you want to refer to the cardinality of the set of permutations with (or without) repetition. Is this the scalar number you mention above? This would be a very tortured way to approach the topic and demonstrates some deep confusion. --Bill Cherowitzo (talk) 21:56, 1 November 2020 (UTC)

That is the use, they are not tuples, they are a special kind of tuples: All the possible tuples that can be made with repeated or not members of a second set. And they are not permutations. Some of the tuples are permutations of others. Orendona (talk) 13:16, 3 November 2020 (UTC)