二重和の交換が苦手なあなたへ

# はじめに
数学を学んでいると, 二重和の交換を行う場面がよくあります.
例えば次のようなものです.

```math
\sum_{n = 0}^{T}\sum_{k = 0}^{n}a_{n, k} = \sum_{k = 0}^{T}\sum_{n = k}^{T}a_{n, k}
```

慣れてしまえばどうってことのない等式変形なのですが, 初見ではなかなか理解することができないものです.

本記事では二重和の交換, 特に和のインデックスが独立していない場合について解説を行います.
また等号が正しいことを確認するために, Pythonを用いて簡単な検算を行います.

高校数学レベルで理解できるので, お気軽にご覧いただければと思います.

また, 大学で学ぶ線形代数では二重和の計算を行うシーンが多々あります.
この春から大学生になる方々は是非本記事で二重和の交換に対する苦手意識を無くしていただきたいです！

# 和のインデックスが独立しているケース
上記のような二重和を考える前に, まずはもっとシンプルな以下のケースを考えます.

```math
\sum_{n = 0}^{T}\sum_{k = 0}^{T}a_{n, k}
```

この二重和は簡単に交換できます.
$k$ が $0$ から $T$ まで走ってから$n$ が $0$ から $T$ まで走ることと, $n$ が $0$ から $T$ まで走ってから $k$ が $0$ から $T$ まで走ることは同じですので,

```math
\sum_{n = 0}^{T}\sum_{k = 0}^{T}a_{n, k} = \sum_{k = 0}^{T}\sum_{n = 0}^{T}a_{n, k}
```

と単純に和を入れ替えればよいだけです.
二重和の計算が複雑になるのは, 最初に挙げたような和のインデックスが独立していない場合です.

# 和のインデックスが独立していないケース
では早速次の二重和

```math
\sum_{n = 0}^{T}\sum_{k = 0}^{n}a_{n, k}
```

を交換していきましょう.
こういうケースでは <b>カウントの順番</b> に着目するとよいです.

上の二重和は, $k$ と $n$ を下図の順番で足し合わせていることに気づいてください.

![24902B93-3620-4435-A957-7A8C579402AA.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342285/b83e345e-9c20-2301-efe7-80d11d86e24f.jpeg)


青の矢印は $n$ を $1$ つ固定したときの $k$ が渡る和に対応しています.
そして, 青の矢印を上へスライドしていくことが $k$ を渡る和に対応しています.

ここで, カウントの順番を下図のように変更してみましょう.

![DB222759-C315-4058-ABE1-E9847689ED8E.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/342285/f7d1a982-12af-9b17-ccdc-f544f1cb36af.jpeg)


緑の矢印は $k$ を $1$ つ固定したときの $n$ を渡る和に対応しています.
そして, 緑の矢印を横方向へスライドしていくことが $n$ を渡る和に対応しています.
これは

```math
\sum_{k = 0}^{T}\sum_{n = k}^{T}a_{n, k}
```

に対応していますね.
そして, $2$ つの画像はどちらも同じ個数の格子点に渡る和ですので,

```math
\sum_{n = 0}^{T}\sum_{k = 0}^{n}a_{n, k} = \sum_{k = 0}^{T}\sum_{n = k}^{T}a_{n, k}
```

が成り立つというわけです.

慣れないうちは狐につままれたような気分になりますね.
しかし何度か練習していくうちに簡単に交換をできるようになりますのでご安心ください.

では最後にこの和の交換が実際に正しいのか,

```math
\sum_{n = 0}^{T}\sum_{k = 0}^{n}\binom{n}{k} = \sum_{k = 0}^{T}\sum_{n = k}^{T}\binom{n}{k}
```

を例に Python で実験してみましょう.

```python:exchange_sum.py
from sympy import binomial

def sumfunction(T) :
  """
  上記等式の左辺
  """
  retval = 0
  for n in range(0, T + 1):
    for k in range(0, n + 1):
      retval += binomial(n, k)
  return retval

def exchange_sumfunction(T) :
  """
  上記等式の右辺
  """
  retval = 0
  for k in range(0, T + 1):
    for n in range(k, T + 1):
      retval += binomial(n, k)
  return retval

if __name__ == "__main__":
  for T in range(1, 101):
    if sumfunction(T) == exchange_sumfunction(T):
      print(f'sumfunction({T}) = exchange_sumfunction(T) = {sumfunction(T)}')
```

