カタラン数（３）

●　カタラン数　●

　カタラン数は、このホームページでは、
道順（みちじゅん）が何通りあるかという個数でしたね。

　たとえば、下の図で青い数字になっているところまで
（より道しないで）いく行き方は、

　　　　　１　，　１　，　２　，　５　，　１４　，　４２　，　・・・

です。

　そして、これがカタラン数とよばれるものでした。

　（ちなみに、いちばん下の青い数字をむすぶ線は道ではありませんよ！）

　でも、さいしょにカタランが考えたのは、道順の個数ではなく、
こんな問題でした。

　たとえば、

　　　　　ａ＋ｂ＋ｃ＋ｄ　

のたし算の順番（じゅんばん）を考えます。

　（もちろん、ａ×ｂ×ｃ×ｄ　のように、かけ算でもいいのです。）

　そうすると、つぎの　５　通りがあります。

　　　　　（（（ａ＋ｂ）＋ｃ）＋ｄ）

　　　　　（（ａ＋（ｂ＋ｃ））＋ｄ）

　　　　　（（ａ＋ｂ）＋（ｃ＋ｄ））

　　　　　（ａ＋（（ｂ＋ｃ）＋ｄ））

　　　　　（ａ＋（ｂ＋（ｃ＋ｄ）））

　えっ、いちばん外のかっこは、つけなくっていいって？

　じつは、これからのお話のつごうというものがあるのです。

　このように、

　　　　　たし算やかけ算などの順番のつけ方が何通りあるか

といった問題を、カタランは考えたのです。

●　結合の方法　と　道順の個数　●

　さて、これから

　　　　　たし算の順番のつけ方　と　道順の個数

が同じ数だけあることをみていきましょう。

　同じ個数だけあるっていいたいときには・・・
そう、「１対１の対応（たいおう）」をつけてみせればいいのですね。

　このホームページの「トーナメント戦」の
＜森の木を数える＞のところでやったようにねっ！

　その前に、

　　　　　（（（ａ＋ｂ）＋ｃ）＋ｄ）

　　　　　（（ａ＋（ｂ＋ｃ））＋ｄ）

　　　　　（（ａ＋ｂ）＋（ｃ＋ｄ））

　　　　　（ａ＋（（ｂ＋ｃ）＋ｄ））

　　　　　（ａ＋（ｂ＋（ｃ＋ｄ）））

から、いらないものをけしてしまいます。

　まず、ａ　ｂ　ｃ　ｄ　をけします。

　　　　　（（（＋）＋）＋）

　　　　　（（＋（＋））＋）

　　　　　（（＋）＋（＋））

　　　　　（＋（（＋）＋））

　　　　　（＋（＋（＋）））

　これから、もとのａ　ｂ　ｃ　ｄ　がある形にもどす方法は
１通りですから、いらないってことで、けしてしまうのです。
　（ためしに、やってみてね！）

　でも、「＋」は、けしてはいけません。

　たとえば、

　　　　　（（（＋）＋）＋）

から、「＋」をけすと

　　　　　（　（　（　）　）　）

となりますが、これでは

　　　　　（（（ａ＋ｂ）＋ｃ）＋ｄ）

　　　　　（（ａ＋（ｂ＋ｃ））＋ｄ）

　　　　　（ａ＋（（ｂ＋ｃ）＋ｄ））

　　　　　（ａ＋（ｂ＋（ｃ＋ｄ）））

といろいろあって、もとにもどしようがなくなります。

　ところが、じつは「　）」なら、いらないのです。

　　　　　（（（＋＋＋

　　　　　（（＋（＋＋

　　　　　（（＋＋（＋

　　　　　（＋（（＋＋

　　　　　（＋（＋（＋

　これから、もとのａ　ｂ　ｃ　ｄ　と　「　）」　がある形にもどす方法は
１通りなのです。

　さて、この３つの「（　」　と　３つの「＋」　のならべ方ですが、

　　　　　（（（＋＋＋

　　　　　（（＋（＋＋

　　　　　（（＋＋（＋

　　　　　（＋（（＋＋

　　　　　（＋（＋（＋

これらはどれも、とちゅうまでの「（　」の個数が、
「＋」の個数より多いか同じであるものになっています。

　たとえば、

　　　　　（（＋（＋＋

でみてみると、

　　　　　（　　　　　　　　・・・　ここまでの　「（　」は１個　、「＋」は０個
　　　　　（（　　　　　　　・・・　ここまでの　「（　」は２個　、「＋」は０個
　　　　　（（＋　　　　　　・・・　ここまでの　「（　」は２個　、「＋」は１個
　　　　　（（＋（　　　　　・・・　ここまでの　「（　」は３個　、「＋」は１個
　　　　　（（＋（＋　　　　・・・　ここまでの　「（　」は３個　、「＋」は２個
　　　　　（（＋（＋＋　　・・・　ここまでの　「（　」は３個　、「＋」は３個

