note-math

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

permutation_(tag) 以下等价

$1, \dots, 𝑛$ 双射
$1, \dots, 𝑛$ 排列
$𝑛$ 阶置换. 数量 $𝑛 (𝑛 - 1) \dots 1 = 𝑛!$ . 通常记为 $𝑆_{𝑛}$

combination_(tag) 以下等价

$Subset {1, \dots, 𝑛}$ 中选取子集 $𝐴$ with $| 𝐴 | = 𝑖$
选取子集 $𝐴, 𝐵 \in Subset {1, \dots, 𝑛}$ with

划分

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

| 𝐴 | = 𝑖, | 𝐵 | = 𝑗

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

选取置换 $𝑎$ with $𝐴 = {𝑎 (1), \dots, 𝑎 (𝑖)}, 𝐵 = {𝑎 (𝑖 + 1), \dots, 𝑎 (𝑖 + 𝑗)}$ 并且另一个置换 $𝑎^{'}$ 给出相同的划分 if

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

定义这种相同的划分的置换的 quotient_(tag) $𝑎 \sim 𝑎^{'}$ as $𝑆_{𝑛}$ 的子集满足上述条件, i.e. 划分可能性 $𝐴 ⊔ 𝐵$ 的逆像

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

基数计算

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

记为

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

所有 $𝑖 = 0, \dots, 𝑛$ 组合 <==> 所有 $𝑖 = 0, \dots, 𝑛$ 在 $Subset {1, \dots, 𝑛}$ 中选取子集 $𝐴$ with $| 𝐴 | = 𝑖$

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

是从 $2$ 个中可重复选 $𝑛$ 次的数量

from 用归纳法计算或者直接观察, 可得

\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 二项式 ${(1 + 𝑥)}^{𝑝} = \sum_{𝑖 = 0 . . \infty} (\binom{𝑝}{𝑖}) 𝑥^{𝑖}, 𝑝 \in ℝ$

multi-combination_(tag) 类似地, 以下等价

$𝑑$ 重组合. $1, \dots, 𝑛$ 选取 $𝑘_{1}, \dots, 𝑘_{𝑑}$ with $𝑘_{1} + \dots + 𝑘_{𝑑} = 𝑛$
划分 ${1, \dots, 𝑛} = 𝐴_{1} ⊔ \dots ⊔ 𝐴_{𝑑}$ with $| 𝐴_{𝑖} | = 𝑘_{𝑖}$ and $𝑘_{1} + \dots + 𝑘_{𝑑} = 𝑛$
选取置换, 且 quotient
$(\binom{𝑛}{𝑘_{1}, \dots, 𝑘_{𝑑}}) = \frac{| 𝑆_{𝑛} |}{| 𝑆_{𝑘_{1}} \times \dots \times 𝑆_{𝑘_{𝑑}} |} = \frac{𝑛!}{𝑘_{1}!, \dots, 𝑘_{𝑑}!}$

总数量 $\sum_{\begin{matrix} 𝑘_{1}, \dots, 𝑘_{𝑑} \in ℕ \\ 𝑘_{1} + \dots + 𝑘_{𝑑} = 𝑛 \end{matrix}} (\binom{𝑛}{𝑘_{1}, \dots, 𝑘_{𝑑}}) = 𝑑^{𝑛}$ , 即从 $𝑑$ 个中可重复选 $𝑛$ 次的数量 $𝑑^{𝑛}$

Proof

重复 $𝑛$ 次选取 $1, \dots, 𝑑$ , 数量 $𝑑^{𝑛}$ <==> 映射 $1, \dots, 𝑛 \to 1, \dots, 𝑑$ 的数量 $| {1, \dots, 𝑑} |^{| {1, \dots, 𝑛} |}$

任何选取都可以置换到 $\underset{𝑘_{1}}{\underset{⏟}{1, \dots, 1}}, \underset{𝑘_{2}}{\underset{⏟}{2, \dots, 2}}, \dots, \underset{𝑘_{𝑑}}{\underset{⏟}{𝑑, \dots, 𝑑}}$ with $𝑘_{1} + \dots + 𝑘_{𝑑} = 𝑛$

恢复所有顺序就是 $1, \dots, 𝑛$ 选取 $𝑘_{1}, \dots, 𝑘_{𝑑}$ 个位置, 即多重组合 $(\binom{𝑛}{𝑘_{1}, \dots, 𝑘_{𝑑}})$ . 这给出

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

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

Example 数量 10, 分组数量 4. $𝑛 = 10, 𝑑 = 4, 𝑘 (1, \dots, 4) = 3, 2, 0, 5$

star & bar 模型

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

$𝑛 + 𝑑 - 1$ 个位置选取 $𝑑 - 1$ 个作为 bar, 将 $𝑛$ 个 ★ 分成 $𝑑$ 组. 数量

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

dimension-of-symmetric-tensor_(tag) 也得到对称张量空间 ${(𝕂^{𝑛})}^{⊙ 𝑘}$ 的维数是 $(\binom{𝑘 + 𝑛 - 1}{𝑘, 𝑛 - 1})$ , 基 $𝑒_{1}^{⊙ 𝑘_{1}} ⊙ \dots ⊙ 𝑒_{𝑛}^{⊙ 𝑘_{𝑛}}$

重复数量 $(\binom{𝑛}{𝑘_{1}, \dots, 𝑘_{𝑑}})$ 会有用于例如计算 $𝐿^{2}$ 归一化

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

置换的 $sign$ 分解

张量空间的 $sign$ 分解, $\oplus$ irreducible represenation