塗り分けの方法　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　最近、基本的な図形についての塗り分けの問題を考える機会があった。これらについて、
このページに整理しておこうと思う。

（１）　正四角錐を２色で塗り分ける方法

この場合の数は全部で、１２通りある。

（計算による確認）　２色を、赤と青とする。

　５面全部が、赤または青の場合は、それぞれ１通りずつの２通り。

　４面が同色で、残り１面が他色の場合

　　残り１面が底面のとき、　赤または青のそれぞれ１通りずつ。

　　残り１面が底面でないとき、　同色が赤または青のそれぞれ１通りずつ。

　　よって、　この場合の数は、　４通り。

　３面が赤で、残り２面が青の場合

　　底面が青のとき、　側面の塗り方は、１通り。

　　底面が赤のとき、　側面の塗り方は、２通り。

　　よって、　この場合の数は、　３通り。

　３面が青で、残り２面が赤の場合

　　底面が青のとき、　側面の塗り方は、２通り。

　　底面が赤のとき、　側面の塗り方は、１通り。

　　よって、　この場合の数は、　３通り。

　以上から、求める場合の数は、　２＋４＋３＋３＝１２（通り）

（図示による確認）　２色を、赤と青とする。




（２）　正四面体を４色で塗り分ける方法

この場合の数は全部で、２通りある。

（計算による確認）　底面に塗る色を一つ固定すると、側面の色の塗り方は、異なる３色の
円順列となる。

　したがって、　（３−１）！＝２（通り）　となる。

（３）　立方体を２色で塗り分ける方法

この場合の数は全部で、１０通りある。

（計算による確認）　２色を、赤と青とする。

　６面全部が、赤または青の場合は、それぞれ１通りずつの２通り。

　５面が同色で、残り１面が他色の場合は、それぞれ１通りずつの２通り。

　４面が赤で、残り２面が青の場合

　　上面と底面が青のとき、　側面の塗り方は、１通り。

　　上面と底面が赤と青のとき、　側面の塗り方は、１通り。

　　よって、　この場合の数は、　２通り。

　４面が青で、残り２面が赤の場合

　　上面と底面が赤のとき、　側面の塗り方は、１通り。

　　上面と底面が赤と青のとき、　側面の塗り方は、１通り。

　　よって、　この場合の数は、　２通り。

　３面が赤で、残り３面が青の場合

　　上面が青のとき、底面の塗り方は、赤または青の ２通り。このうちの１通りに対して、側
　　面の塗り方は、１通りしかない。

　　　よって、　この場合の数は、　２×１＝２（通り）。

以上から、求める場合の数は、　２＋２＋２＋２＋２＝１０（通り）

（図示による確認）　２色を、赤と青とする。

　　


（４）　格子点を２色で塗り分ける方法

この場合の数は全部で、２３通りある。

（図示による確認）　２色を、赤と青とし、使用面数で場合分けして地道に考える。

　　


（５）　正八面体の８面の内、４面を赤、他の４面を青で塗り分ける方法

この場合の数は全部で、７通りある。

（図示による確認）

　当ＨＰがいつもお世話になっているＨＮ「ＦＮ」さんが、この話題について考察された。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２３年１０月２２日付け）

　上記で、次のような問題が取り上げられている。

　(1) 正四角錐を２色で塗り分ける方法　　(2) 正四面体を４色で塗り分ける方法

　「２色で」、「４色で」、という表現は曖昧さを含み、(1)(2)で違う意味で使われている。(1)で
は「２色以下で」の意味で、(2)では「ちょうど４色で」の意味で使われている。日常言語で、
どちらの意味で解釈される場合が多いかはどちらとも言えないが、数学では曖昧さを含ま
ない表現が望ましい。

　(1A)　正四角錐をちょうどｎ色で塗り分ける方法の数 A(ｎ) を求めよ。(n=1、2、3、4、5)
　(2A)　正四面体をちょうどｎ色で塗り分ける方法の数 B(ｎ) を求めよ。(n=1、2、3、4)
　(3A)　立方体をちょうどｎ色で塗り分ける方法の数 C(ｎ) を求めよ。(n=1、2、3、4、5、6)

　(1B)　正四角錐をｎ色以下で塗り分ける方法の数 A’(ｎ) を求めよ。(n=1、2、3、4、5)
　(2B)　正四面体をｎ色以下で塗り分ける方法の数 B’(ｎ) を求めよ。(n=1、2、3、4)
　(3B)　立方体をｎ色以下で塗り分ける方法の数 C’(ｎ) を求めよ。(n=1、2、3、4、5、6)

　もちろん何れも回転によって同じになる塗り分け方は同じとみなす。

　(1A)、(2A)、(3A) の方がやりやすいでしょう。その結果を使って、(1B)、(2B)、(3B) を解くこ
とになると思います。

　(1A)の場合は、底面を固定すれば円順列の問題になる。ただし、同じものを含む円順列
なので、公式に入れれば終わりとはいかない。まず、同じものを含む4個のものの円順列の
個数を考えよう。

　4個のうち異なるものがm個ある場合の円順列の個数を、Cir(4，m) と書く。

　　m=4 のときは、普通の円順列で、Cir(4，4)=3!=6

　　m=1 のとき、Cir(4，1)=1 は明らか。

　　m=2 のとき、 1122なら、1122と1212で、2通り
　　 　　　　　　　　1222や1112のときは、1通り 　　　従って、Cir(4，2)=4

　　m=3 のとき、 1123のとき、 3を固定すれば、112の順列で、3通り
　　　　　　　　　　 1223や1233も同じだから、Cir(4，3)=3×3=9

(1A)の解について、

　A(1)=1 は明らか

　A(2)　底面が1のとき、側面は、(1と2)または(2だけ)で、これらの円順列となる。
　　　　 底面が2のときも同じだから、　A(2)=(Cir(4，2)+Cir(4，1))×2=10

　A(3)=(Cir(4，3)+Cir(4，2))×3=39

　A(4)=(Cir(4，4)+Cir(4，3))×4=60

　A(5)=Cir(4，4)×5=30

　正しいかどうかあまり自信はありません。(1A)より、(2A)、(3A)の方が難しそうです。考えて
見てください。


　ＦＮさんからの続報です。（平成２３年１０月２３日付け）

