數學傳播

1. 前言

Eulerian 數早由 Euler 於 1755 年提出。

本文目的是由 Eulerian 數定義出發去討論 Eulerian 數的性質及組合應用。

我們以 $D$ 代表$\frac{d}{dx}$, 將幾何級數 $\sum_{k=0}^{\infty} x^k =\frac{1}{1-x}~(|x|\lt 1)$ 連續做 $xD$ 的運算得 \begin{align*} (xD)^0(\frac{1}{1-x})&=\sum_{k=0}^{\infty} kx^k=\frac{1}{1-x},\\ (xD)^1(\frac{1}{1-x})&=\sum_{k=0}^{\infty} k^2x^k=\frac{x}{(1-x)^2}\\ (xD)^2(\frac{1}{1-x})&=\sum_{k=0}^{\infty} k^3x^k=\frac{x^2+x}{(1-x)^3}\\ (xD)^3(\frac{1}{1-x})&=\sum_{k=0}^{\infty} k^4x^k=\frac{x^3+4x^2+x}{(1-x)^4}\\ \vdots \end{align*} 於是 Euler 定義 $(xD)^k(\frac{1}{1-x})$ 中分子部分 $x^k$ 的係數為 Eulerian 數 ${n \brace k}$。 \begin{align*} (xD)^0(\frac{1}{1-x})&\mbox{的分子為}1 =1={0 \brace 0}\\ (xD)^1(\frac{1}{1-x})&\mbox{的分子為}x =0+1x={1 \brace 0}+{1 \brace 1}x\\ (xD)^2(\frac{1}{1-x})&\mbox{的分子為}x^2+x=0+1x+1x^2={2 \brace 0}+{2 \brace 1}x+{2 \brace 2}x^2\\ (xD)^3(\frac{1}{1-x})&\mbox{的分子為}x^3+4x^2+x=0+1x+4x^2+x^3\\ &\hskip 2cm ={3 \brace 0}+{3 \brace 1}x+{3 \brace 2}x^2+{3 \brace 3}x^3\\ \vdots\\ (xD)^n(\frac{1}{1-x})&\mbox{的分子為}{n \brace 0}+{n \brace 1}x+{n \brace 2}x^2+\cdots+{n \brace k}x^k+\cdots+{n \brace n}x^n. \end{align*}

從而可得到以下 ${n \brace k}$ 的表

$k$ $n$	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$\ldots$	$k=n$
$n=0 $	1	0	0	0	0	$\ldots$	0
$n=1 $	0	1	0	0	0	$\ldots$	0
$n=2 $	0	1	1	0	0	$\ldots$	0
$n=3 $	0	1	4	1	0	$\ldots$	0
$n=4 $	0	1	11	11	1	$\dots$	0
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$
$n=n$	${n \brace 0}$	${n \brace 1}$	${n \brace 2}$	${n \brace 3}$	${n \brace 4}$	$\ldots$	${n \brace n}$

由定義我們可以整理出一般式 \begin{align} (xD)^n(\frac{1}{1-x})=\sum_{k=0}^{\infty} k^n x^k =\frac{\sum_{k=0}^n {n \brace k} x^k}{(1-x)^{n+1}}。 \end{align} 另外, 也可以用其組合意義來定義 Eulerian 數, ${n \brace k}$ 的組合意義為對稱群 $S_{n}$ 中恰有 $k-1$ 個下降 (descent)的 $n$-置換 (permutation)的個數, 本文不從組合意義下去探討, 想了解請參閱 Bóna 。

在第二節中, 我們討論Eulerian數與$\sum_{k=0}^nk^m$的關聯, 在第三節中我們找出 Eulerian 數與 $n$ 維三角數還有差分之間的關係, 而最後一節我們則討論與 Stirling 數的關聯性。

2. Eulerian 數與 $\sum\limits_{k=0}^n k^m$ 的關聯

Eulerian 數具有以下兩個性質, 其證明請參閱 Comtet :

• ${n \brace k+1} ={n \brace n-k}$,
• ${n \brace k} =k{n-1 \brace k}+(n-k+1){n-1 \brace k-1}。$

其封閉表達式為 \begin{align*} {n \brace k} &= \sum_{j=0}^k (-1)^j {n+1 \choose j}(k-j)^n = \sum_{l=0}^k {n+1 \choose k-l}(-1)^{k-l}l^n。 \end{align*} Eulerian 數與連續整數冪次和 $\sum_{k=0}^n k^m$ 有關, 其結果如下定理。

定理1. 對任意正整數 $n$ 及 $m$ $$\sum_{k=0}^{n} k^m=\sum_{i=1}^{m} {m \brace i}{n+m+1-i \choose n-i}。$$

證明： 由(1)式知$$(\frac{1}{1-x})\sum_{k=0}^{\infty} k^m x^k = \frac{\sum_{k=0}^m {m \brace k} x^k}{(1-x)^{n+1}}, $$ 兩邊同乘$\frac{1}{1-x}$可得 \begin{align*} (\frac{1}{1-x})\sum_{k=0}^\infty k^m x^k & = \frac{1}{1-x} \frac{\sum_{k=0}^m {m \brace k} x^k}{(1-x)^{m+1}}\\ & = (\sum_{k=0}^m {m \brace k} x^k)(1-x)^{-(m+2)}\\ & = (\sum_{k=0}^m {m \brace k} x^k)(\sum_{j=0}^\infty {j+m+1 \choose m+1} x^j)\\ & =({m \brace 1}x+{m \brace 2}x^2+ \cdots +{m \brace m}x^m)(\sum_{j=0}^\infty {j+m+1 \choose m+1} x^j)。 \end{align*} 接著我們取兩邊$x^n$的係數 \begin{align*} \sum_{k=0}^n k^m & ={m \brace 1}{n-1+m+1 \choose m+1}+{m \brace 2}{n-2+m+1 \choose m+1}+{m \brace 3}{n-3+m+1 \choose m+1} \\ & \quad + \cdots +{m \brace m}{n-m+m+1 \choose m+1}\\ & ={m \brace 1}{n+m \choose m+1}+{m \brace 2}{n+m-1 \choose m+1}+\cdots+{m \brace m}{n+1 \choose m+1}\\ & ={m \brace 1}{n+m \choose n-1}+{m \brace 2}{n+m-1 \choose n-2}+\cdots+{m \brace m}{n+1 \choose n-m}\\ & =\sum_{i=0}^{m} {m \brace i}{n+m+1-i \choose n-i}。\tag*{$\Box$} \end{align*}

