一辺の長さnの正方形の桝目を考え、一つの頂点Pから、対角線を経て向かい合う頂点Qに桝目に沿って向かう最短経路の個数を数える。
下の図は、n=4の場合の例示であるが、例えば右図に示した一つの経路は、PからスタートしてQに向かう動作を、「右に向かう→」、「下に向かう↓」の二つに分解して、羅列すると、「右下下右右右下下」、または、「→↓↓→→→↓↓」という文字の配列として表現できる。求めたい最短経路のそれぞれは、それを表す文字列との間に、「一対一で、かつ、漏れのない」対応関係があるから、最短経路の個数を数える「代わり」に、この文字列の個数を数えてもよいことになる。

ここでは、一辺の長さ4であるから、右にも、下にも、それぞれ4回ずつしか移動できないから、これらの文字列の中には、「→」が4個、「↓」が4個、それぞれ含まれることになる。ならば、さらに話をすり替えて、これを「カード並べ」に見立てることもできよう。いわく、
「→」と書かれたカードと、「↓」と書かれたカード、同じしるしが書かれたカード同士は区別がつかないとして、それぞれが4枚ずつある。これらを並べる方法の個数は?
「区別がつ・か・な・い・」のは、観測者側の能力、いわば「主観的」事情で、ここにあるカード「→」と、その右隣の「→」とが、「客観的」に異なる存在であることは言を俟たない。「主観的」に区別を付け得る場合の数を算出するには、ま・ず・、「客観的」なものに対してこれを数え、しかるのち、観測者の能力によって「同じもの」と見えてしまっている「重複分」を除去するのを原則とする。
「→→→→↓↓↓↓」なる8枚のカード、すべて区別がつくならば、その並べ方は、8!、ところが、「→→→→」の4枚は、区別がつかないのであるから、この中に4!ずつの重複が含まれ、同様に「↓↓↓↓」についても、4!ずつの重複が含まれる。よって求める場合の数は、

一般化すると、

これは、次のように説明することもできる。すなわち、「→→→→↓↓↓↓」なる8枚のカードを並べるべき「場所」が8か所ある。この8か所のうち、4か所だけ、「→」を並べるべき「場所」を選べ、というのなら、それは「組み合わせ」8C4であり、一般化すれば、2nCnで、同じ結論になる。

ここで、最短経路の取り方に、若干の制限を加える。すなわち、対角線PQを境に、右上の領域しか使ってはならない、とするのである。ただしPQ上の各点を通過することは差支えない。つまり、

のようなものは数えるが、

のようなものは、ルール違反として排除する、というのである。
さて、では、この「制限を受けた」最短距離の個数を数えるには、「ルール違反をしていな・い・」という否定文で表示されるものよりも、「ルール違反をしている」と肯定文で表示されるものの方が、数えやすそうであるから、もちろん、これは、前者を「ルールを守っている」、後者を「ルールを守っていない」と言い換えれば、直ちに「肯定/否定」が逆転するのだから、「詭弁」ではある(笑)が、方針としては、上で述べた、すべての経路の個数2nCn、から、「ルール違反」の個数を何とか算出したうえ、これを除去する、ということにする。

ルール違反の事実が最初に検知されるのは、対角線PQよりも左下の領域の経路を採用した瞬間、ということは、Pの下隣り、Qの左隣り、を結んだ、下図ならばブルーで示した線上の各点、に至ったときである。

そこで、すべての「ルール違反」の経路に関して、最初のルール違反以降の経路を、このブルーの直線に関して線対称に裏返してみる、という奇抜な発想を取る。もちろん、私が思いついたわけではなく、どこの参考書にも書かれているのかもしれないが、ここでは、「離散数学『数え上げ理論』」野崎昭弘(講談社ブルーバックス)をまねすることにする。
「ルール違反」の3例と、その「裏返し」操作を、下に示す。


