1.2 映射与Stirling数

标签：right 1.2 映射 mathscr sum Stirling mid 集合 left

记号 1 对于集合 \(X, Y\), 记

\[Y^X:=\{f: X \rightarrow Y\}, \]

即从 \(X\) 到 \(Y\) 的映射构成的集合.

性质 2 对于集合 \(X, Y\), 成立

1. \(\left|Y^X\right|=|Y|^{|X|}\).
2. # \(\left\{f \in Y^X \mid f\right.\) 是单射 \(\}=(|Y|)_{|X|}:=|Y|(|Y|-1) \cdots(|Y|-|X|+1)\).

自然要问, 对于集合 $X, Y$, 从 $X$ 到 $Y$ 的满射有多少个?

记号 3 对于 (非空) 集合 \(X\), 记 \(S_X:=\left\{f \in X^X \mid f\right.\) 是双射 \(\} . S_X\) 中的元素称为集合 \(X\) 的置换, 或者重排. 对于正整数 \(n\), 记 \(S_n:=S_{[n]}\).

众所周知, 对任意 \(f, g \in S_X\), 复合映射 \(f \circ g \in S_X\), 逆映射 \(f^{-1} \in S_X\), 恒等映射 id: \(X \rightarrow X\) 也属于 \(S_X\), 因此 \(S_X\) 关于映射的复合运算构成群, 这个群称为集合 \(X\) 的置换群. 容易证明, 若 \(|X|=n\), 则有群同构 \(S_X \cong S_n\), 因此我们不妨只考虑 \(S_n\). 众所周知, \(S_n\) 中的元素都可唯一分解为两两不交的轮换之积.

定义 4 对于集合 \(X\), 以及 \(\mathscr{A} \subseteq 2^X\)(\(X\) 的全体子集构成的集合), 即 \(\mathscr{A}\) 是由 \(X\) 的某些子集构成的集合, 如果 \(\mathscr{A}\) 中的元素都非空且两两不交, 且 \(\bigsqcup_{A \in \mathscr{A}} A=X\), 则称 \(\mathscr{A}\) 是 \(X\) 的一个划分.

定义 5 对于正整数 \(r, n\), 令

\[\begin{aligned} (-1)^{n-r} s(r, n) & :=\#\left\{f \in S_r \mid f \text { 形如 } n \text { 个不交轮换之积 }\right\} \\ S(r, n) & :=\#\left\{\mathscr{A} \subseteq 2^{[r]}\Bigg | \varnothing \notin \mathscr{A},| \mathscr{A} \mid=n, \bigsqcup_{A \in \mathscr{A}}=[r]\right\} . \end{aligned} \]

\(s(r, n)\) 与 \(S(r, n)\) 分别称为第一类 Stirling 数与第二类 Stirling 数.
可见, \(S(r, n)\) 是将 \([r]\) 划分为 \(n\) 个非空子集的方法数.

性质 6 从 \([r]\) 到 \([n]\) 的满射的个数为 \(S(r, n) \cdot n!\).
证明: 对于满射 \(f:[r] \rightarrow[n]\), 考虑集合 \(\mathscr{A}:=\left\{f^{-1}(y) \subseteq[r] \mid y \in[n]\right\}\), 则 \(\mathscr{A}\)给出了 \([r]\) 的一个 \(n\) 元划分. 反之, \([r]\) 的每个 \(n\) 元划分都自然地对应于 \(n!\) 个从 \([r]\) 到 \([n]\) 的满射. 因此 \([r]\) 到 \([n]\) 的满射共有 \(S(r, n) \cdot n!\) 个.

性质 7 对任意 \(x \in \mathbb{C}\), 以及正整数 \(n\), 成立

\[x^n=\sum_{k=0}^n S(n, k)(x)_k \text {. } \]

证明: 将上式等号两边视为关于 \(x\) 的多项式, 因此只需证明 \(x\) 为正整数的情形. 现在令 \(x=m \in \mathbb{Z}_{+}\). 考虑从 \([n]\) 到 \([m]\) 的映射个数, 一方面, 它显然为 \(m^n\); 另一方面, 对于映射 \(f:[n] \rightarrow[m]\), 考虑对 \(f\) 的像集 \(f([n])\) 进行分类, 先确定 \(f\) 的像集有多少个元素, 再确定 \(f\) 的像集有哪些元素, 从而

\[\begin{aligned} & m^n=\left|[m]^{[n]}\right|=\sum_{k=0}^n \sum_{X \in\binom{[m]}{k}} \#\{f:[n] \rightarrow[m] \mid f([n])=X\} \\ & =\sum_{k=0}^n \sum_{X \in\binom{[m]}{k}} \#\{f:[n] \rightarrow X \mid f \text { 为满射 }\} \\ & =\sum_{k=0}^n \sum_{X \in\binom{[m]}{k}} k!S(n, k)=\sum_{k=0}^n \frac{m!}{k!(m-k)!} k!S(n, k) \\ & =\sum_{k=0}^n S(n, k) \cdot(m)_k \text {, } \\ & \end{aligned} \]

标签：right,1.2,映射,mathscr,sum,Stirling,mid,集合,left
From： https://www.cnblogs.com/Pizixsir-Math/p/18262138