部屋割りの仕方を数えます

[問題 PS-06] 部屋割りの仕方を数えます

 $n$ 人を部屋割りします。
 1つの部屋には少なくとも1人は入れるものとして以下の問いに答えてください。

 (1) $n\geq 2$ とします。$n$ 人を $2$ 室に入れる方法は何通りありますか。
 (2) $n\geq 3$ とします。$n$ 人を $3$ 室に入れる方法は何通りありますか。
 (3) $n\geq 4$ とします。$n$ 人を $4$ 室に入れる方法は何通りありますか。
 

問題 PS-06 のヒント

 シンプルな設定ですが、このタイプの問題を初めて見る場合は意外に手こずるかもしれません。考え方さえわかれば計算自体は簡単です。(2) は (1) の結果を、(3) は (1) と (2) の結果を使います。
 

図解と実例と論理で、今度こそわかるガロア理論

新品価格
¥2,160から
(2017/9/2 14:40時点)

解答 PS-06

 部屋に人がいる場合を A , 空室を X という記号で表すことにします。

(1) $n$ 人が無条件で部屋を選択できる場合は重複順列なので $2^n$ 通りですが、空室を作ってはいけないというルールなので、

XA AX

という $2$ 通りを除かなくてはいけません。よって答えは $2^n-2$ 通りです。

(2) 無条件で部屋を選択できる場合は $3^n$ 通りです。
  $1$ 室が空室になるような状況、すなわち

XAA AXA AAX

という状況は、それぞれについて $2$ 部屋に空室のないように入れる仕方の数をかぞえればよいので、(1) の結果より全部で $3\,(2^n-2)$ 通りです。また、$3$ 室のうち $2$ 室が空室となるのは

XXA XAX XXA

の $3$ 通りです。以上より答えは

$3^n-3\,(2^n-2)-3=3^n-3\cdot 2^n+6$ 通り

となります。

(3) 無条件で部屋を選択できる場合は $4^n$ 通りです。
  $1$ 室が空室になるような状況、すなわち

XAAA AXAA AAXA AAAX

という状況は、それぞれについて $3$ 部屋に空室のないように入れる仕方の数をかぞえればよいので、(2) の結果より全部で

$4\,(3^n-3\cdot 2^n+6)$ 通り

あります。$1$ 室が空室になるような状況は $4$ つの異なるものから $2$ つを選ぶので ${}_{4}\mathrm{C}_{2}=6$ 通りです:

AAXX AXXA XXAA XAAX XAAX XAXA AXAX

 それぞれについて $2$ 部屋に空室のないように入れる仕方の数をかぞえればよいので、(1) の結果より全部で

$6\,(2^n-2)$ 通り

あります。また、$4$ 室のうち $3$ 室が空室となるのは

XXXA XXAX XAXX AXXX

の $4$ 通りです。以上より答えは

$4^n-4\,(3^n-3\cdot 2^n+6)-6\,(2^n-2)-4=4^n-4\,\cdot 3^n+6\,\cdot 2^n-16$ 通り

となります。 ≫ 四角形を塗り分けます ≫ 確率統計演習問題

スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。