例1. \begin{align*} \sum_{k=0}^n k^3 &={3 \brace 1}{n+3 \choose 4}+{3 \brace 2}{n+2 \choose 4}+{3 \brace 3}{n+1 \choose 4}\\ &= 1\frac{(n\!+\!3)(n\!+\!2)(n\!+\!1)n}{4!}\!+\!4\frac{(n\!+\!2)(n\!+\!1)n(n\!-\!1)}{4!}\!+\!1\frac{(n\!+\!1)n(n\!-\!1)(n\!-\!2)}{4!}\\ & =\frac{n^2(n+1)^2}{4!}。\\ \end{align*}

德國數學家 Worpitzky 於 1883 年定義 Eulerian 數為 \begin{align*} x^n =\sum_{k=0}^n{n \brace k}{n+x-k \choose n} =\sum_{k=0}^n{n \brace k}{x+k-1 \choose n}。 \end{align*}

例2. \begin{align*} 3^2&={2 \brace 0}{6 \choose 2}+{2 \brace 1}{5 \choose 2}+{2 \brace 2}{4 \choose 2}=1 \times 6+1 \times 3, \\ 3^3&={3 \brace 0}{3+3-0 \choose 3}+{3 \brace 1}{3+3-1 \choose 3}+{3 \brace 2}{3+3-2 \choose 3}+{3 \brace 3}{3+3-3 \choose 3}\\ &=0+1 \times 10+4 \times 4+1 \times 1=27。 \end{align*} 由此公式也可以得出 \begin{align*} \sum_{k=0}^n k^m &=\sum_{k=0}^n \sum_{i=0}^m{m \brace i}{m+k-i \choose m}\\ &=\sum_{i=0}^m{m \brace i}\sum_{k=0}^n{m+k-i \choose m}\\ &=\sum_{i=0}^m{m \brace i}{m+k-i+1 \choose m+1}\\ &=\sum_{i=0}^m{m \brace i}{m+k-i+1 \choose k-i}。 \end{align*} 與定理 1 相同。

定理 1 是有關 $\sum_{k=0}^n k^m$ 與 Eulerian 數的關聯, 自然地我們猜測是否交錯和 Eulerian 數也有類似的關係, 為了達到此目的我們先證明以下引理。

引理1. 對任意正整數 $m$ $$\sum_{k=0}^{\infty} k^m(-x)^k=((-x)D)^m (\frac{1}{1+x})=\frac{\sum_{k=0}^m {m \brace k}(-1)^{k}x^k}{(1+x)^{m+1}}\mbox{ 。}$$

證明： 將 $x$ 以 $-x$ 代入(1)即可得 $$ ((-x)D)^m (\frac{1}{1+x})=\sum_{k=0}^{\infty} k^m(-x)^k=\frac{\sum_{k=0}^m {m \brace k}(-1)^kx^k}{(1+x)^{m+1}} $$

接著由引理1來求$\sum_{k=0}^n(-1)^k k^m。$
定理2. $$\sum_{k=0}^n (-1)^k k^m=\sum_{a=0}^m \sum_{j=0}^{n-a} (-1)^{n-j}{m \brace a}{n-a-j+m \choose m}。 $$

證明： 由引理1知$$\sum_{k=0}^{\infty} k^m(-x)^k=((-x)D)^m (\frac{1}{1+x})=\frac{\sum_{k=0}^m {m \brace k}(-1)^{k}x^k}{(1+x)^{m+1}}。$$ 等號兩邊同除$\frac{1}{1-x}$ \begin{align*} &(\frac{1}{1-x})\sum_{k=0}^m k^m (-x)^k = \frac{1}{1-x}\frac{\sum_{k=0}^m {m \brace k}(-1)^{k}(x)^k}{(1+x)^{m+1}}\\ & =({m \brace 1}(-1)^{1}x+{m \brace 2}(-1)^{2}x^2+\cdots+{m \brace m}(-1)^{m}x^m)(1-x)^{-1}(1+x)^{-(m+1)}\\ &=({m \brace 1}(-)^{1}x+{m \brace 2}(-1)^{2}x^2+\cdots+{m \brace m}(-1)^{m}x^m)(\sum_{i=0}^\infty x^i)(\sum_{j=0}^\infty {j+m \choose m}(-x)^j)。 \end{align*} 我們取等號兩邊$x^n$的係數 \begin{align*} \sum_{k=0}^n (-1)^k k^m & =\sum_{a=0}^m {m \brace a}(-1)^{a} (\sum_{j=0}^{n-a} {n-a-j+m \choose m}(-1)^{n-a-j})\\ & =\sum_{a=0}^m \sum_{j=0}^{n-a} (-1)^{n-j} {m \brace a}{n-a-j+m \choose m}。\tag*{$\Box$} \end{align*}

例3. $$\sum_{k=0}^n(-1)^kk^3 =\sum_{a=0}^3 \sum_{j=0}^{n-a} (-1)^{n-j}{3 \brace a}{n-a-j+3 \choose 3}。$$ 令$g=n-a-j$,因此 $g$ 的範圍是從 $0$ 到 $n-a, $ \begin{align*} \sum_{k=0}^n(-1)^kk^3 &= \sum_{a=0}^3 {3 \brace a}\sum_{g=0}^{n-a} (-1)^{a+g}{g+3 \choose 3}\\ &= \sum_{a=0}^3 {3 \brace a}(-1)^{a} \sum_{g=0}^{n-a}(-1)^g {g+3 \choose 3}。 \end{align*} 所以當$n=3$時, \begin{align*} \mbox{左式}&=\sum_{k=0}^3(-1)^kk^3=-1+8-27=-20\\ \mbox{右式}&={3 \brace 1}(-1)^1((-1)^0{3 \choose 3}+(-1)^1{4 \choose 3}+(-1)^2{5 \choose 3})\\ &+{3 \brace 2}(-1)^2((-1)^0{3 \choose 3}+(-1)^1{4 \choose 3})+{3 \brace 3}(-1)^3((-1)^0{3 \choose 3})\\ &=-1 \times (1-4+10)+4 \times (1-4)+(-1) \times 1=-7-12-1=-20。 \end{align*} 接著我們已經知道$${\frac{1}{1-x}}=\sum_{k=0}^{\infty} x^k。$$ 因此我們想探討如果只加到有限項 $\sum_{k=0}^n x^k$, 則對其做 $(xD)^k$ 會變成怎樣的形式。
定理3. 令 $n$ 為正整數, 則 \begin{eqnarray*} (xD)^k(\frac{1-x^{n+1}}{1-x})&=&\sum_{r=0}^n r^k x^r\\ &=&-x^{n+1}\sum_{r=0}^k{k \choose r}(n+1)^{k-r}\sum_{m=0}^r \frac{{r \brace m}x^m}{(1-x)^{m+1}}+\sum_{r=0}^k \frac{{k \brace r}x^r}{(1-x)^{k+1}}\mbox{ 。}\end{eqnarray*}

