プロ家庭教師、尾関が受験算数の核心的問題を紹介します。
カ タラン数
 カ
タラン数とは？
数学者カタランの発見した数で、次の式で求めることができます。
(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には何通りの完全式がありますか。
問題１の解説
(1) ◆2 個の数の和のとき・・・１通り
◆３個の
数の和のとき・・・２ 通り
◆４個の数の和のとき・・・４個の数をとりあえず、(１ 個、３個)(２個、２個)(３個、１個)と分けて、２個の数の和の１通りと３個の
数の和の２ 通りをあてはめて、２＋１＋２＝５通り
◆5個の数の和のとき・・・5個の数をとりあ えず、(１個、4個)(２個、3個)(３個、2個)(4
個、1個)と分けて、同様にあてはめると5+2+2+5＝14通り となる。
答え 14通り
(２) ６個の数をとりあえず、(１個、５個)(２個、４個)(３個、３個)(4個、２個)(５個、１
個)と分けて、同様にあてはめると、
14＋５＋２×２＋５＋14＝42通り
答 え 42通り
考察
二分木やカタラン数と呼ばれる数列です。
1,2,5,14,42,132,429,1430,4862,16796という風に急激に増加してゆきます。
カタラン数は次の式で定義されています。
Cn＝ (2n)!/(n+1)!n! ！は階乗、例えば、３！＝ 3×２×１ ですね。
「将来の大学受験に備えて」という事でもないと思いますが、数学の考え方をヒントにした出題はこれからも増
えることでしょう。
問題2
４チームがトーナメントで試合を行い優勝チームを決めます。それには３試合が必要ですが、試合のやり方は何通りあり
ますか。
問題２の解説
• A,Bの2チームしかないときは、もちろん１通り。
• A,B,Cの３チームでトーナメントをするときは、
A対B・・・１試合目、その勝者対C・・・２試合目、このこ
とを、( (AB)C)と表す。
B対C・・・1試合目、その勝者対A・・・２試合目、このことを、(A(BC)を表す。
以上2通りある。
• A,B,C,Dの4チームでトーナメントをするときは、
(((AB)C)D)、((A(BC))D)、((AB)
(CD))、 (A((BC)D))、(A(B(CD))) の ５通りある。
答え ５通り
問題３
表の空らんに１から８までの数字を順に入れてゆくとき、上の段の数字が下の段の数字より小さく、左のらんの数字が右
のらんの数字より 小さ くな るようにします。何通りの入れ方がありますか。
解説
４列のときは、このような入れ方ですが、１列のときは
の１通りあり、２列のときは、左上の１と右下の４は決定なので、
の２通りあり、3列のときも同様に
の５通りある。場合の数が、１、２、５となっているのでカタラン数を予測して、次のオオカミとヒツジ解法で４列の場合を求める。
上の段に数字を入れることを、右に１区間進むことに対応させ、下の段に数字を入れることを、上に１区間進むことに対
応させている。
答え 14通り
(別解)
計算でやるには、ガウス公式のように、上下で逆に数をならべて、
１ １ ２ ５
５ ２ １ １
上下に並んだの数の積をすべてたしあわせて、１×５＋１×２＋２×１＋５×１＝１４通りとなります。
 考 察
このようにいろいろな場面で登場するカタラン数ですが、「2つの数の和や積」、「1対１の試合」、「上段と下段」、
「オオカミとヒツ ジ」、 「円周上の２点を交わらないよう結ぶ」といった、１対になっている条件付き問 題 で、場合の数
が、１、２、５・・・と増加して行きます。
カタラン数の問題は、最難関校ではよく見かけます
|
