■増加整数列(その7)

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

  {3,5,7,1,6,8,9,4,2}

を考える.同様に連続上昇部分の数列の長さを計算すると

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

  |L1|=3,|L2|=4,|L3|=1,|L4|=1

  |L1|=e−1=1.718281828

  |L2|=e^2−2e=1.9524

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

  |Ln|→2

はある多項式fn(x)のeにおける値fn(e)である.驚くことにこれは2に近づく.

 この問題の出典は

  D. Knuth, Tha art of computer programming, Reading, Mass. Addison Wesley, 1975

  Sorting and Searching

にあった.

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

 結論を先にいうと,この問題はオイラー数<n,k>に関係している.

  <n,k>=k<n−1,k>+(n−k+1)<n−1,k−1>

  <n,0>+<n,1>+・・・+<n,n>=n!

  <n,0>=0,<n,1>=1,<n,n>=1

  <n,n−k+1>=<n,k>

  <n,n−1>=2^n−n−1

 二項係数を使うと

  <n,k>=k^n−(k−1)^n(n+1,1)+(k−2)^n(n+1,2)−・・・+(−1)^k0^n(n+1,k)

=Σ(−1)^j(k−j)^n(n+1,j)

 Lkは

  Lk=<1,k>/1!+<2,k>/2!+・・・=Σ<m,k>/m!

その母関数は

  L(z)=ΣLkz^k=z(1−z)/(exp(z−1)−z)−z

より,

  Lk=kΣe^j・(−1)^k-jj^k-j-1/(k−j)!

より,

  |L1|=e−1=1.71828182

  |L2|=e^2−2e=1.95249

  |L3|=e^3−3e^2+3e/2=1.99579

  |Ln|→2

 しかし,Lkは単調増加するのではなく

  |L4|=2.0003

  |L5|=2.0005

  |L6|=2.0000

  |L7|=1.9999

  |L8|=1.9999

  |L9|=1.9999

  |L10|=2.0000

  |L11|=2.0000

  |L12|=1.9999

  |L13|=1.9999

  |L14|=1.9999

  |L15|=2.0000

  |L16|=2.0000

  |L17|=2.0000

  |L18|=2.0000

と振動しながら2に収束する.

 そして,

  L1+L2+・・・+Lk→2k−1/3

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