證明： \begin{align*} &\hskip -5pt \sum_{r=0}^n r^k x^r =(xD)^k \left(\frac{1-x^{n+1}}{1-x}\right)\\ & =(xD)^k(\frac{-x^{n+1}}{1-x})+(xD)^k(\frac{1}{1-x})\\ & =(xD)^k(\frac{-x^{n+1}}{1-x})+\sum_{r=0}^k \frac{{k \brace r}x^r}{(1-x)^{k+1}}\\ & =-(xD)^{k-1}({1 \choose 0}(n+1)x^{n+1}(\frac{1}{1-x})+{1 \choose 1}x^{n+1}(xD)(\frac{1}{1-x}))+\sum_{r=0}^k \frac{{k \brace r}x^r}{(1-x)^{k+1}}\\ & =-(xD)^{k-2}({1 \choose 0}(n+1)^2 x^{n+1}(\frac{1}{1-x})+{1 \choose 1}(n+1)x^{n+1}(xD)({\frac{1}{1-x}})\\& \quad + {1 \choose 0}(n+1)x^{n+1}(xD)(\frac{1}{1-x})+{1 \choose 1}x^{n+1}(xD)^2(\frac{1}{1-x})) +\sum_{r=0}^k \frac{{k \brace r}x^r}{(1-x)^{k+1}}\\ & =-(xD)^{k-2}({2 \choose 0}(n+1)^2x^{n+1}(\frac{1}{1-x})+{2 \choose 1}(n+1)x^{n+1}(xD)(\frac{1}{1-x})\\& \quad + {2 \choose 2}x^{n+1}(xD)^2(\frac{1}{1-x}))+\sum_{r=0}^k \frac{{k \brace r}x^r}{(1-x)^{k+1}}\\ & =\cdots\\ & =-\sum_{r=0}^k{k \choose r}(n+1)^{k-r}(xD)^r(\frac{1}{1-x})+\sum_{r=0}^k \frac{{k \choose r}x^r}{(1-x)^{k+1}}\\ & =-x^{n+1}\sum_{r=0}^k{k \choose r}(n+1)^{k-r}\sum_{m=0}^r\frac{{k \choose m}x^m}{(1-x)^{m+1}}+\sum_{r=0}^k \frac{{k \choose r}x^r}{(1-x)^{k+1}}。\tag*{$\Box$} \end{align*}

註: 在 Hsu 與 Shiue 中有給出類似的證明。

3. ${n \brace k}$ 與 $n$ 維三角數的關聯

本節之目的是說明 Eulerian數與 $n$ 維三角數 的關聯。 首先, 我們先介紹何謂 $n$ 維三角數。 像商家平常賣水果一般會先將水果排成一排, 形成一條線的樣子, 這樣就是一維的三角數。 之後排不夠我們會排第二、三排等, 形成平面的樣子, 這就是二維的三角數, 然而水果還是很多我們就會將它疊到原本第一及第二排的上面依序排下去, 形成立體的樣子, 這就是三維的三角數, 依此類推可以推到 $n$ 維的三角數。 以數學式子來表示則推出以下定理。

定義1. 令 $t_{n}^k$ 代表每邊為 $n$ 的 $k$ 維三角數, $$t_{n}^k=t_{n}^{k-1}+t_{n-1}^{k-1}+\cdots+t_{2}^{k-1}+t_{1}^{k-1}\mbox{, }$$其中$t_{n}^1=n$, 其堆疊的方式如下圖。

觀察 $t_{n}^k~(k=1,2,\ldots)$ 的值: \begin{align*} t_{n}^1 &= n={n \choose 1}\\ t_{n}^2 &= 1+2+\cdots+n=\sum_{k=0}^n {k \choose 1}=\frac{n(n+1)}{2!}={n+1 \choose 2}\\ t_{n}^3 &= (1+2+\cdots+n)+(1+2+\cdots+n-1)+\cdots+(1+2)+(1)\\ &=t_{n}^2+t_{n-1}^2+\cdots+t_{2}^2+t_{1}^2\\ &=\sum_{k=0}^n {k+1 \choose 2}=\frac{n(n+1)(n+2)}{3!}={n+2 \choose 3}\\ t_{n}^4 &= t_{n}^3+t_{n-1}^3+\cdots+t_{2}^3+t_{1}^3 \\ &=\sum_{k=0}^n {k+2 \choose 3}=\frac{n(n+1)(n+2)(n+3)}{4!}={n+3 \choose 4}\\ & \hspace{0.5em}\vdots\\ t_{n}^k &=t_{n}^{k-1}+t_{n-1}^{k-1}+\cdots+t_{2}^{k-1}+t_{1}^{k-1}\\ &=\sum_{r=0}^n {n+k \choose k-1}=\frac{n(n+1)(n+2)\cdots(n+k-1)}{k!}={n+k-1 \choose k}\mbox{ 。} \end{align*} 由上面式子我們可以得到以下定理。

定理4. $$t_{n}^k={n+k-1 \choose k}\mbox{ 。}$$ 由定理4我們發現三角數有以下性質。

性質1. $$t_{n}^k=t_{n-1}^k+t_{n}^{k-1}。$$