　(2A)は難しいと思ったのですが、場合の数が非常に少ないので簡単なようです。

　B(1)=1 は、明らか

　B(4)=2 は、上記を参照

　B(2)　2色を1と2とする。使う色は、1112、1122、1222 のどれかであるが、何れも塗り分け

　　　　方は、1通りしかないので、B(2)=3

　B(3)　2色を1と2と3とする。使う色は、1123、1223、1233 のどれかであるが、何れも塗り分

　　　　け方は、1通りしかないので、B(3)=3

　(1B)、(2B) は、(1A)、(2A)から出ます。(3A)は、多分本当に難しいと思いますが、実はそれ
ほどでもないのかもしれません。となると、正八面体も不可能ではないのでしょうか。

(4A)　正八面体をちょうどｎ色で塗り分ける方法の数D(ｎ)を求めよ。(n=1、2、･･･、8)

　これは、さすがに難しそうです。ｎ=8とｎ=2ぐらいはなんとかなるでしょうか。


　ぽっぽさんからのコメントです。（平成２３年１０月２３日付け）

　(4A)は、コーシー・フロベニウスの定理というので、漸化式の範囲でですが、解けそうで
す。

コーシー・フロベニウスの定理（バーンサイドの定理）

　ある集合Xと、それに作用する置換群Gがあるとき、Gの部分群 g で不変であるXの

集合を、X^g とおく。ここで、軌道の個数│X/G│は、

　　　　│X/G│=(1/│G│)Σ_g∈G│X^g│

　まず、正８面体をｎ色で塗り分けるということは、立方体の頂点をｎ色で塗り分ける方法と
場合の数は変わりません。ここである問題を考えます。

(4AS)　立方体の頂点ををｎ色で塗り分ける(使わない色があってもよい)方法の数 DS(ｎ) を
　　　求めよ。(ｎ=1、2、･･･、8)

　ここで、Xは立方体の頂点をｎ色で塗り分けるものの集合を、Gは立方体を回転させる回
転群とします。│G│=24 である。

　実際に、　恒等置換の場合が１通り、ある面の中心と向いの面の中心を結んだ直線を軸
に90度右に回転する場合が６通り、ある面の中心と向いの面の中心を結んだ直線を軸に
180度に回転する場合が３通り、互いに向かい合う頂点を貫く軸によって、120度回転させる
場合が８通り、ある辺の中点と向かい合う辺の中点を軸として180度回転させる場合が６通
りあるので、　１＋６＋３＋８＋６＝２４（通り）

　次に、Σ_g∈G│X^g│を求める。

(1)　g が、恒等置換のとき、　│X^g│=ｎ⁸

(2)　g が、ある面の中心と向いの面の中心を結んだ直線を軸に90度右に回転するとき、6 つ
　　の回転群があり、X^gは、これらの2つの正方形（上面と底面）の頂点がそれぞれ全て同じ
　　色である集合なので、│X^g│=ｎ²

(3)　g がある面の中心と向いの面の中心を結んだ直線を軸に180度に回転するとき、3つの
　　回転群があり、X^gは、これらの正方形（上面と底面）の向かいの頂点が同じ色である集
　　合なので、│X^g│=ｎ⁴

(4)　互いに向かい合う頂点を貫く軸によって120度回転させるとき、8つの回転群があり、軸
　　を通る頂点の色はそれぞれ自由で、軸によって対称的である3点の2組はそれぞれ全て
　　同じ色なので、│X^g│=ｎ⁴

(5)　ある辺の中点と向かい合う辺の中点を軸として180度回転させるとき、6つの回転群があ
　　り、軸と交わる辺の端点はそれぞれ同じ色で、他の点はそれぞれ向かい合う点と同じ色
　　なので、│X^g│=ｎ⁴

　したがって、立方体の頂点を全て使わないでいいとして、ｎ色で塗り分ける方法の数は

　DS(ｎ)=(ｎ⁸+17ｎ⁴+6ｎ²)/24

である。ここで、次のような漸化式が立つことがわかる。

　Σ_{k=1〜n n}Ｃ_k・D(ｋ)=DS(n)　より、　D(ｎ)=DS(ｎ)-Σ_{k=1〜n-1 n}Ｃ_k・D(ｋ)

　ただし、D(1)=1、DS(ｎ)=(ｎ⁸+17ｎ⁴+6ｎ²)/24

　これより、D(1)=1、D(2)=21、D(3)=267、…、D(8)=1680　が分かる。

　ＦＮさんからのコメントです。（平成２３年１０月２３日付け）

　もう少しゆっくりやりたかったのですが、あっさり解かれてしまったようです。(群の位数が
24であることすらすぐにはわからないので理解できてはいません)

　コーシー・フロベニウスの定理(旧称バーンサイドの補題)は名前ぐらいは知っていますが
よくわかっていません。まともにやるなら、これになるのだろうとは思っていましたが、高校
数学の範囲でも、そこそこはいけるかなと考えていました。真面目に勉強して理解する努
力をしてみます。

　コーシー・フロベニウスの定理を使うやり方だと、(2A)、(3A)、(4A)より、(2B)、(3B)、(4B)
の方が自然な問題ということのようです。(3A)、(3B)がまだ解かれていません。コーシー・
フロベニウスの定理を使うやり方と使わないやり方の両方での解を考えてみようと思いま
す。他の人も考えてみてください。

　攻略法さんが、４⁴通りの場合を直接に描画されました。（平成２３年１０月２４日付け）

正四面体

　　使用した色数
　＼ 1　2　3　4　計
1色　1　-　-　-　1通り
2色　2　3　-　-　5
3色　3　9　3　- 15
4色　4 18 12　2 36
　　　 ：
ｎ色 ｎ _nC₂*3 _nC₃*3 _nC₄*2 0 …

　ＦＮさんからのコメントです。（平成２３年１０月２４日付け）

　SB(4)=36通りをすべて実際に書くとは驚きです。それも色つきで。(2A)、(2B)も解かれてい
ます。(2A)と(2B)はどちらが自然なのでしょう。

　(2B)について、コーシー・フロベニウスの定理を使って、SB(4)を計算してみます。(正四面
体の場合は使わない方が簡単ですが、正六面体(立方体)、正八面体・・・となれば、使うこと
の有利さが段々と増えていくと思います。立方体等を考える練習とすれば、コーシー・フロベ
ニウスの定理を使ってみるのも意味があるでしょう)

