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

【1】ファン・デル・ヴェルデン予想

 n次の行列で成分aij≧0,行和=1,列和=1のとき,永久式の値≧n!/n^nである.等号はaij=1/nのときのみ成立する.

 すなわち,各成分が非負で,すべての行和=1,すべての列和=1であるような2重確率行列Aについて,

  perA≧n!/n^n

である.

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

[1]行和,列和がすべて2のn次(0,1)行列に対して

  perA≦2^[n/2]

[2]行和がr1,r2,・・・,rnのn次(0,1)行列に対して

  perA≦Π(rj!)^1/rj

[3]行和,列和がすべてrのn次(0,1)行列に対して

  M(n,k)=maxperA,M(k)=lim{M(n,k)}^1/k

  m(n,k)=minperA,m(k)=lim{m(n,k)}^1/k

とおくと,

  M(n,k)≧k!,M(k)≧{k!)^1/k

  k→∞のとき,M(k)→k/e

  m(k)≧k/e,

したがって,k→∞のとき,(perA)^1/n→k/e

  m(n,3)≧6(4/3)^n-3

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