■いろいろの漸化式と母関数(その14)

 K6のすべての2頂点間を2色の線で結ぶと,点をつなぐ線がすべて赤かすべて青の三角形ができる.

 従って,どのような6人の集団でも,3人の友人関係が存在するか,互いに見知らぬ3人が存在することになる.つまり,この問題はラムゼー理論と密接な関係にある.

 たとえば,3つに自然数b,p,q(p,q≧b)に対し,以下の性質をもつ整数R(b,p,q)が存在する.

 Eを位数|E|≧R(b,p,q)なる任意の集合とし,Eの部分集合でb元からなるものを2つのグループF1,F2に分ける.このときEのp元からなる部分集合が存在し,そのどのb元からなる部分集合もF1の属する,かつ,Eのq元からなる部分集合が存在し,そのどのb元からなる部分集合もF2に属する.

 R(2,3,3)=6,R(2,3,4)=9,R(2,3,5)=14,

 R(2,3,6)=18,R(2,4,4)=18,

 R(2,3,7)=23,R(2,3,9)=36

であるが,高次ラムゼー数の大多数はまだ知られていない.ラムゼー数R(b,p,q)の決定すら完全にはできていないのである.

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

  N(1)=2,N(2)=5,N(3)=16

  N(q)=R2(31,32,・・・,3q)−1

であるから,

  R2(3)=3,R2(3,3)=6,R2(3,3,3)=17

別の流儀に従って書けば

  R(2,3)=3,R(2,3,3)=6,R(2,3,3,3)=17

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