　そのためには正四面体群についての情報が必要ですが、「私の備忘録」の「正四面体群」
にあります。そのページにあることは既知とし記号等はそのまま使います。

　色は、1、2、3、4の4色とし、4つの面ABC、ACD、ADB、BCDの順に考えるものとして、それ
ぞれに、1、2、3、4を塗る塗り方を。1234のように書くことにする。

　4色以下で塗る塗り方は、4⁴=256通り。

　正四面体群の位数は12で、その元は、(1)=X のタイプが、(1)〜(8)の8個で、(9)=Y のタイプ
が、(9)〜(11)の3個、(12)=I (恒等変換)が、1個　である。

　I によって不変なものは、すべてだから　256通り。
　X によって不変なものは、1112のタイプ 12通りと、1111のタイプ 4通りで、計16通り。
　(2)〜(8)も同じだから、全部で、16×8=128通り。
　Y によって不変なものは、1221のタイプ 12通りと、1111のタイプ 4通りで、計16通り。
　(10)(11)も同じだから、全部で、16×3=48通り。

　　コーシー・フロベニウスの定理より、SB(4)=(1/12)(256+128+48)=432/12=36

　SB(ｎ)もほとんど同様にできます。SB(1)は、もちろん1だから、n≧2とする。ここで、n≦4で
ある必要はない。n≧5でも同じである。

　ｎ色以下で塗る塗り方は、ｎ⁴通り。

　I によって不変なものは、すべてだから、ｎ⁴通り。
　X によって不変なものは、1112のタイプと1111のタイプだから、n(n-1)+n=n²通り。
　Y によって不変なものは、1221のタイプと1111のタイプだから、n(n-1)+n=n²通り。

　従って、SB(n)=(1/12)(n⁴+8n²+3n²)=n²(n²+11)/12

　ここで、問題「ｎが整数のとき、n²(n²+11)は12の倍数であることを示せ」が派生する。
ごく簡単に証明できますが．．．。

　実際に、自然数 ｎ に対して、　ｎ²≡０、１　（ｍｏｄ　３）　、ｎ²≡０、１　（ｍｏｄ　４）　なので、
　　　　　ｎ²（ｎ²＋１１）≡０　（ｍｏｄ　３）　かつ　ｎ²（ｎ²＋１１）≡０　（ｍｏｄ　４）　より明らか。


　攻略法さんからのコメントです。（平成２３年１０月２４日付け）

　(1A)　正四角錐をちょうどｎ色で塗り分ける方法の数 A(ｎ) を求めよ。(n=1、2、3、4、5)
　(1B)　正四角錐をn色以下で塗り分ける方法の数 A’(n) を求めよ。(n=1、2、3、4、5)

　　使用した色数
　＼ 1　 2　 3　 4　5　計
1色　1　 -　 -　 -　-　1通り
2色　2　10　 -　 -　-　12
3色　3　30　39　 -　-　72
4色　4　60 156　60　-　280
5色　5 100 390 300 30　825
　　　　：
ｎ色 ｎ _nC₂*10 _nC₃*39 _nC₄*60 _nC₅*30 0 …　　計 n²(n³+n+2)/4

(3A)　立方体をちょうどｎ色で塗り分ける方法の数 C(ｎ) を求めよ。(n=1、2、3、4、5、6)
(3B)　立方体をｎ色以下で塗り分ける方法の数 C’(ｎ) を求めよ。(n=1、2、3、4、5、6)

立方体（正6面体）

　　使用した色数
　＼ 1　 2　 3 　 4　 5 　6　計
1色　1　 -　 - 　 -　 -　 -　1通り
2色　2　 8　 - 　 -　 -　 -　10
3色　3　24　30 　 -　 -　 -　57
4色　4　48 120　 68　 -　 -　240
5色　5　80 300　340　75　 -　800
6色　6 120 600 1020 450　30　2226
　　　：
ｎ色 ｎ _nC₂*8 _nC₃*30 _nC₄*68 _nC₅*75 _nC₆*30 0 …　　計 n²(n⁴+3n²+12n+8)/24


　ＦＮさんからのコメントです。（平成２３年１０月２５日付け）

　(1A)、(1B)について、私も、n≦5について同じ結果を得ました。ｎについてはやってなかっ
たので、コーシー・フロベニウスでやってみました。

　底面(正方形)の中心を通って、底面に垂直な直線の周りの90度の回転をgとする。群は、
g、g²、g³、g⁴=1(恒等変換)　からなる位数4の巡回群。

　1で不変なものは、塗り分け方の総数で、n⁵個
　gで不変なものは、側面がすべて同じだから、底面、側面それぞれｎ通りで、n²個
　g²で不変なものは、向かい合う側面が同じだから、底面、隣り合う側面がｎ通りで、n³個
　g³は、gと同じで、n²個

従って、(1/4)(n⁵+n³+2n²)=n²(n³+n+2)/4

　(2B)を、コーシー・フロベニウスで解くときに、「Xによって不変なものは、1112のタイプと
1111のタイプだから、n(n-1)+n=n²通り」のように書きましたが、側面3つは同じで任意、底
面も任意だから、直接、n²と書く方がいいです。n≧2とする必要もありません。


（コメント）　平成２９年８月２３日付け

　数学セミナー（日本評論社）１９９４年１１月号の「エレガントな解答をもとむ」に次のような
問題が出題されていました。

　立方体の６面を絵の具で塗り分ける。使える色は６色までで、すべて違う色でも、２色か３
色だけを使っても、全くの自由。違う塗り方は何通りあるか。
　ただし、立方体を転がしたとき、同じ塗り方になるものは１通りと数えるものとする。

　この問題に対して、立方体の３組の対面に着目し上手い解釈をするとエレガントな解答が
得られるようだ。

　立方体の６面は反対側に向かい合った２面を１組として、上下、前後、左右の３組あるも
のと考えられる。この３組の対面の塗り方を指定する。

　対面を同色にする塗り方は、₆Ｃ₁＝６（通り）、異なる色にする塗り方は、₆Ｃ₂＝１５（通り）

なので、合わせて、₆Ｈ₂＝₇Ｃ₂＝２１通りある。この中から重複を許して３通り選ぶ場合の

