■ラムゼー数(その24)

 カタラン数には,たとえば,n×n格子で対角の位置に移動するのに対角線をまたがないでいくやり方というの意味がある.

 その図形は階段状をなすが,たとえば,8段の階段状図形を6個の長方形で覆うやり方と八角形を6個の三角形に分割する仕方の数は等しく,ともに

  C6=132

通りである.

===================================

【1】モツキン数

 n×n格子の原点(0,0)から(n,0)の位置に移動するやり方を考える.経路としては1単位右に移動する(+1,0),斜め上に移動する(+1,+1),斜め下に移動する(+1,−1)の3経路だけが可能であるとする.

 6×6格子の場合,51通りの経路が可能である.

 カタラン数はn組の括弧{,}を正しく並べるやり方の数という意味があるが,モツキン数は可能な経路が3経路になるので,括弧{,}と文字xを入れ個にした正しく並べるやり方の数になる.したがって,

  モツキン数51>カタラン数C4=14

===================================