１からｎの数字をｋ個の空でない部分に分割する方法の数

質問

n＞２とする。１からｎの数字をｋ個の空でない部分に分割する方法の数をS_n(k)で表す。たとえばS_3(2)＝3である。
(1)S_n(n-1)を求めよ。
(2)S_n(n-2)を求めよ。
(3)S_n(２)を求めよ。
(4)ｎ＞２のとき、S_n+1(k)をS_n(k-1)とS_n(k)を用いて表せ。

この問題を解いています。
(1)はn(n-1)/2　(2)はn^2(n-1)(n-2)/6
となりました（全然自信ありません）
(3)からよくわからなくなりました。
「１からｎまでの数字を２個の部分に分ける方法の数」を求めるには何個ずつ分配するかによって場合わけが必要なのでしょうか？（そんなことできるのでしょうか？）
回答いただければ幸いです。よろしくお願いします

回答No.1

fronteye · ベストアンサー

(3)については説明できます。
２ヶ所の分割先を集合A,Bとします。
1～n が必ずA,Bのどちらかの要素になるわけだから、組み合わせの総数は、2^n 個 (2のn乗個)。
その内A,Bが空集合の場合は除くから、(2^n-2) 個。
Aの要素とBの要素が等しい場合は同じ分割と考えるから、(2^n-2)/2 個となります。

回答No.2

Tacosan

う～ん, よくある離散数学の問題だ....
(4):
n+1 個の要素を k個の空でない集合に分割するわけだから, 最後 (n+1 個目) を除いた n 個は次のいずれかのように分割されています:
1. k-1個の空でない集合に分割する: このとき最後の n+1 個目は k個目の集合の (唯一の) 要素になります.
2. k個の空でない集合に分割する: n+1 個目は k個の集合のどれに入れてもかまいません.
この 2つの場合を別々に数えてください. なお, 2においては k個の集合が (その中にある要素によって) 区別できることに注意.