組み合わせ記号の問題（第二種スターリング数）

質問

Σ[k=0…n] (-1)^(n+k) * C[n+1, k+1] * (k+1)^m
＝
Σ[k=0…n] (-1)^k * C[n, k] * (n-k)^m
が示せなくて困っています。

これは、「m人が全n曲中1曲聞いてくるとき、全ての曲が少なくとも一回は聞かれている場合の数」の一般項を表しています。
エクセルで計算したところ二式は等しかったので、等しいことは確かです。

元々は、「m人のグループがn曲中l曲聞いてくる時、グループ全体でX曲聞きこぼしている場合の数」を求めるという問題を考察していたところ上記の数列の一般項を求める事に辿り着きました。
一般項は求まったのですが、ネットで実際の項で検索してみたところ、同じ数列が別の式で表されていました。
上の式が自分で出した式で下が載っていた式なのですが、そのサイトには説明は載っていませんでした。そこで上の式から下の式を出そうとしたのですが、それが上手くいきませんでした。
ちなみに同サイトに依ると第二種スターリング数S_2(n,m)を使って m!*S_2(n,m)とも表せるそうです。

分かる方いらっしゃいましたら、どうかよろしくお願いします！

回答No.2

nag0720 · ベストアンサー

Σ[k=0…n] (-1)^(n+k) * C[n+1, k+1] * (k+1)^m

p=n-k　とするとk=n-p , p=n…0 なので、
Σ[k=0…n] (-1)^(n+k) * C[n+1, k+1] * (k+1)^m
＝Σ[p=n…0] (-1)^(n+n-p) * C[n+1, n-p+1] * (n-p+1)^m
＝Σ[k=0…n] (-1)^(2n-k) * C[n+1, n+1-k] * (n+1-k)^m

ここで、
(-1)^(2n-k)＝(-1)^k　　（∵(2n-k)とkの偶奇は同じ）
C[n+1, n+1-k]＝C[n+1, k]
なので、

左辺＝Σ[k=0…n+1] (-1)^k * C[n+1, k] * (n+1-k)^m
となります。

お礼

なるほど逆から足していくんですね！
夜遅く、朝早くにご解答ありがとうございました。

回答No.1

nag0720

＞エクセルで計算したところ二式は等しかったので、等しいことは確かです。

どこか違ってませんか？

例えば、n=2のとき、

Σ[k=0…2] (-1)^(2+k) * C[3, k+1] * (k+1)^m
＝(-1)^2 * C[3, 1] * 1^m ＋ (-1)^3 * C[3, 2] * 2^m ＋ (-1)^4 * C[3, 3] * 3^m
＝3-3*2^m+3^m

Σ[k=0…2] (-1)^k * C[2, k] * (2-k)^m
＝(-1)^0 * C[2, 0] * 2^m ＋ (-1)^1 * C[2, 1] * 1^m ＋ (-1)^2 * C[2, 2] * 0^m
＝2^m-2

となって、イコールとはなりませんが・・・

お礼

ごめんなさい、下の式が間違っていました。
×　Σ[k=0…n] (-1)^k * C[n, k] * (n-k)^m
○　Σ[k=0…n+1] (-1)^k * C[n+1, k] * (n+1-k)^m
nを１シフトさせると一致するので、それを逃していました。
こうすると、n=2の場合いずれも3-3*2^m+3^mとなりました。

この和の末項では必ず(n+1-k)^m = 0となるので、kの範囲をnに改めて
Σ[k=0…n] (-1)^k * C[n+1, k] * (n+1-k)^m
としても良さそうです。
この後はどうするのでしょうか・・。