1132: For Index Set, Sum by n-th Power of Index Set Is Sum by Quotient Set of n-th Power Index Set of Sum by Quotient Set of n-Symmetric Group

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

description/proof of that for index set, sum by $n$-th power of index set is sum by quotient set of $n$-th power index set of sum by quotient set of $n$-symmetric group

---

Topics

About: set

---

The table of contents of this article

• Starting Context
• Target Context
• Orientation
• Main Body
• 1: Structured Description
• 2: Note
• 3: Proof

---

Starting Context

• The reader knows a definition of product set.
• The reader knows a definition of quotient set.
• The reader knows a definition of $n$-symmetric group.
• The reader knows a definition of representatives set of quotient set.

---

Target Context

• The reader will have a description and a proof of the proposition that for any index set, the sum by the $n$-th power of the index set is the sum by the canonical quotient set of the $n$-th power index set of the sum by the canonical quotient set of the $n$-symmetric group for each element of the quotient set of the $n$-th power index set.

---

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:
$J$: $\in \{\text{ the index sets }\}$
$n$: $\in \mathbb{N}\setminus \{0\}$
$J^n$: $=\text{ the product set }$
$S_n$: $=\text{ the }n\text{ -symmetric group }$
$\sim$: $\in \{\text{ the equivalence relations on }{J}^n\}$, such that $\mathrm{\forall }j=(j_1,...,j_n),j^{\prime }=(j_1^{\prime },...,j_n^{\prime })\in J^n(j\sim j^{\prime }⟺\mathrm{\exists }\sigma \in S_n((j_{{\sigma }_1},...,j_{{\sigma }_n})=(j_1^{\prime },...,j_n^{\prime })))$
$J^n/\sim$: $=\text{ the quotient set }$
$\overline{J^n/\sim -f}$: $=\text{ the representatives set of }{J}^n/\sim$, where $f:J^n/\sim \to J^n$, the representatives map, is chosen arbitrarily
$\{{\sim }_j|j\in \overline{J^n/\sim -f}\}$: ${\sim }_j\in \{\text{ the equivalent relations of }{S}_n\}$, such that $\mathrm{\forall }\sigma ,{\sigma }^{\prime }\in S_n(\sigma {\sim }_j{\sigma }^{\prime }⟺(j_{{\sigma }_1},...,j_{{\sigma }_n})=(j_{{\sigma }_1^{\prime }},...,j_{{\sigma }_n^{\prime }}))$
$\{S_n/{\sim }_j|j\in \overline{J^n/\sim -f}\}\}$: $S_n/{\sim }_j\in \{\text{ the quotient sets }\}$
//

Statements:
$\sum _{j\in J^n}=\sum _{j\in \overline{J^n/\sim -f}}\sum _{\sigma \in S_n/{\sim }_j}=\sum _{[j]\in J^n/\sim }\sum _{\sigma \in S_n/{\sim }_{f([j])}}$
//

---

2: Note

What is being done is really just a common sense: $J^n$ is divided into the subsets each of which is the permutations of a combination ('combination' means any element of $J^n/\sim$).

For example, when $j=\{1,2\}$ and $n=3$, $J^n=\{(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)\}$, $J^n/\sim =\{\{(1,1,1)\},\{(1,1,2),(1,2,1),(2,1,1)\},\{(1,2,2),(2,1,2),(2,2,1)\},\{(2,2,2)\}\}$, $\overline{J^n/\sim -f}=\{(1,1,1),(1,1,2),(1,2,2),(2,2,2)\}$ as a choice, and $\sum _{j\in J^n}$ is accomplished by taking each element of $\overline{J^n/\sim -f}$, summing by all the distinct permutations of the element, and summing up the sums.

The point of this proposition is offering an exact notation of the intuitively natural procedure.

${\sim }_j$ depends on the choice of $f$ (the choice of the representative for each class).

For example, when $j=\{1,2\}$ and $n=3$, if $(1,1,2)$ is a representative, $(1,2,3)\mapsto (1,2,3)\in S_n$ and $(1,2,3)\mapsto (2,1,3)\in S_n$ will be equivalent, but if $(1,2,1)$ is a representative, $(1,2,3)\mapsto (1,2,3)\in S_n$ and $(1,2,3)\mapsto (2,1,3)\in S_n$ will not be equivalent (instead, $(1,2,3)\mapsto (1,2,3)\in S_n$ and $(1,2,3)\mapsto (3,2,1)\in S_n$ will be equivalent).

