漸近評価
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/06/30 11:12 UTC 版)
デデキント数の対数をとったものは次の上界・下界で漸近的な評価ができる。 ( n ⌊ n / 2 ⌋ ) ≤ log 2 M ( n ) ≤ ( n ⌊ n / 2 ⌋ ) ( 1 + O ( log n n ) ) . {\displaystyle {n \choose \lfloor n/2\rfloor }\leq \log _{2}M(n)\leq {n \choose \lfloor n/2\rfloor }\left(1+O\left({\frac {\log n}{n}}\right)\right).} ここで左側の不等式はちょうど ⌊ n / 2 ⌋ {\displaystyle \lfloor n/2\rfloor } 個の元から成る反鎖の個数を数えることで得られ、右側の不等式は Kleitman & Markowsky (1975) により証明された。 Korshunov (1981) は、以下のより正確な評価式を導いた。 n が偶数のとき、 M ( n ) = ( 1 + o ( 1 ) ) 2 ( n ⌊ n / 2 ⌋ ) exp a ( n ) {\displaystyle M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor }\exp a(n)} n が奇数のとき、 M ( n ) = ( 1 + o ( 1 ) ) 2 ( n ⌊ n / 2 ⌋ + 1 ) exp ( b ( n ) + c ( n ) ) {\displaystyle M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor +1}\exp(b(n)+c(n))} ただし a ( n ) = ( n n / 2 − 1 ) ( 2 − n / 2 + n 2 2 − n − 5 − n 2 − n − 4 ) , {\displaystyle a(n)={n \choose n/2-1}(2^{-n/2}+n^{2}2^{-n-5}-n2^{-n-4}),} b ( n ) = ( n ( n − 3 ) / 2 ) ( 2 − ( n + 3 ) / 2 + n 2 2 − n − 6 − n 2 − n − 3 ) , {\displaystyle b(n)={n \choose (n-3)/2}(2^{-(n+3)/2}+n^{2}2^{-n-6}-n2^{-n-3}),} c ( n ) = ( n ( n − 1 ) / 2 ) ( 2 − ( n + 1 ) / 2 + n 2 2 − n − 4 ) . {\displaystyle c(n)={n \choose (n-1)/2}(2^{-(n+1)/2}+n^{2}2^{-n-4}).} とする。この評価式の背景にあるアイディアは、ほとんどの反鎖において、各元（部分集合）の濃度が n/2 に非常に近いという事実である。n = 2, 4, 6, 8 に対してKorshunovの公式はそれぞれ誤差率 9.8%, 10.2%, 4.1%, -3.3% の評価値を与える。
※この「漸近評価」の解説は、「デデキント数」の解説の一部です。
「漸近評価」を含む「デデキント数」の記事については、「デデキント数」の概要を参照ください。
- 漸近評価のページへのリンク