数は、　₂₁Ｈ₃＝₂₃Ｃ₃＝２３・２２・２１/６＝１７７１（通り）

　特に、３組の対面が異なる色で、どの２組の対面にも同じ２色を使わない塗り方は２通り

（鏡映で同じになるもの）あるので、₁₅Ｃ₃＝１５・１４・１３/６＝４５５（通り）だけ加算が必要

である。よって、求める場合の数は、　１７７１＋４５５＝２２２６（通り）　となる。


　攻略法さんからのコメントです。（平成２３年１０月２５日付け）

　正多角錐、正多面体の塗り分けは、数学と図工の教材
・展開図を考える　・全ての塗り方で塗り分ける　・組み立てる　・同じものを見つけて分類
と考えたとき、4、5人のグループ作業では、正4面体が手頃だと思います。

　視覚的に理解するには、「私の備忘録」の中の「円順列の数え上げ」があります。実際に、
81通りすべてを塗るのがポイントです（笑）

練習問題　　「私の備忘録」の中の「エイト・クィーン問題」で、92個のすべての解が求まって
　　　　　　　いる。この一覧から異なる解を求めよ。

（解）　この表は、12行で構成され、行単位が同じグループになっている。回転、裏返しなど
　　　すれば確認できる。従って、例えば、各行1列目を選んだ計12個とすればよい。（終)

　攻略法さんからのコメントです。（平成２３年１０月２５日付け）

　ぽっぽさんの漸化式について、Excel ワークシートを使って、

行＼列　A　　　B　　　　　C　　　　　　 …　I
　 1: 　1　　　　　　　　　　　　　 　　…　1=(A1^8+17*A1^4+6*A1^2)/24
　 2: 　2　21=I2-A2　　　　　　　　 　　…　23=(A2^8+17*A2^4+6*A2^2)/24
　 3: 　3　63=3C2*B2　267=I3-A3-B3　　　…　333=(A3^8+17*A3^4+6*A3^2)/24

などセル参照の式を使って、左上から順に埋めていきました。

　ただし、_nC_r の計算式は、FACT(n)/(FACT(n-r)*FACT(r))

正８面体

　　使用した色数
　＼ 1　 2　　 3　　　4　　　5 　　 6 　　7 　 8　　　計
1色　1　 -　　 -　　　-　　　-　　　-　　 -　　-　　　 1
2色　2　21　　 -　　　-　　　-　　　-　　 -　　-　　　23
3色　3　63　 267　　　-　　　-　　　-　　 -　　-　　 333
4色　4 126　1068　 1718　　　-　　　-　　 -　　-　　2916
5色　5 210　2670　 8590　 5250 　　 -　　 -　　-　 16725
6色　6 315　5340　25770　31500　 7980　　 -　　-　 70911
7色　7 441　9345　60130 110250　55860　5880　　-　241913
8色　8 588 14952 120260 294000 223440 47040 1680　701968
　　　：
ｎ色 n _nC₂*21 _nC₃*267 _nC₄*1718 _nC₅*5250 _nC₆*7980 _nC₇*5880 _nC₈*1680 0 …

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　計 n²(n⁶+17n²+6)/24

　正ｍ面体のｍ個の面をｍ色すべて使って塗る場合、1面が正L角形とすると、

　　　(ｍ-1)！/L 通り

　実際に、ｍは、4、6、8、12、20 の５つ（→　参考：「正多面体が５種類しかない理由」）で、

　それぞれに対して、L＝3、4、3、5、3

　よって、　m=4　のとき、(4-1)！/3=2
　　m=6　のとき、(6-1)！/4=30
　　m=8　のとき、(8-1)！/3=1680
　　m=12　のとき、(12-1)！/5=7983360
　　m=20　のとき、(20-1)！/3=40548366802944000

　ＦＮさんからのコメントです。（平成２３年１０月２５日付け）

　(3A)、(3B)については、問題として出しましたが、ほとんど考えていませんでした。C(6)=30
だけはよくある問題なのでわかりましたが．．．。

　攻略法さんがすべて答えを出されたので考えてみましたが、攻略法さんの答えを見て、そ
れにあわせたようなところもあります。

　(3A)ができれば、即ち、上の図の対角線の 1、8、30、68、75、30 が出れば、(3B)、即ち、
最後の行はそんなに難しくない。色を、1、2、･･･、ｎ として、C(ｎ)を求める。

C(6)：底面を固定する。上面は5通り。側面は4個の円順列。よって、C(6)=5・3！=30

C(5)：112345のとき、5を底面に置く。1が上面にくれば、1234の円順列で、3！=6
　　　2が上面にくれば、1134の円順列で、3通り。3、4のときも同じだから、計15通り。
　　　122345等もすべて15通りだから、C(5)=15・5=75

C(2)：111112のとき、1通りしかない。122222も同じ。111122のとき、22を隣合わせに置くか
　　　向かい合わせに置くかで2通り。112222も同じ。111222のとき、1が向かい合った位置
　　　にくるとき、1通り。こないときも、1通り。よって、C(2)=8

C(4)：111234のとき、4を底面におく。1が上面なら、1123の円順列で、3通り。2が上面なら
　　　1113の円順列で、1通り。3のときも同じで、計5通り。122234等も同じだから、このタイ
　　　プで、4・5=20通り。112234のとき、4を底面に、1が上面なら1223の円順列で3通り。2
　　　のときも同じ。3が上面なら、1122の円順列で2通りの計8通り。112334等も同じだから
　　　このタイプで、8・₄C₂=48。　よって、C(4)=68

C(3)：111123のとき、3を底面におく。2が上面にくるとき、1通り。1が上面にくるとき、1112の
　　　円順列で、1通り。122223、123333も同じだから、2・3=6通り。111223のとき、3を底面
　　　におく。1が上面にくるとき、1122の円順列で2通り。2が上面にくるとき、1222の円順列
　　　で1通りの計3通り。1、2、3を交換しても同じく3通りずつで、1、2、3の交換は6通りだか
　　　ら、このタイプ全体で、3・6=18通り。112233のとき、3が向かい合わせなら、1122の円
　　　順列で、2通り。3が隣り合わせなら、11が向かい合うとき、1通り、22が向かい合うとき
　　　1通り、12が向かい合うとき、多分2通り。よって、C(3)=30

