このページでの記法

• $1[p] = \text{if } p \text{ then } 1 \text{ else } 0$

寄与・主客転倒のよくあるパターン

$A_i, f(x), g(x)$ は0以上の整数とする。このとき、以下が成り立つ。

• $\displaystyle \sum_{i=0}^{N-1} A_i = \sum_{k=0}^{\max A} \#\{i \mid A_i = k\} k$
• $\displaystyle \sum_{i=0}^{N-1} f(A_i) = \sum_{k=0}^{\max A} \#\{i \mid A_i = k\} f(k)$
• $\displaystyle \sum_{i=0}^{N-1} f(A_i) = \sum_{k=0}^{\max f(A)} \#\{i \mid f(A_i) = k\} k$
• $\displaystyle \sum_{i=0}^{N-1} f(g(A_i)) = \sum_{k=0}^{\max g(A)} \#\{i \mid g(A_i) = k\} f(k)$

• 1つめの導出

寄与・主客転倒のよくあるパターン2

$A_i$ を0以上の整数とする。このとき、以下が成り立つ。

$\displaystyle \sum_{i=0}^{N-1} A_i = \sum_{k=0}^{\max A} \#\{i \mid A_i = k\} k = \sum_{k=0}^{\max A} \#\{i \mid A_i > k\}$

• 別のパターン ($A_i = 0$ となってもよい)