|
|
| |
|
| |
| |
| 波利亚定理 |
|
[ 2008-9-5 20:19:00 | By: wantnon ] |
一，引理：
设集合A被划分为若干等价类，用C(a)表示包含元素a的等价类。
引理1：类数为：
$sum_{ainA}1/{|C(a)|}$.
此式正确性显然，是求类数的一般方法。
如果各等价类的阶相同，则式子简化为$|A|/|C(a)|$.
如果A的上述分类是群G导致的，则C(a)称为a在G下的迹，因为C(a)是a在G下的像集。
引理2：设G是A上的群，如果G中存在a->b，也存在a->c，则两种变换的个数一样多。
证：由于G中存在a->b的变换，也存在a->c的变换，故由群的除法封闭性知G中存在${a->c}/{a->b}=b->c$的变换，也存在${a->b}/{a->c}=c->b$的变换。
设f1为一b->c变换，f2为一c->b变换。
任取一a->b变换f,都对应着一个a->c变换f*f1,所以a->b变换数不多于a->c变换数。
同理任取一a->c变换f,都对应着一个a->b变换f*f2,所以a->c变换数不多于a->b变换数。
所以a->b变换数等于a->c变换数。
推论：|G|=|C(a)||St(a)|。
(其中St(a)为a的不动变换集）
证：设C(a)={a,a2,a3,...,am},则m=|C(a)|.
由于a经G作用只能得到a,a2,a3,...am，所以可将G中变换f作如下分类：
F1={f|a->a}=St(a)
F2={f|a->a2}
F3={f|a->a3}
...
Fm={f|a->am}
由引理2知|F1|=|F2|=...=|Fm|(=|St(a)|)
又|F1|+|F2|+...+|Fm|=|G|
所以|G|=|St(a)|m=|St(a)||C(a)|.
引理3：设G是A上的群，则$sum_{ainA}|St(a)|=sum_{finG}|Inv(f)|$.
(其中Inv(f)为f的不动点集)
证：
如图：上行是元素，下行是变换，如果元素ai是变换fj的不动点（或者说变换fj是元素ai的不动变换），则两者连一条线，于是得到一个二部图。易见$sum_{ainA}|St(a)|$与$sum_{finG}|Inv(f)|$均计数此图的边数，所以相等。
二，伯恩赛德引理：
设G是A上的群，则A上由G决定的等价类个数为：
$1/{|G|}sum_{f\inG}|Inv(f)|$
证：等价类个数
=$sum_{ainA}1/{|C(a)|}$...(引理1)
=$1/{|G|}sum_{ainA}|St(a)|$...(引理2推论)
=$1/{|G|}sum_{finG}|Inv(f)|$...(引理3)
注：可见，等价类个数即G中变换的平均不动点数。
三，物件集上的群在着色集上的衍生群：
设G是集合V上的群，C(V,R)是集合V上的R着色集，则当G使V中元素发生置换时，C(V,R)中元素会随之发生置换，就像是其上有一个群G*在发生作用一样，G*可以通过G和V计算出来,称为V上的群G在C(V,R)上的衍生群。
注：常有|G*|=|G|.
四，群下的等价着色：
如果C(V,R)中两个着色c1,c2可以通过G*互化，则称为是等价的。
五，计数式波利亚定理：
下面求顶点集V在群G下的不同R(|R|=m)着色数量。
即求G*下C(V,R)的等价类数，据伯恩赛德引理为：
$1/{|G★|}sum_{f★\inG★}|Inv(f★)|$...(1)
考虑f*的不动点个数－－即当f引起顶点置换时C(V,R)中有多少个着色不发生变化。
显然，不发生变化的是那些对f的各轮换区用了相同颜色的方案，若用cyc(f)表示f的轮换区个数，则f*下不发生变化的着色数为$m^{cyc(f)}$.即
|Inv(f*)|=$m^{cyc(f)}$
再结合|G*|=|G|,(1)式变为：
$1/{|G|}sum_{f\inG}m^{cyc(f)}$
注：轮换区个数可以通过轮换分解求得。如：
$f=((1,2,3,4,5,6,7,8),(5,4,8,6,7,2,1,3))=(157)(246)(38)$
所以cyc(f)=3.
算法：（待）
六，目录式波利亚定理：
着色的颜色积：着色中分配给各物件颜色之积，着色c的颜色积记为W(c)。
由于等价着色只是V作了一个置换并不改变用色的种类和数量，所以等价着色的颜色积相同(但非等价着色的颜色积未必不同)，因此我们可以说“等价类的颜色积”，即等价类中任一着色的颜色积。
着色目录：各等价类的颜色积之和，记作I。
因I是V,G,R的函数，可记作I(V,G,R)，即V在G下的R着色目录。
下面计算着色目录I：
引理1*：$sum_{cinC(V,R)}W(c)|St(c)|=sum_{f★inG★}sum_{cinInv(f★)}W(c)$.
证：
(其中Wi是指W(ci))
如
图：对有不动关系的元素与变换连线，并把元素的权赋在边上。用两种方法计算边上的权和，一种是以元素为分类计算，
为$sum_{cinC(V,R)}W(c)|St(c)|$；一种是以变换为分类计算，
为$sum_{f★inG★}sum_{cinInv(f★)}W(c)$。故二者相等。
引理2*：对任意f*，设f中长度为j的轮换有bj个(j=1,2,3,...)，则$sum_{cinInv(f★)}W(c)=prod_{j=1}^{\infty}(sum_{rinR}r^j)^{bj}$.
证：
前面说过f*下不动的c是对f的各轮换区用了相同的颜色。
因此W(c)中各r的指数恰是f中各轮换的长度。
设f的轮换分解为f=$D1*D2*D3*...$
即W(c)具有形式$□^|D1|*□^|D2|*□^|D3|...$ (#)
其中每个□填R中一种颜色。
将所有这种形式的积求和得：
$(r_1^|D1|+r_2^|D1|+...+r_m^|D1|)
(r_1^|D2|+r_2^|D2|+...+r_m^|D2|)
(r_1^|D3|+r_2^|D3|+...+r_m^|D3|)....$(可以乘出来看一下是否各项均为(#)形式)
相同因式写成幂：
=$(r_1+r_2+...+r_m)^{b1}(r_1^2+r_2^2+...+r_m^2)^{b2}(r_1^3+r_2^3+...+r_m^3)^{b3}....$
=$prod_{j=1}^{\infty}(sum_{rinR}r^j)^{bj}$
母函数式波利亚定理：I=$1/{|G|}sum_{finG}prod_{j=1}^{\infty}(sum_{rinR}r^j)^{bj}$.
证：I
=$sum_{cinC(V,R)}{W(c)}/|C(c)|$...(引理1)
=$1/|G★|sum_{cinC(V,R)}W(c)|St(c)|$...(引理2)
=$1/|G★|sum_{f★inG★}sum_{cinInv(f★)}W(c)$...(引理1*)
=$1/|G★|sum_{f★inG★}prod_{j=1}^{\infty}(sum_{rinR}r^j)^{bj}$...(引理2*)
=$1/|G|sum_{finG}prod_{j=1}^{\infty}(sum_{rinR}r^j)^{bj}$
注：1，可见，波利亚定理优于伯恩赛德引理之处在于省去了求物件集G在着色集上衍生群G*的过程。
2，在母函数式波利亚定理中令所有的r都为1即得到计数式波利亚定理。
七，目录式波利亚定理的修饰：
令$P_G(x_1,x_2,...)=1/|G|sum_{finG}x_1^{b_1}x_2^{b_2}...$
($b_j$是f的轮换分解中长度为j的轮换个数)
则波利亚定理可改述为：
I=$P_G(sum_{rinR}r,sum_{rinR}r^2,...)$（注1）
也就是说，只需在圈指标中用$sum_{rinR}r^j$代替xj即得着色目录。
这样写法好处是将功能分离：
$P_G(x_1,x_2,...)$仅取决于G的结构，称为群G的圈指标。
而$sum_{rinR}r^j$只与颜色集R有关。
这就清晰地显示出着色目录只取决于G和R。而|R|显然易见，所以重点只在搞清G的结构。
注：1，注意到sum_{rinR}r为颜色目录，sum_{rinR}r^2为颜色平方目录，...。即定理可述为：着色目录等于圈指标中代入颜色诸次方的目录。
2，波利亚定理的思想是把无区别的物体看成有区别的，再通过同构群恢复其无区别性。
也就是说把“不区分”用“区分＋同构群”代替了，这样更便于从数学上进行精确描述。
八，母函数式波利亚定理：
1，目录，计数，母函数三者的转化：
在目录中令所有的字母均为1即得到计数。
母函数即计数按指标的分布，因此欲得母函数，只需对目录添加指标(即对每个字母乘上一个x的指标次方)并按指标合并同类项，此时x^k为指标和为k的模式目录，令所有字母均为1，则x^k的系数就变为指标和为k的模式数量，于是得到母函数。
2，母函数式波利亚定理：
依上转化方法，将I转化成着色模式数量按指标h分布的母函数I(x)。
I(x)
=$P_G(sum_{rinR}rx^{h(r)},sum_{rinR}r^2x^{2h(r)},...)|_{forallr=1}$
=$P_G(sum_{k}指标和为k的不同着色的目录x^k,sum_{k}指标和为k的不同着色的平方的目录x^2k,...)|_{forallr=1}$
[注意到当$forallr=1$时
$sum_{k}指标和为k的不同着色的目录x^k|_{forallr=1}=u(x)$.
$sum_{k}指标和为k的不同着色的平方的目录x^{2k}|_{forallr=1}=u(x^2)$
(其中u(x)为r按指标h分布的母函数).
所以：]
=$P_G(u(x),u(x^2),...)$
|
|
| | |
|
