カタラン数                                 戻る

 数学セミナー(2009 8月号)の特集で、寺尾宏明氏(北大・理)がカタラン数のことを取
り上げておられる。2006オープンキャンパスで高校生や一般の方を対象に話されたもの
ということで興味深く読ませていただいた。

 その中で、実は当HPで既に、「三角形分割」や「最短経路問題」で、「カタラン数」のことに
触れているということに気づかされた。

 何でも、「カタラン数」の解釈の仕方にはいろいろあって、2009年4月3日現在、170通
りもあるそうである。

 「カタラン数」という名は、ベルギーの数学者 E.C.Catalan(1814〜1894) の名に由来す
るという。

 n 番目のカタラン数は、「 」と記される。

 カタラン数の解釈として、私的には「トーナメント(勝ち抜き戦)表の場合の数」が一番分か
りやすいような気がする。

例 題  m チームがトーナメント戦を行う。各試合に引き分けはないものとすると、

    優勝チームが決まるまで全部で m−1 試合が必要であることは自明だろう。

    それではその試合のやり方は何通りあるのだろうか。ただし、m≧2 とする。


 いま、  n+1 チームによるトーナメント表の場合の数 とする。

(イ) m=2 のとき、
               

  で、1種類しかない。 このとき、 C1=1 となる。

(ロ) m=3 のとき、
                   

  で、2種類しかない。 このとき、 C2=2 となる。

(ハ) m=4 のとき、
                   


              

  で、5種類しかない。 このとき、 C3=5 となる。


 ところで、上図の(イ)(ロ)(ハ)を眺めていると、演算の結合法則が関係していそうな雰囲
