Differences

This shows you the differences between two versions of the page.

--- strategies-j [2024/07/13 00:23] – [効率的な魔方陣の数え上げ] mino
+++ strategies-j [2024/08/29 16:14] (current) – [効率的な魔方陣の数え上げ] mino
@@ Line 29: / Line 29: @@
   * 主対角魔方組は副対角魔方組より大きい
-変換 3. はM変換の一部であり、最後の節で議論します。
+変換 3. はM-変換の一部であり、最後の節で議論します。
 ==== 相補対 ====
@@ Line 40: / Line 40: @@
   - 等しい場合
-. と 2. のケースは補数変換にお互いに1対1に対応するため、1. だけ数えて 2倍することで、2.の数え上げを省略することができます。3. の場合は単にそのまま数え上げます。
+. と 2. のケースは補数変換により互いに1対1に対応するため、1. だけ数えて 2倍することで、2.の数え上げを省略することができます。3. の場合は単にそのまま数え上げます。
 . のケースがすべて自己補数的だとは限りません。3.のケースをさらに細かく分解してさらに無駄を省くことができるかも知れません。ただしその分解によるオーバーヘッドが大きくならなければです。
@@ Line 49: / Line 49: @@
 上記の条件を満たす 2N+2個の魔方組が与えられたとして、対角魔方組(候補)の要素が正しく配置できるかどうはまだわかりません。我々に残された自由度である、行の並べ替え、列の並べ替えによって魔方陣が構成できるかどうかを調べる必要があります。
       * 列だけを適当に並べ替えることでいつでも主対角要素を正しく並べることができます。
-      * その上で、列と行に対して同じ並べ替えを実行すると主対角要素は正しい配置に留まります。
+      * その上で、列と行に対して同じ並べ替えを実行しても主対角要素は正しい配置に留まります。
       * 従って残された問題は:
         * 「行と列に同じ並べ替えを施して、副対角要素を正しく並べられるか?」ということになります。
       * 答えは「場合による」ですが、対称性の議論を使うとうまい判定法が導けます。副対角線は行と列の入れ替えに対して対称であり、行と列に同じ並べ替えを実行してもこの対称性は決して破れません。従って以下の定理が成り立ちます。
         * 副対角候補は、行と列の交換に対して対称な配置にある時にのみ、副対角線上に整列できる。
-      * 対称な配置が常に副対角線に変換できると単純には言えませんが、小さな Nに対して、副対角要素がとりうる対称的な配置を全て調べることは難しくありません。 N=6のとき、そのような配置は {{ :up-diag2.pdf |この15通り}}だけであり、これらはすべて副対角線に変換可能です。従って、(主対角候補を正しく並べるための列の並べ替えを行った後、)副対角候補の配置が行と列の交換に対して対称であることを確認すれば、M変換の数だけ魔方陣を見つけたことになります。N=6 における M変換の自由度は 48です。
+      * 対称な配置が常に副対角線に変換できると単純には言えませんが、小さな Nに対して、副対角要素がとりうる対称的な配置を全て調べることは難しくありません。 N=6のとき、そのような配置は {{ :up-diag2.pdf |この15通り}}だけであり、これらはすべて副対角線に変換可能です。従って、(主対角候補を正しく並べるための列の並べ替えを行った後、)副対角候補の配置が行と列の交換に対して対称であることを確認すれば、[[https://oeis.org/A266237|M-変換]]の数だけ魔方陣を見つけたことになります。N=6 における M-変換の自由度は 48です。
-      * 2つ目の節で触れたように、180度の回転による重複は取り除かれるべきです。M変換の自由度の半分は除去されて24となります。
+      * 2つ目の節で触れたように、180度の回転による重複は取り除かれるべきです。M-変換の自由度の半分は除去されて24となります。
 == 数学(群論)の言葉で言うと  ==
       * 対角候補の要素は各行、各列に1回だけ登場しますから、この配置はN個の対象の入れ替え、すなわち対称群 S<sub>N</sub>の元になります。
-      * 主対角候補、副対角候補の配列をそれぞれ d と u とします。これらは S<sub>N</sub>の元です。
+      * 主対角候補、副対角候補の配置をそれぞれ d と u とします。これらは S<sub>N</sub>の元です。
       * 主対角候補を主対角線に並べるために列を入れ替える操作は d<sup>-1</sup>をかけることに対応します。この入れ替えによって、dd<sup>-1</sup> = e と ud<sup>-1</sup> が得られます。eは単位元です。
-      * この段階での副対角候補の配置 ud<sup>-1</sup> は、副対角線の配置(反転置換)と同じ共役類に属する時、そしてその時にのみ、副対角線の配置に変換可能です。N=6の時、この共役類はまさに上の図で表される 15の元からなります。
+      * この段階での副対角候補の配置 ud<sup>-1</sup> は、副対角線の配置(逆順置換)と同じ共役類に属する時、そしてその時にのみ、副対角線に変換可能です。N=6の時、この共役類はまさに先に示した図で表される 15の元からなります。
-      * 実際問題として、置換の共役類の判定は置換の循環型で判定します。副対角線の配置(反転置換)の循環型は floor(N/2)個の2-循環と(N mod 2)個の1-循環からなります。我々はすでに主対角候補と副対角候補が N mod 2 個だけの共通項を持つとことを要請済みなため、1-循環の個数を確認する必要はありません。結果として、残された条件は( ud<sup>-1</sup> ) <sup>2</sup> = e または ud<sup>-1</sup> = du<sup>-1</sup> となります。
+      * 実際問題として、置換の共役類は置換の巡回置換型で判定します。副対角線の配置は対象全体の並び順を逆にする置換であり、その巡回置換型は floor(N/2)個の2-巡回と(N mod 2)個の1-巡回からなります。我々はすでに主対角候補と副対角候補が N mod 2 個だけの共通項を持つとことを要請済みなため、1-巡回の個数を確認する必要はありません。結果として、確認すべき条件は長さ3以上の巡回がないことであり、( ud<sup>-1</sup> ) <sup>2</sup> = e または ud<sup>-1</sup> = du<sup>-1</sup> = ( ud<sup>-1</sup> )<sup>T</sup>とも表現できます。