證明： $$ t_{n}^k={n+k-1 \choose k}={n+k-2 \choose k}+{n+k-2 \choose k-1}=t_{n-1}^k+t_{n}^{k-1}。\tag*{$\Box$} $$

性質2. $$x^n=\sum_{i=0}^n {n \brace i}t_{x+1-i}^n。$$

證明： $$x^n =\sum_{i=0}^n{n \brace i}{n+x-i \choose n}\\$$ 又$$t_{x+1-i}^n={x+1-i+n-1 \choose n}={n+x-i \choose n}$$ 所以可推得$$x^n=\sum_{i=0}^n {n \brace i}t_{x+1-i}^n。\tag*{$\Box$}$$

接著我們藉由觀察以下的圖來找出規律。

圖 6 和圖 7 為立體圖, 我們將前面的圖疊加在後面的圖後就可以發現我們所說的三角數, 我們會發現當我們從 $k^n$ 到 $(k+1)^n$ 時就相當於在往下多一層而上面不變, 而從圖 5 到圖 6 我們會發現其三角數的維度會增加 1, 且其係數恰為 Eulerian 數, 確實與性質 2 相同。

註： 另外圖7為何是這樣分割, 請查閱。

另外我們也發現三角數與差分 $\bigtriangleup h$ 也有關係, 差分 $\bigtriangleup h$ 如下定義： 定義2. $$\bigtriangleup f(x)=f(x)-f(x-1)$$ $${\bigtriangleup}^{k+1} f(x)={\bigtriangleup}^k f(x)-{\bigtriangleup}^k f(x-1)$$

令 $h_{k}=k^n$, 則 \begin{eqnarray*} \bigtriangleup h_{k} &=&k^n-(k-1)^n\\ {\bigtriangleup}^2 h_{k} &=&\bigtriangleup (\bigtriangleup h_{k})=\bigtriangleup h_{k}-\bigtriangleup h_{k-1}=(k^n-(k-1)^n)-((k-1)^n-(k-2)^n)\\& =&k^n+(k-2)^n\\ &\vdots&\\ {\bigtriangleup}^l h_{k} &=&{\bigtriangleup}^{l-1} h_{k}-{\bigtriangleup}^{l-1} h_{k-1} \end{eqnarray*}

因此由性質1及性質2我們可以得到其差分表。 $$\begin{array}{cccccc} k^n & \bigtriangleup h & {\bigtriangleup}^2 h & {\bigtriangleup}^3 h & {\bigtriangleup}^4 h & \ldots \\ 1^n=\sum_{i=0}^n {n \brace i}t_{2-i}^n & & & & & \\ & \sum_{i=0}^n {n \brace i}t_{3-i}^{n-1} & & & & \\ 2^n=\sum_{i=0}^n {n \brace i}t_{3-i}^n & & \sum_{i=0}^n {n \brace i}t_{4-i}^{n-2} & & & \\ & \sum_{i=0}^n {n \brace i}t_{4-i}^{n-1} & & \sum_{i=0}^n {n \brace i}t_{5-i}^{n-3} & & \\ 3^n=\sum_{i=0}^n {n \brace i}t_{4-i}^n & & \sum_{i=0}^n {n \brace i}t_{5-i}^{n-2} & & \sum_{i=0}^n {n \brace i}t_{6-i}^{n-4} & \\ & \sum_{i=0}^n {n \brace i}t_{5-i}^{n-1} & & \sum_{i=0}^n {n \brace i}t_{6-i}^{n-3} & & \\ 4^n=\sum_{i=0}^n {n \brace i}t_{5-i}^n & & \sum_{i=0}^n {n \brace i}t_{6-i}^{n-2} & & \sum_{i=0}^n {n \brace i}t_{7-i}^{n-4} & \\ & \sum_{i=0}^n {n \brace i}t_{6-i}^{n-1} & & \sum_{i=0}^n {n \brace i}t_{7-i}^{n-3} & & \\ 5^n=\sum_{i=0}^n {n \brace i}t_{6-i}^n & & \sum_{i=0}^n {n \brace i}t_{7-i}^{n-2} & & \sum_{i=0}^n {n \brace i}t_{8-i}^{n-4} & \\ \vdots & \vdots & \vdots & \vdots &\vdots &\vdots \\ (k\!-\!1)^n=\sum_{i=0}^n {n \brace i}t_{k-i}^n & & \sum_{i=0}^n {n \brace i}t_{k+1-i}^{n-2} & & & \\ & \sum_{i=0}^n {n \brace i}t_{k+1-i}^{n-1} & & & & \\ k^n=\sum_{i=0}^n {n \brace i}t_{k+1-i}^n & & & & & \\ \end{array}$$ 從而發現以下定理。

定理5. 若$h_{k}=k^n$ $${\bigtriangleup}^l h_{k}=\sum_{i=0}^n {n \brace i}t_{k-i+1}^{n-l}=\sum_{i=0}^n {n \brace i}{n-l+k-i \choose k-i+1}$$

證明： 我們將利用數學歸納法來證明。 當$l=1$時, \begin{align*} {\bigtriangleup}^1 h_{x} &=x^n-(x-1)^n=\sum_{i=0}^n{n \brace i}t_{x+1-i}^n-\sum_{i=0}^n{n \brace i}t_{x-i}^n=\sum_{i=0}^n{n \brace i}t_{x+1-i}^{n-1}\mbox{ 成立。} \end{align*} 假設$l=a$時, $${\bigtriangleup}^a h_{k}=\sum_{i=0}^n {n \brace i}t_{k-i+1}^{n-a}\mbox{ 成立。}$$ 則當$l=a+1$時, \begin{align*} {\bigtriangleup}^{a+1} h_{k} &=\bigtriangleup({\bigtriangleup^{a}} h_{k})\\ &=\sum_{i=0}^n {n \brace i}t_{k-i+1}^{n-a}-\sum_{i=0}^n {n\brace i}t_{k-i}^{n-a}\\ &=\sum_{i=0}^n {n \brace i}(t_{k-i+1}^{n-a}-t_{k-i}^{n-a})\\ &=\sum_{i=0}^n {n \brace i}t_{k-i+1}^{n-(a+1)} \mbox{ 成立。} \end{align*} 由數學歸納法原理可知$${\bigtriangleup}^l h_{k}=\sum_{i=0}^n {n \brace i}t_{k-i+1}^{n-l}\mbox{ 。}\tag*{$\Box$}$$

