典型90-083 Colorful Graph 別解
典型90-083 Colorful Graph について、勉強会をしていたところ公式解説と少し違う解法を議論することができたのでここに書き残します。
問題内容についてはリンク先を参照。（シンプルな問題設定です）
公式解説について
次数についての平方分割を行う。詳細は公式解説スライド：
83 日目の解説です。平方分割は情報オリンピック（JOI）などで頻出であるほか、セグメント木などによる高速化が思いつかないときにも有効です。この機会に理解しておくようにしましょう。
— E869120 (@e869120) 2021年7月4日
明日からはいよいよ「最終週」です。皆さん楽しみにしておいてください！！！ #競プロ典型90問 pic.twitter.com/0W1MRLmbWQ
別解
準備
与えられた無向単純グラフを \(G = (V, E)\) とする。 \(v \in V\) に対し、グラフ \(G\) における近傍や次数を次のように定める：
- \(N_G(v) := \{u \in V \mid \{u, v\} \in E\}\)
- \(d_G(v) := |N_G(v)| \)
元のグラフの辺に次数が小さい方から次数が大きい方へ向きをつけることにより有向グラフを作る。すなわち、有向グラフ \(D = (V, A)\) を、頂点集合は元のグラフ \(G\) と等しく、有向辺 \(A\) を
$$A := \{ (u, v) \mid \{u, v\} \in E \text{ かつ } d_G(u) \leq d_G(v) \}$$
として定める。
\(v \in V\) に対し、有向グラフ \(D\) における近傍 \(N_D(v)\) と出次数 \(d_D(v)\) を次のように定める：
- \(N_D(v) := \{u \in V \mid (u, v) \in A\}\)
- \(d_D(v) := |N_D(v)|\)
解法
クエリ \(q = (x, y)\) に対して、以下の処理を行う：
- \(x\) の \(D\) における近傍を見てその時点での \(x\) の色を確定させる
- 1によって確定した色をクエリの答えとして出力する
- \(x\) の色を \(y\) で更新する
- \(x\) の \(D\) における近傍に対して色 \(y\) で更新する
ステップ1 において色を確定させるために、どのクエリで色が更新されたかなどの時間情報を管理しておく必要がある。詳細は提出コード：
上のは自分のコードだが、勉強会にてこの方針を教えてくれた後輩の提出の方がわかりやすいかも：
正当性と計算量
正当性については公式解説とほとんど同じ。（公式解説スライドの2枚目参照）
計算量について、各クエリにおける計算量を考える。クエリ \((x, y)\) について、処理1 及び処理 2 がボトルネックで、この部分は \(d_D(x)\) 回の計算によってできる。この値を評価する。
ここで、明らかに \(d_D(x) \leq d_G(x)\) であり、 $D$ では元のグラフにおいて次数が小さい方から大きい方へ辺が伸びていることと握手補題から、
$$ \begin{aligned} d_D(x) \cdot d_G(x) &= \sum_{v \in N_D(x)} d_G(x) \\ &\leq \sum_{v \in N_D(x)} d_G(v) \\ &\leq \sum_{v \in V} d_G(v) \\ &= 2 |E| \end{aligned} $$
が成り立つ。よって、
$$ \begin{aligned} d_D(x) \leq \mathrm{min}\left\{ d_G(x), \frac{2|E|}{d_G(x)} \right\} \end{aligned} $$
を得る。
さらに、 \(d_G(x) \leq \frac{2|E|}{d_G(x)}\) のとき、\(d_G(x) \leq \sqrt{2|E|}\) であり、
\(d_G(x) \geq \frac{2|E|}{d_G(x)}\) のとき、\(d_G(x) \geq \sqrt{2|E|}\) より \(\frac{2|E|}{d_G(x)} \leq \frac{2|E|}{\sqrt{2|E|}} = \sqrt{2|E|}\) となる。以上より、
$$ \begin{aligned} d_D(x) \leq \mathrm{min}\left\{ d_G(x), \frac{2|E|}{d_G(x)} \right\} \leq \sqrt{2|E|} \end{aligned} $$
を得る。したがって、1つのクエリを計算量は $O(\sqrt{|E|})$ で処理できるので、全体での計算量は $O(Q\sqrt{|E|})$ となる。
コメント
今回の計算量評価では、「次数が低い方から高い方へ向きづけを行うと、各頂点の出次数は \(\sqrt{2|E|}\) 以下になる」というのがポイントでした。これは他にも使えることがありそう。
この解法はサークルでの勉強会↓
【7/18 競プロ班】
— WACPAC（早稲田競技系プログラミングサークル） (@wacpac_wsd) 2025年7月18日
典型90の★5、★6の勉強会を行いました！ pic.twitter.com/oIiVp72tmD
にて後輩からアイデアを教えてもらい、計算量評価を自分が行いました。勉強会、とても楽しいです！
ICPC 2024 参加記（早稲田・tcknyo）
はじめに
12月21日, 22日に行われた大学対抗競技プログラミングの大会、 ICPC 2024 Asia Yokohama Regional に出場してきました。後輩2人と共に tcknyo というチーム名で参加し、結果は 55 チーム中 39 位でした。良い結果とは言えないですが、個人的にはこの大会に出られたことがまず嬉しかったのとコンテスト中にやれることはやったと感じているのと、何よりコンテスト中とっても楽しかったので参加記を書いてみました。
チームについて
チームメンバーを紹介します！（AtCoder のユーザー名）
- toku4388
- B1。AtCoder青 (Highest 黄) 。
- なんでもできる。重い実装強め。
- ロシア語と brainf*ck が好きらしい。
- chimaki821（私です）
- M1。AtCoder青。
- 得意不得意に波あり（え？）
- 研究も就活もサボっててやばい。
- kyomikyomi（キクタン）
- B4。AtCoder水。
- ひらめき系、パズル系に強い。センス担当。
- 卒論がもう終わってるらしくて偉い。
チーム名は、 tcknyo です。由来↓
1日目のチーム紹介の時にスライド見せながら話す時間がありました。それについては後で書きます。
国内予選
7月5日にオンラインで国内予選がありました。早稲田には去年 Playoff に進んでいるメンバー3人で構成されている 2get という強いチームがあり、自分たちは横浜大会に進むのを目標にしていました。結果的には、チームメイトのおかげで全体30位になり、横浜大会に進むことができました。
ICPCおつかれさまでした！
— ちまき (@chimaki_yama821) 2024年7月5日
@toku4388 と@kikutannnb とtcknyoというチームで参加して30位、アジア地区行けそうです😭😭
自分は後輩を応援する係をしてました📣
2get チームはこの大会では高い順位ではなかったですが、台湾大会で上位に入って Playoff 出場権を獲得しており流石だな〜となりました。応援してます。
1日目（リハーサル・チーム紹介）
会場に着いたらスタッフとのやりとりを全て英語で行う必要があり、英語ができない自分は入場後に飲み物を買いに外に出ていいか確認することさえできませんでした。悲しい。
1日目の流れとしては、ルール説明→リハーサル→チーム紹介 となっていました。
リハーサル
リハーサルでは、本番用の PC でエディターやジャッジシステムの使い方などを練習することができました。自分たちのチームでは VSCodium というほとんど VSCode のようなエディターを使うことになりました。事前情報では全く拡張機能を使うことができないと聞いていたのですが、C/C++ は clangd というものが、Python は Microsoft のものが入っており、補完などが効いてストレスなくコーディングすることができてよかったです。 clangd については使い慣れない挙動もありましたが、toku くんが 記事 を参考にして設定してくれることになりました。ありがとう...
チーム紹介
事前にチーム紹介用の1枚のスライドを提出し、それを表示しながら30秒ほどのチーム紹介をする時間があります。大学順で呼ばれるので自分たちは最後から2番目でした。キクタンくんに話してもらったのですが、 " 'nyo' is a Japanese traditional suffix" というのがウケてて嬉しかったです。スライドはどうしよ〜〜って悩みながら ChatGPT に丁寧丁寧丁寧にプロンプト投げたらおもしろ返答してきたので採用しました。ちなみにこのエンジ色は早稲田カラー（R142 G23 B40）です。
他のチームの紹介は、suzuken さんに「あれ誰ですか？？」って聞いて有名人だ〜〜〜！！！って楽しんでました。
2日目（コンテスト本番・懇親会）
いよいよ2日目、本番です。全員起床に成功して8時半には会場に集合できていてよかった。
コンテスト本番
コンテスト開始後、tokuくんに簡単に環境を整えてもらい、キクタンくんに A を解いてもらいました。ちょっと時間かかってたっぽいけどちゃんと AC。[16分] 自分はその間 B を考えましたが、あれ？これむずくね？？と言いながら toku くんに軽く相談しました。5分ほど喋って解法がまとまり、自分が実装して（ちょっと怖かったのでランダムテストして）AC。[37分]
その間に toku くんが E はやるだけっぽいです！と言って出来そうだったので実装してもらい、少しのバグとりなどをしたのちにスムーズにAC。[58分] ここまでいい感じ。
ここからがかなりしんどい時間でした。順位表も見つつ、IとKはいけそう・Cは少し解かれてるけどきつそう・Lは解かれてないけどワンチャン？・余裕があればD,F,G、みたいな状況。キクタンくんに I を任せ、toku くんと K を詰める。話し合いながら解法が見えてきたので toku くんに実装をお願いする。サンプルが合ったので提出するが、WA。[約2時間]
その間にキクタンくんがIできそう、って感じだったので軽く解法を聞いて実装をしてもらう。半分お祈りの計算量で出してみたが、TLE。[約2時間半?]
toku くんとデバッグ祭りをして原因を見つけて修正に。2人にそれぞれの問題を任せつつ、順位表を見るとCを解かないとまずそうなので chimaki が見に行く。なんもわかんね〜〜と思いながら考えてることをキクタンくんに話してたら解法を思いついた。ちょうどそのタイミングで toku くんが K を AC。[3時間16分]
PC が空いたので C の実装を chimaki が行う。やることは単純なのでパパッと実装し、提出すると AC。[3時間27分]
残り時間1時間半、Playoff には最低2問必要。順位表を見ると D と I に注目すべきっぽいのでこれらを考えるが何もわからず。残り20分ほどで F に対してちょっとした予想解法を提出（WA）して終了。[5時間]
順位発表・懇親会
はじめて yes/no *1を経験しました。凍結後の順位表ってこんな感じで開くんだ、おもしろすぎる。うちのチームは F に提出した分が隠されていて、WA (No) だったのですが司会の方が nyo ~~ って言って盛り上げてくれてすごかった。
懇親会ではたくさんの企業ブースと美味しい食事がありました。企業ブースでは何人かの知り合いと挨拶したり、ボードゲームをしたり、難しい問題を考えたりしてました。あと、早稲田OBの siro さん・かっつさん・ tossy さんとお話できて、よりモチベーションが上がりました。毎週土曜に半日の練習会、やりたい。
感想
C, K をもっと早く通したかった〜〜とか I, D あたりを解きたかった〜〜とかありますが、解説聞いてもなるほど！ってならなかった（英語ができないせいかも）ので、まだまだ実力不足だと痛感しました。でも一人では解けなかったような問題もコンテスト中に通せたのでとても楽しかったです。いや〜〜〜〜また出たい、出たすぎる。自分の実力を磨きつつ、WACPAC（競プロサークル）をもっと盛り上げて早稲田全体で強くなるのを目指すぞ。
自分は来年は ICPC に出場できないので、後輩たちを応援しつつ一緒に練習会をやりたいと考えてます！チーム戦は楽しい！！
最後に、チームの二人・コーチの suzuken さん・応援してくれた皆さん、本当にありがとうございました！
*1:コンテスト終了1時間前に順位表の更新が止まり、終了後に順番に正解かどうか開けていくイベント
表現論ゼミ活動報告
Wathematicaで行っている表現論ゼミの紹介をします！
ゼミの概要
発表担当をあらかじめ決めておいて発表する、輪講形式のゼミを行っています。雑談時間などを除くと平均3時間ほどで毎回のゼミをしています。 ゼミ中の様子はこんな感じです。
<表現論ゼミ第21回>
— 理工系学術サークルWathematica (@wathematica) 2022年10月15日
リー群とリー代数の表現について、直和・テンソル積・双対空間の表現を構成しました。 pic.twitter.com/SFxa8LQKjd
基本情報
- メンバー：数学科・応用数理学科のB3, B4 現在は4人
- 使用教科書：途中で教科書を変更しました。*1以下、[F-H], [Hall]と略記します。
- [F-H] William Fulton, Joe Harris "Representation Theory: A First Course"
- [Hall] Brian C. Hall "Lie Groups, Lie Algebras, and Representation Theory"
- 開始時期：2022年1月末
- 活動頻度：週1回、夏休みや試験前は休み
- 活動場所：大学内のホワイトボードがある部屋 or 黒板のある教室
内容について
表現論とは？
代数的な対象（e.g. 群、代数）が線型空間に対してどのように作用するかを記述するのが表現論です。「群などの代数的対象を直接調べるのは難しいから表現によって扱いやすい線型空間の理論によって解決する」「線型空間の対称性を記述する」などが表現論が重要である理由らしいです。 内容に関する詳しい話はここではしませんが、有限群の表現は化学への応用・リー群の表現は量子力学をはじめとする物理学への応用があるそうです。
自分は「代数的組合せ論」を専門にしようと考えているのですが、そこでは当たり前のように表現論が使われているので自分で使えるようになりたいと思って勉強をしています。他のゼミメンバーは皆幾何学が専門で、幾何学的な具体例をたくさん扱うために表現論へのモチベーションがある、と話していました。
必要な予備知識、勉強方法
表現論は線型空間を扱っているので、線型代数の知識が非常にたくさん要求されます。さらに、リー群やリー代数の重要な具体例は多くが行列からなるものであるので、そこでも線型代数の知識がたくさん要求されます。*2逆に、線型代数を勉強したのでそれの応用を見たいという人はぜひ表現論を勉強してみてほしいです。
おすすは下の池田先生の本です！（B1の線型代数のみを仮定して表現論に必要な線型代数を最初に準備してくれます）
テンソル代数と表現論: 線型代数続論 | 池田 岳 |本 | 通販 | Amazon
このゼミから受けた恩恵
モチベーションの維持と向上、これが一番です。以下、少し詳しく書きます。
誤った理解の防止
一人で本を読んでいるときは大丈夫だと思ったこともゼミで発表するとギャップに気づく、ということがあります。話すことで自分で気づく場合や人から言われて気づく場合がありますが、どちらにせよこれは一人で勉強しているだけでは得られないことなのでとてもありがたいことです。発表時に詰められるのはつらいですが…それも発表準備のモチベーションになるのでヨシ！
定期的な勉強の機会
自分はあまりいろいろなことが長続きしないのですが、ゼミ形式で勉強することによって長期的・計画的な勉強をすることができます。
必要な予備知識の補助
（これを期待して人に頼りきりでゼミをするのは良くないとは思いますが…）
このゼミでは他のメンバーが幾何学専攻なのでリー群・リー代数を扱うときの多様体、微分幾何に関して足りない知識を教えてもらっています。また、線型代数の勉強不足な部分についても助けてもらうことが多々あります。自分も他のゼミメンバーの役に立ちたい！とはいつも思っているのですが、残念ながら今のところは特にできていないのでたくさん勉強したいです。
線型代数力の向上
ゼミを始めたころに比べて、線型代数パワーがかなりあがりました。（e.g. 双対空間、テンソル代数、同時対角化、非退化双線型形式）まあ、まだまだ足りないですけど。
最後に
このゼミの今後の予定
しばらくは、Root systemやDynkin diagramが何なのか、それによって何がわかるのかなどを目標として進めていく予定です。余裕があれば、Kac-Moody algebraも少し触れたい…… あと個人的には、新潟に帰省するときに上越新幹線のE7系に乗りながらルート系のE_7について勉強したいと思っています。
過去の活動記録
せっかくの機会なので、今までのゼミ記録をここにまとめておきます。
- 第1回：1/28 [F-H] §1.1, 1.2
- 有限群の表現の基本
- Schurの補題、Machukeの定理
- 第2回：2/4 [F-H] §1.3, 2.1, 2.2
- S_3の表現
- 指標の導入と直交性
- 第3回：2/18 [F-H] §2.3, 2.4
- S_4, A_4の指標、射影公式
- 第4回：2/25 [F-H] §3.1
- S_5, A_5の指標
- 第5回：3/5 [F-H] §3.2, 3.3
- S_dの標準表現から得られる表現
- 誘導表現の存在と一意性
- 第6回：3/11 [F-H] §3.3
- Frobeniusの指標公式
- 第7回：3/25 [F-H] §3.4
- 群環
- 第8回：4/1 [F-H] §3.5
- 係数拡大と表現
- 第9回：4/8 [F-H] §3.5
- 双線型形式による特徴づけ
- 第10回：4/22 [F-H] §4.1
- S_dの表現について成立することを確認
- 第11回：5/6 [F-H] §4.2
- Young図形から既約表現の構成
- 第12回：5/13 [F-H] §4.3
- Frobenius Formulaの証明
（有限群の表現終了、リー群とリー代数の表現へ。）
- 第13回：5/20 [F-H] §7.1, 7.2
- Lie群の導入と具体例
- 第14回：5/27 [F-H] §7.2
- Lie群の具体例
- 第15回：6/10 [F-H] §8.1, 8.2
- Lie代数の導入と具体例
- 第16回：6/17 [F-H] §8.2, 8.3
- Lie代数の具体例と指数写像
- 第17回：6/23 [F-H] §8.2, 7.3
- 被覆空間とSecond Principle
（以降、[Hall]に変更。）
- 第18回：7/2 [Hall] §3.1 ~ 3.4
- Lie代数の可解性と冪零性
- 行列Lie群のLie代数
- 第19回：7/15 [Hall] §3.4 ~ 3.8
- 随伴表現の定義、SO(3)とSU(2)の関係
- 第20回：10/7 [Hall] §4.1, 4.2
- 表現の定義と複素化との関係
- SU(2)の既約表現の構成
- 第21回：10/14 [Hall] §4.3
- 表現の直和、テンソル積、双対
- 第22回：10/21 [Hall] §4.4
- ユニタリ表現、コンパクトLie群の完全可約性
- 第23回：10/28 [Hall] §4.6
- sl(2, C)の表現
- 第24回：11/11 [Hall] §4.7, 4.8
- 第25回：11/25 [Hall] §6.1~ 6.4
- sl(3, C)の表現：Highest weightを用いた分類
- 第26回：12/2 [Hall] §6.5, 6.6
- Highest weight (1, 1)の表現
- Weyl群によるweightの見直し
- 第27回：12/9 [Hall] §6.7, 6.8
- Weight Diagramに関する性質
- 第28回：12/16 [Hall] §7.1
- Lie代数のコンパクト実形から得られる諸性質
以上です！お読みいただきありがとうございました。
参考文献
Burnside の補題を用いた数え上げ【Wathematicaアドベントカレンダー】
はじめましての方ははじめまして。Wathematica2年のchimakiと申します。Wathematica Advent Calender 2021 の12/16日の記事になります。個人的に好きなBurnsideの補題について書こうと思います。
（もくじ）
問題設定
問題１
立方体を $n$ 色以下で塗る場合の数は何通りあるか。ただし、回転などにより重なるものは同じとみなす。
この問題について考えていきます。高校数学では、異なる6色で塗分ける場合の数や同じ色が隣り合わないよう異なる5色で塗る場合の数を求める問題を円順列や数珠順列の考え方を応用することで解くことができましたが、この問題においては「同じ色は隣り合わない」という制約が外れており、難しくなっています。例えば、次の2つの図のような塗り方を同じとみなす必要があります。（雑な図でごめんなさい）
それではこの問題について考えてみましょう。
こういう問題は小さいnについて考察してみると何か見えてくることが多いです。しかし、n＝2の場合でもどの塗り方が回転で重なり合うのか見つけるのは容易ではありません。（ちなみn＝2の場合は10通り、n＝3の場合は57通りになります。気になる人は頑張って試してみてください、おすすめはしません）
Burnsideの補題
そこで本稿の主題であるBurnsideの補題を使うことを考えます！まずはBurnsideの補題の主張をみていきましょう。
命題の主張と解釈
Burnsideの補題の主張は以下の通りです。
Burnsideの補題
有限群 $G$ が集合 $X$ に作用するとする。また、 $g \in G$ に対いて $g$ によって固定されるすべての $X$ の元からなる集合を $\mathrm{fix}(g)$ とする。このとき、軌道の数は $\frac{1}{|G|} \sum_{g \in G} | \mathrm{fix}(g)|$ である。
…………。何言ってるかさっぱりわかりませんね。。。
まず「群」ってなんだよ！って感じだし「作用」も分からないし、「軌道」も意味が分からない。本当にこの命題がさっきのような問題解決につながるの？って感じです。
（群論に詳しい方はこの定理を最初の問題にどう使うか考えてみてください）
具体例：正方形の頂点塗り分け
そこで、具体的な問題を通してこの定理を解釈していきましょう。具体例を考えると分かりやすいのですが最初から立方体の面の塗分けを考えるのは難しいので次のような問題を考えてみます。
問題２
正方形の各頂点を青か黄色で塗り分ける方法は何通りあるか。ただし、回転させて同じものは同じとみなす。
（ここでは簡単のため裏返しは考えないこととします。つまり、裏返したときに同じ塗り方になっても別とみなします。）
（ここでは簡単のため裏返しは考えないこととします。つまり、裏返したときに同じ塗り方になっても別とみなします。）
この問題にBurnsideの補題を応用するために適切に群 $G$ や集合 $X$ を定める必要がありますが、そこはなんとなくノリをつかめればOKです！
まず、群 $G$ が集合 $X$ に作用しているとは、「集合 $X$ には $G$ という群によってあらわされるような対称性がある」ということです。そして結論部分である「軌道の数」とは、「群 $G$ による対称性によって同じものを同一視したときの場合の数」になります！求める場合の数がこの「軌道の数」に一致するように $G$ と $X$ を定めていきます。（要するに「群」ってやつが対称性をあらわすんだな～ってことです）
これを上の問題2で考えましょう。正方形は 90°, 180°, 270° 回転させてもまた同じ形になります。また、当然ですが 0° 回転させる（つまり何もしない）という操作に対しても形は保たれます。
このことから、平面上の正方形には「0°, 90°, 180°, 270° 回転」に対する対称性があるといえます。この4つの回転こそがこの問題における群 $G$ です。
そして、今回の問題では集合 $X$ は以下の図のようなものとしましょう。
つまり、対称性を無視して全ての塗り方を考慮した集合を $X$ と定めるのです。このとき、例えば下の図のような $G$ から $X$ への作用があります。
さて、これで「有限群 $G$ が集合 $X$ に 作用するとする」の部分は分かりました。では次に「 $g \in G$ に対して $g$ によって固定されるすべての $X$ の元からなる集合」という部分を見てみましょう。 $G$ は対称性を表すものなので、今回の問題では上の考察から $g \in G$ は、0° 回転・90° 回転・ 180° 回転・ 270° 回転のいずれかとなります。
まず、「90° 回転」として考えてみます。すると、先ほどの図で定めた $X$ の元のうち、90° 回転させても変わらないものは以下の2つになります。 270° 回転の場合も同じです。
次に、「180° 回転」として考えてみます。これによって固定される $X$ の元は以下の4通りです。
最後に、0° 回転に対して不変なものは $X$ の元全てであることに注意しておきましょう。
以上によって、「各 $g \in G$ に対して $g$ によって固定されるすべての $X$ の元からなる集合」が分かりました。
ではBurnsideの補題の結論の部分の解釈です。最初に述べたとおり、「軌道の数」とは「群 $G$ による対称性によって同じものを同一視したときの場合の数」になります。つまりこの問題では「回転で重なるものを同一視したときの頂点の塗り方」（求めたかったやつ！）がこれにあたるのです！そしてBurnsideの補題の主張から、これが「各 $g \in G$ に対して不変な $X$ の部分集合の要素数の和をとり、対称性の数で割ったもの」と等しくなることが分かります。
今述べたことを図示するとこんな感じです。
よって、この問題の場合の数は
$$\frac{1}{4}(2 \times 2 + 4 + 16) = 6 通り$$
と求めることができます！
以上の例から、Burnsideの補題は次のように応用できると分かります！！
対称性のあるものの数え上げ
対称性のあるものの数え上げは、以下のようにして求められる。
1. 対称性をとらえる
2. それぞれの対称性について不変なものを数え上げる（このときは対称性を無視して全て数える）
3. 2で数えたものを全ての対称性について和をとり、「対称性の数」で割る。
1. 対称性をとらえる
2. それぞれの対称性について不変なものを数え上げる（このときは対称性を無視して全て数える）
3. 2で数えたものを全ての対称性について和をとり、「対称性の数」で割る。
n 色で塗る場合
上と同様の考え方により、頂点を $n$ 色で塗る場合の数も求めることができます！
90°, 270° 回転で不変なものはどちらの場合も全ての頂点の色が同じ場合の $n$ 通りです。よって合計で $2n$ 通りとなります。
また、180° 回転で不変なものは対角線上の2頂点を同じ色で塗る場合の $n^2$ 通りです。
そして、0° 回転で不変なものは $n^4$ 通りです。
以上より、求める場合の数は $\frac{1}{4} (n^4 + n^2 + 2n)$ 通りと分かります！
（余談ですが、「場合の数は必ず整数になる」ということから上の式の分母「 $n^4 + n^2 + 2n$ 」が4の倍数であることが分かります！）
問題を解く
さて、Burnsideの補題の使い方が少しわかったところで実際に立方体の塗分けを考えていきましょう。先ほどの数え上げ方法をもう一度見直しておきます。
対称性のあるものの数え上げ
対称性のあるものの数え上げは、以下のようにして求められる。
1. 対称性をとらえる
2. それぞれの対称性について不変なものを数え上げる（このときは対称性を無視して全て数える）
3. 2で数えたものを全ての対称性について和をとり、「対称性の数」で割る。
1. 対称性をとらえる
2. それぞれの対称性について不変なものを数え上げる（このときは対称性を無視して全て数える）
3. 2で数えたものを全ての対称性について和をとり、「対称性の数」で割る。
1. 立方体の対称性をとらえる
まずは立方体の対称性について考える必要があります。これは厳密にやろうとするとむずかしいのですが、以下のように解釈できます。
（分かりにくいかもしれません……この後図を使って説明するのでいったん飛ばしちゃって大丈夫です）
これらそれぞれについて、何通りの対称軸がとれるかみてみましょう。
それぞれの操作に対する対称軸
- (A) について
動かさないのは1通りしかありません。
- (B) について
以下の図のように3通りあります。
- (C) について
以下の図のように4通りあります。
- (D) について
6通りです。詳しくは各自で確認してみてください。
(A) ~ (D) より、対称性の数は合計で、
(A) : 1通り
(B) : 3 × 3 = 9 通り
(C) : 2 × 4 = 8 通り
(D) : 1 × 6 = 6 通り
であるので、1 + 9 + 8 + 6 = 24 個になります！
これで立方体の対称性が分かりました！
2. 各対称性で不変な塗り方
次に各対称性を表す操作（回転）について不変な塗り方を数えていきましょう！
- (A) について
どのような塗り方を考えても「何もしない」という操作の下では不変であるので、各面を $n$ 色で塗ることを考えることにより、 $n^6$ 通りです。
- (B) について
90°, 270° の場合と 180° の場合で異なるので注意が必要です。
まず、90°, 270° 回転によって不変になる場合を考えます。そのためには、回転軸を含む二つの面は自由に塗り、その他の4面を同じ色で塗る必要があります。よって、前者の二つの面の塗り方が $n^2$ 通り、後者の4面の塗り方が $n$ 通りなので合計 $n^3$ 通りとなります。
次に、180° 回転によって不変になる場合を考えます。そのためには、回転軸を含む二つの面は自由に塗り、その他の4面を向かい合う2面同士が同じ色になるように塗る必要があります。よって、前者が $n^2$ 通り、そのそれぞれに対し後者が $n^2$ 通りなので合計 $n^4$ 通りとなります。
- (C) について
120°, 240° 回転どちらの場合でも、回転軸を上2つの頂点に対して一方の頂点側にある3面を同じ色で、他方の頂点側にある3面を同じ色で塗る必要があります。前者の選び方が $n$ 通り、そのそれぞれに対し後者が $n$ 通りなので合計 $n^2$ 通りとなります。
- (D) について
頑張ると、$n^3$ 通りであることが分かります。（各自で考えてみてください）
以上により、各対称性を表す操作に対して不変な塗り方が求まりました！
あとはこれらに対してBurnsideの補題を適用すると答えがでます！！
3. 2で数えたものから答えを求める
さて、仕上げです。『2で数えたものを全ての対称性について和をとり、「対称性の数」で割る。』を実際に行っていきましょう！これは以下のように求めることができます。
これを整理することにより、
$$\frac{1}{24}(n^6 + 3n^4 + 12n^3 + 8n^2)\ 通り$$
と求めることができました！！！
（なお、n = 6の場合からn = 5の場合を引くことでちょうど6色で塗る場合の数を求めることもできます）
おまけ
いかがでしたでしょうか。Burnsideの補題が対称性のあるものの数え上げにとても役立つことが伝わったでしょうか。ちなみにこの定理は「Cauchy-Frobeniusの定理」とも呼ばれるらしいです。この定理は、「ぐ・こ・き」で知られる位数に関する定理やLagrangeの定理を使うことで証明することができます。（証明は[2], [3]に載っています。そんなに難しくないです）また、群論にある程度慣れている人だと立方体の対称性が4次対称群で表されることをご存じだと思うのですが、そのときの「置換の型」の考え方が塗り分けにおける大きな役割を果たしています。これを生かして「サイクルインデックス」というものを導入し、定理をより使いやすい形に書き直すこともできるようです。（一緒に[3]を読みましょう！）また、この定理は表現論を使って証明することもできるようです。（自分は詳しく知りません）そして、競技プログラミングの問題に応用することもあるらしいです。
最後に
今回は前提知識なしで読めるようになるべく群論のことばを使わずに書いてみました。ですが定理の証明やより深い理解のためには群論が必須です。おすすめは参考文献[1]の本です。
「一人では厳しい……」というそこのあなた！！！Wathematicaでこれから群論ゼミが開催されるらしいですよ！！！！！
参考資料
[1] 雪江明彦. 群論入門 / 雪江明彦著. 東京, 日本評論社, 2010
[2] Godsil, C. D. (Christopher David), Royle, Gordon. Algebraic graph theory / Chris Godsil, Gordon Royle. New York, Springer, 2001
[3] Aigner, Martin. A Course in Enumeration [electronic resource] / by Martin Aigner. 1st ed. 2007., Berlin, Heidelberg, Springer Berlin Heidelberg, 2007
[4] Liu, Chung Laung, 伊理 正夫, 伊理 由美. 組合せ数学入門. 1 / C.L.リウ 著 ; 伊理正夫,伊理由美 共訳. 東京, 共立出版, 1972.
