【第9章】
【円順列と数珠順列】
円形に並べたものを、「円順列」という。
回転させて重なるものは同じ円順列と考える。したがって、位置ではなく、つながり方に注目している。
(解法のイメージ①)
位置も考慮するとP[n,n]=n!
時計周りに1つずらしたもの、2つずらしたもの、…n-1ずらしたものは重なる。
n個ものが同じ円順列になるから
総数は、n!/n=(n-1)!
(解法のイメージ②)
1個を先頭に並べる。P[n-1,n-1]=(n-1)!
この列を円形に並べる。
よって、総数は、(n-1)!
円順列を裏返したものも同じものと考える順列を、「数珠順列」という。
円順列の半分になる。
総数は、(n-1)!/2
例23)7種類の球で数珠を作る。何通りの数珠ができるか。
(7-1)!/2=6!/2=3×5!=360(通り)
例24)サイコロの色分け
6色でサイコロを色分けする。ただし、辺を共有する面は色が異なるとする。
①6色に塗り分ける
最初に塗った面を上にする。
〈上→下→側面の順に塗る〉
側面は円順列
よって、5×(4-1)!=5×6=30(通り)
②5色で塗り分ける
2面を塗る色の選び方 6通り
上と下を塗る。
側面の4色の選び方C[5,4]=C[5,1]=5
上下反転できるから、側面は数珠順列
(4-1)!/2=3
よって、6×5×(4-1)!/2=90
③4色で塗り分け
辺を共有しないから2面まで
2面を塗る2色の選び方 C[6,2]=15通り
1面を塗る2色の選び方 C[4,2]=6
よって、15×6=90(通り)
④3色に塗り分ける
2面ずつ塗る3色の選び方 C[6,3]=20通り
よって、20通り
