7

整数の分割ではfunctional graphを考えたら上手くいく...かもしれない

447
0

まえがき

この記事は 仮の人 さんの企画 AMC2023 (Advent Math Calendar2023) のDay3に当たります. ほかの人の記事もぜひ見よう. 修正点があったら遠慮なくコメント欄で教えてください.

内容

この記事に分割数は出てきません. 出てくるのは整数の分割です. (しいて言えば今回の結果から分割数の上界としてn!が得られるが, 上界としてはあまりにも大きい)
グラフ理論と共役作用の話が主です. 群と群の作用の定義を知っておくといいかもしれない.

概要

この記事では, 全単射な写像のfunctional graph(以降関数グラフと呼ぶ)の自己同型群(対称群の共役作用の安定化群)を考えることにより, 整数の分割に関する以下の等式を導く.

分割に対するスコアの逆数の総和は1

自然数nの分割a:a1++ak=n(aiai+1)について, スコアS(a)を以下のように定義する.
S(a)=i=1iC(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)とすると
aP(n)1S(a)=1

議論の要点

整数の分割と関数グラフの対応

「整数の分割」と「全単射な写像のなす関数グラフの形」の間に一対一の対応があることを使う. 具体的には,
na1個の1, a2個の2, , ak個のk, に分割されたとき,
この分割に対して
a1個の長さ1の有向サイクル, a2個の長さ2の有向サイクル, , ak個の長さkの有向サイクル, で構成された関数グラフを対応させる. このとき, 関数グラフは一意に定まらないが, 関数グラフの形は一意に定まる.

関数グラフの「形が等しい」の言い換え

関数グラフは, 頂点a,bf(a)=bという関係があるときaからbに有向辺をつなげてできたものだった. つまり, 写像f,gの関数グラフが「形が等しい」ということは
ある全単射な写像hが存在しf(a)=bg(h(a))=h(b)となる, と言い換えられる.
これを変形するとg(h(a))=h(f(a)), つまりg=hfh1となる. これは対称群の共役作用を考えたときfの軌道とgの軌道が一致するということである.

「頂点を区別する場合の数」と「区別しない場合の数」の関係

例えばある「頂点を区別していない」頂点数nのグラフGがあったとして, 各頂点に1からnを対応させようと思ったとき, その「対応の数」はn!である. ただし, このとき対称性の分で割る必要が出てくる(例えばサイクルなら2n(n1,2)で割る必要がある(数珠順列)). そしてこの「対称性の分」は, 頂点の置換であって, 頂点を「その置換で入れ替えてもグラフの形が変わらない」ような置換の数である. そのような置換全体の集合をAut(G)と表せば, 「対応の数」はn!|Aut(G)|と表せる. ちなみにAut(G)は群になり, 自己同型群と呼ばれる.

関数グラフの基本的な性質

定義:関数グラフ

この記事では, 関数グラフを集合Sと写像f:SSの組(S,f)であるとする.

関数グラフの同型

「議論の要点」の節で言っていたように, 関数グラフの形が等しい, という同値関係は次のように定義できる.
(S,f)(S,f)ある全単射な写像g:SSが存在しgfg1=f
このときgS(あるいは(S,f))からS(あるいは(S,f))へのグラフ同型と言うことにする.

有限集合Sの要素数を|S|で表し, 関数グラフの頂点数|(S,f)||S|と定義する.
頂点数が有限な関数グラフ全体の集合をGとし, その元を有限関数グラフと呼ぶ. G=G/とする.
Gの元を非標識関数グラフと言うことにする.
aGについて, aaGにおける同値類を表す.

グラフの和, 非負整数倍