Nevertheless, $\sum _{\sigma \in S_n/{\sim }_j}$ covers the same set of permutations for the class $[j]$.

When $J$ is linearly-ordered, a natural choice for the representative of $[(j_1,...,j_n)]$ is $j_1\le ...\le j_n$ (or $j_n\le ...\le j_1$).

The motivation for this proposition is that often, the summand of $\sum _{j\in J^n}$ depends (totally or partially) on the combination $[j]$, and then, thinking $\sum _{j\in J^n}$ as $\sum _{j\in \overline{J^n/\sim -f}}\sum _{\sigma \in S_n/{\sim }_j}$ can become handy: for example, when the summand depends totally on $[j]$, $\sum _{j\in \overline{J^n/\sim -f}}\sum _{\sigma \in S_n/{\sim }_j}=\sum _{j\in \overline{J^n/\sim -f}}|S_n/{\sim }_j|$ where $|S_n/{\sim }_j|$ denotes the cardinality of $S_n/{\sim }_j$.

---

3: Proof

Whole Strategy: Step 1: see that $\sim$ is indeed an equivalence relation; Step 2: see that ${\sim }_j$ is indeed an equivalence relation; Step 3: see that $\sum _{j\in J^n}=\sum _{j\in \overline{J^n/\sim -f}}\sum _{\sigma \in S_n/{\sim }_j}=\sum _{[j]\in J^n/\sim }\sum _{\sigma \in S_n/{\sim }_{f([j])}}$.

Step 1:

Let us see that $\sim$ is indeed an equivalence relation.

For each $j=(j_1,...,j_n)\in J^n$, $j\sim j$, because there is $\sigma =id\in S_n$ such that $(j_{{\sigma }_1},...,j_{{\sigma }_n})=(j_1,...,j_n)$.

For each $j=(j_1,...,j_n),j^{\prime }=(j_1^{\prime },...,j_n^{\prime })\in J^n$ such that $j\sim j^{\prime }$, $j^{\prime }\sim j$, because while there is a $\sigma \in S_n$ such that $(j_{{\sigma }_1},...,j_{{\sigma }_n})=(j_1^{\prime },...,j_n^{\prime })$, there is ${\sigma }^{-1}\in S_n$ such that $(j_{{{\sigma }^{-1}}_1}^{\prime },...,j_{{{\sigma }^{-1}}_n}^{\prime })=(j_1,...,j_n)$, which is true because while there is a ${\sigma }_l=\sigma (l)=1$, $l={\sigma }^{-1}(1)$, and $j_1=j_{{\sigma }_l}=j_l^{\prime }=j_{{\sigma }^{-1}(1)}^{\prime }$.

For each $j=(j_1,...,j_n),j^{\prime }=(j_1^{\prime },...,j_n^{\prime }),j^{″}=(j_1^{″},...,j_n^{″})\in J^n$ such that $j\sim j^{\prime }$ and $j^{\prime }\sim j^{″}$, $j\sim j^{″}$, because while there are a $\sigma \in S_n$ such that $(j_{{\sigma }_1},...,j_{{\sigma }_n})=(j_1^{\prime },...,j_n^{\prime })$ and a ${\sigma }^{\prime }\in S_n$ such that $(j_{{\sigma }_1^{\prime }}^{\prime },...,j_{{\sigma }_n^{\prime }}^{\prime })=(j_1^{″},...,j_n^{″})$, there is $\sigma \circ {\sigma }^{\prime }\in S_n$ such that $(j_{(\sigma \circ {\sigma }^{\prime }{)}_1},...,j_{(\sigma \circ {\sigma }^{\prime }{)}_n})=(j_1^{″},...,j_n^{″})$, which is true because while $j_1^{″}=j_{{\sigma }_1^{\prime }}^{\prime }$, ${\sigma }_1^{\prime }=l$ for an $l$ and $j_{{\sigma }_1^{\prime }}^{\prime }=j_l^{\prime }=j_{{\sigma }_l}=j_{\sigma (l)}=j_{\sigma ({\sigma }_1^{\prime })}=j_{\sigma ({\sigma }^{\prime }(1))}=j_{\sigma \circ {\sigma }^{\prime }(1)}=j_{\sigma \circ {\sigma }_1^{\prime }}$, so, $j_1^{″}=j_{\sigma \circ {\sigma }_1^{\prime }}$.

