數學傳播

一、引言

對合成函數做高次微分後會得到甚麼結果? 歷代的數學家們在賦予函數各種限制之下做過很多討論, 而在 1855 年出現了第一位在沒有限制函數的情況下解決這個問題的數學家 ---
Francesco Faá di Bruno, 以下便是他得到的主要結果: ${\bf Faá di Bruno's}$ 公式： 假設函數 $ f(t) $ 及 $ \phi(t) $ 皆 $ n $ 次可微, 則 $ f\circ\phi $ 的 $ n $ 次微分為 $$ D^n(\left(f\circ\phi\right)(t))=\sum_{\sigma(n)}\frac{n!}{k_1!k_2!\cdots k_n!}(D^kf)\left(\frac{D\phi(t)}{1!}\right)^{k_1}\left(\frac{D^2\phi(t)}{2!}\right)^{k_2} \cdots \left(\frac{D^n\phi(t)}{n!}\right)^{k_n}, $$ 其中 $ D $ 代表 $ \frac{d}{dt}$, $ \sigma(n) $ 表示 $ n $ 的所有分割所成的集合, 即是聯立方程組 $$ \left\{\begin{array}{l} k_1+k_2+\cdots+k_n=k \\ k_1+2k_2+\cdots+nk_n=n\mbox{~}(1\le k\le n) \end{array}\right. $$的所有非負整數解 $ (k_1,k_2,\ldots,k_n)$。

給定正整數 $ k$, 我們以 $ \sigma(n,k) $ 表示將 $ n $ 分成 $ k $ 個部分的分割所成的集合, $ \sigma(n,k) $ 也可以視為一個聯立方程組的所有非負整數解 $ (k_1,k_2,\ldots,k_n): $ $$ \left\{\begin{array}{l} k_1+k_2+\cdots+k_n=k\\ k_1+2k_2+\cdots+nk_n=n \end{array}\right., $$ 顯然地 $ \sigma(n)=\uplus_{k=1}^n\sigma(n,k)$。本文將 Faá di Bruno 公式簡稱為 FdB。

關於FdB的研究已經沉寂了好一段時間, 但近幾年因為發現 FdB 在其他領域上面的應用, 這塊領域又漸漸復甦, Lukacs 將 FdB 應用在數理統計上, Roman 用umbral calculus的理論重新證明FdB公式, Constantine 用 FdB 推廣了與集合分割有關的恆等式並給出其機率解釋, Chu 用FdB得到許多表成行列式的恆等式, Chou, Hsu及Shiue 由 FdB 造出一類互逆關係從而導出一系列的恆等式。關於FdB研究的簡史可以參閱Johnson 。

本文目的為利用 FdB 得到各種著名組合數的恆等式, 含括 Catalan 數,第一類及第二類 Stirling 數, $ q $-二項式係數 $\cdots$ 等, 及 FdB 在計數上的應用; 在第二節中, 我們利用 FdB 得到了多種組合數的恆等式; 在第三節中, 我們由第一類及第二類 Stirling 數、 錯排數(number of derangements)、 Bell數的指數生成函數(exponential generating function)用FdB導出的恆等式獲得這些數的組合意義, 並得到一些限制置換(permutation)中圈結構(cycle structure)和限制集合分割(set partition)的子集大小的結果。

二、用 ${\bf FdB}$ 求組合恆等式

對任意給定冪級數 $ \phi(t)=\sum_{n=0}^{\infty}a_nt^n$, 我們以 $ {\phi \brack n} $ 表示 $ t^n $ 的係數, 即 $$ \phi(t)=\sum_{n\ge 0}{\phi \brack n}t^n\mbox{。} $$ 假設 $ f $ 有反函數, 考慮合成函數 $ \left(f\circ\phi\right)(t) $ 和 $ \left(f^{-1}\circ(f\circ\phi)\right)(t)$, Chou, Hsu 與 Shiue 將 FdB 改寫, 得到下列兩個等式 \begin{eqnarray} {f\circ\phi \brack n} &=&\sum_{\sigma(n)}\left(D^k f\right)_{x=\phi(0)}\frac{{\phi \brack 1}^{k_1}{\phi \brack 2}^{k_2}\ldots {\phi \brack n}^{k_n}}{k_1! k_2!\ldots k_n!}, \label{fcomphi} \\ {\phi \brack n}&=&\sum_{\sigma(n)}\left(D^k f^{-1}\right)_{x=f\circ\phi(0)}\frac{{f\circ\phi \brack 1}^{k_1}{f\circ\phi \brack 2}^{k_2}\ldots {f\circ\phi \brack n}^{k_n}}{k_1! k_2!\ldots k_n!}\mbox{。} \label{phi} \end{eqnarray} 因為 $ {f\circ\phi \brack n} $ 和 $ {\phi \brack n} $ 在 $ (\ref{fcomphi}) $ 及 $ (\ref{phi}) $ 中所處的地位恰好相反, 稱這兩條恆等式為一組互逆關係式。
特別地,考慮 $ f(x)=e^x$, $ \phi(t)=\sum_{n=0}^{\infty}a_nt^n$, 令 $ b_n={f\circ\phi \brack n}$, 若 $ \phi(0)=0$, 則由 $ (\ref{fcomphi}) $ 及 $ (\ref{phi}) $ 有以下互逆關係 \begin{eqnarray} \label{f} b_n&=&\sum_{\sigma(n)}\frac{{a_1}^{k_1}{a_2}^{k_2}\ldots {a_n}^{k_n}}{k_1! k_2!\ldots k_n!}, \\ \label{inv} a_n&=&\sum_{\sigma(n)}(-1)^{k-1}(k-1)!\frac{{b_1}^{k_1}{b_2}^{k_2}\ldots {b_n}^{k_n}}{k_1! k_2!\ldots k_n!}\mbox{。} \end{eqnarray}

$定理1 (Catalan數)\label{cat-inv}$ 對任意正整數 $ n$, 有互逆關係 \begin{eqnarray*} C_n&=&\frac{1}{n+1}\binom{2n}{n}=\frac{1}{n+1}\sum_{\sigma(n)}\frac{2^{2n-k}}{1^{k_1}k_1!2^{k_2}k_2!\ldots n^{k_n}k_n!}\\ \end{eqnarray*} $\hbox{及}$ \begin{eqnarray*} 4^n&=&2n\sum_{\sigma(n)}(-1)^{k-1}(k-1)!\prod_{i=1}^n\frac{\binom{2i}{i}^{k_i}}{k_i!}\mbox{。} \end{eqnarray*}

證明： 令 $ f(x)=e^{x}$、 $ \phi(t)=\ln{\frac{1}{\sqrt{1-4t}}}=-\frac{1}{2}\ln(1-4t)=\frac{1}{2}\left(4t+\frac{4^2t^2}{2}+\frac{4^3t^3}{3}\ldots\right)$, 從而 $$ a_i={\phi \brack i}=\frac{1}{2}\left(\frac{4^i}{i} \right); $$ 又 $ \left(f\circ \phi\right)=f(\phi(t))=\frac{1}{\sqrt{1-4t}}=\sum_{i\ge 0}\binom{2i}{i}t^i$, 於是 $$ b_i={f\circ \phi \brack i}=\binom{2i}{i}\mbox{。} $$ 故由FdB的(\ref{f})可得 \begin{align*} \binom{2n}{n} &=\sum_{\sigma(n)}\frac{\left[\frac{1}{2}\left(\frac{4}{1}\right)\right]^{k_1}\left[\frac{1}{2}\left(\frac{4^2}{2}\right)\right]^{k_2}\ldots \left[\frac{1}{2}\left(\frac{4^n}{n}\right)\right]^{k_n}}{k_1!k_2!\ldots k_n!}\\ &=\sum_{\sigma(n)}\frac{4^{k_1+2k_2+\cdots+nk_n}}{2^{k_1+k_2+\cdots+k_n}1^{k_1}k_1!2^{k_2}k_2!\ldots n^{k_n}k_n!}\\ &=\sum_{\sigma(n)}\frac{4^n}{2^k1^{k_1}k_1!2^{k_2}k_2!\ldots n^{k_n}k_n!}=\sum_{\sigma(n)}\frac{2^{2n-k}}{1^{k_1}k_1!2^{k_2}k_2!\ldots n^{k_n}k_n!} \mbox{。} \end{align*} 等號兩邊同除 $ \frac{1}{n+1} $ 可得第一條恆等式； 由FdB的(\ref{inv})可得 $$ 4^n=2n\sum_{\sigma(n)}(-1)^{k-1}(k-1)!\prod_{i=1}^n\frac{\binom{2i}{i}^{k_i}}{k_i!}\mbox{。}\tag*{$\Box$} $$

$定理2 \label{stirling-inv}$ 對任意正整數 $ n$, $ r$, 有互逆關係 \begin{eqnarray*} 1^n+2^n+\cdots+r^n&=&n\sum_{\sigma(n)}(-1)^{k-1}(k-1)!\prod_{i=1}^{n}\frac{S(r+i,r)^{k_i}}{k_i!} \end{eqnarray*} 及 \begin{eqnarray*} S(n+r,r)&=&\sum_{\sigma(n)}\prod_{i=1}^{n}\frac{(1^i+2^i+\ldots+r^i)^{k_i}}{i^{k_i}k_i!}, \end{eqnarray*} 或 \begin{eqnarray*} S(n,r)&=&\sum_{\sigma(n-r)}\prod_{i=1}^{n-r}\frac{(1^i+2^i+\ldots+r^i)^{k_i}}{i^{k_i}k_i!}\mbox{。} \end{eqnarray*}

證明： 令 $ f(x)=e^x$、 $ \phi(t)=\ln{\frac{1}{(1-t)(1-2t)\cdots (1-rt)}}$, 顯然 $ \phi(0)=0$。 第二類Stirling數的生成函數為(見{p.207}) \begin{eqnarray*} \left(f\circ\phi(t)\right)&=&\frac{1}{(1-t)(1-2t)\cdots (1-rt)}=\sum_{i\ge r}S(i,r)t^{i-r}, \end{eqnarray*} 故 \begin{eqnarray*} b_i&=&{f\circ\phi \brack i}=S(r+i,r); \end{eqnarray*} 另一方面因為 \begin{align*} \phi(t) &=\ln{\frac{1}{(1-t)(1-2t)\cdots (1-rt)}}\\ &=\sum_{i=1}^r(-\ln{(1-it)})=\sum_{i=1}^r\sum_{j\ge 1}\frac{i^j}{j}t^j=\sum_{j\ge 1}\sum_{i=1}^r\frac{i^j}{j}t^j, \end{align*} 觀察 $ t^n $ 的係數可得 $$ a_i={\phi \brack n}=\sum_{i=1}^r\frac{i^n}{n}=\frac{1^n+2^n+\cdots+r^n}{n}\mbox{。} $$ 利用FdB的 ($\ref{inv}$) 我們可以得到 $$ \frac{1^n+2^n+\ldots+r^n}{n}=\sum_{\sigma(n)}(-1)^{k-1}(k-1)!\frac{S(r+1,r)^{k_1}S(r+2,r)^{k_2}\ldots S(r+n,r)^{k_n}}{{k_1}!{k_2}!\ldots{k_n}!}, $$ 等號兩邊同乘 $ n $ 即得第一條恆等式； 由 FdB 的 (\ref{f}) 可得第二條恆等式 $$ S(n,r)=\sum_{\sigma(n-r)}\prod_{i=1}^{n-r}\frac{(1^i+2^i+\ldots+r^i)^{k_i}}{i^{k_i}k_i!}\mbox{。}\tag*{$\Box$} $$

註1. 除了上述定理外, 連續整數的冪次和與 $ S(n,k) $ 還有以下關係(見{p.221}) $$ 1^n+2^n+\ldots+r^n=\sum_{k=1}^{n}k!S(n,k)\binom{r+1}{k+1}\mbox{。} $$

$定理3 \label{binom}$ 對任意整數 $ n$, $ r$, 有互逆關係 \begin{eqnarray*} \binom{n}{r}&=&\sum_{\sigma(r)}\frac{(-1)^{r-k}n^k}{1^{k_1}k_1!2^{k_2}k_2!\ldots r^{k_r}k_r!} \end{eqnarray*} 及 \begin{eqnarray*} (-1)^{r-1}\frac{n}{r}&=&\sum_{\sigma(r)}(-1)^{k-1}(k-1)!\frac{\binom{n}{1}^{k_1}\binom{n}{2}^{k_2}\ldots\binom{n}{r}^{k_r}}{k_1! k_2!\ldots k_r!}\mbox{。} \end{eqnarray*}

證明： 取 $ f(x)=e^x$、 $ \phi(t)=\ln(1+t)^n=n\ln(1+t)$, 顯然 $ \phi(0)=0$。 因為 $ f\circ\phi(t)=(1+t)^n=\sum_{i=0}^n\binom{n}{i}t^i$, 可以推得 $$ b_i={f\circ\phi \brack i}=\binom{n}{i}; $$ 由 $ \phi(t)=n\ln{(1+t)}=\sum_{i\ge 1}\frac{(-1)^{i-1}n}{i}t^i$, 可以推得 $$ a_i={\phi \brack i}=(-1)^{i-1}\frac{n}{i}\mbox{。} $$ 於是由FdB的(\ref{f})可得 \begin{align*} \binom{n}{r} &=\sum_{\sigma(r)}\frac{\left((-1)^0\frac{n}{1}\right)^{k_1}\left((-1)^1\frac{n}{2}\right)^{k_2}\ldots\left((-1)^{r-1}\frac{n}{r}\right)^{k_r}}{k_1! k_2!\ldots k_r!}\\ &=\sum_{\sigma(r)}\frac{(-1)^{r-k}n^k}{1^{k_1}k_1!2^{k_2}k_2!\ldots n^{k_r}k_r!}; \end{align*} 由FdB的(\ref{inv})可得第二條恆等式 $$ (-1)^{r-1}\frac{n}{r}=\sum_{\sigma(r)}(-1)^{k-1}(k-1)!\frac{\binom{n}{1}^{k_1}\binom{n}{2}^{k_2}\ldots\binom{n}{r}^{k_r}} {k_1! k_2!\ldots k_r!}\mbox{。}\tag*{$\Box$} $$

接下來我們要討論與二項式係數有很多相似性質的組合數 --- $ q $-二項式係數 ($q $-binomial coefficient) $ {n \brack r}_q$。定義 $$ {n \brack k}_q=\left\{\begin{array}{ccl} \dfrac{(1-q^n)(1-q^{n-1})\ldots (1-q^{n-k+1})}{(1-q)(1-q^2)\ldots (1-q^k)},&& \mbox{當} n\ge k\gt 0;\\[7pt] 1,&\quad~&\mbox{當}n\ge k=0 \end{array}\right. $$

$定理4 \label{q-binom}$ 對任意正整數 $ n$, $ r$, 有互逆關係 \begin{eqnarray*} q^{\binom{r}{2}}{n \brack r}_q&=&\sum_{\sigma(r)}(-1)^{r-k}\prod_{i=1}^{r}\frac{\left(\frac{1-q^{ni}}{1-q^i}\right)^{k_i}}{i^{k_i}k_i!}\\ {\hbox{及}} \frac{q^{nr}-1}{q^r-1}&=&r\sum_{\sigma(r)}(-1)^{r-k}(k-1)!q^{\sum_{i=0}^rk_i\binom{i}{2}}\prod_{j=0}^r\left(\frac{{n \brack j}_q^{k_j}}{k_j!}\right)\mbox{。} \end{eqnarray*}

證明： $ q$-二項式係數有下列恆等式 (見{p.118}) $$ \prod_{j=0}^{n-1}(1+q^{j}t)=\sum_{j=0}^{n}q^{\binom{j}{2}}{n \brack j}_qt^j\mbox{~} $$ 令 $ f(x)=e^{x}$、 $ \phi(t)=\ln{\Big(\prod\limits_{j=0}^{n-1}(1+q^{j}t)\Big)}=\sum\limits_{j=0}^{n-1}\ln{(1+q^jt)} =\sum\limits_{m\ge 1}\sum\limits_{j=0}^{n-1}\frac{(-1)^{m-1}q^{jm}}{m}t^m$, 則 $ \phi(0)=0 $ 且 \begin{align*} a_i={\phi \brack i} &=(-1)^{i-1}\sum_{j=0}^{n-1}\frac{q^{ji}}{i}=(-1)^{i-1}\frac{1+q^i+q^{2i}+\ldots+q^{(n-1)i}}{i}\\ &=\frac{(-1)^{i-1}}{i}\frac{1-q^{ni}}{1-q^i}; \end{align*} 現在 $ \left(f\circ \phi\right)(t)=\prod\limits_{j=0}^{n-1}(1+q^{j}t)=\sum\limits_{j=0}^{n}q^{\binom{j}{2}}{n \brack j}_qt^j$, 則對任意 $ i\le n $ 有 $$ b_i={f\circ\phi \brack i}=q^{\binom{i}{2}}{n \brack i}_q; $$ 於是由 FdB 的 (\ref{f}) 可得 \begin{align*} q^{\binom{r}{2}}{n \brack r}_q &={f\circ\phi \brack r}=\sum_{\sigma(r)}(-1)^{\sum_{j=1}^r(j-1)k_j}\frac{\left(\frac{1-q^n}{1-q}\right)^{k_1}\left(\frac{1-q^{2n}}{1-q^2}\right)^{k_2}\ldots\left(\frac{1-q^{rn}}{1-q^r}\right)^{k_r}}{1^{k_1}k_1!2^{k_2}k_2!\ldots r^{k_r}k_r!}\\ &=\sum_{\sigma(r)}(-1)^{r-k}\frac{\left(\frac{1-q^n}{1-q}\right)^{k_1}\left(\frac{1-q^{2n}}{1-q^2}\right)^{k_2}\ldots\left(\frac{1-q^{rn}}{1-q^r}\right)^{k_r}}{1^{k_1}k_1!2^{k_2}k_2!\ldots r^{k_r}k_r!}\mbox{;} \end{align*} 又由 FdB 的 (\ref{inv}) 可得第二條恆等式 $$ \frac{q^{nr}-1}{q^r-1}=r\sum_{\sigma(r)}(-1)^{r-k}(k-1)!q^{\sum_{i=0}^rk_i\binom{i}{2}}\prod_{j=0}^r \Big(\frac{{n \brack j}_q^{k_j}}{k_j!}\Big)\mbox{。} \tag*{$\Box$} $$

$定理5 \label{q-binom2}$ 對任意正整數 $ n$, 有互逆關係 \begin{eqnarray*} {n+r-1 \brack r}_q&=&\sum_{\sigma(r)}\prod_{i=1}^{r}\frac{\left(\frac{1-q^{ni}}{1-q^i}\right)^{k_i}}{i^{k_i}k_i!} \end{eqnarray*} 及 \begin{eqnarray*} \sum_{i=0}^{n-1}q^{ir}&=&\frac{1-q^{rn}}{1-q^r}=r\sum_{\sigma(r)}(-1)^{k-1}(k-1)!\prod_{i=1}^r\frac{{n+i-1 \brack i}_q^{k_i}}{k_i!}\mbox{。} \end{eqnarray*}

證明： $ q $-二項式係數有下列恆等式(見{p.118}) \begin{equation} \prod_{i=0}^{n-1}\frac{1}{1-q^it}=\sum_{i\ge 0}{n+i-1 \brack i}_qt^i\mbox{。} \end{equation} 令 $ f(x)=e^x$、 $ \phi(t)=\ln\Big(\prod\limits_{j=0}^{n-1}\frac{1}{1-q^jt}\Big)=\sum\limits_{j=0}^{n-1}(-\ln(1-q^jt)) =\sum\limits_{m\ge 1}\sum\limits_{j=0}^{n-1}\frac{q^{mj}}{m}t^m$, 則 $ \phi(0)=0 $ 且 $$ a_i={\phi \brack i}=\sum_{j=0}^{n-1}\frac{q^{ij}}{i}=\frac{1}{i}\cdot\frac{1-q^{ni}}{1-q^i}\mbox{;} $$ $ \left(f\circ \phi\right)(t)=\prod_{i=0}^{n-1}\frac{1}{1-q^it}$, 則 $$ b_i={f\circ \phi \brack i}={n+i-1 \brack i}_q\mbox{。} $$ 於是用FdB的(\ref{f})可得第一條恆等式 $$ {n+r-1 \brack r}_q=\sum_{\sigma(r)}\frac{\left(\frac{1-q^{n}}{1-q}\right)^{k_1}\left(\frac{1-q^{2n}}{1-q^2}\right)^{k_2}\ldots\left(\frac{1-q^{rn}}{1-q^r}\right)^{k_r}}{1^{k_1}k_1!2^{k_1}k_2!\ldots r^{k_r}k_r!}\mbox{;} $$ 由FdB的(\ref{inv})可得第二條恆等式 $$ \sum_{i=0}^{n-1}q^{ir}=\frac{1-q^{rn}}{1-q^r}=r\sum_{\sigma(r)}(-1)^{k-1}(k-1)!\prod_{i=1}^r\frac{{n+i-1 \brack i}_q^{k_i}}{k_i!}\mbox{。} \tag*{$\Box$}$$

我們稱 $ a_1+a_2+\ldots+a_m=n{~}(a_1\ge a_2\ge\ldots\ge a_m\ge 1) $ 的一組整數解 $ (a_1,a_2,\ldots,a_m) $ 為正整數 $ n $ 的一個分割(partition), 並將 $ n $ 的所有 分割的個數記為 $ p(n)$。於是 $ p(n) $ 的生成函數為(見{p.97}) \begin{equation}\label{d} \sum_{n\ge 0}p(n)t^n=\prod_{i\ge 1}\frac{1}{1-t^i}, \end{equation} 令 $ \alpha(n)=\sum_{d|n}{d}$, 即 $ n $ 的所有正因數和。

$定理6 \label{int-part}$ 對任意正整數 $ n$, 有互逆關係 \begin{eqnarray*} p(n)&=&\sum_{\sigma(n)}\frac{\alpha(1)^{k_1}\alpha(2)^{k_2}\ldots\alpha(n)^{k_n}}{1^{k_1}k_1!2^{k_2}k_2!\ldots n^{k_n}k_n!} \\{\hbox{及}} \sum_{d|n}\frac{1}{d}&=&\frac{\alpha(n)}{n}=\sum_{\sigma(n)}(-1)^{k-1}(k-1)!\frac{p(1)^{k_1}p(2)^{k_2}\ldots p(n)^{k_n}}{k_1!k_2!\ldots k_n!}\mbox{。} \end{eqnarray*}

證明： 令 $ f(x)=e^x$、 $ \phi(t)=\ln(\prod_{j\ge 1}(1-t^j)^{-1})=-\sum_{j\ge 1}\ln(1-t^j)=\sum_{l\ge 0}\sum_{j\ge 1}\frac{1}{l}t^{jl}$, 則 $ \phi(0)=0 $ 且 $$ a_i={\phi \brack i}=\sum_{d|i}\frac{1}{d}; $$ 又由 $ (\ref{d}) $ 知 $ \left(f\circ \phi\right)(t)=\frac{1}{(1-t)(1-t^2)\ldots(1-t^n)\ldots}=\sum_{n\ge 0}p(n)t^n$, 從而 $$ b_i={f\circ \phi \brack n}=p(n)\mbox{。} $$ 注意到 $ \sum_{d|n}\frac{1}{d}=\sum_{d|n}\frac{1}{n/d}=\frac{1}{n}\sum_{d|n}d=\frac{1}{n}\alpha(n)$, 從而 $ \sum_{d|n}\frac{1}{d}=\frac{1}{n}\alpha(n)$。 現在用FdB的 $ (\ref{f}) $ 可推得 \begin{align*} p(n) &=\sum_{\sigma(n)}\frac{\left(\sum_{d|1}\frac{1}{d}\right)^{k_1}\left(\sum_{d|2}\frac{1}{d}\right)^{k_2}\ldots\left(\sum_{d|n}\frac{1}{d}\right)^{k_n}}{k_1!k_2!\ldots k_n!}\\ &=\sum_{\sigma(n)}\frac{\left(\frac{1}{1}\alpha(1)\right)^{k_1}\left(\frac{1}{2}\alpha(2)\right)^{k_2}\ldots\left(\frac{1}{n}\alpha(n)\right)^{k_n}}{k_1!k_2!\ldots k_n!}\\ &=\sum_{\sigma(n)}\frac{\alpha(1)^{k_1}\alpha(2)^{k_2}\ldots\alpha(n)^{k_n}}{1^{k_1}k_1!2^{k_2}k_2!\ldots n^{k_n}k_n!}\mbox{。} \end{align*} 由FdB的(\ref{inv})可推得第二條恆等式 $$ \frac{1}{n}\alpha(n)=\sum_{d|n}\frac{1}{d}=\sum_{\sigma(n)}(-1)^{k-1}(k-1)!\frac{p(1)^{k_1}p(2)^{k_2}\ldots p(n)^{k_n}}{k_1!k_2!\ldots k_n!}\mbox{。} \tag*{$\Box$}$$

註2. Chou,Hsu和Shiue 也有得到以上等式, 但用的方法與我們不同。

三、對稱群及集合分割上的組合數

這一節, 我們將由已知的第一類及第二類Stirling數、Bell數、錯排數(number of derangements)的指數生成函數出發, 利用FdB推導出這些數的組合意義, 從而可用 FdB求出錯排數及Bell數加上更多限制的生成函數。 首先, 我們先考慮第一類Stirling數 $ s(n,k) $ 及錯排數 $ D_n$ 。

對稱群 $ S_n $ (symmetric group)中的每一個置換皆可唯一分解成互斥圈(disjoint cycle)的乘積。若一個置換分解成互斥圈後, 長度為 $ i $ 的圈有 $ k_i $ 個 $ (i=1,2,\ldots,n)$, 則我們稱這個置換是屬於 $ 1^{k_1}2^{k_2}\ldots n^{k_n} $ 型的置換。

下面是已知的事實(證明請參閱Charalambides {p.464}):

給定非負整數 $ k_1,k_2,\ldots,k_n$, 則 $ S_n $ 中 $ 1^{k_1}2^{k_2}\ldots n^{k_n} $ 型置換的個數為 \begin{equation}\label{cycle} \frac{n!}{1^{k_1}k_1!2^{k_2}k_2!\ldots n^{k_n}k_n!}\ \hbox{。} \end{equation}

第一類Stirling數的指數生成函數為 \begin{equation}\label{segf} \sum_{n\ge r}s(n,r)\frac{t^n}{n!}=\frac{1}{r!}\left(\ln(1+t)\right)^r\mbox{。} \end{equation} 錯排數 $ D_n $ 的指數生成函數為 \begin{equation}\label{degf} \sum_{n\ge 0}D_n\frac{t^n}{n!}=\frac{1}{e^t(1-t)}\mbox{。} \end{equation}

$定理7. \label{s}$ 對任意正整數 $ n $ 及非負整數 $ r\mbox{~}(n\ge r)$, $$ s(n,r)=(-1)^{n-r}\sum_{\sigma(n,r)}\frac{n!}{1^{k_1}k_1!2^{k_2}k_2!\ldots n^{k_n}k_n!}\mbox{。} $$

證明： 取 $ f(x)=x^r$、 $ \phi(t)=\ln(1+t)$。因為 $ D^kf(x)=D^kx^k=r(r-1)(r-2)\ldots(r-k+1)x^{r-k}$, 所以 $$ \left(D^kf(x)\right)_{x=\phi(0)=0}=r(r-1)(r-2)\ldots(r-k+1)\delta_{r,k}, $$ 其中 $$ \delta_{r,k}=\left\{\begin{array}{ll} 1 &\mbox{,若}r=k\\ 0 &\mbox{,若}r\neq k \end{array}\right.; $$ $ \phi(t) $ 中 $ t^i $ 係數為 $$ {\phi \brack i}=(-1)^{i-1}\frac{1}{i}; $$ 將 $ (\ref{segf}) $ 改寫為 $ \left(\ln(1+t)\right)^r=\sum_{n\ge r}r!s(n,r)\frac{t^n}{n!}$, 於是 $$ {f\circ\phi \brack n}={\left(\ln(1+t)\right)^r \brack n}=\frac{r!}{n!}s(n,r)\mbox{。} $$ 用FdB的 $ (\ref{fcomphi}) $ 可得 \begin{align*} &\hskip -5pt \frac{r!}{n!}s(n,r) \\ &=\sum_{\sigma(n)}r(r-1)(r-2)\ldots(r-k+1)\delta_{r,k}\frac{\left[(-1)^{1-1}\frac{1}{1}\right]^{k_1}\left[(-1)^{2-1}\frac{1}{2}\right]^{k_2}\ldots \left[(-1)^{n-1}\frac{1}{n}\right]^{k_n}}{k_1!k_2!\ldots k_n!}\\ &=\sum_{\sigma(n)}r(r-1)(r-2)\ldots(r-k+1)\delta_{r,k}\frac{(-1)^{n-k}}{1^{k_1}k_1!2^{k_2}k_2!\ldots n^{k_n}k_n!}\\ &=\sum_{\sigma(n,r)}\frac{(-1)^{n-r}r!}{1^{k_1}k_1!2^{k_2}k_2!\ldots n^{k_n}k_n!}, \end{align*} 等號兩邊同乘上 $ \frac{n!}{r!} $ 後可得 $$ s(n,r)=(-1)^{n-r}\sum_{\sigma(n,r)}\frac{n!}{1^{k_1}k_1!2^{k_2}k_2!\ldots n^{k_n}k_n!}\mbox{。}\tag*{$\Box$} $$

註3. Comtet {p.232}也用不同的方法證得上述結果。

$定理8.\label{der}$ 對任意正整數 $ n$, $$ D_n=\sum_{\substack{k_2+k_3+\ldots+k_n=k\\ 2k_2+3k_3+\ldots+nk_n=n}} \frac{n!}{2^{k_2}k_2!\ldots n^{k_n}k_n!}\mbox{。} $$

證明： 取 $ f(x)=\ln(x)$、 $ \phi(t)=\frac{1}{e^t(1-t)}$, 顯然 $ f\circ\phi(0)=0$。 由 ($\ref{degf}$) 知 $ \phi(t) $ 的 $ t^n $ 項係數為 $$ {\phi \brack n}=\frac{D_n}{n!}; $$ 因為 $ f\circ\phi(t)=-\ln(1-t)-t=\frac{t^2}{2}+\frac{t^3}{3}+\ldots$, 對任意正整數 $ i $ $$ {f\circ\phi \brack i}=\left\{\begin{array}{ll} 0 \mbox{, 當} i=1\\ \frac{1}{i}\mbox{, 當} i\neq 1 \end{array}\right.\mbox{。} $$ 因為 $ {f\circ\phi \brack 1}=0$, 只有 $ k_1=0 $ 時 $ \frac{{f\circ\phi \brack 1}^{k_1}{f\circ\phi \brack 2}^{k_2}\ldots {f\circ\phi \brack n}^{k_n}}{k_1!k_2!\ldots k_n!}\neq 0$, 故由FdB的 ($\ref{inv}$) 可得 \begin{align*} \frac{D_n}{n!} &=\sum_{\sigma(n)}\frac{{f\circ\phi \brack 1}^{k_1}{f\circ\phi \brack 2}^{k_2}\ldots {f\circ\phi \brack n}^{k_n}}{k_1!k_2!\ldots k_n!}\\ &=\sum_{\substack{k_2+k_3+\ldots+k_n=k\\ 2k_2+3k_3+\ldots+nk_n=n}}\frac{1}{2^{k_2}k_2!\ldots n^{k_n}k_n!}, \end{align*} 即 $$ D_n=\sum_{\substack{k_2+k_3+\ldots+k_n=k\\ 2k_2+3k_3+\ldots+nk_n=n}} \frac{n!}{2^{k_2}k_2!\ldots n^{k_n}k_n!}\mbox{。}\tag*{$\Box$} $$

註4. 定理 8 的恆等式可直接由 $ (\ref{cycle}) $ 及錯排數本身的定義得到, 但我們的做法是反過來從指數生成函數出發, 利用FdB 得到這個恆等式, 同時也得到錯排數的組合意義。

由 ($\ref{cycle}$) 可知定理 7 及定理 8 中連加符號內的被加項分別為 $ 1^{k_1}2^{k_2}\ldots n^{k_n} $ 型置換及 $ 1^02^{k_2}\ldots n^{k_n} $ 型置換的個數。

我們先觀察定理 7 中的置換, 這些置換所對應的 $ (k_1,k_2,\ldots,k_n) $ 為 $ \sigma(n,r) $ 內的元素, 從而 $ (k_1,k_2,\ldots,k_n) $ 必須滿足 $$ \left\{\begin{array}{l} k_1+k_2+\cdots+k_n=r\\ k_1+2k_2+\cdots+nk_n=n \end{array}\right.\mbox{。} $$ 另一方面, 對所有 $ 1\le i\le n$, $ k_i $ 代表長度為 $ i $ 的互斥圈的個數, 所以 $ k_1+k_2+\cdots+k_n=r $ 代表互斥圈的總數為 $ r$, 而 $ k_1+2k_2+\cdots+nk_n=n $ 則代表 這個置換是 $ S_n $ 中的元素, 因此 $ \sum_{\sigma(n,r)}\frac{n!}{1^{k_1}k_1!2^{k_2}k_2!\ldots n^{k_n}k_n!} $ 可以解釋為 $ S_n $ 中互斥圈總數為 $ r $ 的置換的個數, 於是我們得到了組合學中廣為人知的 $ |s(n,r)| $ 的組合意義: $ S_n $ 中互斥圈總數為 $ r $ 的置換的個數。

而定理 8 中的置換對應的 $ (k_1,k_2,\ldots,k_n) $ 需滿足 $$ \left\{\begin{array}{l} k_1=0\\ k_1+k_2+\cdots+k_n=k\mbox{~}(1\le k\le n)\\ k_1+2k_2+\cdots+nk_n=n \end{array}\right., $$ 其中因為 $ k_1=0$, 這些置換分解成相斥圈後, 都不具有長度為 $ 1 $ 的圈, 換句話說就是沒有固定點(fixed point), 因此 $$ \sum_{\substack{k_2+k_3+\ldots+k_n=k\\ 2k_2+3k_3+\ldots+nk_n=n}} \frac{n!}{2^{k_2}k_2!\ldots n^{k_n}k_n!} $$ 為 $ S_n $ 的所有置換中, 不具有固定點的置換的個數, 用比較貼近生活的言語表達即是:

$\bullet$ 有 $ n $ 個人參加宴會, 每個人各戴一頂帽子, 宴會進場時, $ n $ 人皆將帽子交給服務生, 宴會結束後 $ n $ 人拿回帽子, 沒有人拿到自己帽子的情況的個數。

這就是錯排最初被提出時的問題。

由定理 8 證明的過程中, 我們發現利用FdB得到的等式可以更進一步的探討錯排的問題。
回顧當時的證明, 我們取 $ D_n $ 的指數生成函數 $ \phi(t)=\frac{1}{e^t(1-t)}$、 $ f(x)=\ln(x)$, 所以 $ f\circ\phi(t)=\ln(\frac{1}{e^t(1-t)})=-\ln(1-t)-t=\frac{t^2}{2}+\frac{t^3}{3}+\ldots$, 因為 $ \ln\frac{1}{e^t(1-t)} $ 中的 $ \ln\frac{1}{e^t} $ 消去了 $ \ln\frac{1}{1-t} $ 的 $ t $ 項係數, $ {f\circ\phi \brack 1}=0 $ 迫使 $ k_1=0$, 代表置換中長度為 $ 1 $ 的圈的個數為 $ 0$, 因此我們得到此類置換的個數。

現在我們觀察 $ \phi(t)$, 首先注意到因為 $$ \frac{1}{1-t}=1+t+t^2+t^3+\ldots=1+t+2!\frac{t^2}{2!}+3!\frac{t^3}{3!}+\ldots, $$ 所以 $ \frac{1}{1-t} $ 為對稱群元素個數 $ |S_n| $ 的指數生成函數, 而由先前討論可知, $ \frac{1}{1-t} $ 乘上 $ e^{-t} $ 後使得具有長度 $ 1 $ 的圈被排除而得到 $ D_n $ 的指數生成函數, 因此我們猜測經由乘上 $ e $ 的冪次也能排除具有其他長度圈的置換, 其結果便是以下定理。

給定一集合 $ P\subset\mathbb{N}$。一個置換若其分解成相斥圈後不具有長度為 $ j\in P $ 的圈時, 稱此置換為「$ P $ 免除 ($P $-free)置換」。

$定理9. \label{gd}$ 令 $ D(n;P) $ 為 $ S_n $ 中 $ P $ 免除置換的個數, 則 $ D(n;P) $ 的指數生成函數為 $$ \sum_{n\ge 0}D(n;P)\frac{t^n}{n!}=\frac{1}{e^{\sum_{j\in P}\frac{t^{j}}{j}}(1-t)}=e^{\sum_{j\in(\mathbb{N}-P)}\frac{t^j}{j}}\mbox{。} $$

證明： 令 $ f(x)=\ln(x)$, $ \phi(t)=e^{-\sum_{j\in P}\frac{t^{j}}{j}}(1-t)^{-1}$, 顯然 $ f\circ\phi(0)=0$。 因為 $ f\circ\phi(t)=\ln(e^{-\sum_{j\in P}\frac{t^{j}}{j}}(1-t)^{-1})=(t+\frac{t^2}{2}+\frac{t^3}{3}\ldots)-\sum_{j\in P}\frac{t^{j}}{j}$, 所以 $$ {f\circ\phi \brack i}=\left\{\begin{array}{ll} \frac{1}{i} ,\mbox{ 當}i\notin P\\ 0 ,\mbox{ 當}i\in P\mbox{。} \end{array}\right.\mbox{。} $$ 由 FdB 的 (\ref{inv}) 可得 \begin{align*} {\phi \brack n} &=\sum_{\sigma(n)}\frac{{f\circ\phi \brack 1}^{k_1}{f\circ\phi \brack 2}^{k_2}\ldots {f\circ\phi \brack n}^{k_n}}{k_1! k_2!\ldots k_n!}\\ &=\sum_{\substack{i_1,i_2,\ldots,i_s\notin P \\k_{i_1}+k_{i_2}+\ldots+k_{i_{s}}=k \\ i_1k_{i_1}+i_2k_{i_2}+\ldots+i_{s}k_{i_{s}=n}}} \frac{\left(\frac{1}{i_1}\right)^{k_{i_1}}\left(\frac{1}{i_2}\right)^{k_{i_2}}\ldots\left(\frac{1}{i_{s}}\right)^{k_{i_{s}}}}{k_{i_1}!k_{i_2}!\ldots k_{i_{s}}!}\\ &=\sum_{\substack{i_1,i_2,\ldots,i_s\notin P \\k_{i_1}+k_{i_2}+\ldots+k_{i_{s}}=k \\ i_1k_{i_1}+i_2k_{i_2}+\ldots+i_{s}k_{i_{s}=n}}} \frac{1}{{i_1}^{k_{i_1}}k_{i_1}!{i_2}^{k_{i_2}}k_{i_2}!\ldots {i_{s}}^{k_{i_{s}}}k_{i_{s}}!}, \end{align*} 等號兩邊同乘 $ n! $ 得 $$ n!{\phi \brack n}=\sum_{\substack{i_1,i_2,\ldots,i_s\notin P \\k_{i_1}+k_{i_2}+\ldots+k_{i_{s}}=k \\ i_1k_{i_1}+i_2k_{i_2}+\ldots+i_{s}k_{i_{s}=n}}} \frac{n!}{{i_1}^{k_{i_1}}k_{i_1}!{i_2}^{k_{i_2}}k_{i_2}!\ldots {i_{s}}^{k_{i_{s}}}k_{i_{s}}!}\mbox{。} $$ 注意到由 ($\ref{cycle}$), 等號右邊的式子為 $ S_n $ 中沒有長度 $ l\in P $ 圈的置換的個數 $ D(n;P)$, 故 $ {\phi \brack n}=\frac{D(n;P)}{n!}$, 於是我們得到 $$ \phi(t)=\sum_{n\ge 0}D(n;P)\frac{t^n}{n!}\mbox{。}\tag*{$\Box$} $$

將定理9中的 $ P $ 以 $ \mathbb{N}-P $ 替代, 則因為 $ \mathbb{N}-(\mathbb{N}-P)=P$, 我們得到以下推論:

$推論1.\label{cyc}$ 令 $ P\subset\mathbb{N}$, 則對任意 $ n\in\mathbb{N}$, $ S_n $ 中分解成互斥圈後僅具有長度為 $ l\in P $ 的置換的個數, 其指數生成函數為 $ e^{\sum_{l\in P}\frac{t^l}{l}}$。

由推論 1, 取 $ P=\bigcup_{s=1}^{k}P_s $ 且對任意 $ 1\le i\lt j\le k $ 有 $ P_i\cap P_j=\emptyset$, 於是可得到下一推論:

$推論2.\label{cycp}$ 令 $ P_1,P_2,\ldots,P_k\subset\mathbb{N} $ 且對任意 $ 1\le i\lt j\le k $ 有 $ P_i\cap P_j=\emptyset$, 則對任意 $ n\in\mathbb{N}$, $ S_n $ 中分解成互斥圈後僅具有長度為 $ l\in \bigcup_{s=1}^{k}P_s $ 的置換的個數, 其指數生成函數為 $$ \left(e^{\sum_{l\in P_1}\frac{t^l}{l}}\right)\left(e^{\sum_{l\in P_2}\frac{t^l}{l}}\right)\ldots \left(e^{\sum_{l\in P_k}\frac{t^l}{l}}\right)=e^{\sum_{l\in \bigcup_{s=1}^{k}P_s}\frac{t^l}{l}}\mbox{。} $$

註5. Bóna 也有證明推論1及推論2, 但用的方法與我們不同。

對任意正整數 $ r$, 我們將 $ D(n;\{r\}) $ 記為 $ D(n;r)$。

推論3. 對任意正整數 $ n $ 及 $ r~(n\ge r) $ 有 $$ D(n;r)=\sum_{k=0}^{\lfloor\frac{n}{r}\rfloor}\left(-\frac{1}{r}\right)^k\binom{n}{k}(n-k)!\ \mbox{。} $$ 特別地, 當 $ r=1 $ 時, $ D(n;1)=D_n$ 。

證明： 由定理 9 知, $ D(n;r) $ 的指數生成函數為 $$ \sum_{n\ge 0}D(n;r)\frac{t^n}{n!}=\frac{1}{e^\frac{t^r}{r}(1-t)}\mbox{。} $$ 將上式右邊視為兩指數生成函數相乘, 於是 \begin{align*} \sum_{n\ge 0}D(n;r)\frac{t^n}{n!} &=e^{-\frac{t^r}{r}}\frac{1}{1-t}=\left(\sum_{n\ge 0}\left(-\frac{1}{r}\right)^n\frac{t^{rn}}{n!}\right)\left(\sum_{n\ge 0}n!\frac{t^{n}}{n!}\right)\\ &=\left(\sum_{n\ge 0}\left(-\frac{1}{r}\right)^n\frac{(rn)!}{n!}\frac{t^{rn}}{(rn)!}\right)\left(\sum_{n\ge 0}n!\frac{t^{n}}{n!}\right)\\ &=\sum_{n\ge 0}\left(\sum_{k=0}^{\lfloor\frac{n}{r}\rfloor}\binom{n}{rk}\left(-\frac{1}{r}\right)^k\frac{(kr)!}{k!}(n-rk)!\right)\frac{t^n}{n!}\\ &=\sum_{n\ge 0}\left(\sum_{k=0}^{\lfloor\frac{n}{r}\rfloor}\left(-\frac{1}{r}\right)^k\frac{n!}{k!}\right)\frac{t^n}{n!}\\ &=\sum_{n\ge 0}\left(\sum_{k=0}^{\lfloor\frac{n}{r}\rfloor}\left(-\frac{1}{r}\right)^k\binom{n}{k}(n-k)!\right)\frac{t^n}{n!} \end{align*} 比較等號兩邊 $ t^n $ 係數可得 $$ D(n;r)=\sum_{k=0}^{\lfloor\frac{n}{r}\rfloor}\left(-\frac{1}{r}\right)^k\binom{n}{k}(n-k)!\ \mbox{。}\tag*{$\Box$} $$

令 $ \overline{D}(n;i_1^{k_{i_1}}i_2^{k_{i_2}}\ldots i_s^{k_{i_s}}) $ 為恰有 $ k_{i_l} $ 個 $ i_l $ 圈 $ (1\le l\le s)$、 其它長度的圈無限制的 $ n $-置換的個數。

$性質1.\label{fixed}$ 對任意正整數 $ n,s $ 及 $ r~(s\le n, r\le n)$, 有 $$ \overline{D}(n;s^r)=\frac{((s-1)!)^r}{r!}\binom{n}{s,\ldots,s,n-sr}D(n-sr;s)\mbox{。} $$

證明： 由 ($\ref{cycle}$) 及 $ \overline{D}(n;s^r) $ 的定義可知 \begin{align*} \overline{D}(n;s^r) &=\sum_{{\substack{k_1+\cdots+r+\ldots+k_n=k\\ k_1+2k_2+\cdots+sr+\cdots+nk_n=n}}}\frac{n!}{1^{k_1}k_1!\cdots s^r r!\cdots n^{k_n}k_n!}\\ &=\frac{1}{s^r r!}\sum_{\substack{k_1+k_2+\cdots+k_n=k-r \\ k_1+2k_2+\cdots+nk_n=n-sr}}\frac{n!}{1^{k_1}\cdots(s-1)^{k_{s-1}}k_{s-1}!(s+1)^{k_{s+1}}k_{s+1}!\cdots n^{k_n}k_n!}\\ &=\frac{n!}{s^r r!(n-sr)!}D(n-sr;s)\\ &=\frac{\left((s-1)!\right)^r}{r!}\binom{n}{s,\ldots,s,n-sr}D(n-sr;s)\mbox{。}\tag*{$\Box$} \end{align*}

註6. Riordan {p.17}稱 $ \overline{D}(n;1^k) $ 為 $ D_{n,k}$, 並得到 $$ D_{n,k}=\binom{n}{k}D_{n-k}, $$ 即是性質 1 令 $ s=1 $ 的情況。

接下來我們考慮第二類Stirling數 $ S(n,k) $ 及Bell數 $ B_n$ 。 以下為已知的事實(證明請參閱Charalambides [p.66]):

將一個 $ n $ 元相異集合分割成多個子集合, 其中 $ i $ 元子集的個數有 $ k_i $ 個 $ (1\le i \le n)$, 此種分割的個數為 \begin{equation}\label{partition} \frac{n!}{(1!)^{k_1}k_1!(2!)^{k_2}k_2!\ldots (n!)^{k_n}k_n!}\ \hbox{。} \end{equation}

第二類 Stirling 數的指數生成函數為 \begin{equation}\label{Segf} \sum_{n\ge r}S(n,r)\frac{t^n}{n!}=\frac{1}{r!}\left(e^t-1\right)^r\mbox{。} \end{equation} Bell 數的指數生成函數為 \begin{equation}\label{begf} \sum_{n\ge 0}B_n\frac{t^n}{n!}=e^{e^t-1}\mbox{。} \end{equation}

$定理10. \label{S}$ 對任意正整數 $ n $ 及非負整數 $ r\mbox{~}(n\ge r)$, $$ S(n,r)=\sum_{\sigma(n,r)}\frac{n!}{(1!)^{k_1}k_1!(2!)^{k_2}k_2!\ldots (n!)^{k_n}k_n!}\mbox{。} $$

證明： 取 $ f(x)=x^r$、 $ \phi(t)=e^t-1$。我們有 $$ \left(D^kf(x)\right)_{x=\phi(0)=0}=r(r-1)(r-2)\ldots(r-k+1)\delta_{r,k}; $$ 對所有正整數 $ i $ $$ {\phi \brack i}=\frac{1}{i!}; $$ 將 ($\ref{Segf}$) 改寫為 $ (e^t-1)^r=\sum_{n\ge r}r!S(n,r)\frac{t^n}{n!}$, 於是 $$ {f\circ\phi \brack n}={\left(e^t-1\right)^r \brack n}=\frac{r!}{n!}S(n,r)\mbox{。} $$ 類似定理 7, 用FdB的 ($\ref{fcomphi}$) 可得 $$ S(n,r)=\sum_{\sigma(n,r)}\frac{n!}{(1!)^{k_1}k_1!(2!)^{k_2}k_2!\ldots (n!)^{k_n}k_n!}\mbox{。}\tag*{$\Box$} $$

註7. Charalambides 也用不同的方法證明到這個結果。

$定理11. \label{bell}$ 對任意正整數 $ n$, $$ B_n=\sum_{\sigma(n)}\frac{n!}{(1!)^{k_1}k_1!(2!)^{k_2}k_2!\ldots (n!)^{k_n}k_n!}\mbox{。} $$

證明： 取 $ f(x)=e^x$、 $ \phi(t)=e^t-1$, 顯然 $ \phi(0)=0$。 對所有正整數 $ i $ $$ {\phi \brack i}=\frac{1}{i!}; $$ 由 ($\ref{begf}$) 可知 $$ {f\circ\phi \brack n}={e^{e^{t-1} \brack n}}=\frac{B_n}{n!}\mbox{。} $$ 利用FdB的 ($\ref{f}$) 得 \begin{align*} \frac{B_n}{n!}=\sum_{\sigma(n)}\frac{1}{(1!)^{k_1}k_1!(2!)^{k_2}k_2!\ldots (n!)^{k_n}k_n!}, \end{align*} 等號兩邊同乘 $ n! $ 即得 $$ B_n=\sum_{\sigma(n)}\frac{n!}{(1!)^{k_1}k_1!(2!)^{k_2}k_2!\ldots (n!)^{k_n}k_n!}\mbox{。}\tag*{$\Box$} $$

註8. 定理 11 也可以直接由 Bell 數的定義把定理 7 從 $ r=1 $ 到 $ r=n $ 的情況加起來得到, 但這裡我們由其生成函數出發, 利用 FdB 也能導出相同的結論。 定理 7 中連加符號內的被加項為 $$ \frac{n!}{(1!)^{k_1}k_1!(2!)^{k_2}k_2!\ldots (n!)^{k_n}k_n!}, $$ 由 ($\ref{partition}$) 知其恰為將 $ n $ 元集合分割成 $ k_i $ 個 $ i $ 元子集 $ (1\le i\le n) $ 的方法數, 定理 7 中每一個被加項對應到的 $ (k_1,k_2,\ldots,k_n) $ 都是 $ \sigma(r) $ 裡的元素, 即必須滿足 $$ \left\{\begin{array}{l} k_1+k_2+\cdots+k_n=r\\ k_1+2k_2+\cdots+nk_n=n \end{array}\right., $$ 所以我們可以將每一個被加項都視為一個分割, $ k_1+k_2+\cdots+k_n $ 表示這個分割的子集合總數, $ k_1+2k_2+\cdots+nk_n\!=\!n $ 則代表被分割的集合裡有 $ n $ 個元素, 因此 $ \sum\limits_{\sigma(n,r)}\!\!\frac{n!}{(1!)^{k_1}k_1!(2!)^{k_2}k_2!\ldots (n!)^{k_n}k_n!} $ 可以解釋成將 $ n $ 元相異集合分割成 $ r $ 個子集的方法數, 於是我們得到一般熟知的 $ S(n,r) $ 的組合意義---將 $ n $ 元相異集合分割成 $ r $ 個子集合的方法數。 又因為 $ \sigma(n)=\cup_{k=0}^n\sigma(n,k)$, 我們立即可以得到 $ B_n $ 的組合意義 --- 分割 $ n $ 元相異集合的方法數。

因為定理 9 的啟發, 利用類似於定理 9 中排除有某些特定長度圈的置換的方法, 也可以用來限制分割集合時產生的子集大小, 結果如下:
給定一集合 $ P\subset\mathbb{N}$。一個 $ n $ 元集合若分割成子集後不具有元素個數為 $ j\in P $ 的子集時, 稱此種分割為「$ P $ 免除分割」。　

$定理12. \label{parfor}$ 令 $ B(n;P) $ 為 $ n $ 元相異集合的 $ P $ 免除分割的個數, 則 $ B(n;P) $ 的指數生成函數為 $$ \sum_{n\ge 0}B(n;P)\frac{t^n}{n!}=e^{e^t-1-\sum_{j\in P}\frac{t^{j}}{j!}}=e^{\sum_{j\in (\mathbb{N}-P)}\frac{t^{j}}{j!}}\mbox{。} $$

證明： 令 $ f(x)=\ln(x)$, $ \phi(t)=e^{e^t-1-\sum_{j\in P}\frac{t^{j}}{j!}}$, 顯然 $ f\circ\phi(0)=0$。 又 $ f\circ\phi(t)=e^t-1-\sum_{j\in P}\frac{t^{j}}{j!}=\left(t+\frac{t^2}{2!}+\frac{t^3}{3!}+\ldots\right)-\sum_{j\in P}\frac{t^{j}}{j!}$, 所以 $$ {f\circ\phi \brack i}=\left\{\begin{array}{ll} \frac{1}{i!} ,\mbox{ 當}i\notin P\\ 0 ,\mbox{ 當}i\in P \end{array}\right.\mbox{。} $$ 由FdB的 ($\ref{inv}$) 可得 \begin{align*} {\phi \brack n} &=\sum_{\sigma(n)}\frac{{f\circ\phi \brack 1}^{k_1}{f\circ\phi \brack 2}^{k_2}\ldots {f\circ\phi \brack n}^{k_n}}{k_1! k_2!\ldots k_n!}\\ &=\sum_{\substack{i_1,i_2,\ldots,i_s\notin P \\k_{i_1}+k_{i_2}+\ldots+k_{i_{s}}=k \\ i_1k_{i_1}+i_2k_{i_2}+\ldots+i_{s}k_{i_{s}=n}}} \frac{\left(\frac{1}{i_1!}\right)^{k_{i_1}}\left(\frac{1}{i_2!}\right)^{k_{i_2}}\ldots\left(\frac{1}{i_{s}!}\right)^{k_{i_{s}}}}{k_{i_1}!k_{i_2}!\ldots k_{i_{s}}!}\\ &=\sum_{\substack{i_1,i_2,\ldots,i_s\notin P \\k_{i_1}+k_{i_2}+\ldots+k_{i_{s}}=k \\ i_1k_{i_1}+i_2k_{i_2}+\ldots+i_{s}k_{i_{s}=n}}} \frac{1}{(i_1!)^{k_{i_1}}k_{i_1}!(i_2!)^{k_{i_2}}k_{i_2}!\ldots (i_{s}!)^{k_{i_{s}}}k_{i_{s}}!}, \end{align*} 等號兩邊同乘 $ n! $ 得 $$ n!{\phi \brack n}=\sum_{\substack{i_1,i_2,\ldots,i_s\notin P \\k_{i_1}+k_{i_2}+\ldots+k_{i_{s}}=k \\ i_1k_{i_1}+i_2k_{i_2}+\ldots+i_{n-s}k_{i_{n-s}=n}}} \frac{n!}{(i_1!)^{k_{i_1}}k_{i_1}!(i_2!)^{k_{i_2}}k_{i_2}!\ldots (i_{s}!)^{k_{i_{s}}}k_{i_{s}}!}\mbox{。} $$ 注意到由 ($\ref{partition}$), 等號右邊為將 $ n $ 元相異集的 $ P $ 免除分割的個數 $ B(n;P)$, 故 $ {\phi \brack n}=\frac{B(n;P)}{n!}$, 於是有 $$ \phi(t)=\sum_{n\ge 0}B(n;P)\frac{t^n}{n!}\mbox{。}\tag*{$\Box$} $$

類似於推論 1的情況, 將定理12中的 $ P $ 以 $ \mathbb{N}-P $ 替代, 則因為 $ \mathbb{N}-(\mathbb{N}-P)=P$, 我們得到以下推論:

$推論4.\label{parcer}$ 令 $ P\subset\mathbb{N}$, 則對任意 $ n\in\mathbb{N}$, 將 $ n $ 元相異集合分割成大小 $ l\in P $ 的子集的方法數, 其指數生成函數為 $ e^{\sum_{l\in P}\frac{t^l}{l!}}$。

由推論4, 取 $ P=\bigcup_{s=1}^{k}P_s $ 且對任意 $ 1\le i\lt j\le k $ 有 $ P_i\cap P_j=\emptyset$, 於是可得到下一推論:

$推論5.\label{parcerp}$ 令 $ P_1,P_2,\ldots,P_k\subset\mathbb{N} $ 且對任意 $ 1\le i\lt j\le k $ 有 $ P_i\cap P_j=\emptyset$, 則對任意 $ n\in\mathbb{N}$, 將 $ n $ 元相異集合分割成大小 $ l\in \bigcup_{s=1}^{k}P_s $ 的子集的方法數, 其指數生成函數為 $$ \left(e^{\sum_{l\in P_1}\frac{t^l}{l!}}\right)\left(e^{\sum_{l\in P_2}\frac{t^l}{l!}}\right)\ldots \left(e^{\sum_{l\in P_k}\frac{t^l}{l!}}\right)=e^{\sum_{l\in \bigcup_{s=1}^{k}P_s}\frac{t^l}{l!}}\mbox{。} $$

註9. Bóna 也有證明推論4及推論5, 但用的方法與我們不同。

推論6. 對任意正整數 $ n $ 及 $ r~(n\ge r) $ 有 $$ B(n;r)=\sum_{k=0}^{\lfloor\frac{n}{r}\rfloor}\frac{(-1)^k}{k!}\binom{n}{r,,\ldots,r,n-kr}B_{n-rk}\ \mbox{。} $$

證明： 由定理 12 知 $ B(n;r) $ 的指數生成函數為 $$ \sum_{n\ge 0}B(n;r)\frac{t^n}{n!}=e^{e^t-1-\frac{t^{r}}{r!}}, $$ 將上式視為兩指數生成函數相乘, 從而可得 \begin{align*} \sum_{n\ge 0}B(n;r)\frac{t^n}{n!} &=e^{e^t-1}e^{\frac{t^{r}}{r!}}=\left(\sum_{n\ge 0}B_n\frac{t^{n}}{n!}\right)\left(\sum_{n\ge 0}\left(-\frac{1}{r!}\right)^n\frac{t^{rn}}{n!}\right)\\ &=\left(\sum_{n\ge 0}B_n\frac{t^{n}}{n!}\right)\left(\sum_{n\ge 0}\left(-\frac{1}{r!}\right)^n\frac{(rn)!}{n!}\frac{t^{rn}}{rn!}\right)\\ &=\sum_{n\ge 0}\left(\sum_{k=0}^{\lfloor\frac{n}{r}\rfloor}\binom{n}{rk}\left(-\frac{1}{r!}\right)^k\frac{(rk)!}{k!}B_{n-rk}\right)\frac{t^{n}}{n!}\\ &=\sum_{n\ge 0}\left(\sum_{k=0}^{\lfloor\frac{n}{r}\rfloor}\frac{(-1)^k}{k!}\binom{n}{r,\ldots,r,n-rk}B_{n-rk}\right)\frac{t^{n}}{n!}\mbox{。} \end{align*} 比較等號兩邊 $ t^n $ 係數可得 $$ B(n;r)=\sum_{k=0}^{\lfloor\frac{n}{r}\rfloor}\frac{(-1)^k}{k!}\binom{n}{r,\ldots,r,n-kr}B_{n-rk}\ \mbox{。}\tag*{$\Box$} $$

令 $ B(n;i_1^{k_{i_1}}i_2^{k_{i_2}}\ldots i_s^{k_{i_s}}) $ 為恰有 $ k_{i_l} $ 個 $ i_l $ 元子集 $ (1\le l\le s) $ 的 $ n $ 元集合分割的個數。

性質2. 對任意正整數 $ n,s $ 及 $ r~(s\le n, r\le n)$, 有 $$ B(n;s^r)=\frac{1}{r!}\binom{n}{s,\ldots,s,n-sr}B(n-sr;s)\mbox{。} $$

證明： 由 ($\ref{partition}$) 及 $ B(n;s^r) $ 的定義可知 \begin{align*} B(n;s^r) &=\sum_{\substack{k_1+\cdots+r+\ldots+k_n=k\\ k_1+2k_2+\cdots+sr+\cdots+nk_n=n}}\frac{n!}{(1!)^{k_1}k_1!\cdots (s!)^r r!\cdots (n!)^{k_n}k_n!}\\ &=\frac{n!}{(s!)^r r!(n-sr)!}\\ & \sum_{\substack{k_1+k_2+\cdots+k_n=k-r \\ k_1+2k_2+\cdots+nk_n=n-sr}}\frac{n!}{(1!)^{k_1}\cdots((s-1)!)^{k_{s-1}}k_{s-1}!((s+1)!)^{k_{s+1}}k_{s+1}!\cdots (n!)^{k_n}k_n!}\\ &=\frac{1}{r!}\frac{n!}{(s!)^r(n-sr)!}B(n-sr;s)\\ &=\frac{1}{r!}\binom{n}{s,\ldots,s,n-sr}B(n-sr;s)\mbox{。}\tag*{$\Box$} \end{align*}

致謝

感謝中研院數學所暑期離散及組合數學專題計畫的資助, 讓筆者有機會在暑假跟隨美國內華達大學數學系薛昭雄教授做暑期研究, 也由衷感謝薛昭雄教授的指導及不辭辛勞的審稿人, 因為薛教授和審稿人的鼓勵及鉅細靡遺的建議本文才能完稿。

參考資料

---本文作者投稿時為交通大學應用數學系學生---