```:出力結果
sumfunction(1) = exchange_sumfunction(1) = 3
sumfunction(2) = exchange_sumfunction(2) = 7
sumfunction(3) = exchange_sumfunction(3) = 15
sumfunction(4) = exchange_sumfunction(4) = 31
sumfunction(5) = exchange_sumfunction(5) = 63
sumfunction(6) = exchange_sumfunction(6) = 127
sumfunction(7) = exchange_sumfunction(7) = 255
sumfunction(8) = exchange_sumfunction(8) = 511
sumfunction(9) = exchange_sumfunction(9) = 1023
sumfunction(10) = exchange_sumfunction(10) = 2047
sumfunction(11) = exchange_sumfunction(11) = 4095
sumfunction(12) = exchange_sumfunction(12) = 8191
sumfunction(13) = exchange_sumfunction(13) = 16383
sumfunction(14) = exchange_sumfunction(14) = 32767
sumfunction(15) = exchange_sumfunction(15) = 65535
sumfunction(16) = exchange_sumfunction(16) = 131071
sumfunction(17) = exchange_sumfunction(17) = 262143
sumfunction(18) = exchange_sumfunction(18) = 524287
sumfunction(19) = exchange_sumfunction(19) = 1048575
sumfunction(20) = exchange_sumfunction(20) = 2097151
sumfunction(21) = exchange_sumfunction(21) = 4194303
sumfunction(22) = exchange_sumfunction(22) = 8388607
sumfunction(23) = exchange_sumfunction(23) = 16777215
sumfunction(24) = exchange_sumfunction(24) = 33554431
sumfunction(25) = exchange_sumfunction(25) = 67108863
sumfunction(26) = exchange_sumfunction(26) = 134217727
sumfunction(27) = exchange_sumfunction(27) = 268435455
sumfunction(28) = exchange_sumfunction(28) = 536870911
sumfunction(29) = exchange_sumfunction(29) = 1073741823
sumfunction(30) = exchange_sumfunction(30) = 2147483647
sumfunction(31) = exchange_sumfunction(31) = 4294967295
sumfunction(32) = exchange_sumfunction(32) = 8589934591
sumfunction(33) = exchange_sumfunction(33) = 17179869183
sumfunction(34) = exchange_sumfunction(34) = 34359738367
sumfunction(35) = exchange_sumfunction(35) = 68719476735
sumfunction(36) = exchange_sumfunction(36) = 137438953471
sumfunction(37) = exchange_sumfunction(37) = 274877906943
sumfunction(38) = exchange_sumfunction(38) = 549755813887
sumfunction(39) = exchange_sumfunction(39) = 1099511627775
sumfunction(40) = exchange_sumfunction(40) = 2199023255551
sumfunction(41) = exchange_sumfunction(41) = 4398046511103
sumfunction(42) = exchange_sumfunction(42) = 8796093022207
sumfunction(43) = exchange_sumfunction(43) = 17592186044415
sumfunction(44) = exchange_sumfunction(44) = 35184372088831
sumfunction(45) = exchange_sumfunction(45) = 70368744177663
sumfunction(46) = exchange_sumfunction(46) = 140737488355327
sumfunction(47) = exchange_sumfunction(47) = 281474976710655
sumfunction(48) = exchange_sumfunction(48) = 562949953421311
sumfunction(49) = exchange_sumfunction(49) = 1125899906842623
sumfunction(50) = exchange_sumfunction(50) = 2251799813685247
sumfunction(51) = exchange_sumfunction(51) = 4503599627370495
sumfunction(52) = exchange_sumfunction(52) = 9007199254740991
sumfunction(53) = exchange_sumfunction(53) = 18014398509481983
sumfunction(54) = exchange_sumfunction(54) = 36028797018963967
sumfunction(55) = exchange_sumfunction(55) = 72057594037927935
sumfunction(56) = exchange_sumfunction(56) = 144115188075855871
sumfunction(57) = exchange_sumfunction(57) = 288230376151711743
sumfunction(58) = exchange_sumfunction(58) = 576460752303423487
sumfunction(59) = exchange_sumfunction(59) = 1152921504606846975
sumfunction(60) = exchange_sumfunction(60) = 2305843009213693951
sumfunction(61) = exchange_sumfunction(61) = 4611686018427387903
sumfunction(62) = exchange_sumfunction(62) = 9223372036854775807
sumfunction(63) = exchange_sumfunction(63) = 18446744073709551615
sumfunction(64) = exchange_sumfunction(64) = 36893488147419103231
sumfunction(65) = exchange_sumfunction(65) = 73786976294838206463
sumfunction(66) = exchange_sumfunction(66) = 147573952589676412927
sumfunction(67) = exchange_sumfunction(67) = 295147905179352825855
sumfunction(68) = exchange_sumfunction(68) = 590295810358705651711
sumfunction(69) = exchange_sumfunction(69) = 1180591620717411303423
sumfunction(70) = exchange_sumfunction(70) = 2361183241434822606847
sumfunction(71) = exchange_sumfunction(71) = 4722366482869645213695
sumfunction(72) = exchange_sumfunction(72) = 9444732965739290427391
sumfunction(73) = exchange_sumfunction(73) = 18889465931478580854783
sumfunction(74) = exchange_sumfunction(74) = 37778931862957161709567
sumfunction(75) = exchange_sumfunction(75) = 75557863725914323419135
sumfunction(76) = exchange_sumfunction(76) = 151115727451828646838271
sumfunction(77) = exchange_sumfunction(77) = 302231454903657293676543
sumfunction(78) = exchange_sumfunction(78) = 604462909807314587353087
sumfunction(79) = exchange_sumfunction(79) = 1208925819614629174706175
sumfunction(80) = exchange_sumfunction(80) = 2417851639229258349412351
sumfunction(81) = exchange_sumfunction(81) = 4835703278458516698824703
sumfunction(82) = exchange_sumfunction(82) = 9671406556917033397649407
sumfunction(83) = exchange_sumfunction(83) = 19342813113834066795298815
sumfunction(84) = exchange_sumfunction(84) = 38685626227668133590597631
sumfunction(85) = exchange_sumfunction(85) = 77371252455336267181195263
sumfunction(86) = exchange_sumfunction(86) = 154742504910672534362390527
sumfunction(87) = exchange_sumfunction(87) = 309485009821345068724781055
sumfunction(88) = exchange_sumfunction(88) = 618970019642690137449562111
sumfunction(89) = exchange_sumfunction(89) = 1237940039285380274899124223
sumfunction(90) = exchange_sumfunction(90) = 2475880078570760549798248447
sumfunction(91) = exchange_sumfunction(91) = 4951760157141521099596496895
sumfunction(92) = exchange_sumfunction(92) = 9903520314283042199192993791
sumfunction(93) = exchange_sumfunction(93) = 19807040628566084398385987583
sumfunction(94) = exchange_sumfunction(94) = 39614081257132168796771975167
sumfunction(95) = exchange_sumfunction(95) = 79228162514264337593543950335
sumfunction(96) = exchange_sumfunction(96) = 158456325028528675187087900671
sumfunction(97) = exchange_sumfunction(97) = 316912650057057350374175801343
sumfunction(98) = exchange_sumfunction(98) = 633825300114114700748351602687
sumfunction(99) = exchange_sumfunction(99) = 1267650600228229401496703205375
sumfunction(100) = exchange_sumfunction(100) = 2535301200456458802993406410751
```
$T$ を $1$ から $100$ まで動かしてみましたが, きちんと成立していますね.

