Consider $S_n$, I do not understand how to get the elements of $S_n$ especially for $n \geq 4$ Any one to show me how simply I can find them. Thanks a lot
How to find the elements of $S_n$?
-
1Do you just want to list them? $S_n$ has $n!$ elements, so writing them all down could get quickly out of hand. Do you have some result or application in mind? – 2011-12-25
-
0There are several notations for permutations. Probably the first one that most people encounter is the notation where $1,2,\ldots ,n$ are listed in order on the first row, and then the second row indicates the effect of the permutation on $i$ immediately below $i.$ As long as the second row contains each element of $\{1,2, \ldots, n\}$ once and only once, a valid permutation is obtained, and all elements of $S_n$ can be represented in this way. – 2011-12-25
-
0@Dylan: i cant list all elements,but still i find some difficult s in attempting some questions – 2011-12-25
2 Answers
Take an $n\times n$ chessboard; a permutation corresponds to a selection of $n$ different squares such that no two of them share a same row or a same column. Since every row can contain at most one selected square and there are only $n$ rows, every row must in fact contain a selected square, and by a similar argument every column must contain exactly one selected square. Given such a selection, the corresponding permutation can be taken to be the association to any column number $j$ of the unique row index $i$ for which the square $(i,j)$ occurs in the selection.
To generate all such selections, and therefore all permutations, start selecting any one square in the first column ($n$ choices), then for each choice continue selecting a square in the second column in a row that is not yet occupied ($n-1$ choices), then for each such choice continue to the third column, and so forth, until reaching the last column in which there is precisely one square that can be chosen, in the unique row that was not selected before. All in all there are $n\times(n-1)\times\cdots2\times1=n!$ different selections possible, and as many permutations.
One can avoid actually drawing the board, and just record for each column the number of the row in which the square was selected; a selection then is a sequence of $n$ numbers in the range $1,\ldots,n$ such that no number occurs more than once in the selection (and hence every number occurs exactly once). A permutation is often identified with such a sequence of numbers.
$S_n$ is the group of permutations over $n$ elements. What does this mean? It means that it's the set of functions $f: \{ 1, 2, \dots n \} \to \{ 1, 2, \dots n \}$ such that $f$ is bijective.
Hope this helps.