m！/ nの複雑さ分析（M-N）！

Question

m！/（n！*（m - n）！）M！/（n！*（m - n）！）であることを考えると、mとnの両方が変数であるMCNは、複雑さ階乗または多項式ですか？それとも他のものですか？

詳しく述べてください。

ありがとう

Answer 1

成長は、 $ m $ と $ n $ の関係に応じて、線形または定数です。彼らが大きくなるにつれて。たとえば、 $ n $ が $ m= n + 1 $ 、次に $ \ binom {m} {n}=binom {n + 1} {n}= n + 1 $ 。

今、最大成長に興味がある場合は、二項係数 $ \ binom {m} {n} $ が $ n $ は、 $ m $ の半分です。 put $ m= 2n $ と階乗のスターリングの近似。あなたは

を手に入れます

$$ \ binom {2n} {n}=¥frac {（2n）！} {（n！）^ 2} \ sim \ frac {（2n）^ { ¥sqrt {4n¥Pi}}¥sqrt {4n¥Pi}} {n ^ {2n}} {n ^ {2n}}=¥Pi ^ { - 1/2} 2 ^ {2n} n ^ { -1/2} $$