奇妙なことに、いや、頭のよいヒトにはちっとも奇妙ではないのかもしれないが(笑)、この操作によって、「ルール違反」の経路は、ことごとく、Pから、図中Q'と記した点への、最短経路へ変換される。この変換は、「一対一で、かつ、漏れのない」対応関係、と思われるから、すべての「ルール違反」経路の個数を数え上げる「代わり」に、PからQ'への最短経路の個数を数えればよいことになろう。
ところで、上の例示では、Pを原点として、右にx軸、下にy軸をとれば、Qの座標は、(4,4)であったのに対し、Q'は(3,5)と書ける。つまり「右向き」が一つ減り、「下向き」が、一つ増えるのである。
PからQ'への最短経路の個数、すなわち、「ルール違反」経路の個数は、ここでは、8C3=8C5であり、一般化すれば、2nCn+1=2nCn-1
よって、「ルール違反」していな・い・、右上半分しか使ってはならないという制限を受けた最短経路の個数は、ここでは、8C4-8C3、一般化すれば、
2nCn-2nCn-1
となった。これを世に、「カタラン数」と称し、cnと表記する。こうして、
cn=2nCn-2nCn-1
が得られた。次のようにも書くことができる。


制限なしの最短経路数2nCnと、カタラン数cn、を計算してみた。nが大きくなったところで、近似計算になっているのかどうかは、よくわからない(笑)。

ものを正しく「数える」ために肝要なことは、 の二点であって、例えば「世界=全体集合U」を、「Aであるか?」、「Bであるか?」の二つの問いで切り分けた場合、「世界」は4つの部分集合、A∩B、A∩Bc、Ac∩B、Ac∩Bc、に分けられるが、これらのどの二つの間にも共通の要素はなく、これを「互いに素」という、かつ、これら四つの集合の合併がそのまま全体集合となる。



このように「互いに素」であるものの合併を「直和」と呼び、集合を、「互いに素」な部分集合に分解することを「直和分解」と言ったはずだ。つまり、

ということで、このように分解された集合Ai  (i=1,2,3,・・・,n)についてなら、その要素の個数(濃度、カーディナル数)については、

が成り立つことになる。

では、ここでの、「制限を受けた最短経路」問題、において、一体何を基準に「直和分解」を行えば、都合がよいであろうか?、いやはや、勿体付けるのはやめよう(笑)、私はもう、この書物を読んで答を知っているのだし、いったん知ってしまうと、もう、それはあまりに卓抜なやり方で、それ以外にはありえない気がしてくる、誰がはじめに気づいたのか存じないが、私如きには決して思いつけなかった観点である。

「制限」は、対角線PQ上の点を通ってもいいが、PQより下の領域には決して入ってはならない、ということであった。ということは、対角線PO上の点、一辺nの正方形ならば、n+1個の点があるわけで、これを、P0,P1,・・・,Pn=Qと名づけるならば、許される経路は、これらの点のうちのいくつかを通るかもしれないし、いや、まったく通らないかも知れない。PおよびQ自体、対角線PQ上の点であるので、いかなる経路もこの2点は必ず通る。ならば、
P以外に、は・じ・め・て・通る、対角線PQ上の点、
によって、すべての経路を分解したらどうか?、と言うのである。そのような点の候補としては、PすなわちP0は除外されなければならないから、Pk  (k=1,2,3,・・・,n)ということになろう。ここで、k=nは、Pn=QではじめてPQ上を通る、と言うのだから、それは、PQ以外は「通らない」場合を表しているわけである。
このようにして、1からnの値を取りうる自然数kによって、すべての経路を「直和分解」することができたことになる。ならば、もし、PkにおいてはじめてPQと出会うような経路の個数を、自然数kを含む式で表現できたならば、それらを、k=1からnまで加算することによって、すべての経路の数を、nによって表記することができるではないか?

下図は、Pkで初めて対角線PQと出会った場合を表している。



