あみだくじと群論：全単射・一対一対応の証明の考え方

群論の入門問題として出題されるあみだくじに関する問題は、初めて見ると難しく感じるかもしれません。ここでは数学的帰納法や定義に沿った全単射、一対一対応の考え方を整理してみます。

問題の整理と前提

あみだくじは、ある有限集合上の順列を生成する操作として捉えられます。各横線が要素の交換を表すので、最終的に上から下への対応は順列として理解できます。

問題(1)は数学的帰納法で解けそうとのことなので、まずn=1やn=2のケースを確認し、帰納法の仮定を明確にしてからn+1に拡張する考え方を整理します。

全単射を示すには、まず定義域の任意の要素に対して像が必ず存在すること（全射）、そして異なる元は異なる像を持つこと（一対一性）を確認します。
あみだくじの場合、各横線の操作が順列の積として理解できるため、順列の性質（逆順列の存在や結合則）を活用します。

ポイントとして、最初に定義域と値域を明確にし、順列操作が全域をカバーすることを示すことが有効です。

一対一対応を示すには、逆操作の存在を考えます。あみだくじの横線操作は可逆なので、各最終位置から逆に辿ることで一意に開始位置を求められます。これにより一対一性が保証されます。

図や具体例で小規模なあみだくじを実際に書き、開始位置と終了位置の対応を追うと理解が深まります。

n段のあみだくじをn+1段に拡張する際、帰納法の仮定を使って、n段で全単射・一対一対応が成立しているとします。その上でn+1段目を追加しても操作の可逆性が保たれることを確認することで、帰納的に証明できます。

・あみだくじの横線操作は順列として理解する。
・全単射は定義域の任意の要素に像があることと、一対一性の確認。
・一対一対応は逆操作の存在で示すことができる。
・数学的帰納法で小規模ケースを確認し、段数を増やしても成立することを示す。
・図や具体例で対応を追うと理解が深まる。