と、ちゃんとなっていますね。

　このことは、道順でいうと
とちゅう１度もそんをしない、つまりず〜っと上の方にいるってことです。

　もう、何に何を対応させればいいか、わかりましたね。

　つぎのようになります。

●　オイラーの三角形分割問題　●

　カタランよりも先に、オイラーという数学者が
こんなことを考えました。

　　　　　ｎ角形を三角形に分ける方法は何通りあるだろうか

　そして、ちゃんと答えをみつけたのです。

　それは、５角形なら、

　　　　　（（（ａ＋ｂ）＋ｃ）＋ｄ）

　　　　　（（ａ＋（ｂ＋ｃ））＋ｄ）

　　　　　（（ａ＋ｂ）＋（ｃ＋ｄ））

　　　　　（ａ＋（（ｂ＋ｃ）＋ｄ））

　　　　　（ａ＋（ｂ＋（ｃ＋ｄ）））

と同じ、つまり５通りあるのです。

　さあ、このことをみていきましょう。

　ところで、「ベクトル」って知っていますか。

　中学生なら、理科の時間に「力の平行四辺形」として習っているかも。
　高校生なら、数学の時間にやるはずですよ。

　ここでは、ただの数の

　　　　　ａ＋ｂ＋ｃ＋ｄ

のたし算の順番ではなく、ベクトルのたし算の順番を考えます。

　たし算をすると、対角線（たいかくせん）で三角形に分けられます。

　すると、つぎのようになります。

　５角形のばあいは、頂点（ちょうてん）の個数と同じになってしまい、
つまらなかったですね。

　ぜひ、６角形あたりでやってみてください。

　５　のつぎのカタラン数というと

　　　　　１　，　１　，　２　，　５　，　１４　，　４２　，　・・・

ですから、１４　です。

　６角形で、ちゃんと１４通りみつかりましたか。

●　おつりの問題　●

　カタラン数は、いろいろなところで出てきます。

　そのひとつが、「おつりの問題」です。

　たとえば・・・

　かんたんですね。

　　　　　「５０円玉」　を　「（　」
　　　　　「１００円玉」　を　「＋」

に対応させれば、同じ問題になります。

　道順でいえば、とちゅう１度もそんをしない、
つまりず〜っと上の方を通っていく行き方の個数です。

　だから、さっきと同じ　５通りです。

　　　　　（（（＋＋＋　　　　　５０　５０　５０　１００　１００　１００

　　　　　（（＋（＋＋　　　　　５０　５０　１００　５０　１００　１００

　　　　　（（＋＋（＋　　　　　５０　５０　１００　１００　５０　１００

　　　　　（＋（（＋＋　　　　　５０　１００　５０　５０　１００　１００

　　　　　（＋（＋（＋　　　　　５０　１００　５０　１００　５０　１００

　ところで、このホームページの「カタラン数（１）」で
こんなことを考えました。

　ぜんぶで２０通りのうち、ついている「わりあい」が

　　　　　３/３　つまり　ず〜っと上　　　　　　　は　５通り
　　　　　２/３　つまり　２/３上　で　１/３下　　も　５通り
　　　　　１/３　つまり　１/３上　で　２/３下　　も　５通り
　　　　　０/３　つまり　ず〜っと下　　　　　　　も　５通り

でした。

　これを、今の「おつりの問題」にあてはめると

　　　　　おつりがたりなくならない　　　　　　　は　５通り
　　　　　１回おつりがたりなくなる　　　　　　　も　５通り
　　　　　２回おつりがたりなくなる　　　　　　　も　５通り
　　　　　３回おつりがたりなくなる　　　　　　　も　５通り

となってきます。

　じっさい、こうなりますね。

　カタラン数は、ほかにもいろいろ出てきます。

　たとえば、コンピュータのプログラミングなどで、
（　　）の個数があわないと、エラーになりますね。

　この正しい　（　　）　のつけ方（？）もカタラン数になります。

　たとえば、（　　）を３つ使うばあいは、「＋」を「）　」におきかえるだけです。

　　　　　（（（＋＋＋　　　　・・・　　　（　（　（　　　）　）　）

　　　　　（（＋（＋＋　　　　・・・　　　（　（　）　　　（　）　）

　　　　　（（＋＋（＋　　　　・・・　　　（　（　）　）　　（　　）

　　　　　（＋（（＋＋　　　　・・・　　　（　　）　（　（　　）　）

　　　　　（＋（＋（＋　　　　・・・　　　（　　）　（　　）　（　　）

　カタラン数がでてくるのは、まだまだ、たくさんあります。

　いちど、さがしてみてください。

HOME（もどる）

掲載内容の無断転載、転用、編集を禁じます。(c) 小林吹代
All Rights Reserved, （c）kobayashi fukiyo , 2001