4. ${n \brace k}$ 與 Stirling 數的關聯

Stirling 數 有分為第一類 $s(n,k)$ 跟第二類 $S(n,k)$ ,分別由下式定義 \begin{align} \mbox{第一類: }&[x]_{n}=\sum_{k=0}^ns(n,k)x^k, \hskip 6cm~\\ \mbox{第二類: }&x^n=\sum_{k=0}^nS(n,k)[x]_k, \end{align} 其中$[x]_{k}=x(x-1)(x-2)\cdots(x-k+1)$, $[x]_{0}=1。$
第二類Stirling數具有以下性質 \begin{align} \sum_{k=0}^\infty k^n x^k &= \sum_{k=0}^{n} k!S(n,k)\frac{x^k}{(1-x)^{k+1}}, \\ S(p,k) &= kS(p-1,k)+S(p-1,k-1)。 \end{align} 其證明可分別參閱 Gould 和 Comtet。
此節我們想要尋找 Stirlng 數與 Eulerian 數的關係。

定理6. 對任意正整數$n$有 $$\sum_{k=0}^n 2^{n-k}{n \brace k} =\sum_{k=0}^n S(n,k)k!。$$

證明： 由(1)與(4)得 $$\sum_{k=0}^n {n \brace k} \frac{x^k}{(1-x)^{n+1}} = \sum_{k=0}^\infty k^n x^k=\sum_{k=0}^{n} k!S(n,k)\frac{x^k}{(1-x)^{k+1}}, $$ 可推得 $$\sum_{k=0}^n {n \brace k} x^k = \sum_{k=0}^n k!S(n,k)x^k(1-x)^{n-k}。$$ 當 $x=\frac{1}{2}$ 時 $$\sum_{k=0}^n {n \brace k} (\frac{1}{2})^k = \sum_{k=0}^n k!S(n,k)(\frac{1}{2})^k (\frac{1}{2})^{n-k} =\sum_{k=0}^n k!S(n,k)(\frac{1}{2})^n, $$ 等式兩邊同乘 $2^n$ $$\sum_{k=0}^n{n \brace k}2^{n-k}=\sum_{k=0}^n k!S(n,k)。\tag*{$\Box$}$$

例4. 當 $n=3$ 時, \begin{align*} \sum_{k=0}^3 {3 \brace k}2^{3-k}&={3 \brace 0}2^{3}+{3 \brace 1}2^{2}+{3 \brace 2}2^1+{3 \brace 3}2^0=1 \times 4+4 \times 2+1 \times 1=13\\ &=\sum_{k=0}^3 k!S(3,k)=0!S(3,0)+1!S(3,1)+2!S(3,2)+3!S(3,3)\\ &=1+2 \times 3+6=13。 \end{align*} 由上面定理 6 可反推得以下定理。

定理7. $$n!=\sum_{j=0}^n \sum_{k=0}^j (-1)^{n+j} 2^{j-k} {j \brace k}s(n,j), $$ 其中$s(n,j)$為Stirling數第一型。

證明： 由定理6可得知, $$\sum_{k=0}^n k!S(n,k)=\sum_{k=0}^n {n \brace k} 2^{n-k}。$$ 其矩陣式為 $$ \left( \begin{array}{ccccc} 1 & 0 & 0 & \ldots & 0 \\ 0 & S(1,1) & 0 & \ldots & 0\\ 0 & S(2,1) & S(2,2) & \ldots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & S(n,1) & S(n,2) & \ldots & S(n,n)\end{array} \right) \left( \begin{array}{c} 0!\\ 1!\\ 2!\\ \vdots\\ n!\end{array}\right) =\left( \begin{array}{c} 1\\ \sum_{k=0}^1{1 \brace k}2^{1-k}\\ \sum_{k=0}^2{2 \brace k}2^{2-k}\\ \vdots \\ \sum_{k=0}^n{n \brace k}2^{n-k} \end{array}\right)$$ 由可知上式中的第二類Stirling矩陣之反矩陣為 $$ \left( \begin{array}{ccccc} 1 & 0 & 0 & \ldots & 0 \\ 0 & s(1,1) & 0 & \ldots & 0\\ 0 & s(2,1) & s(2,2) & \ldots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & s(n,1) & s(n,2) & \ldots & s(n,n)\end{array} \right)$$ 故兩邊同乘上反矩陣後可得 $$\left( \begin{array}{c} 0!\\ 1!\\ 2!\\ \vdots\\ n!\end{array}\right) =\left( \begin{array}{ccccc} 1 & 0 & 0 & \ldots & 0 \\ 0 & s(1,1) & 0 & \ldots & 0\\ 0 & s(2,1) & s(2,2) & \ldots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & s(n,1) & s(n,2) & \ldots & s(n,n)\end{array} \right) \left( \begin{array}{c} 1\\ \sum_{k=0}^1{1 \brace k}2^{1-k}\\ \sum_{k=0}^2{2 \brace k}2^{2-k}\\ \vdots \\ \sum_{k=0}^n{n \brace k}2^{n-k} \end{array}\right)\mbox{ , }$$ 比較矩陣內的元素可得 $$n! = \sum_{j=1}^n s(n,j)\sum_{k=0}^j {j \brace k} 2^{j-k} = \sum_{j=1}^n \sum_{k=0}^j 2^{j-k}{j \brace k}s(n,j)\mbox{ 。}$$ 又我們已知$$n!=\sum_{k=0}^n {n \brace k}, $$ 因此可得 $$n!=\sum_{k=0}^n {n \brace k}=\sum_{j=1}^n \sum_{k=0}^j 2^{j-k}{j \brace k}s(n,j)。\tag*{$\Box$}$$

