東大寺学園中学校２００９年算数第２問（解答・解説）
（解法１）
ｎか所の〇には間が（ｎ−１）個あります。
そのそれぞれの間について、仕切りを入れるか入れないかの２通り考えられるから、仕切りの入れ方は全部で２×２×・・・×２（２を（ｎ−１）個かけ合わせた数）通り考えられますが、そのうち全く仕切りを入れない場合は条件を満たさないので、Ｓ（ｎ）＝２×２×・・・×２（２を（ｎ−１）個かけ合わせた数）−１となります。
（１）
Ｓ（４）＝２×２×２−１＝７、Ｓ（５）＝２×２×２×２−１＝１５となります。
（２）
１２７＋１＝１２８は２を７個かけ合わせた数だから、Ｓ（ｎ）＝１２７となるｎは７＋１＝８となります。
（解法２）
まず、問題文の例について考えてみます。
２か所の〇には間が２−１＝１か所あります。
仕切りの入れ方は次の（あ）の場合が考えられます。
（あ）１か所に仕切りを入れる場合・・・１通り
したがって、Ｓ（２）＝１となります。
３か所の〇には間が３−１＝２か所あります。
仕切りの入れ方は次の（あ）、（い）の場合が考えられます。
（あ）２か所すべてに仕切りを入れる場合・・・１通り
（い）２か所のうち１か所に仕切りを入れる場合・・・２通り
したがって、Ｓ（３）＝１＋２＝３となります。
ｎ＝４、５の場合についても同様に考えられます。
（１）
４か所の〇には間が４−１＝３か所あります。
仕切りの入れ方は次の（あ）〜（う）の場合が考えられます。
（あ）３か所すべてに仕切りを入れる場合・・・１通り
（い）３か所のうち２か所に仕切りを入れる場合・・・３通り ←３か所のうち仕切りを入れない１か所の選び方を考えればいいですね。
（う）３か所のうち１か所に仕切りを入れる場合・・・３通り
したがって、Ｓ（４）＝１＋３＋３＝７となります。
５か所の〇には間が５−１＝４か所あります。
仕切りの入れ方は次の（あ）〜（え）の場合が考えられます。
（あ）４か所すべてに仕切りを入れる場合・・・１通り
（い）４か所のうち３か所に仕切りを入れる場合・・・４通り ←４か所のうち仕切りを入れない１か所の選び方を考えればいいですね。
（う）４か所のうち２か所に仕切りを入れる場合・・・（４×３）/（２×１）＝６通り
（お）４か所のうち１か所に仕切りを入れる場合・・・４通り
したがって、Ｓ（５）＝１＋４＋６＋４＝１５となります。
（２）
ハノイの塔（〇番目の数が２を〇個掛け合わせたものから１を引いたもの）と同様の規則性だとわかります。 ←このことがわからなくても隣同士の差をチェックすれば等比数列になっていることがわかるでしょう。
２を７個かけ合わせた数が１２８だから、Ｓ（ｎ）＝１２７を満たすｎは１＋７＝８となります。 ←この問題の場合、ｎ＝〇＋１になっていますね。
なお、仕切り０個の場合も１通りと考えたときの場合の数をｎ＝２の場合から順に書き出すと
２、４、８、１６、・・・
となり、２の累乗となっていることがすぐにわかります。
このことに着目して解いてもいいでしょう。
また、次のパスカルの三角形がこの問題と絡んでいることも確認しておきましょう。 ←この問題の規則性は各段における右端の１以外の和になっていますね。
１ 和１
１ １ 和２
１ ２ １ 和４
１ ３ ３ １ 和８
１ ４ ６ ４ １ 和１６
・・・・・・・・・・・ ・・・