右下のオレンジ色の三角形は、点Pkから、点PnすなわちQ、に至る一辺n-kの正方形の右上半分しか使えないという制限付き経路問題を表しているから、その経路の個数は、私たちはすでに、この問題の解が「カタラン数cn」なるもので表されることを知っているので、その表記にならえば、cn-kということになろう。
一方、点P0すなわちPから、点Pkに至る経路については、この間では、決して対角線PQに触れてはな・ら・な・い・、という厳しい制限に服しているので、ならば一歩譲って(笑)、Pの右隣をX、Pkの上隣りをYとして、対角線XYならば、どうぞご随意に、触れていただいて結構、とすれば、これはXYを対角線とする一辺k-1の正方形の右上半分しか使えない制限付き経路問題、ということになりはしないか?、ならばその経路の個数は、ck-1であり、PからPkまでの経路の選び方と、PkからQまでの経路の選び方は、誰が見ても(笑)、「独立」であるから「乗法定理」に服し、こうして、
PkにおいてはじめてPQと出会うような経路の個数は、ck-1×cn-kであることが、判明したのである。ならば、次のように言うことができよう。



これは、前回紹介した、

のような「閉じた表式」、すなわち、変数nに好き勝手な自然数を代入すれば、多少の手間はかかっても、直ちに、答えを得ることができるものとは異なって、cnを知るために既にして、ck-1なりcn-kを知っていなければならない、そのためには、k=1から順に積み上げるように、「帰納的」に、算出していかないと、決してnに到達できないような構造、いわば「自己言及的」な構造、平たく言えば(笑)。漸化式、ないし、差分方程式、となっているのである。
これによって「カタラン数」を算出する過程を、以下の数表に示す。表が大きくなりすぎて、縮小してあり、老眼ではほとんど判読できないが(笑)、表上をクリックしていただければ、原寸表示できるようにしてある。



そして、この「カタラン数」の「漸化式表現」こそが、むしろ、様々な応用場面への見通しを良くさせてくれるものであることが、次回以降の話題となるであろう。
「数理言語学」と言う学問分野があるそうで、そりゃ、あるだろう、私たちが、その、ほかならぬ学問的見解を語ってしまうときに採用する「言語」と言うものを、いわば「自己言及」的に研究対象とするならば、いったんは、その「意味」をカッコに入れ、出鱈目な記号の配列に過ぎない、と、極端に「客観的」に扱ってみるアプローチが考えつかれて当然であろう。同書、「離散数学『数え上げ理論』」野崎昭弘(講談社ブルーバックス)に挙げられていた例示を芸もなく孫引きすることにすると、たとえば、
黒い、目の、女の、子
と言うひとつながりの言葉があるときに、これら四つに切り分けられた言葉ののつながり方に、少なくとも常識的なやり方で、「意味を成す」方法が、二つ考えられるだろう。
一つ目は、「女の子」が、「黒い目」をしている、のであり、もう一つは、「黒い目の女」に「子」がいる、という話である。両者を区別する記号表記を考えると、例えば、
前者は、((黒い目の)(女の子))、後者が(((黒い目の)女の)子)とすることができる。あるいは、つながりの「階層構造」を強調して、カッコを区別し[{()}]を採用すれば、
前者は、{(黒い目の)(女の子)}、後者が[{(黒い目の)女の}子]となるだろう。このようにして、隣接する二つの言葉の関係の濃淡を、階層構造を表示するカッコによって区切っていく、これを「構文分析」と呼ぶようなのであるが、直ちに生ずる疑問の一つは、まず、なぜ二語なのか?、これは、三語以上の関係も、ことごとく、まず、二語の関係を問題にし、まとめられた二語と、さらに隣接する一語との関係を見ればよい、上の、{(黒い目の)女の}のかわりに、{黒い(目の女の)}でもよい、とするみたいに。もう一つは、隣接している二語の関係しか見ないのか?、ということだが、半ば冗談で素人ながらに考えてみると、上例で、「目」と言う名詞の代わりに、同じく名詞「やんきー」を代入したらどうなるか?、このように相互に「代入」可能な語彙の集合を、「パラダイム」と呼んだはずだ、が、「黒い」と言う形容語句が、直ちに、「目/やんきー」と言う直後の名詞を飛び越えて、「子」ないし「女の子」に意味的に結びついてしまうのである。何とも不思議な現象であるが、こんな雑な議論を続けると、かならずどこかで、racist/sexist的なにやにや笑いを招き寄せてしまうので、ここでは、四つの語を、客観的なA、B、C、Dなる記号に代替することにし、かつ、次の如きルールを導入する。つまり、A、B、C、Dと、ほかならぬこの順序で発話された、語順を、絶対的な前提とし、「関係」は、隣接する二語間にし・か・、生じない。その二者関係を、より緊密なものから順に、()、{}、[]、・・・、なる記号によって表記していこう。

