差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2020:0110_abc150 [2020/01/12] – ikatakos | programming_algorithm:contest_history:atcoder:2020:0110_abc150 [2024/05/30] (現在) – [解法] ikatakos | ||
|---|---|---|---|
| 行 120: | 行 120: | ||
| * [[https:// | * [[https:// | ||
| + | |||
| + | ++++ 式変形による証明 | | ||
| + | |||
| + | * [[https:// | ||
| + | |||
| + | まず、rnCr=nn−1Cr−1rnCr=nn−1Cr−1 という公式がある。（r=0r=0 の時は定義されないが、そもそも 00 なので問題ない） | ||
| + | |||
| + | \begin{eqnarray} | ||
| + | r{}_nC_r &=& r\dfrac{n!}{r!(n-r)!} \\ | ||
| + | & | ||
| + | & | ||
| + | & | ||
| + | \end{eqnarray} | ||
| + | |||
| + | これを使うと、n∑r=0nCr=2nn∑r=0nCr=2n であることも利用すれば、 | ||
| + | |||
| + | \begin{eqnarray} | ||
| + | \sum_{r=0}^{n} (r+1){}_nC_r &=& \sum_{r=0}^{n} r{}_{n}C_{r} + \sum_{r=0}^{n} {}_nC_r \\ | ||
| + | &=& \sum_{r=1}^{n} n{}_{n-1}C_{r-1} + \sum_{r=0}^{n} {}_nC_r \\ | ||
| + | &=& n 2^{n-1} + 2^n \\ | ||
| + | &=& 2^{n-1}(n+2) | ||
| + | \end{eqnarray} | ||
| + | |||
| + | となる。 | ||
| + | |||
| + | ++++ | ||
| + | |||
| よって上の式は、4i×2×2N−i−1×2N−i−2×(N−i+1)×Ci4i×2×2N−i−1×2N−i−2×(N−i+1)×Ci となり、 | よって上の式は、4i×2×2N−i−1×2N−i−2×(N−i+1)×Ci4i×2×2N−i−1×2N−i−2×(N−i+1)×Ci となり、 | ||