(S,f),(S,f)Gについて, (S,f)+(S,f):=(S+S,g)
ただしS+SSSの非交和を表し(つまりSSの時も, S+SにおいてはSの元とSの元は区別する), 写像g:S+SS+S
g(x)={f(x)(xS)f(x)(xS)
という写像である.
またgGについてng=k=1ngとする. ただしn=0のときは, 0gを空集合から空集合への写像のなす関数グラフとする.

この和はGで考えてもwell-definedである. また交換法則や結合法則が成り立つ.

サイクル

Xn0以上n未満の整数の集合とする. このとき長さnのサイクルをcycn:=(Xn,f)とする.
ただしf:XnXnf(k)=(k+1)modnという写像である.

よく知られている事実として以下の補題がある.

全単射な写像のなす有限関数グラフはサイクルの和で表される

a=(S,f)Gで, fが全単射な写像であるとき
a=k=1akcyckとなるakZ0が存在する. ただし十分大きな整数Mが存在しi>Mai=0

自己同型群

グラフの自己同型群

関数グラフGについて, GからGへのグラフ同型全体の集合は写像の合成を積として群をなす.
これをGの自己同型群と呼び, Aut(G)と書く.
特にGGのとき, Aut(G)Gの, |G|次の対称群の共役作用の安定化群である.
また, gGについて, Aut(g)を, G=gとなるようなGを取ってきてAut(g)=Aut(G)と定義すると, これは同型の分を除いて一意的に定まる.

安定化群の性質と, グラフ同型の定義を考えれば次の補題が成り立つ.

自己同型群と同値類

頂点数nの任意の非標識関数グラフGと, |S|=|G|となるような集合Sについて, 写像f:SS(S,f)=Gとなるようなものの個数はn!|Aut(G)|
「議論の要点」の節で言っていたように, Gの各頂点に1,,nを書き込めばいいのでn!通り, ただし同型(=対称性)の分で割る必要があるといった感覚の式である.

上の補題のGを, 頂点数nの写像のなす関数グラフ全体とすれば次の定理が成り立つ.

自己同型群の位数の逆数和

gG,|g|=nn!|Aut(g)|=nn
である. |Aut(g)|1より, 頂点数nの関数グラフの数がnnn!以上であることがわかる.
ほとんどのグラフは対称性がないので, この評価はnが大きいときには有効である(多分).
またGGを全単射な写像のなす非標識関数グラフの集合とすると
gG,|g|=n1|Aut(g)|=1
ちなみに, ほとんど同じ手順で関数グラフだけでなく単純グラフや木についても同様の等式を導くことが可能.

「議論の要点」の節で言っていたように, 次のような写像Fを考える.
F:Gg=k=1akcycka:k=1i=1akk
ただし十分大きな整数Mが存在しi>Mai=0, またak=0のときi=1akk=0とする.
このとき, Gの要素のうち頂点数がnであるものと, nの分割は一対一に対応する.
よってあとは|Aut(g)|=S(F(g))を示せばよい.
fAut(g)について, fによってakcyckakcyckに移る. ak個あるサイクルをどのサイクルに移すかで(ak)!通り. ak個のサイクルそれぞれについて, そのまま移動先のサイクルへ移すか, 1だけずらして移すか, , k1だけずらして移すかのk通りあるのでkak通り.
これをすべてのkについて考えるので,
|Aut(g)|=k=1ak!kak
上記の式を写像Fで整数の分割に対応させると, 右辺はS(F(g))である. よって示された.
ちなみに, 明らかにAut(g)|g|次の対称群の部分群なのでn!=(1a1+2a2+)!は右辺で割り切れます.

分割に対するスコアの逆数の総和は1

自然数nの分割a:a1++ak=n(aiai+1)について, スコアS(a)を以下のように定義する.
S(a)=i=1iC(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)とすると
aP(n)1S(a)=1

投稿日:2023122
更新日:202478
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

抹茶屋
抹茶屋
27
1998
数弱 抹茶より麦茶がすき

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. まえがき
  2. 内容
  3. 概要
  4. 議論の要点
  5. 整数の分割と関数グラフの対応
  6. 関数グラフの「形が等しい」の言い換え
  7. 「頂点を区別する場合の数」と「区別しない場合の数」の関係
  8. 関数グラフの基本的な性質
  9. 定義:関数グラフ
  10. 自己同型群