差分
このページの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 となり、 |