私的数学日誌

9日目「Bell数に関する合同式」

n番目のBell数をB(n)と書くことにして、まずは定義から書いていく。ベル数とは、n元集合を分割するときの総数を表している。

例えば、{1,2,3}の分割の仕方は、

{{1},{2,3}}

{{2},{1,3}}

{{3},{1,2}}

{{1,2,3}}

{{1},{2},{3}}

の5通りであるため、B(3)は5である。

まず、組み合わせ的な意味から出てくる数列は漸化式を考えるのが基本であるので、漸化式を導出してみる。

Bell数の漸化式

B(0)=1として、B(n+1)=Σ(k=0~n) nCk B(k)

証明

組み合わせ的に考察する。n番目までの分割が与えられているとして、しめす。

n+1の分割について考える。この分割には、n+1が単体で存在する、n+1が2つの元と分割されている、......n+1がi個の元と一緒に分割されている.....というパターンに分割することができる。

n+1がi個の元とともに分割されているときについて考える。この集合をBとする。Bの補集合はn+1-(i+1)個の元を持っている。すなわち、n-i個元を持っている。補集合を分割するときの場合の数は、B(n-i)である。また、Bの元の選び方は、nCkであるので、積の法則より、nCk B(n-i)である。

iは0からnまでを渡り、どのパターンも排反であるので、和の法則より、B(n+1)=Σ(i=0~n) nCk B(n-i)=Σ(i=0~n) nCk B(i)。

よって、わざわざ分割の総数を手で数えなくても、簡単にB(n)の値が導き出せるようになった。

Bell数を考察するための補助的な道具として第二種スターリング数nSkがあげられる。nSkはn元集合をkグループに分割する（そのグループは非空でなければならない）場合の数であり、nS1=1が容易に導ける。便宜上、nS0=0とおく。

定義より、Σ(i=0~n)nSk=B(n)が容易に導ける。

また、nSkについて、次の定理が成り立つ

第二種スターリング数の二項係数による表示

nSk=1/k! Σ(i=0~k) (-1)^k-i kCi i^n

ここから、容易にpSk (k=2~p-1)はpで割り切れることが示せる。これとB(n)をスターリング数で表すことにより、次の定理が示された。

Bell数の合同式

pを素数とする。このとき、B(p)≡2 (mod p)

kakuyomuだと数式が見づらくなってしまうので、割愛するが、B(n)の漸化式とB(n)の第二種スターリング数の表示を一般化したモノとして、Hurst-Schultzの公式がなりたち、そこから、Bell数の合同式の一般化である次の定理とさらなる一般化を示せる。

Touchardの合同式

pを素数とする。このとき、B(n+p)≡B(n)+B(n+1)

Hurst-Schultzの合同式

pを素数とする。このとき、非負整数mにたいして、B(n+p^m)≡mB(n)+B(n+1)が成り立つ。

Hurst-Schultzの原論文はarΧiv、An elementary (number theory) proof of Touchard's congruenceに乗っているので、是非読んでみてほしい。原論文は、Hurst-Schultzの公式を証明してから、Touchardの合同式と一般化を示していて、数式も見やすい。