　1つだけという色が1つでもあれば、それを底面におけば、底面に垂直な直線の周りの回
転だけだから、円順列だけ気にすればいいので比較的楽だけど、どの色も2つ以上あると
きは考えにくいです。112233の場合は、すっきり理解できてません。

　立方体の6面を2面を赤、2面を青、2面を白で塗る。回転で同じになるものは同じとみなし
て何通りの塗り方があるか。


　ＦＮさんからの続報です。（平成２３年１０月２６日付け）

　コーシー・フロベニウスの定理(旧称バーンサイドの補題：以下CF定理と略す)を使う練習
をすることが目的です。最初の練習が正多面体群であるのは妥当ではありません。まず、
巡回群あたりから始めるのが妥当です。空間における回転は難しいので、平面における回
転で考えようということです。

　円順列とは、円周上に並べるが、回転によって重なるものは同一とみなすということです。
並べるものの個数がnであるとすると、2π/n の回転によって重なるものは同じとみなしま
す。これらの回転の全体は位数 ｎ の巡回群になります。

　ｎ個のもののうちに、1個だけであるものが1つでもあれば、それを固定して考えればすぐ
にできます。もう少し一般にすれば、1がａ₁個、2がａ₂個、･･･、ｋがａ_k個 (ｎ=ａ₁+ａ₂+･･･+ａ_k)
あり、これらすべてを並べる円順列を考えるとき、ａ₁、ａ₂、･･･、ａ_k の最大公約数が1であ
れば、回転によって自分自身になるような並べ方はないので簡単です。CF定理で言えば、
Σのうち恒等変換以外では不動元はないということになります。同じものを含む順列の公
式をｎで割るだけです。

　(1)　1、1、2、2、3、3のすべてを円形に並べる並べ方は何通りあるか。ただし、回転によ
　　　って重なるものは同じとみなす。

　　このような順列を、「112233の円順列」と呼ぶことにします。

　もちろんCF定理を使わなくてできます。

　112233の1つの順列、例えば、121323に対して、1つずつずらした

　　　　213231　、132312　、323121　、231213　、312132

は円順列としては同じである。従って、だいたい順列の総数は円順列の総数の6倍である。

　ただし、順列123123の場合は、231231　、312312　が同じ円順列になる。このタイプのも
のは、円順列としては、123123　と　132132　だけである。これらの場合は、円順列1個に対
して、順列3個が対応する。これら以外は、円順列と順列の対応は、1：6である。

　従って、円順列の総数を ｘ とすれば、順列の総数は、

　　(ｘ-2)・6+2・3=6x-6　これが、6！/(2！2！2！)=90　であるから、6x-6=90　より、x=16

　CF定理を使った形で書けば、112233の順列は、6!/(2!*2!*2!)=90

　　恒等変換 e によって不変なのは、90個

　　60度の回転を g とすると、g、g²、g⁴、g⁵で不変なものはない。

　　g³(180度の回転)によって不変なのは、

　123123　、231231　、312312　、132132　、321321　、213213

　の6個　　ゆえに、(1/6)・(90+6)=16

　実質的には同じです。慣れれば、CF定理を使う方が書きやすいと思います。両方でやっ
てみて、CF定理というのは当たり前だという感覚を身に着けるのがいいのかもしれません。

　下記の練習問題をやってみてください。

　(2)　11223344の円順列の総数を求めよ。

　(3)　111222333の円順列の総数を求めよ。

　(4)　1、2、3 から重複を許して、5個取ってできる円順列の総数を求めよ。

　(5)　1、2、3、4 から重複を許して、6個取ってできる円順列の総数を求めよ。


　攻略法さんから解答を頂きました。（平成２３年１０月２７日付け）

（別解）　（1/R）・Σ_j=1〜R N^gcd(R，j) で求まる（ようだ）。

(4)　1、2、3 から重複を許して、5個取ってできる円順列の総数を求めよ。

（解）　N=3、R=5　より、

　 σj　3^gcd(5，j)
　-----------------
　 σ1　3¹=3
　 σ2　3¹=3
　 σ3　3¹=3
　 σ4　3¹=3
+) σ5　3⁵=243
------------------------
　255 ÷ 5 = 51通り　　（終）

(5)　1、2、3、4 から重複を許して、6個取ってできる円順列の総数を求めよ。

（解）　N=4、R=6　より、

　 σj　4^gcd(6，j)
　-----------------
　 σ1　4¹=4
　 σ2　4²=16
　 σ3　4³=64
　 σ4　4²=16
　 σ5　4¹=4
+) σ6　4⁶=4096
--------------------------
　4200 ÷ 6 = 700通り


　ＦＮさんからのコメントです。（平成２３年１０月２７日付け）

　そのようですね。一般的な公式があるようです。本によっては、「CF定理より明らか」と書
かれてしまうかもしれないほど、CF定理に近い形ですね。でもやはり証明として書きたい気
はします。今のところうまく書けません。

　一般の場合の証明をする練習という意味で、(5)を少し一般化した形でやってみます。

(5A)　異なるｎ個のものから重複を許して、6個とってできる円順列の総数を求めよ。

（解）　360/6=60度の回転を g とする。

　　g によって不変なもの 　　　1つ隣と同じだから、ｘｘｘｘｘｘ　の形で、n通り
　　g² によって不変なもの 　　2つ隣と同じだから、ｘｙｘｙｘｙ　の形で、n²通り
　　g³ によって不変なもの 　　3つ隣と同じだから、ｘｙｚｘｙｚ　の形で、n³通り
　　g⁴ によって不変なもの 　　4つ隣と同じだから、ｘｙｘｙｘｙ　の形で、n²通り
　　g⁵ によって不変なもの 　　5つ隣と同じだから、ｘｘｘｘｘｘ　の形で、n通り
　　g⁶ =1によって不変なもの 何でもよいから、n⁶通り
　　　(ｘ、ｙ、ｚは同じであってもよい)

　従って、CF定理より、円順列の総数は、(1/6)(n+n²+n³+n²+n+n⁶)=(1/6)(n⁶+n³+2n²+2n)

　これと一般の場合の次の公式との距離はごく短いようです。

　異なるｎ個のものから重複を許して、ｒ個とってできる円順列の総数は、

　　(1/ｒ)Σ_k=1〜r n^gcd(r，k)　ただし、gcd(ｒ，ｋ)は、ｒとｋの最大公約数

