組合せ論的な証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/10/26 15:26 UTC 版)
「シューアの分割定理」の記事における「組合せ論的な証明」の解説
組合せ論的な観点からは、与えられた条件を満たす和因子の2つの集合間を対応付ける全単射写像を具体的に構成することで、シューアの分割定理を証明することができる。 融合・等分写像 オイラーの分割恒等式は、和因子を奇数とする分割と和因子が互いに異なる分割が同数であることを主張する。オイラーの分割恒等式では、同じ和因子を足し合わせる融合操作と、逆に偶数の和因子を二つに等分する等分操作からなる融合・等分写像がこの二つの条件を満たす分割を結ぶ全単射写像となる。この融合・等分写像は和因子が3で割り切れないという性質を保つ。シューアの分割定理の定理において、和因子が±1 (mod 6)であるという条件は3で割り切れない奇数であるという条件と等価である。したがって、この融合・等分写像によって、和因子が±1 (mod 6)である分割と、和因子が相異なり和因子が±1 (mod 3)である分割が同数であることを示すことができる。例えば、和因子が±1 (mod 6)である n=15の分割の例5+5+1+1+1+1+1は融合操作により、 5 + 5 + 1 + 1 + 1 + 1 + 1 → ( 5 + 5 ) + ( 1 + 1 ) + ( 1 + 1 ) + 1 = 10 + 2 + 2 + 1 → 10 + ( 2 + 2 ) + 1 = 10 + 4 + 1 {\displaystyle 5+5+1+1+1+1+1\rightarrow (5+5)+(1+1)+(1+1)+1=10+2+2+1\rightarrow 10+(2+2)+1=10+4+1} と、和因子が相異なり、和因子が±1 (mod 3)である分割10+4+1に写される。 ブレスードの全単射 1980年にデビッド・ブレスードは、シューアの分割定理の巧みな全単射写像を構成した。ブレスードの全単射では、次の例のように±1 (mod 3)に合同で相異なる和因子からなる分割から3-差的で連続する3の倍数を含まない和因子からなる分割への写像を与える。ここでは、±1 (mod 3)に合同で相異なる和因子からなる分割の例として、π:13+10+8+7+4+2+1を用いた説明を行う。πの和因子を縦の列に並べて表示する。まず、最小の和因子から始めて、高々差が2である和因子の対を足し合わせる融合操作を行い、π1に写す。 π : 13 10 8 7 4 2 1 → π 1 : 13 10 15 = 8 + 7 4 3 = 2 + 1 {\displaystyle \pi :{\begin{matrix}13\\10\\8\\7\\4\\2\\1\end{matrix}}\rightarrow \pi _{1}:{\begin{matrix}13&\\10&\\15&=8+7\\4&\\3&=2+1\\\end{matrix}}} 次に、和因子が小さいものから順番に、0から始まる連続する3の倍数を引いていき、π2を構成する。 π 1 : 13 10 15 4 3 → π 2 : 1 = 13 − 12 1 = 10 − 9 9 = 15 − 6 1 = 4 − 3 3 = 3 − 0 {\displaystyle \pi _{1}:{\begin{matrix}13\\10\\15\\4\\3\\\end{matrix}}\rightarrow \pi _{2}:{\begin{matrix}1&=13-12\\1&=10-9\\9&=15-6\\1&=4-3\\3&=3-0\\\end{matrix}}} π2の列の隣には、引き算を行った0から始まる連続する3の倍数を表示しておく。π2の1列目を昇順に並び替えたものを、π3とする。さらにπ3の1列目と2列目を足し合わせたものをπ4とする。 π 2 : 1 12 1 9 9 6 1 3 3 0 → π 3 : 9 12 3 9 1 6 1 3 1 0 → π 4 : 21 = 9 + 12 12 = 3 + 9 7 = 1 + 6 4 = 1 + 3 1 = 1 + 0 {\displaystyle \pi _{2}:{\begin{matrix}1&12\\1&9\\9&6\\1&3\\3&0\\\end{matrix}}\rightarrow \pi _{3}:{\begin{matrix}9&12\\3&9\\1&6\\1&3\\1&0\\\end{matrix}}\rightarrow \pi _{4}:{\begin{matrix}21&=9+12\\12&=3+9\\7&=1+6\\4&=1+3\\1&=1+0\\\end{matrix}}} こうして得られた分割π4は、3-差的で連続する3の倍数を含まない和因子からなる分割となっている。
※この「組合せ論的な証明」の解説は、「シューアの分割定理」の解説の一部です。
「組合せ論的な証明」を含む「シューアの分割定理」の記事については、「シューアの分割定理」の概要を参照ください。
- 組合せ論的な証明のページへのリンク
