平野塾@吉祥寺

2席以上あけて座る方法 /「算数にチャレンジ!!」第1177問

算数にチャレンジ!!

問題概略
空席を分配する
漸化式を立てる

問題概略

あるお店には 11 席のカウンター席があります。
お客さんに 2 つ以上の席を空けて座ってもらう方法は何通りあるでしょうか。
お客さんは区別しないものとし，お客さんは 0 人ではないものとします。

http://www.sansu.org/used-html/index1177.html

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

空席を分配する

客と客の間の空席は 2 席以上で，両端の空席は 0 席以上。
「2 席以上空ける」を「2 席空けてからさらに 0 席以上空ける」と言い換えると，すべての場所を「0 席以上」で処理できます。

客が $k$ 人の場合を考えます。客と客の間の空席は全部で $2(k-1)$ 席以上必要。
残りの座席数は

$11-k-2(k-1)=13-3k$

これを客と客の間 $k-1$ ヵ所と両端の 2 ヵ所，合計 $k+1$ ヵ所に分配します。

場合の数の問題でよくある「 $13-3k$ 個のりんごを $k+1$ 人に配る。1 個ももらえない人がいてもいい。配り方は何通りか」という問題に帰着できました。

この分配法は $13-3k$ 個のボールと $k$ 個の仕切りを並べるのと同じだけあります。

${}_{(13-3k)+k}\mathrm{C}_k={}_{13-2k}\mathrm{C}_k\, \text{通り}$

$13-3k\geqq 0$ から $1\leqq k\leqq 4$ もわかります。答えは

$\displaystyle\sum_{k=1}^4 {}_{13-2k}\mathrm{C}_k=87$

漸化式を立てる

座席が $n$ 個のときの座り方を $f(n)$ 通りとおきます。

$n$ が 3 以下のときは 1 人しか座れません。その人はどの席にでも座れます。

$f(1)=1,\, f(2)=2,\, f(3)=3$

座席 $n$ に人が座らないとき，座席 1 から座席 $n-1$ までの座り方を考えて $f(n-1)$ 通り。

座席 $n$ に人が座るときは座席 $n-1$ と座席 $n-2$ は空席になります。残りの席の座り方は $f(n-3)$ 通りとしたいところですが，座席 1 から座席 $n-1$ まで誰も座らない（＝座席 $n$ にしか客がいない）場合もあります。合計 $f(n-3)+1$ 通りです。

まとめると

$f(n)=f(n-1)+f(n-3)+1$

この漸化式を繰り返し使うと $f(11)=87$ を得ます。

variee.hatenablog.com