スターリング数の相互関係と一般項
はじめに
この記事ではスターリング数の相互関係
\begin{align}
\S n{n-k}&=\sum^k_{m=0}\binom{k-n}{k+m}\binom{n+k}{n+m}\s{m+k}m\\
\s n{n-k}&=\sum^k_{m=0}\binom{k-n}{k+m}\binom{n+k}{n+m}\S{m+k}m
\end{align}
や一般項の公式
\begin{align}
\s nk&=\sum^k_{j=0}(-1)^{k-j}\frac{j^n}{j!(k-j)!}\\
\S nk
&=\sum^{2n-k}_{m=n}\binom{m-1}{k-1}\binom{2n-k}m\sum^{m-n}_{j=0}(-1)^{n-k+j}\frac{j^{m-k}}{j!(m-n-j)!}
\end{align}
についてまとめていきます。
スターリング数
第一種・第二種スターリング数は上昇階乗・下降階乗
\begin{align}
x^{\ol n}&=x(x+1)(x+2)\cdots(x+n-1)\\
x^{\ul n}&=x(x-1)(x-2)\cdots(x-n+1)
\end{align}
と冪乗$x^n$との関係
\begin{align}
x^{\ol n}&=\sum^n_{k=0}\S nkx^k&
x^{\ul x}&=\sum^n_{k=0}(-1)^{n-k}\S nkx^k\\
x^n&=\sum^n_{k=0}\s nkx^{\ul k}&
x^n&=\sum^n_{k=0}(-1)^{n-k}\s nkx^{\ol k}
\end{align}
に現れる係数のことを言い、これらは
\begin{align}
\S{n+1}k&=n\bigg[{n\atop k}\bigg]+\S n{k-1}\\
\s{n+1}k&=k\bigg\{{n\atop k}\bigg\}+\s n{k-1}
\end{align}
という漸化式を満たします。
母関数
まずスターリング数の母関数の一種を求めておきます。
$$(1+t)^x=\sum_{0\leq k\leq n}(-1)^{n-k}\S nkx^k\frac{t^n}{n!}$$
$$\frac{d^n}{dt^n}(1+t)^x=x^{\ul n}(1+t)^{x-n}$$
に注意すると
\begin{align}
(1+t)^x
&=\sum^\infty_{n=0}x^{\ul n}\frac{t^n}{n!}\\
&=\sum^\infty_{n=0}\l(\sum^n_{k=0}(-1)^{n-k}\S nkx^k\r)\frac{t^n}{n!}
\end{align}
とわかる。
$$e^{x(e^t-1)}=\sum_{0\leq k\leq n}\s nkx^k\frac{t^n}{n!}$$
\begin{align}
j^n
&=\sum^n_{k=0}\s nkj^{\ul k}\\
&=\sum^n_{k=0}\s nk\frac{j!}{(j-k)!}
\end{align}
に注意すると
\begin{align}
e^x\sum^\infty_{n=0}\l(\sum^n_{k=0}\s nkx^k\r)\frac{t^n}{n!}
&=\sum^\infty_{n=0}\l(\sum^n_{k=0}\s nk\sum^\infty_{j=0}\frac{x^{j+k}}{j!}\r)\frac{t^n}{n!}\\
&=\sum^\infty_{n=0}\l(\sum^n_{k=0}\s nk\sum^\infty_{j=k}\frac{x^j}{(j-k)!}\r)\frac{t^n}{n!}\\
&=\sum^\infty_{n=0}\l(\sum^\infty_{j=0}\l(\sum^n_{k=0}\s nk\frac{j!}{(j-k)!}\r)\frac{x^j}{j!}\r)\frac{t^n}{n!}\\
&=\sum^\infty_{j=0}\l(\sum^\infty_{n=0}j^n\frac{t^n}{n!}\r)\frac{x^j}{j!}\\
&=\sum^\infty_{j=0}e^{jt}\frac{x^j}{j!}\\
&=e^{xe^t}
\end{align}
が成り立つのでこの両辺を$e^x$で割ることで主張を得る。
\begin{align} \l(\frac{\log(1+t)}t\r)^k&=k!\sum^\infty_{n=k}(-1)^{n-k}\S nk\frac{t^{n-k}}{n!}\\ \l(\frac{e^t-1}t\r)^k&=k!\sum^\infty_{n=k}\s nk\frac{t^{n-k}}{n!}\\ \end{align}
\begin{align}
(1+t)^x&=e^{x\log(1+t)}\\
&=\sum^\infty_{k=0}x^k\farc{(\log(1+t))^k}{k!}\\
e^{x(e^t-1)}
&=\sum^\infty_{k=0}x^k\farc{(e^t-1)^k}{k!}\\
\end{align}
に注意するとわかる。
第二種スターリング数の一般項
ちなみに第二種スターリング数の一般項については母関数から直接求めることができます。
$$\s nk=\sum^k_{j=0}(-1)^{k-j}\frac{j^n}{j!(k-j)!}$$
\begin{align}
e^{x(e^t-1)}
&=\sum^\infty_{k=0}\frac{x^k}{k!}(e^t-1)^k\\
&=\sum^\infty_{k=0}\frac{x^k}{k!}\sum^k_{j=0}(-1)^{k-j}\binom kje^{jt}\\
&=\sum^\infty_{k=0}\frac{x^k}{k!}\sum^k_{j=0}(-1)^{k-j}\binom kj\sum^\infty_{n=0}\frac{(jt)^n}{n!}\\
&=\sum^\infty_{n,k=0}\l(\sum^k_{j=0}(-1)^{k-j}\binom kjj^n\r)\frac{x^k}{k!}\frac{t^n}{n!}\\
\end{align}
より
\begin{align}
\s nk
&=\frac1{k!}\sum^k_{j=0}(-1)^{k-j}\binom kjj^n\\
&=\sum^k_{j=0}(-1)^{k-j}\frac{j^n}{j!(k-j)!}
\end{align}
を得る。
Nörlund多項式
次にスターリング数の母関数と関わりの深いネールント多項式というものについて解説していきます。
$$\l(\frac t{e^t-1}\r)^z=\sum^\infty_{n=0}N_n(z)\frac{t^n}{n!}$$
によって定まる$z$についての多項式$N_n(z)$をネールント多項式と言う。
ネールント多項式は通常$B_n^{(z)}$のように表されますが、ここでは$z$についての多項式という側面を強調するために$N_n(z)$と表すことにします。
ちなみに$B_n^{(z)}$という記法はより一般にベルヌーイ多項式の類似の一つとして
$$\l(\frac t{e^t-1}\r)^ze^{xt}=\sum^\infty_{n=0}B_n^{(z)}(x)\frac{t^n}{n!}$$
という$z$および$x$についての多項式$B_n^{(z)}(x)$を考えていることに起因しています。
漸化式と次数
$$\frac{te^t}{e^t-1}=\sum^\infty_{n=0}\B_n\farc{t^n}{n!}$$
とおくと漸化式
$$N_n(z)=-\frac zn\sum^n_{k=1}\binom nk\B_kN_{n-k}(z)$$
が成り立つ。
\begin{align}
\frac d{dt}\l(\frac t{e^t-1}\r)^z
&=z\l(\frac1t-\frac{e^t}{e^t-1}\r)\l(\frac t{e^t-1}\r)^z\\
&=-\frac zt\l(\farc{te^t}{e^t-1}-1\r)\l(\frac{t}{e^t-1}\r)^z\\
&=-z\l(\sum^\infty_{n=0}\farc{\B_{n+1}}{n+1}\farc{t^n}{(n+1)!}\r)\l(\sum^\infty_{n=0}N_n(z)\frac{t^n}{n!}\r)\\
&=-z\sum^\infty_{n=0}\l(\sum^n_{k=0}\binom nk\farc{\B_{k+1}}{k+1}N_{n-k}(z)\r)\farc{t^n}{n!}
\end{align}
より
$$\frac d{dt}\l(\frac t{e^t-1}\r)^z=\sum^\infty_{n=0}N_{n+1}(z)\farc{t^n}{n!}$$
と係数比較することで
\begin{align}
N_{n+1}(z)
&=-z\sum^n_{k=0}\binom nk\frac{\B_{k+1}}{k+1}N_{n-k}(z)\\
&=-\frac z{n+1}\sum^n_{k=0}\binom{n+1}{k+1}\B_{k+1}N_{n-k}(z)\\
&=-\frac z{n+1}\sum^{n+1}_{k=1}\binom{n+1}k\B_kN_{n-k+1}(z)\\
\end{align}
を得る。
$N_n(z)$は$n$次多項式である。
$n=0$のときは明らかであり、$n\geq1$のときは上の漸化式からわかる。
スターリング数との関係
以下
$$F_z(t)=\l(\frac t{e^t-1}\r)^z$$
とおきます。
$$F_{z+1}(t)e^t=\sum^\infty_{n=0}\l(1-\frac nz\r)N_n(z)\frac{t^n}{n!}$$
\begin{align}
\frac d{dt}F_z(t)
&=z\l(\frac1t-\frac{e^t}{e^t-1}\r)\l(\frac t{e^t-1}\r)^z\\
&=\frac zt(F_z(t)-F_{z+1}(t)e^t)
\end{align}
より
$$F_{z+1}(t)e^t=F_z(t)-\frac tzF'_z(t)$$
が成り立つことに注意するとわかる。
$$\l(\frac{\log(1+t)}t\r)^z=z\sum^\infty_{n=0}\frac{N_n(z+n)}{z+n}\frac{t^n}{n!}$$
$$\l(\frac{\log(1+t)}t\r)^z=F_z(\log(1+t))$$
および
$$\l(1-\frac nz\r)N_n(z)=\frac{n!}{2\pi i}\oint\frac{F_{z+1}(w)e^w}{w^{n+1}}dw$$
に注意して$\z=e^w-1$とおくことで
\begin{align}
\frac{n!}{2\pi i}\oint\frac{F_z(\log(1+\z))}{\z^{n+1}}d\z
&=\frac{n!}{2\pi i}\oint\frac{F_z(w)}{(e^w-1)^{n+1}}e^wdw\\
&=\frac{n!}{2\pi i}\oint\frac{F_{z+n+1}(w)}{w^{n+1}}e^wdw\\
&=\l(1-\frac n{z+n}\r)N_n(z+n)\\
&=\frac z{z+n}N_n(z+n)
\end{align}
を得る。
\begin{align} (-1)^k\S n{n-k}&=\binom{n-1}kN_k(n)\\ \s{n+k}n&=\binom{n+k}kN_k(-n) \end{align}
\begin{align}
\l(\frac{\log(1+t)}t\r)^k
&=k\sum^\infty_{n=0}\frac{N_n(n+k)}{n+k}\frac{t^n}{n!}\\
&=(-1)^nk!\sum^\infty_{n=0}\S{n+k}k\frac{t^n}{(n+k)!}\\
\l(\frac{e^t-1}t\r)^k
&=\sum^\infty_{n=0}N_n(-k)\frac{t^n}{n!}\\
&=k!\sum^\infty_{n=0}\s{n+k}k\frac{t^n}{(n+k)!}\\
\end{align}
より
\begin{align}
(-1)^n\S{n+k}k&=\binom{n+k-1}{k-1}N_n(n+k)\\
\s{n+k}k&=\binom{n+k}kN_n(-k)
\end{align}
がわかるのでこれを適当に変形することで主張を得る。
スターリング数の相互関係
いまスターリング数がネールント多項式によって表せたことから次のような興味深い事実が成り立ちます。
$k$を固定したとき
$$\S n{n-k},\s{n+k}n$$
は$n$についての$2k$次多項式とみなせ、特に多項式として
$$\S{-n}{-n-k}=\s{n+k}n$$
が成り立つ。
定理8より
\begin{align}
\S n{n-k}&=\frac{(1-n)(2-n)\cdots(k-n)}{k!}N_k(n)\\
\s{n+k}n&=\frac{(n+1)(n+2)\cdots(n+k)}{k!}N_k(-n)
\end{align}
が成り立つことからわかる。
そしてこのことを用いることで以下の相互関係が導かれます。
\begin{align} \S n{n-k}&=\sum^k_{m=0}(-1)^{k-m}\binom{n+m-1}{k+m}\binom{n+k}{n+m}\s{m+k}m\\ \s n{n-k}&=\sum^k_{m=0}(-1)^{k-m}\binom{n+m-1}{k+m}\binom{n+k}{n+m}\S{m+k}m \end{align}
$2k$次多項式$f$を
$$f(n)=\S n{n-k}$$
によって定めたとき($k\neq0$において)
$$f(m)=0\qquad(m=0,1,2,\ldots,k)$$
に注意してラグランジュの補間公式を考えることで
\begin{align}
f(n)
&=\sum^k_{m=0}f(-m)\prod^k_{\substack{j=-k\\j\neq m}}\frac{n+j}{-m+j}\\
&=\sum^k_{m=0}(-1)^{k+m}\frac{(n+k)!}{(n+m)(n-k-1)!}\frac1{(k-j)!(k+m)!}f(-m)\\
\S n{n-k}&=\sum^k_{m=0}(-1)^{k+m}\binom{n+m-1}{k+m}\binom{n+k}{n+m}\s{m+k}m
\end{align}
を得る。
同様に
\begin{align}
f(k-n)
&=\sum^k_{m=0}f(k+m)\prod^{2k}_{\substack{j=0\\j\neq k+m}}\frac{(k-n)-j}{k+m-j}\\
&=\sum^k_{m=0}f(k+m)\prod^k_{\substack{j=-k\\j\neq m}}\frac{-n-j}{m-j}\\
\s n{n-k}&=\sum^k_{m=0}(-1)^{k+m}\binom{n+m-1}{k+m}\binom{n+k}{n+m}\S{m+k}m
\end{align}
を得る。
ちなみに
$$(-1)^k\binom{x-1}k=\binom{k-x}k$$
と変形すると
\begin{align}
\S n{n-k}&=\sum^k_{m=0}\binom{k-n}{k+m}\binom{n+k}{n+m}\s{m+k}m\\
\s n{n-k}&=\sum^k_{m=0}\binom{k-n}{k+m}\binom{n+k}{n+m}\S{m+k}m
\end{align}
とも表せます。
\begin{align} \S nk&=\sum^{2n-k}_{m=n}(-1)^{k-m}\binom{m-1}{k-1}\binom{2n-k}m\s{m-k}{m-n}\\ \s nk&=\sum^{2n-k}_{m=n}(-1)^{k-m}\binom{m-1}{k-1}\binom{2n-k}m\S{m-k}{m-n} \end{align}
\begin{align}
\S nk
&=\sum^{n-k}_{m=0}(-1)^{n+m-k}\binom{n+m-1}{n+m-k}\binom{2n-k}{n+m}\s{n+m-k}m\\
&=\sum^{2n-k}_{m=n}(-1)^{k-m}\binom{m-1}{k-1}\binom{2n-k}m\s{m-k}{m-n}
\end{align}
とわかる。
第一種スターリング数の一般項
いま第一種スターリング数が第二種スターリング数を用いて表せたことにより次のような一般項の公式が得られます。
$$\S nk=\sum^{2n-k}_{m=n}\binom{m-1}{k-1}\binom{2n-k}m\sum^{m-n}_{j=0}(-1)^{n-k+j}\frac{j^{m-k}}{j!(m-n-j)!}$$
第二種スターリング数の一般項
$$\s{m-k}{m-n}=\sum^{m-n}_{j=0}(-1)^{m-n-j}\frac{j^{m-k}}{j!(m-n-j)!}$$
から
\begin{align}
\S nk&=\sum^{2n-k}_{m=n}(-1)^{k-m}\binom{m-1}{k-1}\binom{2n-k}m\s{m-k}{m-n}\\
&=\sum^{2n-k}_{m=n}\binom{m-1}{k-1}\binom{2n-k}m\sum^{m-n}_{j=0}(-1)^{n-k+j}\frac{j^{m-k}}{j!(m-n-j)!}
\end{align}
を得る。
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
