プロ家庭教師、尾関が受験算数の核心的問題を紹介します。
カ タラン数
 カ
タラン数とは？
数学者カタランの発見した数で、次の式で求めることができます。
(2n!)÷{ (n＋1)!×n！
} ！は階乗ですが、小学生に教えるときは「びっくり」と読んでいます。例えば、「3びっくり」＝３！＝3×2×1＝６ですね。
n＝0、１、２、３、４、５、６、７、・・・のとき、それぞれのカタラン数は、1、１、２、５、１４、
４２，１３２，４２９、・・・
最難関中学、超難関中学でよく出題されますが、これを知らなければ時間内で解くのは無理では？という問題も見かけま
す。
そんなカタラン数ですが、どんな問題に応用されているのか、いくつか例をあげてみます。カタラン数を使うということ
に気がつかなけれ ば意 味が ありませんので・・・。
問題1
たし算は二つの数から一つの数を求める計算で、三つ以上の数をたすときには、二つの数のたし算をくり返していくこと
になります。例え ば 1+2+3や1+2+
3+4を、カッコを用いて二つの数のたし算で書き表す方法は、次のようにそれぞれ二通り、五通りあります。
1+(2+3)、(1+2)+3・・・二通り
1+(2+(3+4))、1+((2+3)+4)、(1+2)+(3+4)、(1+(2+3))+4、
((1+2)+3)+4・・・ 五通 り
(注意) 1+(3+2)のように、たす数を並べ替えることは考えません。
このような式を完全式と呼ぶことにします。次のような式は完全式ではありません。
1+2+3、1+(2+3)+4 、(1+2+3)+4 （三つをたしている）
1+2+3+4 (四つをたしている)
(1) 1+2+3+4+5 には何通りの完全式がありますか。
(2) 1+2+3+4+5+6には何通りの完全式がありますか。
問題2
４チームがトーナメントで試合を行い優勝チームを決めます。それには３試合が必要ですが、試合のやり方は何通りあり
ますか。
解説はこちらです
問題３
表の空らんに１から８までの数字を順に入れてゆくとき、上の段の数字が下の段の数字より小さく、左のらんの数字が右
のらんの数字より 小さ くな るようにします。何通りの入れ方がありますか。
解説
４列のときは、このような入れ方ですが、１列のときは
の１通りあり、２列のときは、左上の１と右下の４は決定なので、
の２通りあり、3列のときも同様に
の５通りある。場合の数が、１、２、５となっているのでカタラン数を予測して、次のオオカミとヒツジ解法で４列の場合を求める。
上の段に数字を入れることを、右に１区間進むことに対応させ、下の段に数字を入れることを、上に１区間進むことに対
応させている。
答え 14通り
(別解)
計算でやるには、ガウス公式のように、上下で逆に数をならべて、
１ １ ２ ５
５ ２ １ １
上下に並んだの数の積をすべてたしあわせて、１×５＋１×２＋２×１＋５×１＝１４通りとなります。
 考 察
このようにいろいろな場面で登場するカタラン数ですが、「2つの数の和や積」、「1対１の試合」、「上段と下段」、
「オオカミとヒツ ジ」、 「円周上の２点を交わらないよう結ぶ」といった、１対になっている条件付き問 題 で、場合の数
が、１、２、５・・・と増加して行きます。
カタラン数の問題は、最難関校ではよく見かけます
|
