これは何
某本を読みながら木とグラフについて勉強していたら有向非巡回グラフという単語を見かけると同時にこの話を思い出したので、息抜きのつもりでちょっと書いてみようと思いました。ググっても日本語での記事が(多分)なかったのでちょうどいいなと思って書きました。多重ベルヌーイ数という数の一部が組み合わせ的な意味を持っている、という話の紹介をします。P.J.Cameronらの論文の証明を追っていきます。
それ以外の命題はすべて「ベルヌーイ数とゼータ関数」(牧野書店 : 荒川 恒男, 金子 昌信, 伊吹山 知義)という本から引用しています。面白いので買いましょう。
数学に関する予備知識ですが、学部1年程度の知識があれば一応読めるようにはしたつもりです。
グラフ(Graph)とは
グラフ、と言われるとよく学校で習った$xy$平面に描いてある二変数関数の絵とか、棒グラフや線グラフのようなものなど、様々なものをイメージするかと思います。
ですが、ここでいうグラフとは、辺と頂点からなる構造のことを指します。グラフの例を以下にひとつあげておきます。
1~7までの数字が振ってある黒丸を頂点、水色や赤色の線を辺と呼びます。特に赤い辺は矢印になっていますが、これは有向辺と呼ばれています。見ての通り、一つの頂点から何本辺が伸びてもいいし、辺を持たない頂点があってもよいです。
完全二部グラフ(Complete Bipartite Graph)とは
まず二部グラフから定義します。
グラフ$G$が二部グラフであるとは、$G$の頂点集合$V$に対しある分割{ $U$, $W$ }が存在し、各集合内の、どの2頂点間にも辺を持たないようにできるグラフのことである。
同値な言い換えとして2色で塗り分け可能とかもありますね。
特に二部グラフの中で、$U$の任意の頂点と$W$の任意の頂点間に辺がちょうど1本ずつ存在するとき、$G$は完全二部グラフであると言います。
もうちょっと分かりやすく書くと、$|U|=m$, $|W|=n$としたとき、お互いの任意の頂点に向かって辺が1本ずつ伸びているので辺の本数は$mn$になります。このような完全二部グラフを$K_{m,n}$と書いたりします。
以下は完全二部グラフ$K_{2,3}$の例です。どの辺も赤い頂点と青い頂点を結んでいます。
有向非巡回グラフ(Directed Acyclic Graph, DAG)とは
グラフ$G$に閉路がないとき$G$はDAGであるという。
ひとつのグラフの各辺に対して何通りもの向きつけの場合の数があるように、ひとつのグラフ$G$がDAGになるような場合の数も複数あることもあります。
トポロジカルソート
トポロジカルソートを簡単に説明すると、DAGの各頂点に順序を定めることで、$G$の頂点を1列に並べ替えようというものです。Morifolium様の記事に図解や実装例があって分かりやすかったです。
いろいろ書いて消したのですがどんな順序が入っているかだけ紹介して、次に進もうと思います。
DAGであるグラフ$G$の頂点$a,b$について二項関係を、「$a$から$b$への経路が存在するとき、$a\le b$」と定めます。
このときこの順序は以下を満たし、半順序となります。
- 反射律 : $\forall a \in G$に対し、$a\le a$
- 推移律 : $a,b,c\in G$に対し、$a\le b, b\le c\Rightarrow a\le c$
- 反対称律 : $a,b\in G$に対し、$a\le b$かつ$b\le a$ならば$a=b$
反射律 : $a\in G$は移動することなく$a$に到達可能なので成り立つ。
推移律 : $a$から$b$への経路$\rightarrow b$から$c$への経路を辿ることで$a$から$c$へ到達可能なので成り立つ。
反対称律 : $a\neq b$とすると、$a$から$b$への経路を$p_1,b$から$a$への経路を$p_2$としたとき、$p_1\rightarrow p_2$と辿ることでこれはサイクルになってしまう。よって$a=b$
そういうわけで、今回はトポロジカルソートの正当性は認めて進みます。
次は多重ベルヌーイ数の定義に入るために、いくつか準備をします。
ベルヌーイ数 (Bernoulli numbers)
定義 :
ベルヌーイ数$B_n$ $(n = 0, 1, 2...)$を
$\sum_{i=0}^{n}{{n+1}\choose{i}} B_i = n + 1$
で定める。
定義からこれは有理数の列であることが分かりますが、これはよく見るの数列の定義($a_n=n^2+n$のような形)の仕方と違うので困った方もいるかと思います。
このベルヌーイ数のような定義の仕方は「帰納的定義」と呼ばれていて、$B_0$の値から順に求めていきます。
定義に$n=k$を代入した式の中には$B_0$から$B_k$の値が登場するので、$n=0,1,2...$と代入して、順に値を求めていく必要があります。
- $n=0$のとき
$\sum_{i=0}^{0}{{0+1}\choose{i}}B_i={{1}\choose{0}}B_0=B_0=0+1\Rightarrow B_0=1$
- $n=1$のとき
$\sum_{i=0}^{1}{{1+1}\choose{i}}B_i={{2}\choose{0}}B_0+{{2}\choose{1}}B_1=B_0+2B_1=1+2B_1=1+1\Rightarrow B_1=\frac{1}{2}$
- $n=2$のとき
$\sum_{i=0}^{2}{{2+1}\choose{i}}B_i={{3}\choose{0}}B_0+{{3}\choose{1}}B_1+{{3}\choose{2}}B_2=B_0+3B_1+3B_2=1+\frac{3}{2}+3B_2=2+1\Rightarrow B_2=\frac{1}{6}$
- $n=3$のとき....
という感じで求めていきます。
$n$が小さいところからいくつか並べると、
| $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $B_n$ | 1 | $\frac{1}{2}$ | $\frac{1}{6}$ | 0 | $-\frac{1}{30}$ | 0 | $\frac{1}{42}$ | 0 | $-\frac{1}{30}$ | 0 | $\frac{5}{66}$ | 0 | -$\frac{691}{2730}$ |
となっていて、$n$が奇数だとだいたい$B_n=0$な気がしてきます。実際$n \neq 1$な奇数の場合$B_n=0$になりますが、今回の話とは少し逸れるので証明しません。
$B_1=-\frac{1}{2}$ で定義する場合もありますが、今回は上の値を採用します。
またこの定義に対し、形式的冪級数による母関数表示
$\sum_{k=0}^{\infty}B_k\frac{t^k}{k!}=\frac{te^t}{e^t-1}$
を持ちます。
これはおはなしですが、ベルヌーイ数のそもそものモチベーションは自然数のべき乗和を求めたかったことにあります。
$\sum_{i=1}^{n}i = \frac{n(n+1)}{2}$
や、
$\sum_{i=1}^{n}i^2 = \frac{n(n+1)(2n+1)}{6}$
は比較的馴染み深いと思います。$i$ の指数部分を3,4,5...として手計算で公式を求めた方もいるのではないでしょうか。
ベルヌーイは一般の場合(つまり$i^k$ の$i=1$から$i=n$までの和)についてこの和を$n$の多項式で与え、その和公式の係数の一部をベルヌーイ数としました。
他にも色々と面白いのですが、今はこの辺にして次に進みます。
多重ベルヌーイ数(poly-Bernoulli numbers)
ベルヌーイ数の一種の一般化として多重ベルヌーイ数を定義します。
その前に$k \in \mathbb{Z}$に対し形式的冪級数$Li_k(t)$を
$Li_k(t)=\sum_{i=1}^{\infty}\frac{t^i}{i^k}$
で定義します。これに対し、多重ベルヌーイ数を母関数表示により
$\frac{Li_k(1-e^{-t})}{1-e^{-t}}=\sum_{n=0}^{\infty}\mathbb{B}_{n}^{(k)}\frac{t^n}{n!}$
で定義します。
$k$は整数全体を渡っているので、片方のインデックスは負の整数を渡ってもいいことを注意しておきます。
$Li_k(t),e^{-t}$の形式的冪級数の係数は共に有理数であることから、多重ベルヌーイ数も有理数の範囲でおさまることが分かります。
これがベルヌーイ数の一般化になっていることを確かめておきましょう。
$k=1$として$log$のテイラー展開を思い出すことで、
$Li_1(t)=\sum_{i=1}^{\infty}\frac{t^i}{i}=-log(1-t)$
が成り立っていました。したがって多重ベルヌーイ数の定義の左辺に代入することで、
$\frac{Li_1(1-e^{-t})}{1-e^{-t}}=\frac{-log(1-(1-e^{-t}))}{1-e^{-t}}=-\frac{-t}{1-e^{-t}}=\frac{te^t}{e^t-1}$
が成り立つので、これは確かにベルヌーイ数の一般化のひとつであると言えました。
本題
さて、今回のテーマは多重ベルヌーイ数が組み合わせ的な意味を持っているという話でした。
この後示す定理で、$m,n\ge 0$に対して$\mathbb B_{m}^{-n}$が自然数になることが分かります。
なんとなくお気づきかもしれませんが、
完全二部グラフ$K_{m,n}$のDAGの個数が$\mathbb B_{m}^{(-n)}$の値と等しくなります。
数論的なモチベーションから構成した数が、このような(比較的有名な?)グラフのある場合の数を表していることは個人的には大変驚きでした。
これを証明するためにいろいろ準備しなければなりません。そもそも$m,n\ge0$に対して$\mathbb B_{m}^{(-n)}$が自然数になることから非自明なので、多重ベルヌーイ数を組み合わせ的な関数を使って書き直すことで証明に繋げていこうと思います。
そこで、第2種スターリング数というものを導入します。
第2種スターリング数(Stirling subset number)
正の整数$n, k$に対し
$S(n,k)$ :=$n$元集合を$k$個の空でない部分集合に分ける場合の数
で定義します。
例えば
{$1, 2, 3, 4$} = {$1$} $\cup$ {$2, 3, 4$} = {$2$} $\cup$ {$1, 3, 4$} = {$3$} $\cup$ {$1, 2, 4$} = = {$4$} $\cup$ {$1, 2, 3$} = {$1, 2$} $\cup$ {$3, 4$} = {$1, 3$} $\cup$ {$2, 4$} = {$1, 4$} $\cup$ {$2, 3$}
なので、$S(4,2)=7$となります。
また、定義より$n < k$ならば$S(n,k)=0$が成り立ちます。
次に、$S(n,k)$に関する漸化式を考えます。
命題 : $n, k$を正の整数とすると、$S(n+1,k)=S(n,k-1)+kS(n,k)$が成り立つ。
(証明)
一つの元$e$に注目して考える。($n+1$)元集合の分割として、$e$を含む集合が1元集合であるとき、残りの$n$元を($k-1$)個の集合に分ける場合の数を考えるので$S(n,k-1)$通り。
$e$が$k$個の集合どれかの元であるとき、$e$を含む集合の選び方は$k$通りで、そもそもの残りの元の分け方が$S(n,k)$通りであるので、これの組み合わせを考えることで$kS(n,k)$通り。
したがって、場合の数は合わせて$S(n,k-1)+kS(n,k)$通りとなり、等式は成り立つ。(証明終)
ということで漸化式まで得ることができましたが、$n$も$k$も正の整数しか動けないとなるとちょっと不便なので一般化をします。
第2種スターリング数の一般化
任意の整数$m,n$に対し$S(n,m)$を上の漸化式および
$S(0,0)=1, S(n,0)=S(0,m)=0(n,m\neq 0)$
で定義する。
これだけの定義で、全ての整数の組$(n,m)$に対して値$S(n,m)$が一意に与えられます。これは、漸化式を見ると分かります。$xy$平面にプロットしていくと分かりやすいかもしれません。
また本来ならば、この初期値によって定められる値と上で定義した値が等しくなることを確かめなければなりませんが、これも書き下すことですぐに示せるので省略します。
(第1種スターリング数はないの...？)
あります。今回は使わないので紹介だけに留めておきます。
群論の基礎知識がないと分かりにくいし、今回はこれが分からなくても困らないので飛ばしても大丈夫です。
第1種スターリング数(Stirling cycle number)を
正の整数$m,n>0$に対し
$S_1(n,m):=m$個のサイクルからなる$n$次置換の個数
で定義する。
これは漸化式$S_1(n+1,m)=S_1(n,m-1)+nS_1(n,m)$を満たし、初期値$S_1(0,0)=1,S_1(n,0)=S_1(0,m)=0(m,n\neq 0)$によって整数の範囲まで一般化されます。
実はこれは本質的に第2種スターリング数と同じであることも示せます。
第2種スターリング数に関する命題
第2種スターリング数とベルヌーイ数を関連づけるために、命題を2つ示します。
命題 1 : $m,n \ge 0$に対し、
$S(n,m)=\frac{(-1)^m}{m!}\sum_{l=0}^{m}(-1)^l{{m}\choose{l}}l^n$
(証明)
(右辺)$=a_{n,m}$とおいて、$a_{n,m}$が$S(n,m)$と同じ初期値、漸化式を持てば等式が示せる。
初期値 :
$a_{0,0}=\frac{(-1)^0}{0!}(-1)^0{{0}\choose{0}}0^0=1,$
$n \ge 1$のとき、$a_{n,0}=0,$
$m \ge 1$のとき、二項定理より
$S(0,m)=\frac{(-1)^m}{m!}\sum_{l=0}^{m}(-1)^l{{m}\choose{l}}=\frac{(-1)^m}{m!}(1-1)^m=0 $
漸化式 :
$ma_{n,m}+a_{n,m-1}$
$=\frac{(-1)^m}{(m-1)!}\sum_{l=0}^{m}(-1)^l{{m}\choose{l}}l^n+\frac{(-1)^{m-1}}{(m-1)!}\sum_{l=0}^{m-1}(-1)^l{{m-1}\choose{l}}l^n$
$=\frac{(-1)^m}{(m-1)!}\sum_{l=0}^{m}(-1)^l\{{{{m}\choose{l}}-{{m-1}\choose{l}}}\}l^n$
$=\frac{(-1)^m}{(m-1)!}\sum_{l=0}^{m}(-1)^l\frac{l}{m}{{m}\choose{l}}l^n$
$=\frac{(-1)^m}{m!}\sum_{l=0}^{m}(-1)^l{{m}\choose{l}}l^{n+1}$
$=a_{n+1,m}$
3行目で、$l > m-1 \Rightarrow {{m-1}\choose{l}}=0$ を用いた。
したがって、$a_{n,m}$は$S(n,m)$と同じ初期値、漸化式を持つので等しいことが示された。
命題 2 : $m \ge 0$に対し、
$\frac{(e^t-1)^m}{m!}=\sum_{n=m}^{\infty}S(n,m)\frac{t^n}{n!}$
(証明)
まず、$n<m$のとき$S(n,m)=0$だったので、右辺の和を$\sum_{n=0}^{\infty}$に書き換える。
このとき命題1より、
(右辺)
$=\sum_{n=0}^{\infty}\{\frac{(-1)^m}{m!}\sum_{l=0}^{m}(-1)^l{{m}\choose{l}}l^n \}\frac{t^n}{n!}$
$=\frac{(-1)^m}{m!}\sum_{l=0}^{m}(-1)^l{{m}\choose{l}}(\sum_{n=0}^{\infty}\frac{(lt)^n}{n!})$
$=\frac{(-1)^m}{m!}\sum_{l=0}^{m}(-1)^l{{m}\choose{l}}e^{lt}$
$=\frac{(-1)^m}{m!}(1-e^t)^m $
$=\frac{(e^t-1)^m}{m!}$
$=$ (左辺)
よって示された。下から4行目の級数の変換には二項定理を用いた。
多重ベルヌーイ数に関する公式
さて、第2種スターリング数に関する級数にも$(e^t-1)$という項が出てきたのでどうにかして多重ベルヌーイ数にねじ込めそうな気がしてきます。
2つ定理を示しますが、定理1は今回は使わないので興味のある方だけ読んでください。
定理 1 : $n \ge 0,k\in \mathbb{Z}$ に対し、
$\mathbb B_{n}^{(k)}=(-1)^n\sum_{m=0}^{n}\frac{(-1)^{m}m!S(n,m)}{(m+1)^k}$
が成り立つ。
(証明)多重ベルヌーイ数の母関数表示と命題2を用いて、
$\sum_{n=0}^{\infty}\mathbb B_{n}^{(k)}\frac{t^n}{n!}=\frac{Li_k(1-e^{-t})}{1-e^{-t}} = \sum_{m=1}^{\infty}\frac{(1-e^{-t})^{m-1}}{m^k}$
$=\sum_{m=0}^{\infty}\frac{(-1)^m(e^{-t}-1)^m}{(m+1)^k}$
$=\sum_{m=0}^{\infty}\frac{(-1)^mm!}{(m+1)^k}\sum_{n=m}^{\infty}S(n,m)\frac{(-t)^n}{n!}$
$=\sum_{n=0}^{\infty}(-1)^n(\sum_{m=0}^{n}\frac{(-1)^mm!S(n,m)}{(m+1)^k})\frac{t^n}{n!}$
したがって、$\frac{t^n}{n!}$ の係数を比較することで求める式を得られた。(証明終)
この定理からわかるように、$k \le 0$のとき $\mathbb B_{n}^{k}$は整数になるので、少し希望が見えてくるわけです。
定理 : 2 $\forall n,k \ge 0$に対し、
$\mathbb B_{n}^{(-k)}=\sum_{j=0}^{min(n,k)}(j!)^2S(n+1,j+1)S(k+1,j+1),$
$\mathbb B_{n}^{(-k)} = \mathbb B_{k}^{(-n)}>0$
が成り立つ。
最後の不等式は、1つ目の明示公式から得られるものとなります。
(証明)
$\mathbb B_{n}^{(-k)}$の2変数母関数表示を考える。命題2より、
$\sum_{n=0}^{\infty}\sum_{k=0}^{\infty}\mathbb B_{n}^{(-k)}\frac{x^n}{n!}\frac{y^k}{k!}$
$=\sum_{n=0}^{\infty}\sum_{k=0}^{\infty}(-1)^n\sum_{m=0}^{n}(-1)^mm!S(n,m)(m+1)^k\frac{x^n}{n!}\frac{y^k}{k!}$
$=\sum_{n=0}^{\infty}\sum_{k=0}^{\infty}(-1)^n\sum_{m=0}^{n}(-1)^mm!S(n,m)\frac{x^n}{n!}\frac{\{(m+1)y\}^k}{k!}$
$=\sum_{n=0}^{\infty}(-1)^n\sum_{m=0}^{n}(-1)^mm!S(n,m)\frac{x^n}{n!}\sum_{k=0}^{\infty}\frac{\{(m+1)y\}^k}{k!}$
$=\sum_{n=0}^{\infty}(-1)^n\sum_{m=0}^{n}(-1)^mm!S(n,m)e^{(m+1)y}\frac{x^n}{n!}$
$=\sum_{m=0}^{\infty}(-1)^mm!e^{(m+1)y}\sum_{n=m}^{\infty}(-1)^nS(n,m)\frac{x^n}{n!}$
$=\sum_{m=0}^{\infty}(-1)^mm!e^{(m+1)y}\frac{(e^{-x}-1)^m}{m!}$
$=e^y\sum_{m=0}^{\infty}\{(1-e^{-x})e^y\}^m$
$=e^y\frac{1}{1-\{(1-e^{-x})e^y\}}$
$=\frac{e^{x+y}}{e^x+e^y-e^{x+y}}$
最後の関数を変形して、
$\frac{e^{x+y}}{e^x+e^y-e^{x+y}}=\frac{e^{x+y}}{1-(e^x-1)(e^y-1)}$
$=e^{x+y}\sum_{j=0}^{\infty}(e^x-1)^j(e^y-1)^j$
$=\sum_{j=0}^{\infty}\frac{1}{(j+1)^2}\{\frac{d}{dx}(e^x-1)^{j+1}\}\{\frac{d}{dy}(e^y-1)^{j+1}\}$
再び命題2をこれに適用すると、
$\sum_{n=0}^{\infty}\sum_{k=0}^{\infty}\mathbb B_{n}^{(-k)}\frac{x^n}{n!}\frac{y^k}{k!}$
$=\sum_{j=0}^{\infty}\frac{1}{(j+1)^2}\frac{d}{dx}\{(j+1)!\sum_{n=j}^{\infty}S(n+1,j+1)\frac{x^{n+1}}{(n+1)!}\}\frac{d}{dy}\{(j+1)!\sum_{k=j}^{\infty}S(k+1,j+1)\frac{y^{k+1}}{(k+1)!}\}$
$=\sum_{j=0}^{\infty}(j!)^2\sum_{n=j}^{\infty}S(n+1,j+1)\frac{x^n}{n!}\sum_{k=j}^{\infty}S(k+1,j+1)\frac{y^k}{k!}$
$=\sum_{j=0}^{\infty}\sum_{n=j}^{\infty}\sum_{k=j}^{\infty}(j!)^2S(n+1,j+1)S(k+1,j+1)\frac{x^n}{n!}\frac{y^k}{k!}$
を得る。$j > min(n,k)$のとき、$S(n+1,j+1)S(k+1,j+1)=0$ に注意すると最後の式は
$=\sum_{n=0}^{\infty}\sum_{k=0}^{\infty}\sum_{j=0}^{min(n,k)}(j!)^2S(n+1,j+1)S(k+1,j+1)\frac{x^n}{n!}\frac{y^k}{k!}$
とできるので、係数比較によって求める式を得る。
公式より$n$と$k$の対称性は明らか。
また、$\mathbb B_{0}^{(0)}=(0!)^2S(1,1)S(1,1)=1$より、
$\mathbb B_{n}^{(-k)}=1+\sum_{j=1}^{min(n,k)}(j!)^2S(n+1,j+1)S(k+1,j+1) \ge 1 + 0$
したがって、常に$\mathbb B_{n}^{(-k)}>0$であることも示された。
(証明終)
定理の証明
...ということで、$n,k\ge 0$のとき、多重ベルヌーイ数$\mathbb B_{n}^{(-k)}$は正の整数になることが分かりました！
この記事の目的はこの数がどんな意味を持つのか説明することでした。早速主張を確認した上で証明しましょう！
定理 : 完全二部グラフ$K_{n,m}$がDAGになるような辺の向き付けの場合の数は、$\mathbb B_{m}^{(-n)}$と一致する。
(証明)
$K_{m,n}$をDAGであるような完全二部グラフ、$R=\{r_1,r_2,...,r_m\},B=\{b_1,b_2,...,b_n\}$を二分された頂点集合とする。
また、$R$の頂点を赤、$B$の頂点を青に塗っておく。
$K_{m,n}$はDAGなのでトポロジカルソートが可能で、そのソートした頂点の列は赤と青がごちゃまぜになっています。
$R=R_1\cup R_2\cup..., B=B_1\cup B_2\cup...$と分割することにすると点列は、($R_1$の元の並べ替え),($B_1$の元の並べ替え),($R_2$の元の並べ替え)...の順で並んでいることになります。(もちろん、$B_1$が先かもしれません)
このように、どちらの色が先か、どちらの色で終わるのか、などややこしいのでダミーの頂点$r_0,b_0$を用意します。これを用意することで、全ての場合に同時に対応できるようになります。
さて、$R\cup \{r_0\}, B\cup \{b_0\}$をそれぞれ $j (\ge 1)$ 個の空でない部分集合に分ける場合の数を考えます。これは第2種スターリング数そのままで、それぞれの要素数は$m+1,n+1$なので、分け方の組み合わせまで考えることでこれは$S(m+1,j)S(n+1,j)$通りとなります。
このとき、$R\cup \{r_0\}=R_1\cup R_2\cup...\cup R_j, B\cup \{b_0\}=B_1\cup B_2\cup...\cup B_j$と書けます。
ここで、以下の条件で$R_i,B_i$たちを並べ替えます。
- $r_0$を含むものを先頭にする
- 赤と青を交互に並べる
- $b_0$を含むものを末尾にする
つまり$r_0\in R_1,b_0\in B_1$とすると、(途中の添字は省略しますが)$R_1$$B$$R$$B$...$R$$B_1$という風に並べ替えるということです。
ダミーの頂点ですが、取り除いたときに$R_0$が空$\rightarrow$トポロジカルソートの結果が青い頂点から始まっていた、$B_0$が空$\rightarrow$トポロジカルソートの末尾が赤い頂点だった、という解釈になります。
$R_1,B_1$と1つずつ固定されているので、残りの集合の並べ替えの場合の数はそれぞれの色について$(j-1)!$通りあります。
したがって、$R\cup \{r_0\}, B\cup \{b_0\}$をそれぞれ $j (\ge 1)$ 個の空でない部分集合に分けた上で並べ替える場合の数は、$((j-1)!)^2S(m+1,j)S(n+1,j)$通りになります。
$j>min(m+1,n+1)$のとき$S(m+1,j)S(n+1,j)=0$だったので、$j=1$から$min(m+1,n+1)$まで足し合わせて変数変換することで(式の中の$j\rightarrow j+1$と書きなおすと、$j=0$から$j=min(m,n)$とできる)求める式を得ます。
(証明終)
おわりに
途中にも書きましたが、数論的な意味を持った数列がこんな話に繋がるのは面白いですね。僕はこの話を知るまではグラフこええ〜むずかしそ〜と思っていたのですが思っていたよりもずっと楽しそうな対象でした。
あとつよい競プロ勢(非数学徒)に「$K_{m,n}$のDAGの数え上げやって」と言ったらどういう風に数えるかは少し気になるところですね。
冒頭に紹介した本は他にも(タイトルの通り)ベルヌーイ数とゼータ関数の関係に関する話とか、いろいろ書いてあって面白いのでオススメです。
就活がひと段落ついたらまたのんびりこういう趣味の話を書きたいな〜〜
嘘や誤字の指摘、質問などあればコメント欄に書いてくださると嬉しいです！