例5. 當 $n=3$ 時, \begin{eqnarray*} 3!&=&\sum_{k=0}^3 {3 \brace k}={3 \brace 0}+{3 \brace 1}+{3 \brace 2}+{3 \brace 3}=6\\ &=&\sum_{j=1}^3 \sum_{k=0}^j 2^{j-k} {j \brace k}s(3,j)=\sum{k=0}^1 2^{1-k} {1 \brace k}s(3,1)\\ &&+\sum_{k=0}^2 2^{2-k} {2 \brace k}s(3,2)+\sum{k=0}^2 2^{3-k} {3 \brace k}s(3,3)\\ &=&2^{1-0} {1 \brace 0}s(3,1)+2^{1-1} {1 \brace 1}s(3,1)+2^{2-0} {2 \brace 0}s(3,2)+2^{2-1} {2 \brace 1}s(3,2)\\ &&+2^{2-2} {2 \brace 2}s(3,2)+2^{3-0} {3 \brace 0}s(3,3)+2^{3-1} {3 \brace 1}s(3,3)+2^{3-2} {3 \brace 2}s(3,3)\\ &&+2^{3-3} {3 \brace 3}s(3,3)\\ &=&0+1\times 2+0+2 \times (-3)+1 \times (-3)+0+4 \times 1+2 \times 4+1=6。 \end{eqnarray*} 引理2. $$\sum_{k=0}^n k^m =\sum_{r=0}^n r!S(m,r){n+1 \choose r+1}。$$

證明： 由 (4) 可知 $$\sum_{r=0}^{\infty} r^m x^r=\sum_{r=0}^n r!S(m,r)\frac{x^r}{(1-x)^{r+1}}, $$ 2邊同乘$\frac{1}{1-x}$ \begin{align*} \frac{1}{1-x}\sum_{r=0}^{\infty} r^m x^r & =\sum_{r=0}^n r!S(m,r) \frac{x^r}{(1-x)^{r+2}}\\ &= \sum_{r=0}^n r!S(m,r)x^r \sum_{t=0}^{\infty} {t+r+1 \choose t} x^t。 \end{align*} 我們取兩邊 $x^n$ 的係數 \begin{align*} \sum_{k=0}^n k^m &= \sum_{r=0}^n r!S(m,r){n-r+r+1 \choose n-r}\\ & =\sum_{r=0}^n r!S(m,r){n+1 \choose n-r}\\ & =\sum_{r=0}^n r!S(m,r){n+1 \choose r+1}。\tag*{$\Box$} \end{align*}

註: 在中也證明了引理2, 但其方法與本文不同。

我們導出兩個第二類 Stirling 數與 Eulerian數的關係式。定理八將 Stirling 數用 Eulerian 數表示, 而定理九將 Eulerian 數用 Stirling數表示。

定理8. $$S(m,n)=\frac{1}{n!} \sum_{j=1}^n \sum_{r=0}^j (-1)^{n+j}{n \choose j}{m \brace r}{n+m+1-r \choose n-r}。$$

證明： 由引理2和定理1可推得 $$\sum_{r=0}^n r!S(m,r){n+1 \choose r+1}=\sum_{r=0}^n{m \brace r}{n+m+1-r \choose n-r}。$$ 將其以矩陣形式表示如下 $$\left( \begin{array}{ccccc} {0 \choose 0} & 0 & 0 & \ldots & 0 \\ {1 \choose 0} & {1 \choose 1} & 0 & \ldots & 0\\ {2 \choose 0} & {2 \choose 1} & {2 \choose 2} & \ldots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ {n+1 \choose 0} & {n+1 \choose 1} & {n+1 \choose 2} & \ldots & {n+1 \choose n+1}\end{array} \right) \left( \begin{array}{c} 0\\ 0!S(m,0)\\ 1!S(m,1)\\ \vdots\\ n!S(m,n)\end{array}\right) =\left( \begin{array}{c} 0\\ 0\\ \sum_{r=0}^1{m \brace r}{1+m+1-r \choose 1-r}\\ \vdots\\ \sum_{r=0}^n{m \brace r}{n+m+1-r \choose n-r} \end{array}\right) $$ 由二項式定理可知上式中的 ${n \choose k}$ 矩陣之反矩陣 為 $$\left( \begin{array}{cccc} {0 \choose 0} & 0 & \ldots & 0 \\ -{1 \choose 0} & {1 \choose 1} & \ldots & 0\\ {2 \choose 0} & -{2 \choose 1} & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots\\ (-1)^{n+0}{n+1 \choose 0} & (-1)^{n+1}{n+1 \choose 1} & \ldots & (-1)^{2n+1}{n+1 \choose n+1} \end{array} \right)。$$ 因此 \begin{eqnarray*} \left( \begin{array}{c} 0\\ 0!S(m,0)\\ 1!S(m,1)\\ \vdots\\ n!S(m,n)\end{array}\right) &=&\left( \begin{array}{ccccc} {0 \choose 0} & 0 & 0 & \ldots & 0 \\ -{1 \choose 0} & {1 \choose 1} & 0 & \ldots & 0\\ {2 \choose 0} & -{2 \choose 1} & {2 \choose 2} & \ldots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ (-1)^{n+0}{n+1 \choose 0} & (-1)^{n+1}{n+1 \choose 1} & (-1)^{n+1}{n+1 \choose 2} & \ldots & (-1)^{2n+1}{n+1 \choose n+1} \end{array} \right)\\ &&\times\left( \begin{array}{c} 0\\ 0\\ \sum_{r=0}^1{m \brace r}{1+m+1-r \choose 1-r}\\ \vdots\\ \sum_{r=0}^n{m \brace r}{n+m+1-r \choose n-r} \end{array}\right)。 \end{eqnarray*} 可推得 \begin{align*} n!S(m,n)& = \sum_{j=1}^n (-1)^{n+j}{n \choose j}\sum_{r=0}^j {m \brace r}{n+m+1-r \choose n-r}\\ S(m,n) &= \frac{1}{n!}\sum_{j=1}^n (-1)^{n+j}{n \choose j}\sum_{r=0}^j {m \brace r}{n+m+1-r \choose n-r}\\ &= \frac{1}{n!}\sum_{j=1}^n \sum_{r=0}^j (-1)^{n+j}{n \choose j}{n+m+1-r \choose n-r}{m \brace r}。\tag*{$\Box$} \end{align*}