で求められる。


　ＦＮさんから解答を頂きました。（平成２３年１０月３０日付け）

(2)　11223344の円順列の総数を求めよ。

　2π/8=π/4 の回転を g とする。G={g，g²，g³，g⁴，g⁵，g⁶，g⁷，g⁸=1}

　1で不変なものは、すべてで、8！/(2！2！2！2！)=2520（通り）

　g⁴で不変なものは、12341234等、1234の順列の繰り返しで、4！=24（通り）

　g，g²，g³，g⁵，g⁶，g⁷ で不変なものはない。

　従って、(1/8)(2520+24)=318（通り）

(3)　111222333の円順列の総数を求めよ。

　2π/9の回転を g とする。

　1で不変なものは、9！/(3！3！3！)=1680（通り）

　g³，g⁶ で不変なものは、3！=6（通り）で、それ以外で不変なものはない。

　従って、(1/9)(1680+6+6)=188（通り）

　このタイプの問題についても一般的な公式があるようです。でも、(1)(2)(3)から一般の式を
類推するのは無理でしょう。少なくとも個数の最大公約数が素数でなくて、最大公約数で割
ったとき、商がすべて同じではだめで、できれば3種類ぐらいはあった方がいいので、次の
問題ぐらいにしたほうがいいようです。

(6)　1が18個、2が12個、3が6個、全部で36個ある。これらすべてを並べてできる円順列の
　　総数を求めよ。

　これだと、1つの数になるので計算しなければならないと感じるかもしれないから、式で終
わっていいように、次の形にしてみました。どちらでもいいからやってみてください。もちろん
(6)の場合でも式で終わっていいです。

(6A)　1が18個、2が12個、3、4、･･･、ｎ がいずれも6個ずつ、全部で 6(n+3)個ある。これら
　　　すべてを並べてできる円順列の総数を求めよ。(n≧3)　N=n+3とおいて、Nの式で表せ。


　ＦＮさんから、(6A)の解答を頂きました。（平成２３年１１月２日付け）

　N=n+3 とおく。6N個を円形に並べることになる。2π/6N の回転を g とする。

自然数 k (1≦k≦6N)に対して、g^k により不変な順列 a(1)、a(2)、･･･、a(6N) があるとする。

a(t)=a(t+k) は当然成り立つが、もう少し強く次が成り立つ。

　k と 6N の最大公約数を K とするとき、a(t)=a(t+K)。これは、kp+6Nq=K をみたす整数 p、q

が存在することから、g^kp=g^K-6Nq=g^K が成り立ち、g^k で不変なものは、g^kp

　従って、gK で不変であることからわかる。

a(t)=a(t+K) を満たすから、a(1)、a(2)、･･･、a(6N) は、a(1)、a(2)、･･･、a(K) を繰り返すことに

なる。K は、6N の約数であるから、m=6N/K とおく。すなわち、6N=mK

a(1)、a(2)、･･･、a(6N) は、a(1)、a(2)、･･･、a(K) を m 回繰り返すことになる。

a(1)、a(2)、･･･、a(K) は、1、2、･･･、n のすべてを少なくとも1つ含む。

a(1)、a(2)、･･･、a(K) のうちの n の個数を t とする。このとき、mt=6。

　従って、m、t は、6の約数で、1、2、3、6 のどれかである。だから、(m，t，K) は、

　　　　(m，t，K)=(1，6，6N)、(2，3，3N)、(3，2，2N)、(6，1，N)

のどれかである。このうち前の2つは、(m，t，k) も同じである。後の2つについては、(m，t，k)

はそれぞれ2つずつあり、　(m，t，k)=(3，2，2N)、(3，2，4N)、(6，1，N)、(6，1，5N)

　(m，t，k) のとき、a(1)、a(2)、･･･、a(K) の中に、3、･･･、n はそれぞれ t 個ずつあり、1 は、

3t 個、2 は、2t 個ある。K=t(n+3)=tN。

a(1)、a(2)、･･･、a(6N) の個数を求めるのだが、それは、a(1)、a(2)、･･･、a(K) の個数である。

　同じものを含む順列の公式により、(tN)！/{(3t)！(2t)！(t！)^N-5}

　(m，t，K，k)=(1，6，6N，6N) のとき、(6N)！/{18！12！(6！)^N-5}

　(m，t，K，k)=(2，3，3N，3N) のとき、(3N)！/{9！6！(3！)^N-5}

　(m，t，K，k)=(3，2，2N，2N) のとき、(2N)！/{6！4！(2！)^N-5}

　(m，t，K，k)=(3，2，2N，4N) のとき、(2N)！/{6！4！(2！)^N-5}

　(m，t，K，k)=(6，1，N，N) のとき、N！/(3！2！)

　(m，t，K，k)=(6，1，N，5N)のとき、N！/(3！2！)

これらの和を、6N で割ったものが求めるものである。一般の場合の公式は次の形である。

　n(1)個が同じもの、n(2)個が別の同じもの、････、n(r)個がまた別の同じものである

とき、これらすべてを並べてできる円順列の総数は、

　N=n(1)+n(2)+･･･+n(r) とし、n(1)、n(2)、･･･、n(r)の最大公約数を d とするとき、

次式で与えられる。

　　　(1/N)Σ[(N/k)！/{(n(1)/k)！(n(2)/k)！･･･(n(r)/k)！}]φ(k)

ただし、Σは、d の約数 k すべてにわたり、φ(k)はオイラーのφ関数である。


　これのCF定理を使わない証明は下記のページ等にある。（平成２３年１１月３日付け）

　　「木村の数学小ネタ」　　「同じものを含む円順列の個数について」

　この証明も面白そうだが、数ページは必要なようだ。CF定理を使えば、前の(6A)の解答と
ほぼ同じで、具体的に k=N、2N、･･･、6N のケースを書いてる部分が不要になるから、やや
短かくなるかもしれない。実際に証明を書いたわけではないので、意外な困難があるかもし
れないが．．．。

　同じものを含む円順列は、「同じものを含む円順列の公式」と「重複円順列の公式」で、一
応かたがついたとみなしてもいいかと思います。もちろん、どちらも特殊な状況における公式
で、例えば、次のような問題でも相当に面倒です。

(7)　1、2、2、3、3、3、4、4、4、4 のうちの 6 個を使ってできる円順列の総数を求めよ。

