38407 Eulerian數的應用

終極密碼

遊戲規則:本遊戲為猜密碼的遊戲。密碼為0到100之間的其中1個整數,電腦會提示密碼的所在範圍,玩家必須在6次之內猜到密碼才能過關。
★ 終極密碼為0到100之間 ★
您共有六次機會

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}。\\ oalign{\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*}

致謝

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

參考資料

K. Bóna, Combinatorics of Permuations, New York, CHAPMAN HALL/CRC, 2004. L. Comtet, Advance combinatorics, Reidel,Dordrecht, 1974. L. Eulerus, Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum [Foundations of differential calculus,with applications to finite analysis and series], Academia imperialis scientiarum Petropolitana;Berolini: Officina Michaelis, 1755. H. W. Gould, Evaluation of sums of convolved powers using Stirling und Eulerian numbers, Fibonacci Quart., 16(1978), 488-497. L. C. Hsu and P. J.-S. Shiue, On certain summation problems and generalizations of Eulerian polynomials and numbers, Discrete Methematics, 204(1999), 237-247. mathrecreation, Triangular Numbers and Euler's Number Triangle,
http://www.mathrecreation.com/2009/01/triangular-numbers-and-eulers-number.html.
J. Worpitzky, Studien über die Bernoulli schen and Eulerschen Zahlen, Journal für die reine und angewandte Mathematik, 94(1883), 203-232.

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