差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
programming_algorithm:contest_history:atcoder:2020:0110_abc150 [2020/01/12] ikatakosprogramming_algorithm:contest_history:atcoder:2020:0110_abc150 [2024/05/30] (現在) – [解法] ikatakos
行 120: 行 120:
  
   * [[https://www.wolframalpha.com/input/?i=sum+ncr%28n%2C+k%29+*+%28k%2B1%29%2C+k%3D0+to+n&lang=ja|sum ncr(n, k) * (k+1), k=0 to n - Wolfram|Alpha]]   * [[https://www.wolframalpha.com/input/?i=sum+ncr%28n%2C+k%29+*+%28k%2B1%29%2C+k%3D0+to+n&lang=ja|sum ncr(n, k) * (k+1), k=0 to n - Wolfram|Alpha]]
 +
 +++++ 式変形による証明 |
 +
 +  * [[https://examist.jp/mathematics/expression-proof/nikoukeisu-tousiki/|【高校数学Ⅱ】二項係数nCrの和の等式(二項定理の利用) | 受験の月]]
 +
 +まず、rnCr=nn1Cr1rnCr=nn1Cr1 という公式がある。(r=0r=0 の時は定義されないが、そもそも 00 なので問題ない)
 +
 +\begin{eqnarray}
 +r{}_nC_r &=& r\dfrac{n!}{r!(n-r)!} \\
 +         &=& \dfrac{n!}{(r-1)!(n-r)!} \\
 +         &=& n\dfrac{(n-1)!}{(r-1)!(n-r)!} \\
 +         &=& n{}_{n-1}C_{r-1}
 +\end{eqnarray}
 +
 +これを使うと、nr=0nCr=2nnr=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×2Ni1×2Ni2×(Ni+1)×Ci4i×2×2Ni1×2Ni2×(Ni+1)×Ci となり、 よって上の式は、4i×2×2Ni1×2Ni2×(Ni+1)×Ci4i×2×2Ni1×2Ni2×(Ni+1)×Ci となり、
programming_algorithm/contest_history/atcoder/2020/0110_abc150.1578840922.txt.gz · 最終更新: by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0