　円順列が済めば、次は、じゅず順列です。回転の他に裏返し(鏡映)で同じになるものを同
じとみなすので、CF定理における群は、正２面体群という非可換群になります。非可換群の
中では最も簡単かもしれませんが、可換群のなかで最も簡単な巡回群と比べれば、相当難
しいと思います。このことから具体的な問題がどの程度難しくなるかがわかるわけではあり
ませんが．．．。

(8)　1、1、2、2、3 をすべて使ってできるじゅず順列の総数を求めよ。

(9)　1、1、2、2、3、3 をすべて使ってできるじゅず順列の総数を求めよ。

(10)　1、2、3 から重複を許して、5個とってできるじゅず順列の総数を求めよ。

(11)　1、2、3、4 から重複を許して、6個とってできるじゅず順列の総数を求めよ。

　できれば、CF定理を使うやり方と使わないやり方の両方の解が欲しいところです。


　攻略法さんが、(7)の解答を与えられました。（平成２３年１１月５日付け）

（解）　4を、0個使った場合、　1、2、2、3、3、3　の6個なので、公式より、

　　　　　　（１/６）・６！/（１！２！３！）＝10（通り）

　4を、1個使った場合、　1、2、2、3、3、3、4　の7個なので、1、2、3　の組合せは、

　　1、2、2、3、3、4　の6個のとき、30通り

　　1、2、3、3、3、4　の6個のとき、20通り

　　2、2、3、3、3、4　の6個のとき、10通り

　4を、2個使った場合、　1、2、2、3、3、3、4、4　の8個なので、

　　1、2、2、3、4、4　の6個のとき、30通り

　　1、2、3、3、4、4　の6個のとき、30通り

　　1、3、3、3、4、4　の6個のとき、10通り

　　2、2、3、3、4、4　の6個のとき、16通り　※
　　　(3/6)回転して不変なもの　　234┃234で、2、3、4　の並べ方から、3！=6通り

　　2、3、3、3、4、4　の6個のとき、10通り

　4を、3個使った場合、　1、2、2、3、3、3、4、4、4　の9個なので、

　　1、2、2、4、4、4　の6個のとき、10通り

　　1、2、3、4、4、4　の6個のとき、20通り

　　1、3、3、4、4、4　の6個のとき、10通り

　　2、2、3、4、4、4　の6個のとき、10通り

　　2、3、3、4、4、4　の6個のとき、10通り

　　3、3、3、4、4、4　の6個のとき、4通り　※
　　　(2/6)、(4/6)回転して不変なもの　34┃34┃34で、3、4　の並べ方から、2！=2通りずつ

　4を、4個使った場合、　1、2、2、3、3、3、4、4、4、4　の10個なので、

　　1、2、4、4、4、4　の6個のとき、5通り

　　1、3、4、4、4、4　の6個のとき、5通り

　　2、2、4、4、4、4　の6個のとき、3通り　※
　　　(3/6)回転して不変なもの　　244┃244で、2、4、4　の並べ方から、3！/(1！2！)=3通り

　　2、3、4、4、4、4　の6個のとき、5通り

　　3、3、4、4、4、4　の6個のとき、3通り　※
　　(3/6)回転して不変なもの　　344┃344で、3、4、4　の並べ方から、3！/(1！2！)=3通り

　以上、計251通り　　（終）


　CF定理では、　(1490+0+2+12+2+0)/6=251通り

（検算）　すべての解の個数は、「私の備忘録」の「母関数」より、

　　　　指数型母関数
　　　(1+ｘ)(1+ｘ+ｘ²/2！)(1+ｘ+ｘ²/2！+ｘ³/3！)(1+ｘ+ｘ²/2！+ｘ³/3！+ｘ⁴/4！)・6！
　　= … + 1490ｘ⁶ + …

　上記※印より、k=1、2、3、4、5　で、(k/6)回転で不変なものは、　0、2、6+3+3=12、2、0


　ＦＮさんからのコメントです。（平成２３年１１月５日付け）

　(7)は、問題として書いたのですが、とても面倒でやる気はしないなと思っていました。実際
にやれば、面倒なのは確かですが、できないこともないのですね。

　「CF定理では、(1490+0+2+12+2+0)/6=251通り」とありますが、この「1490」を普通に求めて
みました。即ち、(7)の円順列を順列にした場合です。

(7A)　1、2、2、3、3、3、4、4、4、4　のうちの 6 個を使ってできる順列の総数を求めよ。

（解）　AAAABC　の型の場合　　6！/4！=30（通り）

　　　このうちの１通りに対して、Aの選び方は、1通りで、B、Cの選び方は、3通りなので、

　　　30×3=90（通り）

　　AAAABBの型の場合　　6！/(4！2！)=15（通り）

　　　このうちの１通りに対して、Aの選び方は、1通りで、Bの選び方は、2通りなので、

　　　15×2=30（通り）

　　AAABCDの型の場合　　6！/3！=120（通り）

　　　このうちの１通りに対して、Aの選び方は、2通りで、B、C、Dの選び方は、1通りなので、

　　　120×2=240（通り）

　　AAABBCの型の場合　　6！/(3！2！)=60（通り）

　　　このうちの１通りに対して、Aの選び方は、2通りで、BもCも2通りなので、

　　　60×2×2×2=480（通り）

　　AAABBBの型の場合　　6！/(3！3！)=20（通り）

　　　このうちの１通りに対して、A、Bの選び方は、1通りなので、　20×1=20（通り）

　　AABBCDの型の場合　　6！/(2！2！)=180（通り）

　　　このうちの１通りに対して、A、Bの選び方は、3通りで、C、Dは1通りなので、

　　　180×3=540（通り）

　　AABBCCの型の場合　　6！/(2！2！2！)=90（通り）

　　　このうちの１通りに対して、A、B、Cの選び方は、1通りなので、　90×1=90（通り）

　以上から、　90+30+240+480+20+540+90=1490（通り）

　　（※なかなか1490になりませんでした。何回も間違えました。）

　また、同じものを含む順列(すべてを使うわけではないとき)の公式が母関数の形で与えら
れることも知りませんでした。Maximaに入れれば、1490は出ました。手計算で展開する気に
はなりませんでした。


（追記）　平成２７年３月１７日付け

