definition of permutation of sequence
Topics
About: set
The table of contents of this article
- Starting Context
- Target Context
- Orientation
- Main Body
- 1: Structured Description
- 2: Natural Language Description
- 3: Note
Starting Context
- The reader knows a definition of sequence.
Target Context
- The reader will have a definition of permutation of sequence.
Orientation
There is a list of definitions discussed so far in this site.
There is a list of propositions discussed so far in this site.
Main Body
1: Structured Description
Here is the rules of Structured Description.
Entities:
\( \mathbb{N}\):
\( S\): \(\subseteq \mathbb{N}\)
\( f\): \(\in \{\text{ the sequences from } S\}\)
\(*\sigma\): \(: S \to S\),
\( f \circ \sigma\): the result of \(\sigma\) on \(f\), a sequence from \(S\)
\( \sigma (f)\): \(= f \circ \sigma\)
\( \sigma (f)_j\): \(= (f \circ \sigma) (l_j)\) where \(l_j \in S\) is the \(j\)-the element of \(S\) ordered increasingly
//
Conditions:
\(\sigma \in \{\text{ the bijections }\}\).
//
2: Natural Language Description
For the natural numbers set, \(\mathbb{N}\), any subset, \(S \subseteq \mathbb{N}\), and any sequence, \(f\), such that \(dom f = S\), any bijection, \(\sigma: S \to S\), is a permutation of \(f\), where \(f \circ \sigma\) is the permutation result, a sequence; the notation, \(\sigma (f)\), means \(f \circ \sigma\); the notation, \(\sigma (f)_j\), means \((f \circ \sigma) (l_j)\) where \(l_j \in S\) is the \(j\)-the element of \(S\) ordered increasingly
3: Note
This definition does not call \(f \circ \sigma\) "permutation" although \(f \circ \sigma\) is often meant by "permutation". The reason is as follows.
When \(S = \{1, 2\}\), the sequence is \((3, 3)\), and \(\sigma = id\) and \(\sigma', 1 \mapsto 2; 2 \mapsto 1\), \(f \circ \sigma = f \circ \sigma'\), so, we would not be able to say "There are 2 permutations." if we called \(f \circ \sigma\) "permutation". In fact, \(\sigma \neq \sigma'\), so, there are 2 permutations.
So, by this definition, the existence of any duplication among the elements of the sequence does not matter at all, because the definition is about the self bijection over the domain of the sequence and the domain has no duplication.
For example, when we use an expression like \(\sum_{\sigma} sgn \sigma A^{\sigma (f)_1, ..., \sigma (f)_n}\), the sequence may have some duplicate elements and it may be that \(f \circ \sigma = f \circ \sigma'\) for some \(\sigma \neq \sigma'\), but that expression takes all the permutations regardless of any duplication.
So, we call \(f \circ \sigma\) "permutation result" strictly speaking, but we might sometimes call it "permutation" when no devastating confusion will not arise.
The permutation, \(\sigma\), is defined with respect to a sequence, \(f\), but it is also a permutation of any sequence, \(f': S \to f' (S)\), as far as the domain is \(S\), because \(f' \circ \sigma\) makes sense. So, our expression like "\(\sigma\) is a permutation of \((j_1, ..., j_k)\) and we take \(\sum_{(j_1, ..., j_k)} M_{\sigma ((j_1, ..., j_k))_1, ..., \sigma ((j_1, ..., j_k))_k}\)." may not seem make sense (because \(\sigma\) should be on a specific \((j_1, ..., j_k)\) but not on such various \((j_1, ..., j_k)\) s), but that expression means that the same \(\sigma\) can be indeed operated on such various \((j_1, ..., j_k)\) s.
