数えるということは人間の根源にかかわることかもしれない。 セサミストリートのカウント伯爵は、何かについて数えていた。 ほりのぶゆきの「江戸むらさき特急」では、「ひとーつ、ふたーつ、みっつ…これで俺ももうすぐ勘定奉行だな」とつぶやく役人もいた。 そこで、数え上げ数学に関するページを作ってみた。
数え上げ数学では、代数学の理論が重宝される。代数学の用語については主に [1] を参照した。
バーンサイドの補題は、バーンサイドの定理と呼ばれることもあるが、他のバーンサイドの定理があり紛らわしい。 混同を避けるためには、バーンサイドの数え上げ定理、コーシー・フロベニウスの補題、軌道数え上げ定理、などと呼ぶこともある。
余談だが、この補題は名前からして、バーンサイドという人が発見したように思われる。バーンサイドは確かにこれを著書で述べたが、これはフロベニウスに帰するものとした。 実はフロベニウス以前にもコーシーによってこの公式は知られていた。こういったことからして、これは「非バーンサイドの補題」（lemma that is not Burnside's） と呼ばれるべきものである。このように「科学的発見に第一発見者の名前が付くことはない」という事実は多く、 この現象は提唱した社会学者の名前をとって 「スティグラーの法則」と呼ばれる。しかし、スティグラーによれば、 「スティグラーの法則は既に別の社会学者によって発見されていた」という。
それはともかく、バーンサイドの補題とは次のようなものである。[4]から引用する。
有限集合 `A` の上の置換群 `G` から誘導される同値関係による `A` の同値類の数は
`1/abs(G) sum_(g in G) psi(g)`に一致する． ただし `psi(g)` は置換 `g` のもとで不変な `A` の元の数である．
次は [2] の p.51 にある問１である。
3 種類のお料理のお皿 `A` （シューマイ）、`B`（棒棒鶏）、`C`（酢豚）を，回転する円卓の上に 6 皿並べる．最初の並べ方は違っても， 回転すれば同じになる並べ方は，“同値（実質的に同じ）”といってよいであろう．そこで問題：
問 1 3 種類のお料理を 6 皿並べるとき，同値でない（回転しても同じにならない）並べ方は何通りあるか？ただし 1 種類か 2 種類しか並べない場合も，含めて数える．
この問題の「円卓の上に 6 皿」を「円卓の上に 4 皿」にしたものが例題８である。さて、例題１の答は[2]の p.69 によれば次のとおりである。
同値類の個数は次のように計算される。
(0) `W(iota) = 3^6 = 729`
(1) `W(sigma) = 3^1 = 3`
(2) `W(sigma^2) = 3^2 = 9`
(3) `W(sigma^3) = 3^3 = 27`
(4) `W(sigma^4) = 3^2 = 9`
(5) `W(sigma^5) = 3^1 = 3`
したがって， 同値類の個数 = `(729 + 3 + 9 + 27 + 9 + 3) / 6 = 780 / 6 = 130`
次は文献[2]の p.51 にある問２である。文献 [2] には図があったが、引用にあたっては省略した。
カラー被覆の導線を 6 本まとめて，1 本のケーブルを作る．カラーは赤・青・黄の 3 色選べるが，図 5 （ア），（イ）のケーブルは， 回転すれば同じになるので，「製品としては同じもの」である．また（ア），（ウ）も前後を逆（裏返し）にすれば同じになるのでやはり「同じもの」とみなす． そこで次のような実際的な問題が生まれる．
問 2 赤，青，黄のカラー被覆の導線を 6 本束ねたケーブルで，製品として異なるものは，何種類作れるか？
例題２の答は同書p.70 の次の補足を引用する。
問２もこれで解ける―群 `G` のところに，60 ページ＜例３＞で述べた群 `T` をあてはめればよい． しかし「`T` が実際にどんな置換を含んでいるか」（関係 `sigma * tau = tau * sigma^5` が重要）などの議論が必要なので，ここでは結果だけ示しておく．
問 2 の答:３色のカラー被覆導線を 6 本まとめたケーブルで，製品として異なるものは，92 種類作れる．
次は[3]の p.95 にある例題１である。
正 `n` 面体の各面が正 `q` 角形であるとする． この `n` 面を `n` 色で塗る． ただし，1 つの面は 1 色で塗り，異なる面は異なる色で塗るものとする． いま，`n` 面体の中心 `O` のまわりの回転を考える．そのとき，どのように回転しても一致しない異なる塗り方は何通りあるか．
解をまる写しする。
解 この正 `n` 面体の回転群を `G` とする．回転を考えないときの異なる塗り方は，`n` 面に `n` 色であるから，`n!` 通り．その 1 つを `t` とする． `G` に属する回転 `sigma` を正 `n` 面体に作用させれば，塗り方 `t` は（別の）塗り方 `t'` に移る．これを `sigma(t)` と定義すれば，上の `n!` 個の塗り方の集合 `T` は `G` 集合になる．
2 つの塗り方 `t, u in T` が `G` に属する回転 `sigma` により一致するというのは
`u = sigma(t)`のことで，それが `G` 集合 `T` を軌道 `T_i (i = 1, ldots, m)` に類別したときに `t` と `u` が同じ推移類に属することである． よって，`G` に属する回転を行っても一致しない異なる塗り方の総数は軌道 `T_i` の個数 `m` に等しい．塗り方 `t` は `n` 面を `n` 色で塗っているから，面が 1 つでも動けば t と異なる `t' in T` になる．`n` 面がすべて動かないのは `I` だけであるから，固定部分群は
`H(t) = {I}`よって，定理 5.1，5.2 より`abs(G) = abs(T_i)*abs(H(t)) = abs(T_i)`．`:.abs(T) = abs(T_1) + cdots + abs(T_m) = mabs(T_i)= mabs(G)`一方，2.2 節 例題 1 より `abs(G) = nq` ．したがって，求める塗り方の個数は
`m = abs(T) // abs(G) = n! // nq = (n-1)!//q`．
ここで用語の定義をおさらいしよう。用語の定義は特記なき限り[1]による。まず、「作用」 の意味は次のとおりである。[1]
`G` を群とし群の演算を `**` で表す．また，集合 `X` が与えられていて， 任意の `sigma in G` と `x in X` に対して `sigma * x` と表される `X` の元が定まっているとする． （中略）この `sigma * x` に対して，2 つの条件
(GA1) 任意の `sigma, tau in G` と任意の `x in X` に対して， `sigma * (tau * x) = (sigma ** tau) * x` が成立する
(GA2) 任意の `x in X` について `varepsilon * x = x` が成り立つ （`varepsilon` は `G` の単位元を表わす）
が成り立つとき，`(sigma, x) |-> sigma * x` は `G` の `X` への作用（action） である （ または，作用を定める）という（後略）
次は[3]の p.96 にある例題２である。
6 角錐を 2 つ，底面ではり合わせた立体を考える．具体的にいえば： 直交座標の入った空間において，座標原点 O を中心とする正 6 角形 ABCDEFG を `xy` 平面上にとり， 6 個の頂点と 2 点 P(0, 0, 1)，Q(0, 0, -1) を結んでできる多面体を考える（図7.2、引用では省略）． この多面体の 12 の面を黒白 2 色で塗り分ける．ただし，1 つの面は 1 つで塗るものとし，全部の面を 1 色で塗ってもよいものとする． このような塗り方のうち，`O` のまわりに回転しても一致しないような異なる塗り方は何通りあるか．
ここでは塗り方を `m` として、p.97 にある答だけを引用する。
`m = 1/abs(G) sum_(lamda in G) chi(lambda) = 1/12 (2^12 + 2*2^2 + 2*2^4 +7*2^6) = 382`．
次は[3]の p.97 にある例題３である。
黒白の石 `n` 個を円形に並べる．黒石，白石の個数に制限はなく，全部黒でも，全部白でもよいものとする．この円順列の個数は何通りか．
ここでは個数を `m` として p.98 にある答だけを引用する。
`m = 1/abs(G) sum_(tau in G) chi(tau) = 1/n sum_d varphi(n/d)2^d`．
ここで，`d` は `n` の約数全部（1と`n` を含め）を動く．
補足すると、`varphi(n)` は`n = p^aq^bcdotsr^c を `n` の素因数分解とすれば、
文献 [3] にはほかにもいろいろな問題がある。
例題 4 の多面体の 12 の面を 12 色で塗る塗り方は何通りか．
この答えは 11! である。
正 4 面体の 4 面を黒白 2 色で塗る塗り方は何通りか．
この答は 5 である。
例題 4 の多面体を 2 つの平面 `z = +-1/2` で切れば，面数 14 の多面体ができる．これを 14 色で塗る塗り方は何通りか．またこれを黒白 2 色で塗る塗り方は何通りか．
この答はそれぞれ 14!/12，`(2^14 + 2*2^4 + 2*2^6 + 2^8 + 6*2^7)//12 ` である。
次は[4]の pp.61-62 にある例4.7 の前半である。
`k` 種類の色が使えるとき、立方体の頂点に色を割り当てる場合の数を求めよ。
答だけ書くと、`1/24(k^8 + 17k^4 + 6k^2)` とおりである。特に `k = 1, 2, 3` のとき、それぞれ 1 通り、23 通り、333 通りである。
次は[4]の pp.61-62 にある例4.7 の後半である。
`k` 種類の色が使えるとき、立方体の面に色を割り当てる場合の数を求めよ。
答だけ書くと、`1/24(k^6 + 3k^4 + 12k^3+ 8k^2)` とおりである。特に `k = 1, 2, 3` のとき、それぞれ 1 通り、10 通り、57 通りである。
次は[5]の pp.157 にある例 6.22 である。
青、白，黄の 3 色のビーズ玉を糸でつないで作られるビーズ玉 4 個の腕輪の配色が何通りあるかを考える。 ただし，各色のビーズ玉は同時に何個でも使用できるとする。また，問題を簡単にするため，腕輪は裏返せないものとする（すなわち腕輪を回転することによって， 同じパターンとなる配色だけを同一のものとみなす）。
これは例題１の縮小版である。解答は次のとおりである。用語・文字は例題１に従っているので、文献 [5] のものとはことなる。
同値類の個数は次のように計算される。
(0) `W(iota) = 3^4 = 81`
(1) `W(sigma) = 3^1 = 3`
(2) `W(sigma^2) = 3^2 = 9`
(3) `W(sigma^3) = 3^1 = 3`
したがって，
同値類の個数 = `(81 + 3 + 9 + 3) / 4 = 96 / 4 = 24`
バーンサイドの補題の拡張がポーリャの定理である。文献 [5] p.169 にある定理 6.16 から引用する。
定義域 `A` から値域 `B` への関数の同値類の在庫式（パターンの在庫式）は，巡回置換指数 `P_G` を用いて次のように表される。
`P_G( sum_(x in B) weight(x), sum_(x in B) {weight(x)}^2, cdots, sum_(x in B) {weight(x)}^k, cdots)`ここで，`weight(x)` は集合 `B` の元 `x` の重みを表す。
在庫式、巡回置換指数、重みなどの用語は文献をみてほしい。この定理はパターンを実際に求めるために使えるが、個数のみを必要とする場合は次の系が有用だ。同書の p.171 から引用する。
定義域 `A` から値域 `B` への関数の同値類の個数は次のように表される。
`P_G( abs(B), abs(B), cdots, abs(B))`
次は[5]の pp.171 にある例 6.24 である。
正四角錐の 5 個の面を 2 色で塗る方法が何通りあるかを求める。
解答は次のとおりである。
ここでは（中略）正四角錐の底面を `a` として、記号 `a, b, c, d, e` を割り当てる。このとき面の集合 `A` = {a, b, c, d, e} に対して、これらの面に塗る色の集合を `B = {x, y}` とする。 ここで、`x` は黒を、`y` は白を表す。すると集合 `A` から集合 `B` への関数は正四角錐への塗り方に対応することがわかる。
（以下要追記）
次は[6]の pp.136 にある 6.02 例 である。
3 個の黒と 6 個の白のビーズが円形の針金に通されている．このネックレスは回すことも裏がえすこともできる．同色のビーズは区別できないと仮定して， ネックレスの違った型はいくつ作れるか？
解答は 7 である。以下 [6] から引用する。
3 個の黒と 6 個の白のビーズを正 9 角形の頂点の位置に置く． もしその正 9 角形が固定されていれば，これを行なうのに `9 * 8 * 7 // 3 ! = 84` の違った方法が存在する。 もし 1 つの配列を他の配列に写す正 9 角形の対称群 `cc D_9` の元が存在すれば，2 つのこのような配列は同等である． `ccD_9` は違った配列を置換し，同等でない配列の数は，`cc D_9` のもとでの軌道の個数 `N` である． われわれは，`N` を見出すために Burnside の定理を使用できる．
表 6.2 は `ccD_9` の元のすべての異なる型と各型に対する固定された点の個数を表で示している． たとえば，図 6.01 に例示されている，頂点 2 を円の中心に結ぶ直線についての反射 `g in cc D_9` を考える． このとき `g` のもとで不変にされる配列は，黒いビーズが頂点 1 2 3，9 2 4，8 2 5，7 2 6 にあるときに生じる．したがって #Fix `g = 4` である． 各頂点を通る直線に関する 9 つの反射が存在する。したがって，これらの型の元による固定した点の総数は `9*4=36` である． `ccD_9` における位数 3 の回転は，もし黒いビーズが頂点 1 4 7, 2 5 8, 3 6 9 に位置すれば，配列を不変にするであろう． したがって固定される 3 つの配列が存在する．もし配列が位数 9 の回転のもとで固定されるならば，すべてのビーズは同色でなければならない． したがって，もし `g` が位数 9 をもつならば #Fix `g = 0` である． 表 6.2 は固定される点の全ての個数の和は 126 であることを示している． 定理 6.01 によって，`N = 1 / (# ccD_9) sum_(g in ccD_9) #"Fix" g = 126 / 18 = 7` であり，したがってネックレスの 7 つの違った型が存在する。□
表 6.2 ネックレスに関する `ccD_9` の作用 元の型，`g in ccD_9` `g` の位数 このような元の数，`s` # Fix `g` `s *`#Fix `g` 単位 1 1 84 84 線についての反射 2 9 4 36 `2pi // 3` または `4pi // 3` を通る回転 3 2 3 6 他の回転 9 6 0 0 `sum # "Fix" g = 126` 図 6.01 ネックレス上に作用する `ccD_9`
なお本書では、図 6.02 として具体的なネックレスの 7 つの型を示しているが、引用では省略する。
次は[6]の pp.137 にある 6.03 例 である。
ベンゼン環に CH3 または H を付属させて得られる異なる化合物の個数を見出せ．
解答は 13 である。以下 [6] から引用する。
炭素原子は正6角形の６つの頂点に配置され，したがって CH3 または H の基を付属させる `2^6` 通りの方法が存在する． ２面体群 `ccD_6` はこれらの `2^6` 通りの方法に関して作用するが，われわれはその軌道の個数を見つけたい．
相対する頂点を通る線についての反射 `g` を考える．`g` の位数は2であり，３つの相対する頂点の組を通る線についての反射が存在する． #Fix `g` は図 6.03 を調べることで決定される．もし原子配列が `g` で固定されるならば，位数 2 の基は位数 6 の基と同じでなければならず，また位置３と５の基もまた互いに等しくなければならない．したがって位置 1,2,3,4 の基は任意に選べ， そしてそれは `2^4` 通りの方法で行なわれる．
図 6.03 ベンゼン環(図省略)
`ccD_6` の各元によって不変にされる原子配列の数は表 6.3 に与えられている．われわれがいかなる元も落さなかったことを検証するために， われわれは元の個数を含む列を加える．そしてこれは群 `ccD_6` の位数に等しくなるべきである． Burnside 定理から，軌道の個数は `156 // # ccD_6 = 156 // 12 = 13` であることがわかる．したがって得られる分子の 13 の異なる型が存在する．◻
表 6.3 化合物に関する `ccD_6` の作用 元の型，`g in ccD_6` `g` の位数 このような元の数，`s` # Fix `g` `s *`#Fix `g` 単位元 1 1 `2^6` 64 相対する頂点を通る線に関する反射 例 `(26)@(35)@(1)@(4)` 2 3 `2^4` 48 相対する辺の中点を通る線に関する反射 例 `(56)@(14)@(23)` 2 3 `2^3` 24 `+-pi//3` だけの回転 例 (123456) 6 2 2 4 `+-2pi//3` だけの回転 例 `(135)@(246)` 3 2 `2^2` 8 `pi` だけの回転 `(14)@(25)@(36)` 2 1 `2^3` 8 `# ccD_6=12` `sum # "Fix" g = 156`
次は[6]の pp.138-139 にある 6.04 例 である。
もし `n` 種の色を使うとすれば，正 6 面体の頂点を着色するのに可能な方法はいく通りあるか？
解答は `(n^8 + 17n^4 + 6n^2) // 24` である。以下 [6] から引用する。
もしその正６面体が固定されていれば，８つの頂点は `n` 通りの仕方で着色され，全部で `n^8` 通りの着色法がある． 正６面体の回転群 `ccS_4` は，それらの間でこれらの着色法を置換し，軌道の個数は回転を考慮に入れた違った着色法の数である． われわれは Burnside 定理を用いて軌道の数を計算できる．
正６面体の回転群の元には5つの型が存在する． われわれは各型に属する元 `g` をとり，着色法が `g` のもとで不変であるように同じ色をもたなければならない頂点を決定する．
図 6.04 (図省略) は回転の異なった型を例示している．同じ色をもたなければならない頂点は同じように陰がつけられている． 表 6.4 は定められた着色法の個数を与えている．
Burnside 定理によって，軌道の数，したがって着色法の数は
`1 / (#(ccS_4)) sum_(g in ccS_4) # "Fix" g = 1/24 (n^8 + 17n^4 + 6n^2)`．これは，ついでにいえば，`n^8 + 17n^4 + 6n^2` がすべての `n in bbP` に対し 24 で割り切れることを示している．◻
表 6.4 正６面体の頂点の着色法 図 6.04 に例示されている元の型，`g_i` `g_i` の位数 このような元の数，`s` 色の選択法の個数，`r` `n^r` である# Fix `g` `s *`#Fix `g` 単位 1 1 8 `n^8` `n^8` `g_1` 2 `6*1=6` 4 `n^4` `6n^4` `g_2` 3 `4*2=8` 4 `n^4` `8n^4` `g_3` 4 `3*2=6` 2 `n^2` `6n^2` `g_4` 2 `3*1=3` 4 `n^4` `3n^4` `# ccS_4=24` `sum = n^8 + 17n^4 + 6n^2`
なお、`ccS` は `S` のカリグラフ体である。また、`bbP` は正の自然数の集合を表す。通常ならば `NN` を使うところだ。
次は[6]の pp.139-140 にある 6.05 例 である。
正 12 面体の面の 5 つが黒で他の 7 つが白であるように正12面体を着色する．可能な方法はいくつか？
解答は 14 である。以下 [6] から引用する。
固定された12面体の黒く着色される 5 つの面を選ぶ方法の数は
`((12),(5)) = (12*11*10*9*8)/ (5!) = 792`である．12面体の回転群 `ccA_5` に属する元の異なる型は図 6.05 （図省略）に示されている． 表 6.5 における与えられた型の元の個数は次のように計算される． 位数3の元は相対する頂点を通る軸についての回転である． 20個の頂点が存在するから，このような軸は 10 個存在する． 各軸について位数3の2つの単位元でない回転が存在する． したがって位数３の元の合計数は `10*2=20` である． 位数 2 と 5 の元も同様の方法で数えられる．
表 6.5 12面体の着色法 図 6.05 に例示されている元の型，`g_i` `g_i` の位数 このような元の数，`s` # Fix `g_i` `s *`#Fix `g_i` 単位 1 1 792 792 `g_1` 2 15 0 0 `g_2` 3 `10*2=20` 0 0 `g_3` 5 `6*4=24` 2 48 `# ccA_5=60` `sum # "Fix" g = 840` もし `g_2 in ccA_5` が位数３の元なら，われわれは次のようにして `#"Fix" g_2` を計算できる． 元 `g_2` はどの面も固定しないし，互いに素な３巡回置換で面を置換する． 次に，５つの黒い面は２つの面を固定せずに互いに素な３巡回置換で置換できず，したがって `"Fix" g_2 = 0` である． 同様にして，もし `g_1` が 2 巡回置換ならば `#"Fix" g_1 = 0` である． もし `g_3` が位数５の元であれば，`g_3` は２つの相対する面の中心を通る軸に関しての回転であり，これらの２つの面は固定される。 他の10個の面は２つの互いに素な５巡回置換で置換される。 これら５巡回置換のいずれかは黒であり得る．したがって `#"Fix" g_3 = 2` である．
表 6.5 と Burnside の定理から，違った着色法の数は `840 // 60 = 14` であることがわかる．◻
12面体の任意の面の着色方法は，その双対，２０面体の頂点の着色法に対応する．
数式表現はASCIIMathMLを使っている。また表の枠線の制御は CSS を使っている。