　立方体の各面に数字の１〜６を用いて互いに異なる数字を書き込む方法の数は、よく知ら
れているように、　５×（４−１）！＝３０（通り）　である。

　それでは、立方体の各面に、数字の１、２、２、３、３、３を書き込む方法の数は、何通りあ
るだろうか？ちょっと気になったので計算してみた。

（解）　上面に数字の「１」を固定するとき、底面の数字は、「２」または「３」の２通り。

　　　底面の数字が「２」のとき、側面は、２、３、３、３の円順列で、その場合の数は、１通り

　　　底面の数字が「３」のとき、側面は、２、２、３、３の円順列で、その場合の数は、２通り

　　以上から、求める場合の数は、　１＋２＝３（通り）

（コメント）　もっと多いと思ったら意外に少ないですね！


（追記）　当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんが正多面体の色分け方法を考察
　　　　された。（平成２７年５月２７日付け）

　上記では、正ｎ多面体（n=4,6,8,12,20）をｒ色（1≦r≦n）を使って色を塗り分ける方法が研究
されており、その結果、正ｎ面体を異なるｒ色で塗り分けたとき、何通りが可能かのIROn(r)の
表は、下記のフロベニウスの定理から手に入るｋ色から何色かを使って塗り分ける構成式

　f4 (k)=k²(k²+11)/12
　f6 (k)=k²(k+1)(k³-k²+4k+8)/24
　f8 (k)=k²(k⁶+17k²+6)/24
　f12 (k)=k⁴(k⁸+15k²+44)/60
　f20(k)=k⁴(k¹⁶+15k⁶+20k⁴+24)/60

を利用して、ちょうどｒ色で塗り分けられる方法が、

IRO4(r)=sum(i=0,r,(-1)^(r-i)*binomial(r,i)*f4(i)))
IRO6(r)=sum(i=0,r,(-1)^(r-i)*binomial(r,i)*f6(i)))
IRO8(r)=sum(i=0,r,(-1)^(r-i)*binomial(r,i)*f8(i)))
IRO12(r)=sum(i=0,r,(-1)^(r-i)*binomial(r,i)*f12(i)))
IRO20(r)=sum(i=0,r,(-1)^(r-i)*binomial(r,i)*f20(i)))

で各数字を算出してみると（右は辺で隣り合う面は異なる色になっている条件を付加した場合の数字か？）

正4面体
IRO4(1)=1-------------*
IRO4(2)=3-------------*
IRO4(3)=3-------------*
IRO4(4)=2-------------2

正6面体
IRO6(1)=1-------------*
IRO6(2)=8-------------*
IRO6(3)=30------------1
IRO6(4)=68------------6
IRO6(5)=75------------15
IRO6(6)=30------------30

正8面体
IRO8(1)=1-------------*
IRO8(2)=21------------1
IRO8(3)=267-----------?
IRO8(4)=1718----------?
IRO8(5)=5250----------?
IRO8(6)=7980----------?
IRO8(7)=5880----------?
IRO8(8)=1680----------1680

正12面体
IRO12(1)=1------------*
IRO12(2)=94-----------*
IRO12(3)=8814---------*
IRO12(4)=245008-------4
IRO12(5)=2759250------?
IRO12(6)=15884004-----?
IRO12(7)=52701264-----?
IRO12(8)=106866144----?
IRO12(9)=134719200----?
IRO12(10)=103118400---?
IRO12(11)=43908480----?
IRO12(12)=7983360-----7983360

正20面体
IRO20(1)=1----------------------*
IRO20(2)=17822------------------*
IRO20(3)=58076586---------------2
IRO20(4)=18093064608------------?
IRO20(5)=1498413498750----------?
IRO20(6)=51672950917308---------?
IRO20(7)=936058547290608--------?
IRO20(8)=10194866756893728------?
IRO20(9)=72644237439379200------?
IRO20(10)=357895538663241600----?
IRO20(11)=1264592451488446080---?
IRO20(12)=3281293750348373760---?
IRO20(13)=6337930306906598400---?
IRO20(14)=9157388718839961600---?
IRO20(15)=9858321678965760000---?
IRO20(16)=7794071905639219200---?
IRO20(17)=4394429252269056000---?
IRO20(18)=1672620130621440000---?
IRO20(19)=385209484627968000----?
IRO20(20)=40548366802944000-----40548366802944000

　ただし、この数字は隣接する面は同じ色になっているものが含まれているので、各辺で隣
り合う面が異なった色に塗られていたら何通りになるかが知りたくなった。

　そこで、勝手に右にその数を入れ込んだのであるが、不明な部分が数多く残った。ここま
での部分で間違いの部分があれば、知らせてほしい。また、未定の部分の数が分かれば教
えてほしい。


　らすかるさんからのコメントです。（平成２７年５月２７日付け）

　「*」はどういう意味かと思ったら、「0」の意味だったのですね。（0と書けば良いように思いました。）

　全通り探索で調べたところ、

　正四面体の 0,0,0,2　、正六面体の 0,0,1,6,15,30

はその通りで、

　正八面体は、 0,1,12,103,730,2400,3360,1680

　正十二面体は、 0,0,0,4,1320,58896,840672,5308800,16934400,28425600,23950080,7983360

となりました。正二十面体は、5色までは 0,0,144,2808880,1862688076 でしたが、その先は単
純全通り探索で求めるのは不可能ですね。

＃　r=n-1の場合の値は計算で出せますね。隣接する2面が同じ色になるパターンを全体の
　パターンから引くのが簡単そうです。

　r=n-1で隣接する2面が同じ色になるパターンは、(n-1)!/2通りですから

　n=4 のとき、 3-(4-1)!/2=0通り
　n=6 のとき、 75-(6-1)!/2=15通り
　n=8 のとき、 5880-(8-1)!/2=3360通り
　n=12 のとき、 43908480-(12-1)!/2=23950080通り
　n=20 のとき、 385209484627968000-(20-1)!/2=324386934423552000通り

よって、n=20、r=19 の隣接同色禁止パターン数は、 324386934423552000 となりますね。

# n=20以外はプログラムで調べた値と一致しています。n=20のときの値は、地道に場合分け
　して計算する方法でも同じ値になりましたので、間違いないと思います。
　まだn=20の6≦r≦18の値がわかっていませんが、どうしたものでしょうか。



　　　　以下、工事中