3: 2016-09-22 (木) 02:06:19 osinko | 4: 2016-09-22 (木) 16:46:49 osinko | ||
---|---|---|---|
Line 2: | Line 2: | ||
**問題を解く [#b956373c] | **問題を解く [#b956373c] | ||
- | コードを組んで回転置換により元が書き変わらない置換を探した | + | <問題2> |
- | 条件は\(X=\left\{ 1,2,3,4,5,6 \right\} ,Y=\left\{ A,B \right\} \)。出力結果が以下になる | + | 赤、青、黄のカラー被覆の銅線を6本束ねたケーブルで製品として異なるものは何種類作れるか? |
+ | このケーブルは回転させたり、前後を逆(裏返し)にして利用できるものとする。(書籍「なっとくする群・環・体」 P51問2より) | ||
+ | |||
+ | 上記の様な問題を解く。まず順番に考えるために、より小さなスケールに問題を書き換えて考えることにする | ||
+ | 問題を以下のように書き換える | ||
+ | |||
+ | <問題2-a> | ||
+ | A、Bの2種の銅線を6本束ねたケーブルで製品として異なるものは何種類作れるか? | ||
+ | このケーブルは回転させたり、前後を逆(裏返し)にして利用できるものとする | ||
+ | |||
+ | この問題を回転する置換群で考えてモデル化すると集合と置換関数は以下になる | ||
+ | |||
+ | \(X=\left\{ 1,2,3,4,5,6 \right\} \\ Y=\left\{ A,B \right\} \\ \iota =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 4 & 5 & 6 \end{pmatrix}\\ \sigma =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 1 & 2 & 3 & 4 & 5 \end{pmatrix}\\ \tau =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 5 & 4 & 3 & 2 & 1 \end{pmatrix}\) | ||
+ | |||
+ | \(\iota\)が恒等置換(置換しない置換)。\(\sigma\)が回転を表す置換関数。\(\tau\)が反転、この問題の場合「裏返し」をシミュレーションする置換関数となる | ||
+ | これらの関数で群を作成するが、この時、\(\sigma\)と\(\tau\)の二項演算に対して演算の順番によって結果が変わることを考慮する必要がある | ||
+ | 実際にこれを確認すると以下のようになっていた | ||
+ | |||
+ | \(\begin{matrix} \iota \cdot \tau =\tau \cdot \iota \quad & =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 5 & 4 & 3 & 2 & 1 \end{pmatrix} \\ \sigma \cdot \tau =\tau \cdot { \sigma }^{ 5 } & =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 4 & 3 & 2 & 1 & 6 \end{pmatrix} \\ { \sigma }^{ 2 }\cdot \tau =\tau \cdot { \sigma }^{ 4 } & =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 3 & 2 & 1 & 6 & 5 \end{pmatrix} \\ { \sigma }^{ 3 }\cdot \tau =\tau \cdot { \sigma }^{ 3 } & =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 1 & 6 & 5 & 4 \end{pmatrix} \\ { \sigma }^{ 4 }\cdot \tau =\tau \cdot { \sigma }^{ 2 } & =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 1 & 6 & 5 & 4 & 3 \end{pmatrix} \\ { \sigma }^{ 5 }\cdot \tau =\tau \cdot { \sigma } & =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 6 & 5 & 4 & 3 & 2 \end{pmatrix} \end{matrix}\) | ||
+ | |||
+ | 以上の結果を踏まえると、\(\tau\)を先に演算させるか後に演算させるか、どちらかに統一してまとめてしまえば裏返しはシミュレーションできるという事が分かる | ||
+ | よって群は以下のようなものとした | ||
+ | |||
+ | \(T=\left\{ \iota ,\sigma ,{ \sigma }^{ 2 },{ \sigma }^{ 3 },{ \sigma }^{ 4 },{ \sigma }^{ 5 },\tau ,\tau \sigma ,\tau { \sigma }^{ 2 },\tau { \sigma }^{ 3 },\tau { \sigma }^{ 4 },\tau { \sigma }^{ 5 } \right\} \) | ||
+ | |||
+ | この群\(T\)を使いX,Yから作成される順列のひとつひとつに群内の関数により元が書き変わらない置換を探した | ||
+ | 結果は以下となった(ここで後述のプログラムコードを利用する) | ||
\(AAAAAA:ι,σ,σ2,σ3,σ4,σ5,τ,τσ,τσ2,τσ3,τσ4,τσ5,\\ BAAAAA:ι,τσ,\\ ABAAAA:ι,τσ3,\\ BBAAAA:ι,τσ2,\\ AABAAA:ι,τσ5,\\ BABAAA:ι,τσ3,\\ ABBAAA:ι,τσ4,\\ BBBAAA:ι,τσ3,\\ AAABAA:ι,τσ,\\ BAABAA:ι,σ3,τσ,τσ4,\\ ABABAA:ι,τσ5,\\ BBABAA:ι,\\ AABBAA:ι,τ,\\ BABBAA:ι,\\ ABBBAA:ι,τσ5,\\ BBBBAA:ι,τσ4,\\ AAAABA:ι,τσ3,\\ BAAABA:ι,τσ5,\\ ABAABA:ι,σ3,τ,τσ3,\\ BBAABA:ι,\\ AABABA:ι,τσ,\\ BABABA:ι,σ2,σ4,τσ,τσ3,τσ5,\\ ABBABA:ι,\\ BBBABA:ι,τσ3,\\ AAABBA:ι,τσ2,\\ BAABBA:ι,\\ ABABBA:ι,\\ BBABBA:ι,σ3,τσ2,τσ5,\\ AABBBA:ι,τσ,\\ BABBBA:ι,τσ,\\ ABBBBA:ι,τ,\\ BBBBBA:ι,τσ5,\\ AAAAAB:ι,τσ5,\\ BAAAAB:ι,τ,\\ ABAAAB:ι,τσ,\\ BBAAAB:ι,τσ,\\ AABAAB:ι,σ3,τσ2,τσ5,\\ BABAAB:ι,\\ ABBAAB:ι,\\ BBBAAB:ι,τσ2,\\ AAABAB:ι,τσ3,\\ BAABAB:ι,\\ ABABAB:ι,σ2,σ4,τσ,τσ3,τσ5,\\ BBABAB:ι,τσ,\\ AABBAB:ι,\\ BABBAB:ι,σ3,τ,τσ3,\\ ABBBAB:ι,τσ5,\\ BBBBAB:ι,τσ3,\\ AAAABB:ι,τσ4,\\ BAAABB:ι,τσ5,\\ ABAABB:ι,\\ BBAABB:ι,τ,\\ AABABB:ι,\\ BABABB:ι,τσ5,\\ ABBABB:ι,σ3,τσ,τσ4,\\ BBBABB:ι,τσ,\\ AAABBB:ι,τσ3,\\ BAABBB:ι,τσ4,\\ ABABBB:ι,τσ3,\\ BBABBB:ι,τσ5,\\ AABBBB:ι,τσ2,\\ BABBBB:ι,τσ3,\\ ABBBBB:ι,τσ,\\ BBBBBB:ι,σ,σ2,σ3,σ4,σ5,τ,τσ,τσ2,τσ3,τσ4,τσ5,\) | \(AAAAAA:ι,σ,σ2,σ3,σ4,σ5,τ,τσ,τσ2,τσ3,τσ4,τσ5,\\ BAAAAA:ι,τσ,\\ ABAAAA:ι,τσ3,\\ BBAAAA:ι,τσ2,\\ AABAAA:ι,τσ5,\\ BABAAA:ι,τσ3,\\ ABBAAA:ι,τσ4,\\ BBBAAA:ι,τσ3,\\ AAABAA:ι,τσ,\\ BAABAA:ι,σ3,τσ,τσ4,\\ ABABAA:ι,τσ5,\\ BBABAA:ι,\\ AABBAA:ι,τ,\\ BABBAA:ι,\\ ABBBAA:ι,τσ5,\\ BBBBAA:ι,τσ4,\\ AAAABA:ι,τσ3,\\ BAAABA:ι,τσ5,\\ ABAABA:ι,σ3,τ,τσ3,\\ BBAABA:ι,\\ AABABA:ι,τσ,\\ BABABA:ι,σ2,σ4,τσ,τσ3,τσ5,\\ ABBABA:ι,\\ BBBABA:ι,τσ3,\\ AAABBA:ι,τσ2,\\ BAABBA:ι,\\ ABABBA:ι,\\ BBABBA:ι,σ3,τσ2,τσ5,\\ AABBBA:ι,τσ,\\ BABBBA:ι,τσ,\\ ABBBBA:ι,τ,\\ BBBBBA:ι,τσ5,\\ AAAAAB:ι,τσ5,\\ BAAAAB:ι,τ,\\ ABAAAB:ι,τσ,\\ BBAAAB:ι,τσ,\\ AABAAB:ι,σ3,τσ2,τσ5,\\ BABAAB:ι,\\ ABBAAB:ι,\\ BBBAAB:ι,τσ2,\\ AAABAB:ι,τσ3,\\ BAABAB:ι,\\ ABABAB:ι,σ2,σ4,τσ,τσ3,τσ5,\\ BBABAB:ι,τσ,\\ AABBAB:ι,\\ BABBAB:ι,σ3,τ,τσ3,\\ ABBBAB:ι,τσ5,\\ BBBBAB:ι,τσ3,\\ AAAABB:ι,τσ4,\\ BAAABB:ι,τσ5,\\ ABAABB:ι,\\ BBAABB:ι,τ,\\ AABABB:ι,\\ BABABB:ι,τσ5,\\ ABBABB:ι,σ3,τσ,τσ4,\\ BBBABB:ι,τσ,\\ AAABBB:ι,τσ3,\\ BAABBB:ι,τσ4,\\ ABABBB:ι,τσ3,\\ BBABBB:ι,τσ5,\\ AABBBB:ι,τσ2,\\ BABBBB:ι,τσ3,\\ ABBBBB:ι,τσ,\\ BBBBBB:ι,σ,σ2,σ3,σ4,σ5,τ,τσ,τσ2,τσ3,τσ4,τσ5,\) | ||
Line 15: | Line 41: | ||
\(同値類の個数d=\left\{ W\left( \iota \right) +W\left( \sigma \right) +W\left( { \sigma }^{ 2 } \right) +W\left( { \sigma }^{ 3 } \right) +W\left( { \sigma }^{ 4 } \right) +W\left( { \sigma }^{ 5 } \right) +W\left( \tau \right) +W\left( \tau \sigma \right) +W\left( \tau { \sigma }^{ 2 } \right) +W\left( \tau { \sigma }^{ 3 } \right) +W\left( \tau { \sigma }^{ 4 } \right) +W\left( \tau { \sigma }^{ 5 } \right) \right\} \div \left| G \right| \\ d=\left\{ { 2 }^{ 6 }+{ 2 }^{ 1 }{ +2 }^{ 2 }+{ 2 }^{ 3 }+{ 2 }^{ 2 }+{ 2 }^{ 1 }\quad +{ 2 }^{ 3 }+{ 2 }^{ 4 }{ +2 }^{ 3 }+{ 2 }^{ 4 }+{ 2 }^{ 3 }+{ 2 }^{ 4 } \right\} \div 12\\ \quad =\frac { 84+72 }{ 12 } =\frac { 156 }{ 12 } =13\) | \(同値類の個数d=\left\{ W\left( \iota \right) +W\left( \sigma \right) +W\left( { \sigma }^{ 2 } \right) +W\left( { \sigma }^{ 3 } \right) +W\left( { \sigma }^{ 4 } \right) +W\left( { \sigma }^{ 5 } \right) +W\left( \tau \right) +W\left( \tau \sigma \right) +W\left( \tau { \sigma }^{ 2 } \right) +W\left( \tau { \sigma }^{ 3 } \right) +W\left( \tau { \sigma }^{ 4 } \right) +W\left( \tau { \sigma }^{ 5 } \right) \right\} \div \left| G \right| \\ d=\left\{ { 2 }^{ 6 }+{ 2 }^{ 1 }{ +2 }^{ 2 }+{ 2 }^{ 3 }+{ 2 }^{ 2 }+{ 2 }^{ 1 }\quad +{ 2 }^{ 3 }+{ 2 }^{ 4 }{ +2 }^{ 3 }+{ 2 }^{ 4 }+{ 2 }^{ 3 }+{ 2 }^{ 4 } \right\} \div 12\\ \quad =\frac { 84+72 }{ 12 } =\frac { 156 }{ 12 } =13\) | ||
- | ここから問題2が解ける | + | ここから問題2が解ける。書籍「なっとくする群・環・体」ではP70にこの問題の答えを書いてくれている(途中経過や式は無い) |
+ | そこで天下り的に、答えが合致すれば「フロベニウスの利用方法が合っている」と考え計算式を以下のように作って答え合わせをしてみると・・・ | ||
\(同値類の個数d=\left\{ W\left( \iota \right) +W\left( \sigma \right) +W\left( { \sigma }^{ 2 } \right) +W\left( { \sigma }^{ 3 } \right) +W\left( { \sigma }^{ 4 } \right) +W\left( { \sigma }^{ 5 } \right) +W\left( \tau \right) +W\left( \tau \sigma \right) +W\left( \tau { \sigma }^{ 2 } \right) +W\left( \tau { \sigma }^{ 3 } \right) +W\left( \tau { \sigma }^{ 4 } \right) +W\left( \tau { \sigma }^{ 5 } \right) \right\} \div \left| G \right| \\ d=\left\{ { 3 }^{ 6 }+3^{ 1 }{ +3 }^{ 2 }+3^{ 3 }+{ 3 }^{ 2 }+{ 3 }^{ 1 }\quad +3^{ 3 }+3^{ 4 }{ +3 }^{ 3 }+3^{ 4 }+3^{ 3 }+3^{ 4 } \right\} \div 12\\ \quad =\frac { 780+324 }{ 12 } =\frac { 1104 }{ 12 } =92\) | \(同値類の個数d=\left\{ W\left( \iota \right) +W\left( \sigma \right) +W\left( { \sigma }^{ 2 } \right) +W\left( { \sigma }^{ 3 } \right) +W\left( { \sigma }^{ 4 } \right) +W\left( { \sigma }^{ 5 } \right) +W\left( \tau \right) +W\left( \tau \sigma \right) +W\left( \tau { \sigma }^{ 2 } \right) +W\left( \tau { \sigma }^{ 3 } \right) +W\left( \tau { \sigma }^{ 4 } \right) +W\left( \tau { \sigma }^{ 5 } \right) \right\} \div \left| G \right| \\ d=\left\{ { 3 }^{ 6 }+3^{ 1 }{ +3 }^{ 2 }+3^{ 3 }+{ 3 }^{ 2 }+{ 3 }^{ 1 }\quad +3^{ 3 }+3^{ 4 }{ +3 }^{ 3 }+3^{ 4 }+3^{ 3 }+3^{ 4 } \right\} \div 12\\ \quad =\frac { 780+324 }{ 12 } =\frac { 1104 }{ 12 } =92\) | ||
- | ・・・これは個人的な考えですが、回転置換群を考える時ある程度PCの計算支援が無いと計算量的にイメージがつかめないような気がします。本の読み方がわるいんだろうか・・・ | + | 合っていたようだ |
+ | |||
+ | &font(Silver){<個人的認識>&br;これはあくまで演習であり群の利用方法のひとつを学ぶ事が目的だと考えた方が良い(この場合、群Tの存在を認識する事。フロベニウスのようなものが存在すると認識する事が目的)&br;同値類を求めるだけなら、もっとシンプルに直球なコードをプルートフォースで組んでしまう方が早いと思われる(このような回転置換を考える時、PCの計算支援は非常に強力で便利)&br;}; | ||
***支援コード [#c44bc7d8] | ***支援コード [#c44bc7d8] | ||
- | この計算を解く目的だけに作っています。汎用性はありません | + | この計算を解く目的だけに作っている。汎用性はない |
- | 回転置換群はもっと汎用的に作れると思います | + | 回転置換群はもっと汎用的に作れる |
#code(csharp){{ | #code(csharp){{ |