すべての組の差の総和

方針

解答

⓪ 発想 — どう考え始めるか。 組 $(i,j)$ は ${}_{10}{\mathrm{C}}_2=45$ 個あるが、足される値 $j-i$ は $1$ から $9$ の9種類しかない。

なら、値ごとにまとめて「(値)×(個数)」で足すのが速い(分類替え)。差が $d$ になる組は $(1,1+d),(2,2+d),\dots ,(10-d,10)$ の $10-d$ 組。

これで二重和が、1変数の和 $\sum d(10-d)$ に潰れる。

① 差 $d$ の組を数える。 $j-i=d$ となる組は $i=1,\dots ,10-d$ の $10-d$ 組($d=1,\dots ,9$)。

② 分類替えして計算する。

$$\sum _{1\le i<j\le 10}(j-i)=\sum _{d=1}^{9}d(10-d)=10\sum _{d=1}^{9}d-\sum _{d=1}^9{d}^2=10\cdot 45-285=165$$

③ もう1つの見方(検算を兼ねて)。 $j-i$ は「$i\le m<j$ を満たす整数 $m$ の個数」だから、この和は3つ組 $(i,m,j)$($1\le i\le m<j\le 10$)の総数に等しい。$(i,m+1,j+1)$ と置き換えると $1\le i<m+1<j+1\le 11$ の狭義単調な3つ組と1対1に対応するので、総数は ${}_{11}{\mathrm{C}}_3=165$ — ②と一致する。

まとめ: 「分類替え(差の値ごと)」で二重和を潰すのが本筋、「対応(11個から3つ選ぶ)」が裏の顔。同じ和が2通りに数えられるときは、片方をもう片方の検算に使える — 数え上げ的な見方は数列の和の強力な補助線になる。

発展 — 一歩先へ。 $165÷45=\frac{11}{3}$ は、$1$ から $10$ の中から無作為に2数を選んだときの「差の平均値」。寄与分解は、この平均(期待値)を「参加者ごとの支払い」に割って計算する発想で、確率の期待値の線形性とまったく同じ骨格だ。1つの和を、分類替え・寄与分解・対応(${}_{11}{\mathrm{C}}_3$)の3方向から数えられるようになれば、二重和は怖くない。

別解

寄与で分解する(1つの数がいくら払うか)。 和 $\sum (j-i)$ を「大きい側の総和 $-$ 小さい側の総和」と読み替え、各数 $v$ の寄与を数える。

$v$ が組の大きい側になるのは、相手が $1,\dots ,v-1$ の $v-1$ 通り。そのたび $+v$ を払う。小さい側になるのは相手が $v+1,\dots ,10$ の $10-v$ 通りで、そのたび $-v$。よって

$$\sum _{1\le i<j\le 10}(j-i)=\sum _{v=1}^{10}v\{(v-1)-(10-v)\}=\sum _{v=1}^{10}v(2v-11)=2\cdot 385-11\cdot 55=770-605=165$$

分類替え(本解: 差の値ごと)、寄与分解(本ルート: 数ごと)、そして対応(${}_{11}{\mathrm{C}}_3$: 本解の検算)。同じ165を3方向から数えたことになる。

寄与分解は「合計を、参加者ごとの支払いに割る」発想で、期待値の計算(1つずつの寄与を足す)へまっすぐつながる。ちなみに $165÷45=\frac{11}{3}$ が、2数の差の平均値だ。