引理3. 令 $xD=x(\frac{d}{dx})$ 可推得$$(xD)^m=\sum_{k=0}^m S(m,k)x^kD^k$$

證明： 我們利用數學歸納法來證明。
當 $m=1$ 時, $$xD=\sum_{k=0}^1 S(1,k)xD=S(1,0)xD+S(1,1)xD=xD\mbox{成立。}$$ 設 $m=n$ 時, $$(xD)^n=\sum_{k=0}^n S(n,k)x^kD^k\mbox{成立。}$$ 則 $m=n+1$ 時, \begin{align*} (xD)^{n+1}&=(xD)(xD)^n=xD\sum_{k=0}^n S(n,k)x^kD^k\\ &=\sum_{k=0}^n S(n,k)kx^kD^k+\sum_{k=0}^n S(n,k)x^{k+1}D^{k+1}\\ &=\sum_{k=0}^{n+1} S(n,k)kx^kD^k+\sum_{k=1}^{n+1}S(n,k-1)x^kD^k=\sum_{k=0}^{n+1}S(n+1,k)x^kD^k。\tag*{$\Box$} \end{align*}

引理4. $$\sum_{k=0}^n{s+k \choose k}{n-k \choose m}={s+n+1 \choose n-m}$$

證明： 當 $n=1$ 時, $$\mbox{討論}{s \choose 0}{1 \choose m}+{s+1 \choose 1}{0 \choose m}\mbox{是否等於}{s+2 \choose 1-m}$$

• 當 $m=0$ 時, $${s \choose 0}{1 \choose 0}+{s+1 \choose 1}{0 \choose 0}=s+2={s+2 \choose 1}$$
• 當 $m=1$ 時, $${s \choose 0}{1 \choose 1}+{s+1 \choose 1}{0 \choose 1}=1={s+2 \choose 1-1}$$
• 當 $m\geqslant2$ 時, $${s \choose 0}{1 \choose m}+{s+1 \choose 1}{0 \choose m}=0={s+2 \choose 1-m}$$ 因此可知 $n=1$ 是對的。

設 $n=h$ 時, $$\sum_{k=0}^h{s+k \choose k}{h-k \choose m}={s+h+1 \choose h-m}\mbox{成立。}$$ 則 $n=h+1 $時, \begin{eqnarray*} \sum_{k=0}^{h+1}{s+k \choose k}{h+1-k \choose m}&=&\sum_{k=0}^{h}{s+k \choose k}({h-k \choose m}+{h-k \choose m-1})\\ &&+{s+h+1 \choose h+1}{h+1-h-1 \choose m}\\ &=&{s+h+1 \choose h-m}+{s+h+1 \choose h-m-1}={s+h+2 \choose h-m}\ \mbox{成立。} \end{eqnarray*} 由數學歸納法原理得知 $$\sum_{k=0}^n{s+k \choose k}{n-k \choose m}={s+n+1 \choose n-m}\tag*{$\Box$}$$

定理9. \begin{align*} {n \brace i}=\sum_{k=0}^n (-1)^{i-k}{n-k \choose i-k}k!S(n,k)。 \end{align*}

證明： 由上面引理3可得 \begin{eqnarray*}(xD)^n(\frac{1}{1-x})&=&\sum_{k=0}^n S(n,k)x^k\sum_{n=0}^{\infty}\frac{(h+k)!}{h!}x^h\\ \frac{\sum_{r=0}^{\infty}{n \brace r} x^r}{(1-x)^{n+1}}&=&\sum_{k=0}^n S(n,k)x^k\sum_{n=0}^{\infty}\frac{(h+k)!}{h!}x^k。 \end{eqnarray*} 兩邊同乘 $(1-x)^{n+1}$, \begin{eqnarray*} \sum_{r=0}^{\infty} {n \brace r} x^r & =&\sum_{k=0}^n S(n,k)x^k\sum_{h=0}^{\infty}\frac{(h+k)!}{h!}x^h(1-x)^{n+1}\\ & =&\sum_{k=0}^n S(n,k)x^k\sum_{h=0}^{\infty} \frac{(h+k)!}{h!}x^h \sum_{i=0}^{n+1} {n+1 \choose i}(-1)^i x^i\\ & =&\sum_{k=0}^n \sum_{h=0}^{\infty} \sum_{i=0}^{n+1} S(n,k) \frac{(h+k)!}{h!} {n+1 \choose i}(-1)^i x^{k+h+i}。\\ {\hbox{取兩邊 $x^i$ 項可得, }} {n \brace i}x^i & =& \sum_{k=0}^n S(n,k)x^k \sum_{h=0}^{\infty}\frac{(h+k)!}{h!} x^h{n+1 \choose i-k-h}(-1)^{i-k-h}x^{i-k-h}\\ & =&\sum_{k=0}^n\sum_{h=0}^{\infty}S(n,k)k!{h+k \choose h}{n+1 \choose i-k-h}(-1)^{i-k-h}x^i\\ &=&\sum_{k=0}^nS(n,k)k!\sum_{h=0}^{\infty}{h+k \choose h}{i-h-k-n-2 \choose -n-2}x^i\\ &=&\sum_{k=0}^nS(n,k)k!\sum_{h=0}^{i-k-n-2}{h+k \choose h}{i-h-k-n-2 \choose -n-2}x^i\\ \end{eqnarray*} 由引理 4 可知 \begin{eqnarray*} &=&\sum_{k=0}^nS(n,k)k!{i-n-1 \choose i-k}x^i\\ &=&\sum_{k=0}^nS(n,k)k!(-1)^{i-k}{n-k \choose i-k}x^i \end{eqnarray*} 因此可得出 $${n \brace i}=\sum_{k=0}^n (-1)^{i-k}{n-k \choose i-k}k!S(n,k)。$$

例6. 當$n=3$且$i=2$時, \begin{align*} {3 \brace 2}&=\sum_{k=0}^3 (-1)^{2-k}{3-k \choose 2-k}k!S(3,k)\\ &=(-1)^2{3 \choose 2}0!S(3,0)+(-1)^1{2 \choose 1}1!S(3,1)+(-1)^0{1 \choose 0}2!S(3,2)\\ &=0+(-2)+6=4 \end{align*} 當$n=4$且$i=2$時, \begin{align*} {4 \brace 2}&=\sum_{k=0}^4 (-1)^{2-k}{4-k \choose 2-k}k!S(4,k)\\ &=(-1)^2{4 \choose 2}0!S(4,0)+(-1)^1{3 \choose 1}1!S(4,1)+(-1)^0{2 \choose 0}2!S(4,2)\\ &=0+(-3)+14=11 \end{align*}