気が漂ってくる!実のところ、カタランの当初の考え方と聞く。

 すなわち、(イ)の(1)は、「 a に b を掛ける」とも理解される。(もちろん「足す」と考えてもよい。

このことを、「 (ab) 」 と書くことにすると、

(ロ)の(1)は、 ((ab)c) だし、 (ロ)の(2)は、 (a(bc)) という意味になる。

また、(ハ)の(1)は、 (((ab)c)d) だし、 (ハ)の(2)は、 ((a(bc))d) となり、

(ハ)の(3)は、 ((ab)(cd)) で、 (ハ)の(4)は、 (a((bc)d)) となり、

(ハ)の(5)は、 (a(b(cd))) であるものと解釈できる。

 この解釈は、さらに次のように考えると、道順の問題に翻訳される。

すなわち、「 (ab) 」は、「 a に b を掛ける」ということなので、「 ab× 」と書くことにする。

このとき、 ((ab)c) は、 ab×c× 、(a(bc)) は、 abc×× と書ける。

また、 (((ab)c)d) は、 ab×c×d× 、((a(bc))d) は、 abc××d× 、

     ((ab)(cd)) は、 ab×cd×× 、(a((bc)d)) は、 abc×d×× 、

     (a(b(cd))) は、 abcd××× と書ける。

 以下では、(ハ)の場合について、道順の場合の数との対応を考えよう。

 そこで、次のような3×3の格子状の道を準備する。

         

 点Aを出発し、点Bに至る道を考える。ただし、

   ab×c×d×などの順列の2番目以降において、

  文字(b、c、d)ならば、「−」(横に移動)、 掛け算「×」ならば、「|」(縦に移動)

するものとする。このとき、

ab×c×d× abc××d× ab×cd××
 
abc×d×× abcd×××

    上記の道順の方法は、ちょうど左図のような街路の最短

   経路の場合の数に等しい。

    その場合の数は、「最短経路問題」によれば、

      42−1=5(通り)

   で、上記の結果と一致する。


 一般に、n+1 チームによるトーナメント表を考え、それを道順の問題に翻訳すると、下図
の街路の点Aから点Bまでの最短経路の場合の数が、カタラン数 C となる。

       


 このとき、下図のような補助の街路を考えることにより、 C が求められる。

   左図より、

   2n-2n-12n-2n-3

  で、上式の右辺をさらに計算すると、

  2(2n−1)!/{(n+1)!(n−1)!}

  すなわち、
         

  という公式が得られる。






 この公式により、カタラン数を全て求めることが出来る。

10 ・・・
14 42 132 429 1430 4862 16796 ・・・

 ところで、カタラン数と組合せの式の関係と言えば、巷間では、

         

が広く知れ渡っているようである。これは、下図のような補助街路を用いて、最短経路を求
めることにより得られる。



   左図より、

   2n2nn-1

 で、何れも、
         

 となるので等しいのは当然だが、素朴

 な疑問で、どちらの方が覚えやすいの

 かな?




 上記では、最短経路問題として、 2n2nn-1 を導いたが、別な視点で、こ
の公式の意味づけを考えてみよう。

 500円硬貨を持つ人が n 人、千円札を持つ人が n 人の計 2n 人が一列に並ぶ。
  各自より、500円を集金するとき、集金する人がおつりを用意しなくても済むような並び
  方は何通りあるか。

 この問題で、例えば、n=3 とし、500円硬貨を持つ人を○、千円札を持つ人を●で表し、
実際に並び方を書いてみよう。

 まず、おつりのことを考えずに、並び方の全てを書きだしてみると、

○○○●●● ○○●○●● ○○●●○● ○○●●●○ ○●○○●●
○●○●○● ○●○●●○ ○●●○○● ○●●○●○ ○●●●○○
●○○○●● ●○○●○● ●○○●●○ ●○●○○● ●○●○●○
●○●●○○ ●●○○○● ●●○○●○ ●●○●○○ ●●●○○○

の 63=20 通りある。このうち、おつりを用意せずに済む並び方は、次の5通りである。
                                    (上記の表の内の青色部分)

○○○●●● ○○●○●● ○○●●○● ○●○○●● ○●○●○●

 問題は、おつりが不足する場合の数の数え方である。次の15通りが該当する。

○○●● ○●○● ○●○○● ○●○●○ ○●●○○
○○○●● ○○●○● ○○●●○ ○●○○● ○●○●○
○●●○○ ●○○○● ●○○●○ ●○●○○ ●●○○○

 上記の15通りの内、おつり不足が最初に発生する位置は、それぞれ赤色の部分である。

この場合の数を数えるために、までの○と●を入れかえる。

 この操作により、の直前までは、○と●は同数なので、必ず、○が1個増え、●が1個
減る。

●●○○○○ ●○●○○○ ●○○○○● ●○○○●○ ●○○●○○
○○○○●● ○○○●○● ○○○●●○ ○○●○○● ○○●○●○
○○●●○○ ○●○○○● ○●○○●○ ○●○●○○ ○●●○○○

 このとき、上記の場合の数は、○4個と●2個の順列の総数に等しいので、

62=15 通りである。

 よって、求める場合の数は、 6362=5 (通り) である。

 上記の考え方を一般化すると、

 まず、500円硬貨を持つ人が n 人、千円札を持つ人が n 人の計 2n 人が一列に並ぶ

場合の数は、 2n 通りある。このとき、あるところでおつり不足が発生する場合の数は、

500円硬貨を持つ人が n+1 人、千円札を持つ人が n−1 人の計 2n 人が一列に並ぶ

場合の数に等しいので、 2nn-1 通りある。

 よって、求める場合の数は、 2n2nn-1 通りある。

(コメント) 背景に最短経路問題を意識したので、ちょっとスッキリしないような意味づけで
      した。読者の方で、「これは!」という意味づけをお持ちの方は是非ご教示下さい。


 平成21年8月11日付けで、HN「凡人」さんよりカタラン数の漸化式の話題をいただいた。

 トーナメント戦の考え方において、次のように考えると、カタラン数についての漸化式が得
られる。

 「n+1 チームによるトーナメント戦の決勝の相手は、

   n チームによるトーナメント戦の優勝チームと、残り 1 チーム

   n−1 チームによるトーナメント戦の優勝チームと、
                        残り 2 チームによるトーナメント戦の優勝チーム

   n−2 チームによるトーナメント戦の優勝チームと、
                        残り 3 チームによるトーナメント戦の優勝チーム

     ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

   2 チームによるトーナメント戦の優勝チームと、
                      残り n−1 チームによるトーナメント戦の優勝チーム

   1 チームと、残り n チームによるトーナメント戦の優勝チーム

 の各場合が考えられるので、 C0=1 として、

    =Cn-1・C0+Cn-2・C1+Cn-3・C2+・・・+C0・Cn-1

 が成り立つ。


(コメント) 凡人さん、ありがとうございます。とても分かりやすい導き方ですね!でも、この
      漸化式を解くことは可能なのでしょうか?解はもう分かっているので、漸化式とい
      うよりも、一つの性質ととらえておけばいいのかな?

 カタラン数 C はまた、凸 (n+2)角形の三角形分割の個数としてもとらえられる。

 次のように考えればよい。( → 参考:「三角形分割」)

 左辺以外の辺に時計回りに、a、b、c、・・・ と文字を割り当て、三角形の第3の辺に、他
の2辺の積を割り当てる。

例 三角形の場合
               この場合、 C1=1 となる。

例 四角形の場合

          

となり、演算結果 ((ab)c) 、(a(bc)) と三角形分割の方法とが関連づけられる。

 この場合、 C2=2 となる。

 「三角形分割」において、次のことを示した。

 凸 n 角形( n≧3 )において、三角形分割の方法の数が、F(n) 通りあるものとする。

明らかに、F(3)=1 である。 いま、n≧4 とする。 3<k<n において、凸 n 角形は

  3つの部分に分割される。

  F(n) の定義より、

 F(n) =1・F(n−1)+F(3)・F(n−2)+・・・

        + F(k−1)・F(n−k+2) +・・・

          + F(n−2)・F(3) +F(n−1)・1


  が成り立つ。




 この公式を用いて、カタラン数 C を計算してみよう。

 C1=F(3)=1

 C2=F(4)=1・F(3)+F(3)・1=2

 C3=F(5)=1・F(4)+F(3)・F(3)+F(4)・1=2+1+2=5

 C4=F(6)=1・F(5)+F(3)・F(4)+ F(4)・F(3) +F(5)・1=5+2+2+5=14

   ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

 ここで、 C0=1 とすれば、例えば、C4 は、

 C4=C0・C3+C1・C2+ C2・C1 +C3・C0

と書き直せるように、一般のカタラン数 C に関する漸化式

    =Cn-1・C0+Cn-2・C1+Cn-3・C2+・・・+C0・Cn-1

の成り立つことが、F(n) に関する漸化式より分かる。

 「三角形分割」において、F(n) に関する漸化式の一般項

     

を求めることができた。 C = F(n+2) という関係から、C の一般項

     

が直ちに得られる。この式と最短経路の問題で得られた C の式

     

は、当然同じ値になる。(すなわち、 2nn-12nn+1 より明らか!)

(コメント) 上記の話で、HN「凡人」さんの疑問に答えられたでしょうか...?

 平成21年8月17日付けで、「凡人」さんがカタラン数の漸化式の解釈に取り組まれた。
(一部文言等を修正させていただきました!)

      

より、
    F(n+2)=2nn-1/n=C

一方
     F(n+3)=2n+2/(n+1)

なので、
       F(n+3)/F(n+2)=n・2n+2/{(n+1)・2nn-1}=2(2n+1)/(n+2)

よって、 C = F(n+2) より、

   (n+2)・Cn+1=2(2n+1)・C

が成り立つ。この式は、三角形分割の個数 F(n) から得られたが、最初から、

   (n+2)・Cn+1=2(2n+1)・C

という漸化式が導けないかというのが「凡人」さんの意図するところであろう。

例 4・C3=10・C2 の解釈を考えてみよう。

 C2=2 は、次の2通りであった。

                   

 このうちの1通り、例えば、
                  

に、新しい1チームを加えるために新しい試合を追加する方法を考える。

          

        

 上記の通り、10通りある。同様にして、
                         

に、新しい1チームを加えるために新しい試合を追加する方法を考えると、

          

        

で、これも10通りある。これらを、C3=5 の場合

        

と比較すると、上記の20通りの中には、4通りずつ同じものが出現していることが分かる。
(トーナメント表の番号が同じものは、同じトーナメント表!)

 以上から、漸化式 4・C3=10・C2 の成り立つことが分かる。

 上記のことを一般化して、「凡人」さんは軽妙に次のように考えられた。

 1.(n+1)チームによるトーナメント表の縦線の本数は「試合数×2+1」本であるが、試
  合数は、n であるので、2n+1(本)の縦線がある。
   このトーナメント表に新たに 1チームを加えるには、2n+1(本)の縦線のうちの 1 本
  から横に線を出して張り出しのような形で 1 チーム分の試合を追加する。

 2.横線は左右どちらにも出す事ができて、それらは区別されるので、計 2(2n+1)通り
  の増やし方がある。

 3.(n+1)チームでの全てのトーナメント表で同じことを行うと、2(2n+1)・C 通りにな
  る。

 4.ところで、(n+2)チームのトーナメント表で、新しく加えられた 1 チームの入る場所を
  区別して考えると、(n+2)・Cn+1 通りのトーナメント表が得られる。

 5.上述の 3.と4.のトーナメント表の数は一致するので、漸化式

      (n+2)・Cn+1=2(2n+1)・C

  が得られる。


(コメント) 「凡人」さんの非凡さに感動しました! このような経験をさせていただいた「凡
      人」さんに感謝します。この考え方をすれば、何も三角形分割を持ち出すことなく、
      漸化式が作れますね。

   漸化式 (n+2)・Cn+1=2(2n+1)・C より、

         (n+1)・C=2(2n−1)・Cn-1

              n・Cn-1=2(2n−3)・Cn-2

         (n−1)・Cn-2=2(2n−5)・Cn-3

            ・・・・・・・・・・・・・・・・・・・・・

               4・C3=10・C2

               3・C2=6・C1

   これらを辺々かけて、

        (n+1)!・C/2=2n−1・(2n−1)!/{2n−1・(n−1)!}

                   =(2n−1)!/(n−1)!

   よって、
        C=2(2n−1)!/{(n+1)!(n−1)!}

   すなわち、
          

   が得られる。


 上記で、三角形分割と演算の順番の関係を見たが、円周上の互いに交差しない弦の引
き方にも関係することを以下に見てみよう。

 円周上に 2n 個の点があるものとする。

例 n=1 のとき

   これは、 (ab) に相当し、括弧のつけ方に注目すれば、

               ()

  で、その場合の数は、カタラン数 C1=1 と一致する。



例 n=2 のとき

              

 これらは、a を省いて考えると、 (b(cd)) や ((bc)d) となり、3文字 A、B、C の場

合の演算の結合の仕方

    (A(BC)) や ((AB)C)

の場合の数に一致するので、カタラン数 C2=2 となる。

例 n=3 のとき

       

             

 これらは、a を省いて考えると、

 (b(cd)(ef)) 、(b(c(de)f)) 、((bc)d(ef)) 、 ((b(cd)e)f) 、 ((bc)(de)f)

となり、さらに、b を省いて、括弧のつけ方を考慮すると、4文字 A、B、C、D の場合の演

算の結合の仕方

((AB)(CD)) 、((A(BC))D) 、(A(B(CD))) 、(((AB)C)D) 、(A((BC)D))

の場合にそれぞれ対応するので、カタラン数 C3=5 と一致する。

 これらのことを一般化して、次の事実が成り立つ。

 円周上の 2n 個の点を互いに交差しない弦で結ぶ方法の数は、カタラン数 C

(証明)
   円周上の 2n 個の点を互いに交差しない弦で結ぶ方
  法の数を F(n)とおく。

   点 1 と点 k を結ぶ弦で、円周上の 2n 個の点を2つ
  のグループに分ける。点 k は、点 1 と同じグループに
  入るものとする。

   このとき、題意より、k の値が奇数になることはない。

  k=2、4、6、・・・、2n−2、2n と場合分けして考える。



k=2 のとき、  円周上 2n−2 個の点を互いに交差しない弦で結ぶ方法の数は、
          F(n−1)通りで、その1通りに対して、残りの2点の弦の引き方は、1通り。

    よって、この場合の数は、 1・F(n−1) 通り

k=4 のとき、  円周上 2n−4 個の点を互いに交差しない弦で結ぶ方法の数は、
          F(n−2)通りで、その1通りに対して、点 1 と点 4 を除いた残りの2点の
          弦の引き方は、F(1)通り。

    よって、この場合の数は、 F(1)・F(n−2) 通り

   ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

k=2n−2 のとき、  点 1 と点 2n−2 を除いた残りの2点の弦の引き方は、F(1)通り
          で、その1通りに対して、円周上 2n−4 個の点を互いに交差しない弦で
          結ぶ方法の数は、F(n−2)通り。

    よって、この場合の数は、 F(n−2)・F(1) 通り。

k=2n のとき、    点 1 と点 2n の弦の引き方は、1通りで、その1通りに対して、円
          周上、2n−2 個の点を互いに交差しない弦で結ぶ方法の数は、F(n−1)
          通り。

    よって、この場合の数は、 F(n−1)・1 通り

 以上から、求める場合の数 F(n)は、

    F(n) =1・F(n−1)+F(1)・F(n−2)+・・・+ F(n−2)・F(1) +F(n−1)・1

となる。これは、カタラン数 C の漸化式

    C=1・Cn-1+C1・Cn-2・+・・・+C1・Cn-2・+Cn-1・C0

に一致するので、F(n)は、カタラン数 C に一致する。 (証終)

 当HPがいつもお世話になっているS(H)さんが、平成21年3月21日付けで、数学的帰納
法の練習問題として、次のような問題を提起された。

集金問題  ある劇場の入場料は、5千円とする。5千円札しかもっていない n(≧ 1)人と、
       1万円札しかもっていない n 人の合計 2n 人が劇場前の広場で勝手に円形の
       輪を作って開場を待っているとする。

        このとき、劇場の入口の受付人は、ある適当な人から時計回りに集金すれば、
       釣り銭に不足することがないようにできることを示せ。

(この集金問題が必ず可能であることは、カタラン数 C≧1 から明らかだろう。
                                        → 参考:「集金問題」)

 命題 P : 全ての自然数 n に対して、劇場の入口の受付人は、ある適当な人から時計回
       りに集金すれば、釣り銭に不足することがないようにできる

(証明) 数学的帰納法による。

 n=1 のとき、 5千円札しかもっていない人と、1万円札しかもっていない人の合計 2人
   が劇場前の広場で待っているので、5千円札しかもっていない人から、5千円札を受け
   取り、次に、1万円札しかもっていない人から1万円札を受け取り、5千円札を渡せば
   よい。 よって、n=1 のとき成り立つ。

 n=k(k≧1)のとき、命題 P が成り立つと仮定する。

   すなわち、5千円札しかもっていない k(≧ 1)人と、1万円札しかもっていない k 人の合
  計 2k 人が劇場前の広場で勝手に円形の輪を作って開場を待っていて、劇場の入口の
  受付人は、ある適当な人から時計回りに集金すれば、釣り銭に不足することがないよう
  にできる。

   今、5千円札しかもっていない k+1人と、1万円札しかもっていない k+1 人の合計
  2k+2 人が劇場前の広場で勝手に円形の輪を作って開場を待っているものとする。

  この中には、5千円札しかもっていない人がいて、しかも、時計回りで隣の人が、1万円
  札しかもっていない人である組合わせが必ず存在する。

  この2人を除くと、残りは、5千円札しかもっていない k(≧ 1)人と、1万円札しかもってい
  ない k 人の合計 2k 人が劇場前の広場で勝手に円形の輪を作って開場を待っていて、
  劇場の入口の受付人は、ある適当な人から時計回りに集金すれば、釣り銭に不足する
  ことがないようにできる。途中で、最初に見つけた2人からは、5千円札しかもっていない
  人から、5千円札を受け取り、次に、1万円札しかもっていない人から1万円札を受け取り、
  5千円札を渡せばよい。

   よって、 n=k+1 のときも、命題 P は成り立つ。

  以上から、全ての自然数 n に対して、劇場の入口の受付人は、ある適当な人から時計
 回りに集金すれば、釣り銭に不足することがないようにできることが示された。 (証終)

 さて、次は、カタラン数の生成関数の話題に移ろう。

 カタラン数については、上記の計算で、

10 ・・・
14 42 132 429 1430 4862 16796 ・・・

であることを見た。そこでは、カタラン数そのものは、バラバラな感じであったが、これら全て
のカタラン数を係数とする1つの多項式を考え、カタラン数の持つ性質を追究しようというの
が、生成関数の考え方である。

 生成関数には、カタラン数に関する情報が全て含まれると言っても過言ではないだろう。

 カタラン数 C生成関数とは、 C0=1 として、

  F(x)=C0+C1・x+C2・x2+C3・x3+・・・+C・x+・・・

と書けるものを言う。

 具体的には、  F(x)=1+x+2x2+5x3+14x4+・・・ という多項式である。

ここで、 C=Cn-1・C0+Cn-2・C1+Cn-3・C2+・・・+C0・Cn-1 から、

  F(x)2=C02+(C1・C0+C0・C1)x+(C2・C0+C1・C1+C0・C2)x2+・・・

      =C1+C2x+C32+・・・

なので、 1+x・F(x)2=C0+C1・x+C2・x2+C3・x3+・・・=F(x) であると言える。

 すなわち、 F(x)は、等式 x・F(x)2−F(x)+1=0 を満たす。

これを、F(x)に関する2次方程式と考えれば、その解は、

     

となるが、F(0)=1 なので、

     

と書ける。これが、カタラン数 C の生成関数となる。

ここで、Taylor 展開のことを考えれば、

     =F(n)(0)/n!

が成り立つ。


   

  なので、 F’(0)=1 より、 C1=F’(0)/1!=1 となる。


 2項定理というと、(a+b) の展開公式だが、実は、n の値は自然数に限らず任意の実
数においても成り立つことが知られている。
               ( → 参考「超越数を手計算で求める」における二項級数の項

 を二項級数に展開して、xn+1 の項を求めると、

    

となる。したがって、
            

を二項級数に展開したときの x の項は、
                          

となる。よって、カタラン数 C の値は、
                        
すなわち、
         
となる。


(追記) 平成25年5月18日付け

 私の代数学の恩師 土井先生が勤められていた立命館大学の文学部・産業社会学部
A方式(2013年)でカタラン数を題材とする問題が出題された。

 

【図1】

【図2】

 上図で東西、南北それぞれ6本の線分は道であるが、対角線ABは道ではないとする。

(1) 【図1】において、AからEを通ってBへ行く最短経路は何通りあるか。(105通り)

  (2) 左図は、(1)の経路において、EからBへ行く経路

    を、図の点線を軸に対称移動させたものであり、Bは

    Cに移る。この図において、AからEを通ってCへ行く

    最短経路は何通りあるか。(105通り)








(3) 【図2】において、対角線ABより南側を通らないで、AからBへ行く最短経路は何通り

  あるかを考える。

 (イ) (2)の図のような考え方を用いて、AからBへ行く最短経路のうち、対角線ABより

  南側を通る最短経路は何通りあるか。(210通り)

 (ロ) 対角線ABより南側を通らないで、AからBへ行く最短経路は何通りあるか。(42通り)

(4) 東西、南北それぞれn+1本の線分を道とし、対角線ABは道ではないとする。このとき、

  対角線ABより南側を通らないで、AからBへ行く最短経路は何通りあるか。

  ((2n)!/(n!(n+1)!)通り)


(コメント) 上記では、紙面の都合で説明を大幅に省略してあるが、実際の本文では、経路
      を数える手順が図を用いて丁寧に導かれている。ただ、説明が長すぎて、受験生
      が試験時間内に対応できたかはちょっと不明...。

       (4)はまさに、カタラン数 C である。



   以下、工事中