組合せ (数学)
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}}}
となることを示せる。