重複の数珠順列

質問

白玉が４個、黒玉が３個、赤玉が１個あると、これらの玉をひもに通し輪にする方法は（　？　）通りある。

解説には左右対称でない順列と左右対称な順列を分けて考えるみたいなんですが、どうしてなのかわかりません。

これの普通の円順列が３５通りというとこまでは出ましたが、そこから先がわかりません。

回答No.3

Mr_Holland · ベストアンサー

円順列が
　　7!/(4! 3!)＝35
で求められているとして、後を考えて見ます。

　赤玉を上にしておいたとき、左右対称になるパターンを考えます。

(1)　一番下が黒玉のとき：　次の3通り。
　　　赤　　　　　赤　　　　赤
　　黒　黒　　白　白　　白　白
　　白　白　　黒　黒　　白　白
　　白　白　　白　白　　黒　黒
　　　黒　　　　　黒　　　　黒

(2)　一番下が白玉のとき：　なし。
　　（奇数の黒玉を左右対称に配置できないため）

　そこで、全体の35通りから3通り引いたものが左右対称になっていることになるので、その分を求めると

　　（35-3)/2＝16　通り

　したがって、全体のパターンは、左右対称になる3通りに、左右対称になる16通りを加えたものなので、

　　3+16＝19　通り

になると思います。

　ちなみに、＃１さんのパターンに、（１０１１０）と（００１１１）の2種類を加えれば全19パターンになるかと思います。（検証に役立ちました。）

回答No.4

kkkk2222

ーーーーーーーーーーーーーーーー
幸い、赤が一個なので、
（赤）？？？？？？？で固定させます。
例として、○○○○●●●
円順列は順列に変化して、Ｃ［７、３］＝３５
円順列のままならば（８！／４！３！１！）／８＝３５　
貴殿が、どちらで算出したかは、わかりませんが。

ーーーーーーーーーーーーーーーー
○○○○●●●（例）
数珠では、
左右対称と、左右＜非＞対称を分ける事になります。
左右対称、では重複しない。
左右＜非＞対称、では重複する。
ーーー
左右対称になるのは、

　　　　　　　　　　　両端が●の場合は、　　　　　　　　　　　
●○○●○○●　の１通り。

　　　　　　　　　　　両端が○の場合は、
　　　　　　　　　　　○？？？？？○の中で、
○○●●●○○
○●○●○●○　の２通り。

合計３通り。
ーーー

３５－３＝３２　左右＜非＞対称の数。
３２／２＝１６　重複しているので２で割る。
１６＋３＝１９　左右対称の数を加える。
まとめて書くと、
［（３５－３）／２］＋３＝１９　（解）
ーーーーーーーーーーーーーーーー

確認のため、左右＜非＞対称になるのは、

両端が○●
○？？？？？●　Ｃ［５、２］＝１０
両端が●○
●？？？？？○　Ｃ［５、２］＝１０
両端が●●
●？？？？？●　　　　　　　　　４
両端が○○
○○？？？●○　　Ｃ［３、１］＝３
○●？？？○○　　Ｃ［３、１］＝３
○●？？？●○　　　　　　　　　２

合計３２　でＯＫのようです。
ーーーーーーーーーーーーーーーーー

回答No.2

KamoLife

まず、赤玉を固定し、そこを基準に考えます。

　赤｜ＡＢＣＤＥＦＧ｜赤

まずは、左右対称の組み合わせの場合を考えましょう。
（何故そうするかは、後で説明します）
この場合、Ｄには必ず白が入ります（白は奇数個であるため）
組み合わせの数は、ＡＢＣに黒２個・白１個を配置するのと等しく、３通り。

次に、左右対称でない組み合わせを考えます。
普通に円順列として考えれば、組み合わせは３５通り。
その内、３通りは左右対称な組み合わせなので除外して３２通り。

ここで注意しなければならないのは、これら３２通りの組み合わせには、
重複する組み合わせが混じっているということです。
例えば　赤｜白白白黒黒黒黒｜赤　と　赤｜黒黒黒黒白白白｜赤　は
裏返すと重なってしまい、本来なら１通りとして数えなければならないところ、
普通に円順列として考えた際には２通りとしてカウントされてしまっています。

つまり、この「３２通り」という数は、本来１通りとカウントされるべきモノを
２としてカウントした結果、本来求めるべき数の２倍になってしまっているのです。
したがって、求めるべきはその重複分を除去した数、
すなわち２で割った「１６通り」というわけです。

以上より、求める答えは左右対称３＋非対称１６の計１９通りです。

この解答のキモは、左右対称の組み合わせを別にしているところ。
質問者様はこれに疑問をお持ちのようですが、これには理由があります。
左右対称である場合、裏返しても自分自身と重なるだけ。
つまり、重複カウントされていないので、別に考えているのです。

回答No.1

coffeebar

もっとスマートな解き方があるような気がしますが、私が求めた方法を書きます。

数珠問題は1個を固定すると解きやすいことが多いです。これは先頭を仮定してから答えを考え、その仮定した先頭が実際には何番目であっても同じ数珠になることを利用するものです。
この問題の場合、赤玉が1個なので、これを先頭に固定しましょう。

次に白を全部つないでしまって、後から黒を入れると考えると
赤A白B白C白D白E（A～Eは黒が入る可能性のある場所）
この時、数珠問題なので、ABCDEとEDCBAが同じになるつなぎ方は1つとして考えます。（数珠を裏返すとEはA、DはBの位置に来るので、同じになるから）

同じ個所に3個の黒玉が入る場合（A,B,C,D,E）は
（0,0,0,0,3）（0,0,0,3,0）（0,0,3,0,0）の3種類
*（3,0,0,0,0）（0,3,0,0,0）は左右対称になるので、数えない

同じ個所に2個の黒玉が入る場合
（0,1,0,2,0）（0,0,0,2,1）（0,2,0,0,1）（2,0,0,0,1）（0,0,0,1,2）（0,1,0,0,2）
（0,0,1,0,2）（0,0,1,2,0）
（0,0,2,0,1）（0,0,2,1,0）
の10種類
*これは真ん中（C）が0の時、1の時、2の時と考えると分かりやすいと思います。

同じ個所に複数の黒玉が入らない場合
（0,1,0,1,1）（1,0,0,1,1）（1,0,1,0,1）（0,1,1,1,0）
の4種類

で合計が17種類が答えだと思います。