description/proof of for sequence of finite elements, set of permutations has same number of even permutations and odd permutations
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: Proof
- 4: Note
Starting Context
- The reader knows a definition of set.
- The reader knows a definition of sequence.
- The reader knows a definition of permutation of sequence.
Target Context
- The reader will have a description and a proof of the proposition that for any sequence of any finite elements, the set of the permutations has the same number of the even permutations and the odd permutations.
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:
\(n\): \(\in \mathbb{N}\), \(2 \le n \lt \infty\)
\(S\): \(\subseteq \mathbb{N}\), \(= \{j_1, ..., j_n\}\)
\(f\): \(\in \{\text{ the sequences over } S\}\), \(= (e_1, ..., e_n)\)
\(P_+\): \(= \{\text{ the even permutations of } f\}\)
\(P_-\): \(= \{\text{ the odd permutations of } f\}\)
//
Statements:
\(\vert P_+ \vert = \vert P_- \vert = (1 / 2) n!\).
//
2: Natural Language Description
For any finite subset, \(S \subseteq \mathbb{N}\), \(= \{j_1, ..., j_n\}\), where \(2 \le n \lt \infty\), and any sequence, \(f = (e_1, ..., e_n)\) such that \(dom f = S\), the set of the even permutations of \(f\), \(P_+\), and the set of the odd permutations of \(f\), \(P_-\), have the same cardinality, which is \(\vert P_+\vert = \vert P_- \vert = (1 / 2) n!\).
3: Proof
Whole Strategy: prove it inductive with respect to \(n\); Step 1: suppose that \(n = 2\), and see that \(\vert P_+ \vert = \vert P_- \vert = (1 / 2) 2!\); Step 2: suppose that for an \(n\), \(\vert P_+ \vert = \vert P_- \vert = (1 / 2) n!\), and see that for \(n + 1\), \(\vert P_+ \vert = \vert P_- \vert = (1 / 2) (n + 1)!\).
Let us prove it inductively with respect to \(n\).
Step 1:
Let us suppose \(n = 2\).
\(P_+ = \{(j_1, j_2)\}\); \(P_- = \{(j_2, j_1)\}\). So, \(\vert P_+ \vert = \vert P_- \vert = (1 / 2) 2!\).
Step 2:
Let us suppose that \(\vert P_+ \vert = \vert P_- \vert = (1 / 2) n! := m\) for an \(n\) and \(f = (e_1, ..., e_{n + 1})\).
The permutations can be exclusively divided in these cases: 1) \(j_{n + 1}\) is mapped from \(j_{n + 1}\); 2) \(j_{n + 1}\) is mapped from \(j_n\); ...; n + 1) \(j_{n + 1}\) is mapped from \(j_1\).
For the case 1), the permutations are the permutations of \((j_1, ..., j_{n + 1})\) with \(j_{n + 1}\) fixed.
While \((j_1, ..., j_{n + 1})\) has the sign \((-1)^0\), the permutations are the permutations of \((j_1, ..., j_n)\), which has the \(m\) even permutations and the \(m\) odd permutations, by the induction hypothesis.
So, the case 1) has the \(m\) even permutations and the \(m\) odd permutations
For the case 2), the permutations are the permutations of \((j_1, ..., j_{n - 1}, j_{n + 1}, j_n)\) with \(j_{n + 1}\) fixed.
While \((j_1, ..., j_{n - 1}, j_{n + 1}, j_n)\) has the sign \((-1)^1\) (because \(j_n\) and \(j_{n + 1}\) have been switched), the permutations are the permutations of \((j_1, ..., j_n)\), which has the \(m\) even permutations and the \(m\) odd permutations, by the induction hypothesis.
So, the case 2) has the \(m\) even permutations and the \(m\) odd permutations
...
For the case n + 1), the permutations are the permutations of \((j_{n + 1}, j_1, ..., j_n)\) with \(j_{n + 1}\) fixed.
While \((j_{n + 1}, j_1, ..., j_n)\) has the sign \((-1)^n\) (because 1st, \(j_n\) and \(j_{n + 1}\) have been switched, then, \(j_{n - 1}\) and \(j_{n + 1}\) are switch, ..., and then \(j_1\) and \(j_{n + 1}\) are switch), the permutations are the permutations of \((j_1, ..., j_n)\), which has the \(m\) even permutations and the \(m\) odd permutations, by the induction hypothesis.
So, the case n + 1) has the \(m\) even permutations and the \(m\) odd permutations
So, \(f\) has the \(m + ... + m = (n + 1) m = (1 / 2) (n + 1)!\) even permutations and the \(m + ... + m = (n + 1) m = (1 / 2) (n + 1)!\) odd permutations.
So, by the induction principle, \(\vert P_+ \vert = \vert P_- \vert = (1 / 2) n!\) for each \(n\).
4: Note
The existence of any duplication among the elements of the sequence does not matter, because any permutation is about a self bijection over the domain of the sequence (see Note of the definition of permutation of sequence).
