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 が 1 ? k ? n に対して成立する。スターリングの近似からは √n (2n が 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 − ε) は ε の二値エントロピー関数である。
上界・下界と漸近公式
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}}
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)}}}}