カタラン数
た し 算は二つの数から一つの数を求める計算で、三つ以上の数をたすときには、二つの数のたし算をくり返していくことになります。例えば 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 個の数の和のとき・・・1通り
◆3個の数の和のとき・・・2通り
◆4個の数の和のとき・・・4個の数をとりあえず、(1 個、3個)(2個、2個)(3個、1個)と分けて、2個の数の和の1通りと3個の数の和の2 通りをあてはめて、2+1+2=5通り
◆5個の数の和のとき・・・5個の数をとりあ えず、(1個、4個)(2個、3個)(3個、2個)(4 個、1個)と分けて、同様にあてはめると5+2+2+5=14通り となる。
答え 14通り
(2) 6個の数をとりあえず、(1個、5個)(2個、4個)(3個、3個)(4個、2個)(5個、1個)と分けて、同様にあてはめると、14+5+2×2+5+14=42通り
答 え 42通り
考察
二分木やカタラン数と呼ばれる数列です。 1,2,5,14,42,132,429,1430,4862,16796という風に急激に増加してゆきます。
カタラン数は次の式で定義されています。Cn=(2n)!/(n+1)!n! !は階乗、例えば、3!= 3×2×1 ですね。
「将来の大学受験に備えて」という事でもないと思いますが、数学の考え方をヒントにした出題はこれからも増えることでしょう。
もど る