814: For Sequence of Finite Elements, Set of Permutations Has Same Number of Even Permutations and Odd Permutations

<The previous article in this series | The table of contents of this series | The next article in this series>

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<\mathrm{\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:
$|P_{+}|=|P_{-}|=(1/2)n!$.
//

---

2: Natural Language Description

For any finite subset, $S\subseteq \mathbb{N}$, $=\{j_1,...,j_n\}$, where $2\le n<\mathrm{\infty }$, and any sequence, $f=(e_1,...,e_n)$ such that $domf=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 $|P_{+}|=|P_{-}|=(1/2)n!$.

---

3: Proof

Whole Strategy: prove it inductive with respect to $n$; Step 1: suppose that $n=2$, and see that $|P_{+}|=|P_{-}|=(1/2)2!$; Step 2: suppose that for an $n$, $|P_{+}|=|P_{-}|=(1/2)n!$, and see that for $n+1$, $|P_{+}|=|P_{-}|=(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, $|P_{+}|=|P_{-}|=(1/2)2!$.

Step 2:

Let us suppose that $|P_{+}|=|P_{-}|=(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, $|P_{+}|=|P_{-}|=(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).

---

References

<The previous article in this series | The table of contents of this series | The next article in this series>