【离散数学】笔记-台湾清华赵启超11C11D Enumeration

这是台湾清华赵启超教授离散数学11C11D课程的笔记。

Example 1
Let $X$ and $Y$ be sets with $|X|=m$ and $|Y|=n$. specifically, suppose that $X=\{1,2,3,\dotsc ,m\}$ and $Y=\{1,2,3,\dotsc ,n\}$, we know that there are $n^m$ functions from $X$ to $Y$.

How many of these functions are onto?

Let this number be denoted by $onto(m,n)$.

Clearly,
$onto(m,n)=0$ if $m<n$
$onto(m,m)=m!$ for all $m \ge 1$
$onto(m,1)=1$ for all $m \ge 1$
$onto(m,2)=2^m-2$ for all $m \ge 2$

Let $A_i$ denote the set of function from $X$ to $Y$ which do not take on the value $i$ in $Y$ $1\le i \le n$.
Then $onto(m,n)=|\overline{A_1} \cap \overline{A_2} \cap \dotsc \overline{A_n} |$
that is $=|\overline{A_1 \cup A_2 \cup \dotsc \cup A_n}|$
that is $=|S|-|A_1 \cup A_2 \cup \dotsc \cup A_n|$
where $S$ is the set of all functions from $X$ to $Y$.

for $m \ge n$, $onto(m,n)$ is also the number of ways to distribute $m$ distinct objects into $n$ numbered(but otherwise identical) containers with no containers left empty.

$S(m,n)=\begin{Bmatrix} m\\n\end{Bmatrix}$ is Stirling number of the second kind.
= number of ways to distribute $m$ distinct objects into $n$ identicable containers with no container left empty.
=$\frac{1}{n!}onto(m,n)$
=$\frac{1}{n!}\sum _{r=0}^n (-1)^r\begin{pmatrix}n\\r \end{pmatrix}(n-r)^m$