四語ABCDに対して、さて、このような切り分け方が、何通りあるであろうか?、もちろん「オチ」としては、これが「カタラン数」に関連付けられるわけなのだが、差し当たり、知らないふりをしてやってみる。
さしあたり、最初の二語ABをカッコに入れてみようか?、・・・、(AB)CD
これで(AB)は、一語になってしまった、と見ればよい、ならばそれをたとえばPとでも置き換え、いまや、PCDなる配列を考えているのである。次なるカッコ付けは、(PC)DとP(CD)しかありえないわけである。元に戻すと、・・・、((AB)C)Dと(AB)(CD)
階層構造を強調して書けば、・・・、[{(AB)C}D]と{(AB)(CD)}
実は、最初にCDを選んでいても、ほぼ同様の事態が生じていたはずだ。・・・[(A{B(CD)}]と{(AB)(CD)}
{(AB)(CD)}は重複しているから、現時点で、3種類の方法がリストアップされたことになる、・・・、[{(AB)C}D]、[(A{B(CD)}]と{(AB)(CD)}
まだ検討していないのは、はじめにBCをカッコに入れる場合である。・・・、A(BC)D
これまた(BC)が一語Qになったと考えれば、AQD、これを区切る方法は、(AQ)D、A(QD)、のみ、もとに戻すと、・・・、(A(BC))D、A((BC)D)
階層構造を強調すると、・・・、[{A(BC)}D]、[A{(BC)D}]
こうして、やっとのことで、すべてリストアップできたのである。・・・、[{(AB)C}D]、[(A{B(CD)}]、{(AB)(CD)}、[{A(BC)}D]、[A{(BC)D}]
答は、ABCD4語に対して、5通りであった。

こんな迂遠なことをしなければならないのだろうか?、もちろん否である(笑)。
ABCD四語の、「間」は3つある。ここに、ま・ず・、第一段階の「仕切り」と入れよう。これを赤色の「|」で表す。
A|BCD、AB|CD、ABC|D
もちろん三通りに決まっている(笑)。次に第二段階の「仕切り」を入れるのだが、語は、最低でも二つ、つながっていなければならなかった。だから、もはや二語になってしまっているところに、もう一つ下位の「仕切り」を入れることは、してはならない。つまり、まんなかのAB|CD、には、第二段階の「仕切り」を入れることは、できない。よって、これを緑色の「|」で表すことにすれば、
A|B|CD、A|BC|D、AB|CD、A|BC|D、AB|C|D
ほら、ちゃんと5通り、できているじゃないか?、これを、緑色の線が「下位」の区分で、赤色の線が「上位」の区分だ、ということを意識して、カッコ書きに改めれば、
[A{B(CD)}]、[A{(BC)D}]、{(AB)(CD)}、[{A(BC)}D]、[{(AB)C}D]
の5通りに、ちゃんと対応している!、どうやら、「仕切り」を入れる、が、ここでの話の「直和分解」として有効らしいことがわかったのである。「カタラン数」とのつながりは、まだまだ不明だがね。次回以降のお楽しみ、である。
4語の「構文分析」が、
A|B|CD、A|BC|D、AB|CD、A|BC|D、AB|C|D
の5通りだったのである。奇しくもこの5なる数字が、「カタラン数」c3に符合している訳である。

わずかこの一例をもって、
m語の「構文分析」の方法の個数は、cm-1である、
と断言するのは、いや、結局は断言するのだが、さすがに気が引けるので、もう少し、裏を取っておきたい。
ちなみに、c0=1である。これは、一辺ゼロの正方形の上半分しか使えないという制限付き経路問題、などと言ってみても無意味で、0!=1、を無理由的に「定義した」ことに由来する。順列nPr=n!/(n-r)!の「公式」がn=rにおいても通用するように、言わば、システムに「ほころび」が生じないようにするための「約束事」なのだ、と理解する以外に方法がない。現に、「カタラン数」の「閉じた表式」において、n=0を代入すれば、0!=1である限り、文句なく、c0=1が導かれる。

つまり、 では、5語について、本当に、c4=14、14通り、となるかを、確かめてみたい。
ABCDE、なる5語の「間」は4つ、ここに「第1段階」の「仕切り|」を入れる方法は、以下の4通り、
A|BCDE、AB|CDE、ABC|DE、ABCD|E
この「第1段階」の「仕切り」の左右のどちらか一方が、すでに2語以下になってしまった部分には、もはや、「第二段階」の「仕切り|」を入れることができないので、
A|BCDE、からは、A|B|CDE、A|BC|DE、A|BCD|E、の3通り、
AB|CDE、からは、AB|C|DE、AB|CD|E、の2通り、
ABC|DE、からは、A|BC|DE、AB|C|DE、の2通り、
ABCD|E、からは、A|BCD|E、AB|CD|E、ABC|D|E、の3通り、
ここまでで、3+2+2+3=10通り、これらのうち、さらに「第三段階」の「仕切り|」をほどこすことが可能なのは、少なくとも3語のつながりが、仕切りと仕切りの間に残されているものに限るから、
A|B|CDE、A|BCD|E、A|BCD|E、ABC|D|E、の4通りで、これらから、それぞれ、次のものが生じる。
A|B|CDE、から、A|B|C|DE、A|B|CD|E、
A|BCD|E、から、A|B|CD|E、A|BC|D|E、
A|BCD|E、から、A|B|CD|E、A|BC|D|E、
ABC|D|E、から、A|BC|D|E、AB|C|D|E、
これで出そろった。確かに14とおりである。これを、階層構造を示すカッコで表すとすると、[{()}]の3段階しか表記方法がないので、一番外側は省略して、
  1. A|B|C|DE、・・・・・・、A[B{C(DE)}]
  2. A|B|CD|E、・・・・・・、A[B{(CD)E}]
  3. A|BC|DE、・・・・・・、A{(BC)(DE)}
  4. A|B|CD|E、・・・・・・、A[{B(CD)}E]
  5. A|BC|D|E、・・・・・・、A[{(BC)D}E]
  6. AB|C|DE、・・・・・・、(AB){C(DE)}
  7. AB|CD|E、・・・・・・、(AB){(CD)E}
  8. A|BC|DE、・・・・・・、{A(BC)}(DE)
  9. AB|C|DE、・・・・・・、{(AB)C}(DE)
  10. A|B|CD|E、・・・・・・、[A{B(CD)}]E
  11. A|BC|D|E、・・・・・・、[A{(BC)D}]E
  12. AB|CD|E、・・・・・・、{(AB)(CD)}E
  13. A|BC|D|E、・・・・・・、[{A(BC)}D]E
  14. AB|C|D|E、・・・・・・、[{(AB)C}D]E
嗚呼、疲れた。今日はこれまで。
実は、この段階で、以前述べた、「カタラン数」の、漸化式表示、

と、この「構文分析」との関連は、見えていることに気づくのである。
5語の「構文分析」において、「第1段階」の「仕切り|」を入れる方法は、以下の4通りであった。
A|BCDE、AB|CDE、ABC|DE、ABCD|E
それぞれの場合について、この「第1段階」の「仕切り|」の左右が、何・語・の・「構文分析」の「サブ・ユニット」になっているかを見てみよう。 全体として、5語の「構文分析」に対応する「カタラン数」c4は、
c4=c0×c3+c1×c2+c2×c1+c3×c0
と、上に掲げた漸化式表示そのままのことが、生じているのである。

ここまでの話をまとめよう。
  • 一辺nの正方形の格子の、上半分しか使ってはならない、という「制限付きの最短経路」問題においては、
    対角線PQ上の、P以外のどの点をは・じ・め・て・通過するか?、が、有効な「直和分解」となった。
    そして、そのすべての場合の数は、cnで表された。
  • m語の「構文分析」においては、
    m語の「間」の、m-1か所の、どこに第・1・段・階・の・仕切りを入れるか?、が、有効な「直和分解」となる。
    そして、そのすべての場合の数は、cm-1で表されることになる。

では、次のテーマ、「カタラン数」の応用場面として知られているもう一つの有名なものに、「凸多角形の三角形分解」がある、のだそうである。
ちょっと趣向を変えて、7角形にしてみよう。頂点に番号1〜7を振り、辺1-7を、底辺として「固定」する。この、底辺1-7を一辺とする三角形の、他のも・う・一・つ・の・頂点、これが、ここでの「直和分解」の基準となる。7角形の一辺を固定したのだから、この一辺と三角形をなしうる頂点の個数は、7-2=5。「構文分析」における「第1段階の仕切り」からの類推によれば、どうやら、「カタラン数」c5に対応しそうではないか?

では、その予測のもとに、「カタラン数」の漸化式表現と、関連付けてみよう。 合計、
c0×c4+c1×c3+c2×c2+c3×c1+c4×c0=1×14+1×5+2×2+5×1+14×1=42
ほら、c5じゃないか!
42通りの対角線を引いてみる労は惜しみたいので(笑)、もう少し数の少ない、五角形で、確認してみたい。
合計、
c0×c2+c1×c1+c2×c0=1×2+1×1+2×1=5=c3
上図に破線で示したように、確かに、全部で5通りなのである。したがって、
  • 一辺nの正方形の格子の、上半分しか使ってはならない、という「制限付きの最短経路」問題においては、
    対角線PQ上の、P以外のどの点をは・じ・め・て・通過するか?、が、有効な「直和分解」となった。
    そして、そのすべての場合の数は、cnで表された。
  • m語の「構文分析」においては、
    m語の「間」の、m-1か所の、どこに第・1・段・階・の・仕切りを入れるか?、が、有効な「直和分解」となる。
    そして、そのすべての場合の数は、cm-1で表されることになる。
  • 「凸l角形の三角形分解」においては、
    l個の頂点のうち2頂点を底辺として固定するから、残りl-2個のうち、その底辺と三角形をなしうる、も・う・一・つ・の・頂点をどれにするか?、が、有効な「直和分解」となる。
    そして、そのすべての場合の数は、cl-2で表されることになる。
と、言えそうである。

最後に、「凸多角形の三角形分解」と「構文分析」をつなげて考える方法について、考えてみよう。
4語の「構文分析」、ABCD、なる文字列に対して、その「間」及び両端に、数字1〜5をはめこむ、つまり、
1A2B3C4D5
「構文分析」での「直和分解」の要諦は、語と語の「間」に仕切りを入れることであった。それは、この例では、数字2,3,4の中から、どれか一つを選ぶことに対応している。これすなわち、「凸五角形の三角形分解」と、同じではないか?

「カタラン数」の、ネタは、大体、この辺でおしまいのようである。