組合せの数の計算
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/07/26 09:00 UTC 版)
「組合せ (数学)」の記事における「組合せの数の計算」の解説
n-元に対する k-組合せの総数を効率的に計算するために以下の等式が利用できる。0 ≤ k ≤ n として: ( n k ) = ( n n − k ) , ( n + 1 k + 1 ) = n + 1 k + 1 ( n k ) , ( n 0 ) = 1. {\displaystyle {\binom {n}{k}}={\binom {n}{n-k}},\quad {\binom {n+1}{k+1}}={\frac {n+1}{k+1}}{\binom {n}{k}},\,{\binom {n}{0}}=1.} 最初の式は k ≤ n/2 なる場合に帰着するのに利用できるし、後の二つは ( n k ) = ( n − k + 1 ) 1 ⋅ ( n − k + 2 ) 2 ⋅ ⋯ ⋅ n k {\displaystyle {\binom {n}{k}}={\frac {(n-k+1)}{1}}\cdot {\frac {(n-k+2)}{2}}\cdot \dotsb \cdot {\frac {n}{k}}} となることを示せる。
※この「組合せの数の計算」の解説は、「組合せ (数学)」の解説の一部です。
「組合せの数の計算」を含む「組合せ (数学)」の記事については、「組合せ (数学)」の概要を参照ください。
- 組合せの数の計算のページへのリンク