Sorry for the long text; this is a nebulous question that has always been in the back of my mind, and I've had trouble putting into a short form.
"Natural" Definition
If someone on the street hears the word "permutation," I think they will naturally assume that a permutation:
- Involves rearranging objects
- The order in which the objects are written, before and after the permutation is performed, is of crucial importantce (it's really the essence of the permutation)
I would naturally expect a permutation to be an instruction, or an action. For example, I would expect a permutation to look something like
$$\sigma = \text{interchange the first two entries.}$$
Then, if we apply $\sigma$ to $(A, B, C)$ we get $(B, C, A);$ if we apply it to $(4, 6, 9)$ we get $(6, 4, 9).$ To me this is a very satisfying (informal) definition of a permutation, because it captures exactly what many people (or at least me) would think a permutation "should be."
Another way to define "permutation" (to me, less satisfactory than the previous, but still more satisfactory than the official definition) could be to just say that "the 3-tuple $(B, A, C)$ is a permutation of $(A, B, C).$" (In fact, I think this is the definition used in elementary Statistics books.)
Percieved Weaknesses of the Official Definition
- It makes little sense to "permute" your set of objects. If you have a set of objects $\{4, 6, 8 \},$ and while you are not in the room someone applies a permutation to your set, you will never know; the output of your permutation is still $\{4, 6, 8 \}.$ Even if they only apply the permutation to a subset, you only might be able to tell.
- Permutations seem to have nothing to do with the order that your objects are in, either before or after doing the permutation. This, like I mentioned above, seems to violate the whole point of a permutation
I call these weaknesses because they seem to violate the "person on the street" understanding of a permutation, and I know that generally mathematicians try really hard to not distort the meaning of common English words too much.
My Question
Is there really such a big disconnect between the "Natural" and Official definitions of permutations? Even if there is not, and there is a way to tediously link the natural definition with the official definition (which I'm sure there is), why does the Official definition deserve to be called a permutation more than the natural one? Is there a name for the Natural definition?
Thanks.
Best Answer
"Rearranging" objects is a procedure that is not inherently related with order. The relation with order is more due to how we usually list things than the essence of permutation itself.
For instance, I have three pockets in my pants, on which I put my cell phone, keys and wallet, one on each pocket. I sometimes rearrange them; driving with the wallet on the right pocket of some pants is somewhat unpleasant. I think it is natural to call this process of changing from one alocation to another a permutation, and I think people would generally agree. This is precisely a function $f: Pockets \to Pockets$ which tells me that whatever was in pocket $x$ is now in pocket $f(x)$. Note that I never made any ordering of the pockets.
As I mentioned in the introduction, I think you are assuming that an ordering must be given due to the same reason why I said "cell phone, keys and wallet": because this is how we are used to communicate things, by listing them.