note-math

let mapping $1, \dots, 𝑛 ⇝ 𝑎_{1}, \dots, 𝑎_{𝑛}$

permutation_(tag) The following are equivalent

$1, \dots, 𝑛$ bijection
$1, \dots, 𝑛$ permutation
$𝑛$ order permutation. Quantity $𝑛 (𝑛 - 1) \dots 1 = 𝑛!$ . Usually denoted as $𝑆_{𝑛}$

combination_(tag) The following are equivalent

Select subset $𝐴$ with $| 𝐴 | = 𝑖$ from $Subset {1, \dots, 𝑛}$
Select subsets $𝐴, 𝐵 \in Subset {1, \dots, 𝑛}$ with

partition

{1, \dots, 𝑛} = 𝐴 ⊔ 𝐵

| 𝐴 | = 𝑖, | 𝐵 | = 𝑗

| 𝐴 | + | 𝐵 | = 𝑖 + 𝑗 = 𝑛

Select a permutation $𝑎$ with $𝐴 = {𝑎 (1), \dots, 𝑎 (𝑖)}, 𝐵 = {𝑎 (𝑖 + 1), \dots, 𝑎 (𝑖 + 𝑗)}$ and another permutation $𝑎^{'}$ gives the same partition if

\begin{matrix} {𝑎^{'} (1), \dots, 𝑎^{'} (𝑖)} & = & {𝑎 (1), \dots, 𝑎 (𝑖)} \\ {𝑎^{'} (𝑖 + 1), \dots, 𝑎^{'} (𝑖 + 𝑗)} & = & {𝑎 (𝑖 + 1), \dots, 𝑎 (𝑖 + 𝑗)} \end{matrix}

Define the quotient_(tag) $𝑎 \sim 𝑎^{'}$ of permutations with the same partition as a subset of $𝑆_{𝑛}$ that satisfies the above conditions, i.e., the inverse image of the partitioning possibility $𝐴 ⊔ 𝐵$

<==> $(\exists 𝑏_{𝑖} \in 𝑆_{𝑖}) \land (\exists 𝑏_{𝑗} \in 𝑆_{𝑗}), (𝑏_{𝑖}, 𝑏_{𝑗}) 𝑎 = 𝑎^{'}$

Cardinality calculation

\frac{| 𝑆_{𝑛} |}{| 𝑆_{𝑖} \times 𝑆_{𝑗} |} = \frac{𝑛!}{𝑖! 𝑗!} = \frac{𝑛!}{𝑖! (𝑛 - 𝑖)!}

Denoted as

(\binom{𝑛}{𝑖}) = (\binom{𝑛}{𝑖, 𝑗})

All $𝑖 = 0, \dots, 𝑛$ combinations <==> All $𝑖 = 0, \dots, 𝑛$ select subsets $𝐴$ with $| 𝐴 | = 𝑖$ in $Subset {1, \dots, 𝑛}$

\begin{matrix} \sum_{𝑖 + 𝑗 = 𝑛} (\binom{𝑛}{𝑖, 𝑗}) & or & \sum_{𝑖 = 0 . . 𝑛} (\binom{𝑛}{𝑖}) \\ = & | Subset {1, \dots, 𝑛} | \\ = & 2^{𝑛} \end{matrix}

is the number of repeatable selections of $𝑛$ from $2$

from can be calculated by induction or observed directly, we can get

\frac{𝑛!}{𝑖! 𝑗!} = \frac{(𝑛 - 1)! (𝑖 + 𝑗)}{𝑖! 𝑗!} = (\binom{𝑛 - 1}{𝑖 - 1, 𝑗}) + (\binom{𝑛 - 1}{𝑖, 𝑗 - 1})

binom-expansion_(tag)

\begin{matrix} {(𝑥 + 𝑦)}^{𝑛} & = & \sum_{𝑖 + 𝑗 = 𝑛} (\binom{𝑛}{𝑖, 𝑗}) 𝑥^{𝑖} 𝑦^{𝑗} \\ {(𝑥_{1} + \dots + 𝑥_{𝑑})}^{𝑛} & = & \sum_{𝑘_{1} + \dots + 𝑘_{𝑑} = 𝑛} (\binom{𝑛}{𝑘_{1}, \dots, 𝑘_{𝑑}}) 𝑥_{1}^{𝑘_{1}} \dots 𝑥_{𝑑}^{𝑘_{𝑑}} \end{matrix}

vs Newton binomial ${(1 + 𝑥)}^{𝑝} = \sum_{𝑖 = 0 . . \infty} (\binom{𝑝}{𝑖}) 𝑥^{𝑖}, 𝑝 \in ℝ$

multi-combination_(tag) Similarly, the following are equivalent

$𝑑$ multi-combination. $1, \dots, 𝑛$ select $𝑘_{1}, \dots, 𝑘_{𝑑}$ with $𝑘_{1} + \dots + 𝑘_{𝑑} = 𝑛$
partition ${1, \dots, 𝑛} = 𝐴_{1} ⊔ \dots ⊔ 𝐴_{𝑑}$ with $| 𝐴_{𝑖} | = 𝑘_{𝑖}$ and $𝑘_{1} + \dots + 𝑘_{𝑑} = 𝑛$
Select permutation, and quotient
$(\binom{𝑛}{𝑘_{1}, \dots, 𝑘_{𝑑}}) = \frac{| 𝑆_{𝑛} |}{| 𝑆_{𝑘_{1}} \times \dots \times 𝑆_{𝑘_{𝑑}} |} = \frac{𝑛!}{𝑘_{1}!, \dots, 𝑘_{𝑑}!}$

Total number $\sum_{\begin{matrix} 𝑘_{1}, \dots, 𝑘_{𝑑} \in ℕ \\ 𝑘_{1} + \dots + 𝑘_{𝑑} = 𝑛 \end{matrix}} (\binom{𝑛}{𝑘_{1}, \dots, 𝑘_{𝑑}}) = 𝑑^{𝑛}$ , which is the number of selecting $𝑛$ times from $𝑑$ with replacement $𝑑^{𝑛}$

Proof

Selecting $𝑛$ times with replacement from $1, \dots, 𝑑$ , number $𝑑^{𝑛}$ <==> number of mappings $1, \dots, 𝑛 \to 1, \dots, 𝑑$ , $| {1, \dots, 𝑑} |^{| {1, \dots, 𝑛} |}$

Any selection can be permuted to $\underset{𝑘_{1}}{\underset{⏟}{1, \dots, 1}}, \underset{𝑘_{2}}{\underset{⏟}{2, \dots, 2}}, \dots, \underset{𝑘_{𝑑}}{\underset{⏟}{𝑑, \dots, 𝑑}}$ with $𝑘_{1} + \dots + 𝑘_{𝑑} = 𝑛$

Restoring all the order is selecting $𝑘_{1}, \dots, 𝑘_{𝑑}$ positions from $1, \dots, 𝑛$ , which is multinomial coefficient $(\binom{𝑛}{𝑘_{1}, \dots, 𝑘_{𝑑}})$ . This gives

\sum_{\begin{matrix} 𝑘_{1}, \dots, 𝑘_{𝑑} \in ℕ \\ 𝑘_{1} + \dots + 𝑘_{𝑑} = 𝑛 \end{matrix}} (\binom{𝑛}{𝑘_{1}, \dots, 𝑘_{𝑑}}) = 𝑑^{𝑛}

what is $| {𝑘_{1}, \dots, 𝑘_{𝑑} \in ℕ : 𝑘_{1} + \dots + 𝑘_{𝑑} = 𝑛} |$ ?

Example Quantity 10, number of groups 4. $𝑛 = 10, 𝑑 = 4, 𝑘 (1, \dots, 4) = 3, 2, 0, 5$

star & bar model

★ ★ ★ | ★ ★ | | ★ ★ ★ ★ ★

Selecting $𝑑 - 1$ positions from $𝑛 + 𝑑 - 1$ positions as bar, dividing $𝑛$ ★ into $𝑑$ groups. Number

(\binom{𝑛 + 𝑑 - 1}{𝑑 - 1}) = (\binom{𝑛 + 𝑑 - 1}{𝑛, 𝑑 - 1})

dimension-of-symmetric-tensor_(tag) The dimension of symmetric tensor space ${(𝕂^{𝑛})}^{⊙ 𝑘}$ is also $(\binom{𝑘 + 𝑛 - 1}{𝑘, 𝑛 - 1})$ , basis $𝑒_{1}^{⊙ 𝑘_{1}} ⊙ \dots ⊙ 𝑒_{𝑛}^{⊙ 𝑘_{𝑛}}$

The repetition number $(\binom{𝑛}{𝑘_{1}, \dots, 𝑘_{𝑑}})$ will be used for example to calculate $𝐿^{2}$ normalization

conjugate-class-of-permutation-is-cycle_(tag) #link(<conjugate-class>)[] of $𝑆_{𝑛}$ <==> cycle := permutation $𝑎$ with $𝑖_{1} \overset{𝑎}{⇝} 𝑖_{2} \overset{𝑎}{⇝} \dots \overset{𝑎}{⇝} 𝑖_{𝑘} \overset{𝑎}{⇝} 𝑖_{1}$

The $sign$ decomposition of permutation

Tensor space's $sign$ decomposition, $\oplus$ irreducible represenation