Step 2:

Let us see that ${\sim }_j$ is indeed an equivalence relation.

For each $\sigma \in S_n$, $\sigma {\sim }_j\sigma$, because $(j_{{\sigma }_1},...,j_{{\sigma }_n})=(j_{{\sigma }_1},...,j_{{\sigma }_n})$.

For each $\sigma ,{\sigma }^{\prime }\in S_n$ such that $\sigma {\sim }_j{\sigma }^{\prime }$, ${\sigma }^{\prime }{\sim }_j\sigma$, because while $(j_{{\sigma }_1},...,j_{{\sigma }_n})=(j_{{\sigma }_1^{\prime }},...,j_{{\sigma }_n^{\prime }})$, $(j_{{\sigma }_1^{\prime }},...,j_{{\sigma }_n^{\prime }})=(j_{{\sigma }_1},...,j_{{\sigma }_n})$.

For each $\sigma ,{\sigma }^{\prime },{\sigma }^{″}\in S_n$ such that $\sigma {\sim }_j{\sigma }^{\prime }$ and ${\sigma }^{\prime }{\sim }_j{\sigma }^{″}$, $\sigma {\sim }_j{\sigma }^{″}$, because while $(j_{{\sigma }_1},...,j_{{\sigma }_n})=(j_{{\sigma }_1^{\prime }},...,j_{{\sigma }_n^{\prime }})$ and $(j_{{\sigma }_1^{\prime }},...,j_{{\sigma }_n^{\prime }})=(j_{{\sigma }_1^{″}},...,j_{{\sigma }_n^{″}})$, $(j_{{\sigma }_1},...,j_{{\sigma }_n})=(j_{{\sigma }_1^{\prime }},...,j_{{\sigma }_n^{\prime }})=(j_{{\sigma }_1^{″}},...,j_{{\sigma }_n^{″}})$.

Step 3:

Let us see that $\sum _{j\in J^n}=\sum _{j\in \overline{J^n/\sim -f}}\sum _{\sigma \in S_n/{\sim }_j}$.

There is no duplication in $\sum _{j\in J^n}$, obviously.

There is no duplication in $\sum _{j\in \overline{J^n/\sim -f}}\sum _{\sigma \in S_n/{\sim }_j}$, because while there is no duplication in $\sum _{j\in \overline{J^n/\sim -f}}$, there is no duplication in the corresponding $\{[j]\}$, and for each $[j]$, there is no duplication in $\sum _{\sigma \in S_n/{\sim }_j}$ because $\sigma \in S_n/{\sim }_j$ is determined exactly for that effect, and there is no duplication between $[j]$ and $[j^{\prime }]$ because $[j]$ and $[j^{\prime }]$ represent some different combinations and permutating any combination does not change the combination.

Each element of $\sum _{j\in J^n}$ exists in $\sum _{j\in \overline{J^n/\sim -f}}\sum _{\sigma \in S_n/{\sim }_j}$, because the element is of a combination whose representative is in $\sum _{j\in \overline{J^n/\sim -f}}$, and the element is a permutation of the combination, which is in the corresponding $\sum _{\sigma \in S_n/{\sim }_j}$.

Each element of $\sum _{j\in \overline{J^n/\sim -f}}\sum _{\sigma \in S_n/{\sim }_j}$ obviously exists in $\sum _{j\in J^n}$.

So, $\sum _{j\in J^n}=\sum _{j\in \overline{J^n/\sim -f}}\sum _{\sigma \in S_n/{\sim }_j}$.

$\sum _{j\in \overline{J^n/\sim -f}}\sum _{\sigma \in S_n/{\sim }_j}=\sum _{[j]\in J^n/\sim }\sum _{\sigma \in S_n/{\sim }_{f([j])}}$ is just an obvious reformulation: the latter is taking the class, $[j]$, instead of its representative, $j$, but anyway, $\sum _{\sigma \in S_n/{\sim }_j}=\sum _{\sigma \in S_n/{\sim }_{f([j])}}$ because $j=f([j])$.

---

References

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