[ 掲示板に戻る ]
記事No.61522に関するスレッドです
★ (No Subject) / セレクト
(1)n(n-1)/2
(2)n(n-1)(n-2)(3n-5)/24
(3)2^(n-1)-1
(4)S[n+1](k)=S[n](k-1)+kS[n](k)

なのですが、プロセスが分かりません。
No.61522 - 2019/09/26(Thu) 09:30:24
☆ Re: / らすかる
(1)
1〜nの数字をn-1個の空でない部分に分割するということは、
n-1個のうちどれか1個に数字が2個入り、残りの数字は単独です。
従って分割する方法の数はn個の数字から2個選ぶ組合せですから、
S[n](n-1)=nC2=n(n-1)/2となります。

(2)
1〜nの数字をn-2個の空でない部分に分割するということは、
n-2個のうちどれか1個に数字が3個入り、残りの数字が単独であるか、
もしくはn-2個のうちのどれか2個に数字が2個ずつ入り、残りの数字が
単独であるかのいずれかです。
前者はnC3=n(n-1)(n-2)/6通り
後者は{nC2×(n-2)C2}/2=n(n-1)(n-2)(n-3)/8通り
従って
S[n](n-2)=n(n-1)(n-2)/6+n(n-1)(n-2)(n-3)/8
={n(n-1)(n-2)/24}{4+3(n-3)}
=n(n-1)(n-2)(3n-5)/24
となります。

(3)
1〜nの数字を2個の空でない部分に分割するということは、
n個の数字を2グループに分ける方法なので
グループに区別があるとき2^n-2通り、
よって区別がなければ
S[n](2)=(2^n-2)/2=2^(n-1)-1
となります。

(4)
1〜n+1の数字をk個の空でない部分に分割するとき、
n+1という数字がどこに入っているか考えると、
n+1が単独のときはそれを除けば1〜nがk-1個の空でない部分に
分割されている状態になるのでS[n](k-1)通り
n+1が他の数字と一緒のときは1〜nがk個の空でない部分に
分割されている状態からkグループのどれかにn+1を追加した
状態なのでkS[n](k)通り
従って合わせて
S[n+1](k)=S[n](k-1)+kS[n](k)
となります。
No.61526 - 2019/09/26(Thu) 10:17:34