最後, 在前面的第三節裡我們提到三角數與Eulerian的關係, 我們將用性質2與 Stirling數的定義來推得Stirling數與三角數的關係

定理10. $$S(n,k)=\sum_{j=0}^x \sum_{i=0}^n (-1)^{x+j} {x \choose j}{n \brace i} t_{j+1-i}^n$$

證明： 由性質2與Stirling數的定義可推得 $$x^n=\sum_{i=0}^n {n \brace i}t_{x+1-i}^n =\sum_{k=0}^n S(n,k)k!{x \choose k}。$$ 將其以矩陣形式表示如下 $$\left( \begin{array}{ccccccc} {0 \choose 0} & 0 & 0 & \ldots & 0 & \ldots & 0 \\ {1 \choose 0} & {1 \choose 1} & 0 & \ldots & 0 & \ldots & 0\\ {2 \choose 0} & {2 \choose 1} & {2 \choose 2} & \ldots & 0 & \ldots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \ldots & \vdots\\ {x \choose 0} & {x \choose 1} & {x \choose 2} & \ldots & {x \choose x} & \ldots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \ldots & \vdots\\ {n \choose 0} & {n \choose 1} & {n \choose 2} & \ldots & {n \choose x} & \ldots & {n \choose n}\end{array} \right) \left( \begin{array}{c} 0\\ 0!S(m,0)\\ 1!S(m,1)\\ \vdots\\ x!S(m,x)\\ \vdots\\ n!S(m,n)\end{array}\right) =\left( \begin{array}{c} \sum_{i=0}^n {n \brace i}t_{1-i}^n\\ \sum_{i=0}^n {n \brace i}t_{2-i}^n\\ \sum_{i=0}^n {n \brace i}t_{3-i}^n\\ \vdots\\ \sum_{i=0}^n {n \brace i}t_{x+1-i}^n\\ \vdots\\ \sum_{i=0}^n {n \brace i}t_{n+1-i}^n\\ \end{array}\right) $$ 由二項式定理可知上式中的${n \choose k}$矩陣之反矩陣為 $$\left( \begin{array}{cccc} {0 \choose 0} & 0 & \ldots & 0 \\ -{1 \choose 0} & {1 \choose 1} & \ldots & 0\\ {2 \choose 0} & -{2 \choose 1} & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots\\ (-1)^{x+0}{x \choose 0} & (-1)^{x+1}{x \choose 1} & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots\\ (-1)^{n+0}{n \choose 0} & (-1)^{n}{n \choose 1} & \ldots & (-1)^{2n}{n \choose n} \end{array} \right)。$$ 因此 \begin{eqnarray*}\left( \begin{array}{c} 0\\ 0!S(m,0)\\ 1!S(m,1)\\ \vdots\\ x!S(m,x)\\ \vdots\\ n!S(m,n)\end{array}\right) &=&\left( \begin{array}{ccccc} {0 \choose 0} & 0 & 0 & \ldots & 0 \\ -{1 \choose 0} & {1 \choose 1} & 0 & \ldots & 0\\ {2 \choose 0} & -{2 \choose 1} & {2 \choose 2} & \ldots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ (-1)^{x}{x \choose 0} & (-1)^{x+1}{x \choose 1} & (-1)^{x+2}{x \choose 2} & \ldots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ (-1)^{n}{n \choose 0} & (-1)^{n+1}{n \choose 1} & (-1)^{n+2}{n \choose 2} & \ldots & (-1)^{2n}{n \choose n} \end{array} \right)\\ &&\times\left( \begin{array}{c} \sum_{i=0}^n {n \brace i}t_{1-i}^n\\ \sum_{i=0}^n {n \brace i}t_{2-i}^n\\ \sum_{i=0}^n {n \brace i}t_{3-i}^n\\ \vdots\\ \sum_{i=0}^n {n \brace i}t_{x+1-i}^n\\ \vdots\\ \sum_{i=0}^n {n \brace i}t_{n+1-i}^n\\ \end{array}\right)。 \end{eqnarray*} 可推得 \begin{align*} x!S(m,x)& = \sum_{j=0}^x (-1)^{x+j}{x \choose j}\sum_{i=0}^n {n \brace i}t_{j+1-i}^i\\ S(m,x) &= \frac{1}{x!}\sum_{j=0}^x (-1)^{x+j}{x \choose j}\sum_{r=0}^n {n \brace i}t_{j+1-i}^i\\ &= \frac{1}{x!}\sum_{j=0}^x \sum_{r=0}^n (-1)^{x+j}{x \choose j} {n \brace i}t_{j+1-i}^i。\tag*{$\Box$} \end{align*}

例7. 當$n=4$且$x=2$時, \begin{align*} S(4,2) &= 7\\ &=\frac{1}{2!}\sum_{j=0}^2 (-1)^{2+j}{2 \choose j} \sum_{i=0}^4 t_{j+1-i}^4\\ &=\frac{1}{2}((-1)^2{2 \choose 0}\sum_{i=0}^4 t_{1-i}^4+(-1)^3{2 \choose 1}\sum_{i=0}^4 t_{2-i}^4+(-1)^4{2 \choose 2}\sum_{i=0}^4 t_{3-i}^4)\\ &=\frac{1}{2}((-2)({4 \brace 1}t_{1}^4)+({4 \brace 1}t_{2}^4+{4 \brace 2}t_{1}^4))\\ &=\frac{1}{2}(-2+5+11)=7 \end{align*}

致謝

感謝中研院數學所提供筆者在暑期的時候來參與組合數學與圖論專題的暑期研習，使筆者有機會與美國回來的薛昭雄教授學習與研究。 非常感謝薛昭雄教授的大力指導與協助，另外還要感謝廖信傑和孫維良的幫忙，筆者才能完成此篇文章。

參考資料

---本文作者就讀國立交通大學應用數學所---