■増加整数列(その1)

n=rs+1個の整数列は、必ず長さr+1の増加部分列か、長さs+1の減少部分列を含む。

証明はrに関する数学的帰納法による。

それでは

増加(減少)列の長さの平均は?

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

 (1,2,3,4,5,6,7)の順列,たとえば,

  3,4,5,1,6,7,2

を考える.

 これは単調増加する部分列3つ

  L1={3,4,5},L2={1,6,7},L3={2}

に分かれる.

 (1,2,3,4,5,6,7,・・・,n)の順列でも同様に考えることができる.

 n→∞のとき,L1の長さの平均は,

  e−1=1.718281828

に近づく.同様に

  L2=e^2−2e=1.9524

  L3=e^3−3e^2+3e/2=1.9957

  Ln→2

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