二項係数
[Wikipedia|▼Menu]
□記事を途中から表示しています
[最初から表示]

m) を整除する最大の p-冪が pc であるとき、c は m と n を加えるときに生じる p-進表示における繰り上がりの数に等しいことを示した[9]。同じことだが、(n
k) における素因子 p の冪指数は .mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}k⁄p j の小数部 が n⁄p j の小数部よりも大きくなるような非負整数 j の総数に等しい。これにより、(n
k) が n⁄gcd(n,k) で割り切れることが導かれる。したがって特に、任意の正整数 r および s < pr なる正整数 s に対して p は (pr
s) を割り切る。しかしより高次の p-冪に対してこれは正しくない(例えば 9 は (9
6) を割り切らない)。

Singmaster (1974) は「任意の整数がほとんど全ての二項係数を整除する」という幾分驚くべき結果を与えた。より精確に言えば、整数 d を固定して、f⁡(N) は n < N なる二項係数 (n
k) のうち d で割り切れるものの総数を表すものとすると、 lim N → ∞ f ( N ) N ( N + 1 ) / 2 = 1 {\displaystyle \lim _{N\to \infty }{\frac {f(N)}{N(N+1)/2}}=1}

が成り立つというものである。n < N なる二項係数 (n
k) の総数は 1/2N(N + 1) であるから、これは d で整除可能なものの占める密度が 1 に収束することを意味する。

別の事実として、整数 n ? 2 が素数となる必要十分条件は、中間二項係数 ( n 1 ) , ( n 2 ) , … , ( n n − 1 ) {\displaystyle {\binom {n}{1}},{\binom {n}{2}},\ldots ,{\binom {n}{n-1}}}

の全てが n で整除可能なことである。実際、p が素数ならば、0 < k < p なる任意の k に対して p は ( p k ) = p ⋅ ( p − 1 ) ⋯ ( p − k + 1 ) k ⋅ ( k − 1 ) ⋯ 1 {\displaystyle {\binom {p}{k}}={\frac {p\cdot (p-1)\cdots (p-k+1)}{k\cdot (k-1)\cdots 1}}}

を割り切る。これは分子は素因数 p を含むが分母は p を素因数に持たないことによる。n が合成数のとき、p を n を割り切る最小の素因数とし、k = n/p と置けば、0 < p < n かつ ( n p ) = n ( n − 1 ) ( n − 2 ) ⋯ ( n − p + 1 ) p ! = k ( n − 1 ) ( n − 2 ) ⋯ ( n − p + 1 ) ( p − 1 ) ! {\displaystyle {\binom {n}{p}}={\frac {n(n-1)(n-2)\cdots (n-p+1)}{p!}}={\frac {k(n-1)(n-2)\cdots (n-p+1)}{(p-1)!}}}

は n で割り切れない。仮に割り切れるとすると分子 k(n − 1)(n − 2) × … × (n − p + 1) が n = k × p で割り切れることになり、それは (n − 1)(n − 2) × … × (n − p + 1) が p で割り切れる場合しかありえないが、n は p で割り切れるのだから、p は n − 1, n − 2, …, n − p + 1 を割り切らず、p は素数だから従って (n − 1)(n − 2) × … × (n − p + 1) も割り切らず、それゆえ分子が n で割り切られることもない。
上界・下界と漸近公式

(n
k) に関して以下の評価 ( n k ) k ≤ ( n k ) ≤ n k k ! ≤ ( n ⋅ e k ) k {\displaystyle \left({\frac {n}{k}}\right)^{k}\leq {\binom {n}{k}}\leq {\frac {n^{k}}{k!}}\leq \left({\frac {n\cdot e}{k}}\right)^{k}}

が 1 ? k ? n に対して成立する。スターリングの近似からは √n (2n
n) ? 22n−1, 一般に n ( m n n ) ≥ m m ( n − 1 ) + 1 ( m − 1 ) ( m − 1 ) ( n − 1 ) {\displaystyle {\sqrt {n}}{\binom {mn}{n}}\geq {\frac {m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}}}

が m ? 2 かつ n ? 1 に対して成立する。また n → ∞ のとき近似 ( 2 n n ) ∼ 4 n π n {\displaystyle {\binom {2n}{n}}\sim {\frac {4^{n}}{\sqrt {\pi n}}}}

が成り立つ。n, k がともに 1 より十分大きければスターリング近似からは以下の漸近近似 log 2 ⁡ ( n k ) ∼ n H ( k n ) {\displaystyle \log _{2}{\binom {n}{k}}\sim nH\left({\frac {k}{n}}\right)}

も従う。ここに H⁡(ε) = −εlog2⁡(ε) − (1 − ε)log2⁡(1 − ε) は ε の二値エントロピー関数である。


次ページ
記事の検索
おまかせリスト
▼オプションを表示
ブックマーク登録
mixiチェック!
Twitterに投稿
オプション/リンク一覧
話題のニュース
列車運行情報
暇つぶしWikipedia

Size:157 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)
担当:undef