<b>(2021/03/18 追記)</b>
最後に, 二重和を交換するメリットについて簡単にお話しします.
二重和を計算するシーンにおいて, 二重和を交換することで計算が容易になることがあります.
例えば上記で扱った,

```math
\sum_{k = 0}^{T}\sum_{n = k}^{T}\binom{n}{k}
```

の値を計算してみましょう.
このままだとなかなか骨が折れそうですが二重和の交換を行えば,

```math
\begin{align}
\sum_{k = 0}^{T}\sum_{n = k}^{T}\binom{n}{k} &= \sum_{n = 0}^{T}\sum_{k = 0}^{n}\binom{n}{k} \\
&= \sum_{n = 0}^{T}2^{n} \\
&= 2^{T + 1} -1
\end{align}
```

といとも容易く求めることができてしまいます.
ただし $2$ つめの等号では,

```math
\sum_{k = 0}^{n}\binom{n}{k} = (1 + 1)^{n} = 2^{n}
```

を用いました.
# さいごに
今回は有限和を取り扱いましたが, 二重級数の場合にも収束性が担保されていれば同様の考え方で和を交換することができます.
またお気づきの方も多いと思いますがこの考え方は重積分の計算にも出てきますね.
要はあれの離散版です.

何か対象を数え上げる, ということにはたくさんの楽しみや喜びが隠れています.
皆さんも是非物を数える際には, そこに隠れている数学に想いを馳せてみてください！