整数の分割ではfunctional graphを考えたら上手くいく...かもしれない
まえがき
この記事は 仮の人 さんの企画 AMC2023 (Advent Math Calendar2023) のDay3に当たります. ほかの人の記事もぜひ見よう. 修正点があったら遠慮なくコメント欄で教えてください.
内容
この記事に分割数は出てきません. 出てくるのは整数の分割です. (しいて言えば今回の結果から分割数の上界として$n!$が得られるが, 上界としてはあまりにも大きい)
グラフ理論と共役作用の話が主です. 群と群の作用の定義を知っておくといいかもしれない.
概要
この記事では, 全単射な写像のfunctional graph(以降関数グラフと呼ぶ)の自己同型群(対称群の共役作用の安定化群)を考えることにより, 整数の分割に関する以下の等式を導く.
自然数$n$の分割$a:a_1 + \cdots + a_k = n \hspace{8pt} (a_i \geq a_{i + 1})$について, スコア$S(a)$を以下のように定義する.
$$S(a) = \prod_{i = 1}^{\infty} i^{C(a,i)} C(a,i)!$$
ここで, $C(a,i)$は分割$a$に含まれる$i$の個数である.
例えば分割$a:3 + 2 + 1 + 1 = 7$のとき$C(a,1) = 2 , C(a,2) = C(a,3) = 1, C(a,10) = 0$
このとき, $n$の分割全体の集合を$P(n)$とすると
$$\sum_{a \in P(n)} \frac{1}{S(a)} = 1$$
議論の要点
整数の分割と関数グラフの対応
「整数の分割」と「全単射な写像のなす関数グラフの形」の間に一対一の対応があることを使う. 具体的には,
$n$が$a_1$個の$1$, $a_2$個の$2$, $\cdots$, $a_k$個の$k$, $\cdots$に分割されたとき,
この分割に対して
$a_1$個の長さ$1$の有向サイクル, $a_2$個の長さ$2$の有向サイクル, $\cdots$, $a_k$個の長さkの有向サイクル, $\cdots$で構成された関数グラフを対応させる. このとき, 関数グラフは一意に定まらないが, 関数グラフの形は一意に定まる.
関数グラフの「形が等しい」の言い換え
関数グラフは, 頂点$a,b$に$f(a) = b$という関係があるとき$a$から$b$に有向辺をつなげてできたものだった. つまり, 写像$f,g$の関数グラフが「形が等しい」ということは
ある全単射な写像$h$が存在し$f(a) = b \Leftrightarrow g(h(a)) = h(b)$となる, と言い換えられる.
これを変形すると$g(h(a)) = h(f(a))$, つまり$g = h \circ f \circ h^{-1}$となる. これは対称群の共役作用を考えたとき$f$の軌道と$g$の軌道が一致するということである.
「頂点を区別する場合の数」と「区別しない場合の数」の関係
例えばある「頂点を区別していない」頂点数$n$のグラフ$G$があったとして, 各頂点に$1$から$n$を対応させようと思ったとき, その「対応の数」は$n!$である. ただし, このとき対称性の分で割る必要が出てくる(例えばサイクルなら$2n(n \neq 1,2)$で割る必要がある(数珠順列)). そしてこの「対称性の分」は, 頂点の置換であって, 頂点を「その置換で入れ替えてもグラフの形が変わらない」ような置換の数である. そのような置換全体の集合を$Aut(G)$と表せば, 「対応の数」は$\frac{n!}{|Aut(G)|}$と表せる. ちなみに$Aut(G)$は群になり, 自己同型群と呼ばれる.
関数グラフの基本的な性質
定義:関数グラフ
この記事では, 関数グラフを集合$S$と写像$f:S \rightarrow S$の組$(S,f)$であるとする.
「議論の要点」の節で言っていたように, 関数グラフの形が等しい, という同値関係$\sim$は次のように定義できる.
$(S,f) \sim (S',f') \Leftrightarrow $ある全単射な写像$g:S \rightarrow S'$が存在し$g \circ f \circ g^{-1} = f'$
このとき$g$を$S$(あるいは$(S,f)$)から$S'$(あるいは$(S',f')$)へのグラフ同型と言うことにする.
有限集合$S$の要素数を$|S|$で表し, 関数グラフの頂点数$|(S,f)|$を$|S|$と定義する.
頂点数が有限な関数グラフ全体の集合を$\mathbf{G}$とし, その元を有限関数グラフと呼ぶ. $\mathbb{G} = \mathbf{G} / \hspace{-2pt} \sim$とする.
$\mathbb{G}$の元を非標識関数グラフと言うことにする.
$a \in \mathbf{G}$について, $\overline{a}$で$a$の$\mathbb{G}$における同値類を表す.
$(S,f) , (S',f') \in \mathbf{G}$について, $(S,f) + (S',f') := (S + S', g)$
ただし$S + S'$は$S$と$S'$の非交和を表し(つまり$S \cap S' \neq \emptyset$の時も, $S + S'$においては$S$の元と$S'$の元は区別する), 写像$g:S + S' \rightarrow S + S'$は
$g(x) = \begin{eqnarray}
\left\{
\begin{array}{l}
f(x) \hspace{8pt} (x \in S)\\
f'(x) \hspace{8pt} (x \in S')
\end{array}
\right.
\end{eqnarray}$
という写像である.
また$g \in \mathbf{G}$について$n \cdot g = \sum_{k = 1}^n g$とする. ただし$n = 0$のときは, $0 \cdot g$を空集合から空集合への写像のなす関数グラフとする.
この和は$\mathbb{G}$で考えてもwell-definedである. また交換法則や結合法則が成り立つ.
$X_n$を$0$以上$n$未満の整数の集合とする. このとき長さ$n$のサイクルを$cyc_n := \overline{(X_n,f)}$とする.
ただし$f:X_n \rightarrow X_n$は$f(k) = (k + 1) \bmod n$という写像である.
よく知られている事実として以下の補題がある.
$a = \overline{(S,f)} \in \mathbb{G}$で, $f$が全単射な写像であるとき
$$a = \sum_{k = 1}^{\infty} a_k cyc_k$$となる$a_k \in \mathbb{Z}_{\geq 0}$が存在する. ただし十分大きな整数$M$が存在し$i > M \Rightarrow a_i = 0$
自己同型群
関数グラフ$G$について, $G$から$G$へのグラフ同型全体の集合は写像の合成を積として群をなす.
これを$G$の自己同型群と呼び, $Aut(G)$と書く.
特に$G \in \mathbf{G}$のとき, $Aut(G)$は$G$の, $|G|$次の対称群の共役作用の安定化群である.
また, $g \in \mathbb{G}$について, $Aut(g)$を, $\overline{G} = g$となるような$G$を取ってきて$Aut(g) = Aut(G)$と定義すると, これは同型の分を除いて一意的に定まる.
安定化群の性質と, グラフ同型の定義を考えれば次の補題が成り立つ.
頂点数$n$の任意の非標識関数グラフ$G$と, $|S| = |G|$となるような集合$S$について, 写像$f : S \rightarrow S$で$\overline{(S,f)} = G$となるようなものの個数は$\frac{n!}{|Aut(G)|}$個
「議論の要点」の節で言っていたように, $G$の各頂点に$1, \cdots , n$を書き込めばいいので$n!$通り, ただし同型(=対称性)の分で割る必要があるといった感覚の式である.
上の補題の$G$を, 頂点数$n$の写像のなす関数グラフ全体とすれば次の定理が成り立つ.
$$\sum_{g \in \mathbb{G} , |g| = n} \frac{n!}{|Aut(g)|} = n^n$$
である. $|Aut(g)| \geq 1$より, 頂点数$n$の関数グラフの数が$\frac{n^n}{n!}$以上であることがわかる.
ほとんどのグラフは対称性がないので, この評価は$n$が大きいときには有効である(多分).
また$\mathbb{G}' \subset \mathbb{G}$を全単射な写像のなす非標識関数グラフの集合とすると
$$\sum_{g \in \mathbb{G}' , |g| = n} \frac{1}{|Aut(g)|} = 1$$
ちなみに, ほとんど同じ手順で関数グラフだけでなく単純グラフや木についても同様の等式を導くことが可能.
「議論の要点」の節で言っていたように, 次のような写像$F$を考える.
$$F : \mathbb{G}' \ni g = \sum_{k = 1}^{\infty} a_k cyc_k \mapsto 分割a : \sum_{k = 1}^{\infty} \sum_{i = 1}^{a_k} k$$
ただし十分大きな整数$M$が存在し$i > M \Rightarrow a_i = 0$, また$a_k = 0$のとき$\sum_{i = 1}^{a_k} k = 0$とする.
このとき, $\mathbb{G}'$の要素のうち頂点数が$n$であるものと, $n$の分割は一対一に対応する.
よってあとは$|Aut(g)| = S(F(g))$を示せばよい.
$f \in Aut(g)$について, $f$によって$a_k cyc_k$は$a_k cyc_k$に移る. $a_k$個あるサイクルをどのサイクルに移すかで$(a_k)!$通り. $a_k$個のサイクルそれぞれについて, そのまま移動先のサイクルへ移すか, $1$だけずらして移すか, $\cdots$ , $k - 1$だけずらして移すかの$k$通りあるので$k^{a_k}$通り.
これをすべての$k$について考えるので,
$$|Aut(g)| = \prod_{k = 1}^{\infty} a_k! k^{a_k}$$
上記の式を写像$F$で整数の分割に対応させると, 右辺は$S(F(g))$である. よって示された.
ちなみに, 明らかに$Aut(g)$は$|g|$次の対称群の部分群なので$n! = (1a_1 + 2a_2 + \cdots)!$は右辺で割り切れます.
自然数$n$の分割$a:a_1 + \cdots + a_k = n \hspace{8pt} (a_i \geq a_{i + 1})$について, スコア$S(a)$を以下のように定義する.
$$S(a) = \prod_{i = 1}^{\infty} i^{C(a,i)} C(a,i)!$$
ここで, $C(a,i)$は分割$a$に含まれる$i$の個数である.
例えば分割$a:3 + 2 + 1 + 1 = 7$のとき$C(a,1) = 2 , C(a,2) = C(a,3) = 1, C(a,10) = 0$
このとき, $n$の分割全体の集合を$P(n)$とすると
$$\sum_{a \in P(n)} \frac{1}{S(a)} = 1$$