USTC课程资源分享在线

Contributors

• 1. 计算(123)(234)(5)(14)(23),并指出它所在的共轭类。
• *2.求正四面体关于顶点集合{1, 2, 3, 4}的置换群
• *3.设D是n元集合,G是D上的置换群。对于D的子集A和B,如果存在$\sigma \in G$使得$B=\{\sigma (a)|a\in A\}$,则称A与B是G等价的.求G的等价类的个数。
• 4.对本题中顶点进行m着色，问有多少中着色方案？
• 5. 由0， 1， 6，8，9组成的n位数，如果把一个数调转过来读得到另一个数，则称这两个数是相等的。例如0168与8910， 0890和0680是相等的。问不相等的n位数由多少个？
• 6. 用三色珠子串成4珠项链，要求各种颜色的珠子至少有一个。问有多少种不同的项链？
• 7. 把4个球a,a,b,b放入3个不同的盒子里面，求分配方案数。若不允许空盒，问有多少种分配方案？
• 8.用4种颜色（红、黄、绿、蓝）对正四面体的顶点着色，求着色方案数。若要求m(m=0, 1, 2, 3, 4)个顶点为红色，求着色方案数。
• 9. 证明式(8.7.2)
• *10. 设$s=(1234)$, $t=(1243)$。试找出一个置换群$g\in S_4$,使得$s=g^{-1}tg$,从而证明s与t是$S_4$共轭的。
• 11. 写出$S_4$的所有$i$不动置换类
• 12. 在8.5节例6中，令$w(红色)=r,w(蓝色)=b$。
• 13.将2个红色球和2个蓝色球放在正六面体的顶点上，问有多少种不同的方案？
• 14. 将8个相同的骰子堆成一个正六面体，问有多少种不同的方案？
• 15. 用$Polya$计数定理求多重集合$M=\{\infty \cdot a_1,\infty \cdot a_2,\cdots ,\infty \cdot a_n\}$的r圆排列数。
• 16. 用6种颜色涂立方体的6个面，使得每面颜色均不相同的涂法有多少种？
• 17. 在6种颜色种选取一种或多种颜色涂立方体的面，涂法有多少种？若6种颜色中有一种是红色，则有多少种涂法使得立方体中恰好有3面是红色的？
• 18. 在一个有7匹马的旋转木马上用n种颜色着色，问有多少种可供选择的方案（旋转木马只能旋转不能翻转）？
• 19. 给一根8尺长的棍子着色，每尺着不同的颜色，共有m种颜色可供选择。仅有的变换是翻转$180^0$,因此置换群G只有两个元素。
• 20. 证明二维欧几里得空间的刚体旋转变换集合$T=\{T_{\alpha }\}$构成群，其中
• 21.证明:
• *补充题-Page207例7。求正方体的24个旋转也确定出6面构成的集合上的24个置换，它们的构成6次24阶置换群及型(仿照例4)

转载自liuzengh/combinatorial-mathematics

1. 计算(123)(234)(5)(14)(23),并指出它所在的共轭类。

(13)(24)(5), $S_5$ 中型为$1^1{2}^2$的置换共有$\frac{5!}{1!2!1^1{2}^2}=15$,

(12)(34)(5), (13)(24)(5), (14)(23)(5),
(12)(35)(4), (13)(25)(4), (15)(23)(4),
(12)(45)(3), (14)(25)(3), (15)(24)(3),
(13)(45)(2), (14)(35)(2), (15)(34)(2),
(23)(45)(1), (24)(35)(1), (25)(34)(1)

1->4->2->3
2->3->4
3->2->3->1
4->1->2

*2.求正四面体关于顶点集合{1, 2, 3, 4}的置换群

(i)不旋转，对应于恒等变换${\sigma }_I$，确定出$1^4$型的置换 1 个；
(ii)以顶点和相对面中心的连线为轴旋转，可旋转 120°,(1)(234)和 240°,(1)(243)，确定出$1^1{3}^1$ 型的置换 8 个；
(iii)以相对棱中点的连线为轴旋转，可旋转 180°，(12)(34), 确定出$2^2$ 型的置换 3 个。
综上所述，上述 12 个置换构成所求置换群。

*3.设D是n元集合,G是D上的置换群。对于D的子集A和B,如果存在$\sigma \in G$使得$B=\{\sigma (a)|a\in A\}$,则称A与B是G等价的.求G的等价类的个数。

令$R=\{0,1\}$,对于 D 的子集 A，定义映射$f_A:D\to R$, 其中 $f_A(x)=1,x\in A;f_A(x)=0,x\notin A$,则 A 与 B 是 G 等价的等同于$f_A(x)$与$f_B(x)$是 G 等价的, 问题转化为则问题转化为求在$F=f|f_A:D\to R上的等价类个数。由P\acute{o}lya计数定理得等价类的个数为：$$\frac{1}{|G|}{\sum }_{\sigma \in G,\sigma 的型是1^{b_1}{2}^{b_2}\cdots n^{b_n}}{2}^{b_1+b_2+\cdots +b_n}$$

4.对本题中顶点进行m着色，问有多少中着色方案？

$D = {1, 2, 3, 4, 5, 6, 7, 8, 9}, R = {c_1, c_2, \cdots, c_m}, F = {f | f: D\rightarrow R}$,绕中心点顺时针旋转0，90，180，270可以得到D上的置换群为:$G = {\sigma_I, (1357)(2468), (15)(26)(37)(48), (1753)(2864)}$其轮换指标为:$P_G(x_1, x_2, \cdots, x_9) = \frac{1}{4}(x_1^8 + 2x_2^4 + x_4^2)$于是等价类的个数为:$l = P_G(m, m, \cdots, m) = \frac{1}{4}(m^8 + 2m^4 + m^2)$

5. 由0， 1， 6，8，9组成的n位数，如果把一个数调转过来读得到另一个数，则称这两个数是相等的。例如0168与8910， 0890和0680是相等的。问不相等的n位数由多少个？

位置集$D = {1, 2, \cdots, n}$，元素集合$R={c_1, c_2, c_3, c_4, c_5}$,定义$F ={f|f:D\rightarrow R}$D上的的置换群$G = {\sigma_I, \tau}$,不相等的n位数的个数即为置换群G的等价类个数：$\tau = (1, n)(2, n-1)(3, n-2) \cdots$当n为偶数时，对应的轮换指标为：$\frac{1}{2}(x^5 + x_2^{\frac{n}{2}})$，等价类的个数为：$\frac{1}{2}(5^n + 5^{\frac{n}{2}})$当n为奇数时，中间数字必须为0,1或8。所以对应的轮换指标为：$\frac{1}{2}(x^5 + x_2^{\frac{n-1}{2}})$，等价类的个数为：$\frac{1}{2}(5^n + 5^{\frac{n-1}{2}})$

6. 用三色珠子串成4珠项链，要求各种颜色的珠子至少有一个。问有多少种不同的项链？

$D = {1, 2, 3, 4}, R={c_1, c_2, c_3}, F={f| f: D\rightarrow R}$,定义颜色的权为$w(c_1)= r, w(c_2)=g, w(c_3) = b$。D上的置换群为：$G = {\sigma_I, (1234), (13)(24), (1432), (24), (13), (12)(43), (14)(23)}$其轮换指标为:由$P_G(x_1, x_2, x_3, x_4) = \frac{1}{8}(x_1^4 + 2x_1^2x_2 + 3x_2^2 +2x_4)$令$x_1 = x_2 = x_3 = 3$，得到等价类的个数为：$l = P_G(3, 3, 3) = \frac{1}{8}(3^4 + 2\times3^2\times3 + 3\times 3^2 + 3) = 21$着色方案的模式表为:$$F的全部模式表=\frac{1}{8}((r+g+b{)}^4+2(r+g+b{)}^2(r^2+g^2+b^2)+3(r^2+g^2+b^2{)}^2+2(r^4+g^4+b^4))$$其中要求各种颜色的珠子至少有一个，就是上述展开式$r^2gb, rg^2b, rgb^2$项的系数之和：$3\times \frac{1}{8}(\frac{4!}{2!1!1!} + 2\cdot2) = 6$

7. 把4个球a,a,b,b放入3个不同的盒子里面，求分配方案数。若不允许空盒，问有多少种分配方案？

解法1：
$D={a_1, a_2, b_1,b_2}, R={盒1, 盒2， 盒3}， F= {f|f:D\rightarrow R}$,D上的置换群$G={\sigma_I, (a_1a_2), (b_1b_2), (a_1a_2)(b_1b2)}$,轮换指标$P_G(x_1, x_2, x_3, x_4)=\frac{1}{4}(x_1^4+2x_1^2x_2 + x_2^2)$容斥原理$$\frac{1}{4}(3^4+2\cdot 3^2\cdot 3+3^2)-\frac{1}{4}{C}_3^2(2^4+2\cdot 2^2\cdot 2+2^2)+\frac{1}{4}{C}_3^1(1^4+2\cdot 1^2\cdot 1+1^2)=36-27+3=12$$解法2：$(ab, a, b), (bb, a, a), (aa, b, b)$，分配方案数为：$A_3^3 + 2\cdot\frac{3!}{2!} =12$

8.用4种颜色（红、黄、绿、蓝）对正四面体的顶点着色，求着色方案数。若要求m(m=0, 1, 2, 3, 4)个顶点为红色，求着色方案数。

$D = {1, 2, 3, 4}, R={c_1, c_2, c_3, c_4}, w(c_1)= r, w(c_2)=y, w(c_3)=g, w(c_4)=b, F = {f| f:D\rightarrow R}$,D上的置换群G，$1^4$型的置换1一个，$1^13^1$型置换8个，$2^2$型置换3个。所以轮换指标为:$P_G(x_1, x_2, x_3, x_4) = \frac{1}{12}(x_1^4 + 8x_1x_3 + 3x_2^2)$令$x_1=x_2=x_3 =x_4 = 4$,得到等价类的个数为:$\frac{1}{12}(4^4 + 8\cdot4\cdot4+3\cdot4^2) = 368$F的全部模式表=\frac{1}{12}((r+y+g+b{)}^4+8(r+y+g+b)(r^3+y^3+g^3+b^3)+3(r^2+y^2+g^2+b^2{)}^2)$$令$ w(c_2)=y=1, w(c_3)=g=1, w(c_4)=b=1$,则:$$F的全部模式表=\frac{1}{12}((r+3{)}^4+8(r+3)(r^3+3)+3(r^2+3{)}^2)=12r^4+36r^3+72r^2+132r+180$$所以要求m(m=0,1,2,3,4)个顶点为红色，求着色方案数分别对于上述展开式子中$r^4, r^3, r^2， r^1, r^0$对应的系数180，132，72，36和12。

9. 证明式(8.7.2)

$F_i$是$D$的子集，考虑$\overset{\sim}G$是可重集时(但不影响计数)，$\overset{\sim}G$和G的势相同。由Burnside定理，式(8.7.2)成立。

*10. 设$s=(1234)$,$t=(1243)$。试找出一个置换群$g\in S_4$,使得$s=g^{-1}tg$,从而证明s与t是$S_4$共轭的。

(34), (124), (132), (1423)

from itertools import permutations
s = {1:2, 2:3, 3:4, 4:1}
t = {1:2, 2:4, 3:1, 4:3}
p = permutations([1, 2, 3, 4])
for p1 in p:
    g = { i:p1[i-1 ]for i in range(1, 5)}
    l1 = [t[g[i]] for i in range(1, 5)]
    l2 = [g[s[i]] for i in range(1, 5)]
    if l1 == l2:
        print(g)

{1: 1, 2: 2, 3: 4, 4: 3}
{1: 2, 2: 4, 3: 3, 4: 1}
{1: 3, 2: 1, 3: 2, 4: 4}
{1: 4, 2: 3, 3: 1, 4: 2}

11. 写出$S_4$的所有$i$不动置换类$Z_1 = {\sigma_I, (23), (24), (34), (234), (243)}Z_2 = {\sigma_I, (13), (14), (34), (134), (143)}Z_3 = {\sigma_I, (12), (14), (24), (124), (143)}Z_4 = {\sigma_I, (12), (13), (23), (123), (132)}$

12. 在8.5节例6中，令$w(红色)=r, w(蓝色)=b$。

(1)写出着色方案的模式表

$r^4 + r^3b + 2r^2b^2 + rb^3 + b^4$

(2)将正方形的四个顶点分别标记为1,2,3,4.则正方形的旋转群 $G= \sigma^0, \sigma^1, \sigma^2, \sigma^3$，其中$\sigma = (1234)$.令$w_1 = b^4, w_2 = r^2b^2$,对$w_1, w_2$分别求式(\mathrm{8.7.1})定义的$\overset{\sim}Gw_1 = b^4, F_1 = {f_{16}}$,所以$\overset{\sim}G = {\pi_{(1)}^{1}} = {\pi_{(2)}^{1}} = {\pi_{(3)}^{1}} = {\pi_{(4)}^{1}}, \pi_{(i)}^{1}(f_{16}) = f_{16}w_2 = r^2b^2, F_2 ={f_6, f_7, f_8, f_9, f_{10}, f_{11}}$，所以所以$\overset{\sim}G = {\pi_{(1)}^{2}, \pi_{(2)}^{2}, \pi_{(3)}^{2}, \pi_{(4)}^{2}} = {\sigma_I, (f_6f_7f_8f_9)(f_{10}f_{11}), (f_6f_8)(f_7f_9), (f_6f_9f_8f_7)(f_{10}f_{11})}$

13.将2个红色球和2个蓝色球放在正六面体的顶点上，问有多少种不同的方案？

没有放置球的顶点的颜色统一设置为绿色。所以该问题等价于$D={1, 2, \cdots, 8}, R={c_1, c_2, c_3}, w(c_1)=r, w(c_2)=b, w(c_3)=g, F={f|f:D\rightarrow R}$,D上置换群G型可以表示为$1\times 1^8, 8\times 1^23^2, 6\times 4^2, 9\times 2^4$。所以轮换指标为:$P_G(x_1, x_2, \cdots, x_8) = \frac{1}{24}(x_1^8 + 8x_1^2x_3^2 + 6x_4^2 + 9x_2^4)$F的模式表为:$$\frac{1}{24}((r+g+b{)}^8+8(r+g+b{)}^2(r^3+g^3+b^3{)}^2+6(r^4+g^4+b^4{)}^2+9(r^2+g^2+b^2{)}^4)$$其中展开式中$r^2g^4b^2$项的系数就是将2个红色球和2个蓝色球放在正六面体的顶点上的方案数：$$\frac{1}{24}(\frac{8!}{2!2!4!}+9C_4^2{C}_2^1)=22$$

14. 将8个相同的骰子堆成一个正六面体，问有多少种不同的方案？

一个骰子可以露出3个共顶点的面，相当于8种颜色的球放置在正方体的8个顶点上。所以该问题等价于$D={1, 2, \cdots, 8}, R={c_1, c_2, \cdots, c_8}, w(c_1)=r, w(c_2)=b, w(c_3)=g, F={f|f:D\rightarrow R}$,D上置换群G的型可以表示为$1\times 1^8, 8\times 1^23^2, 6\times 4^2, 9\times 2^4$。所以轮换指标为:$P_G(x_1, x_2, \cdots, x_8) = \frac{1}{24}(x_1^8 + 8x_1^2x_3^2 + 6x_4^2 + 9x_2^4)$令$x_1=x_2=\cdots=x_8=8$，展开式的系数之和即为不同的方案数：$\frac{1}{24}(8^8 + 8^5 + 6\cdot 8^2 + 9 \cdot 8^4)$

15. 用$Polya$计数定理求多重集合$M={\infty\cdot a_1, \infty \cdot a_2, \cdots, \infty \cdot a_n}$的r圆排列数。$D={1, 2, \cdots, r}, R={a_1, a_2, \cdots, a_n}, F={f|f:D\rightarrow R}$,D上的对称群$G={\sigma_I, \sigma, \sigma^2, \cdots, \sigma^{r-1}}$,$\sigma$表示绕圆心旋转$\frac{360}{r}$度的置换。分类讨论$\sigma^i(1\le i \le r-1)$的型：1.若i与r互质，型为$r^1$,与r互质的i的个数有$\phi(r)$，其中$\phi(\cdot)$表示欧拉函数；2.若i与r有最大公因子$d(d\ge2)$,则型为$(\frac{r}{d})^d$,对于给定的d,与r互质的i的个数有$\phi(\frac{r}{d})$由P\acute{o}lya计数定理得多重集合的r圆排列数为:所以轮换指标为：$$P_G(x_1,x_2,\cdots ,x_r)=\frac{1}{r}(x_1^r+\varphi (r)x_r+{\sum }_{d|r,2\le d\le r-1}\varphi (\frac{r}{d})x_{r/d}^d)$$令$x_1 = x_2 = \cdots = x_r = n$则等价类的个数为:$$\frac{1}{r}(n^r+\varphi (r)n+{\sum }_{d|r,2\le d\le r-1}\varphi (\frac{r}{d})n^d))=\frac{1}{r}({\sum }_{d|r}\varphi (\frac{r}{d})n^d)$$教材Page77关于欧拉函数的定义：欧拉函数$\phi(n)$表示小于n且与n互素的整数的个数。$\phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \cdots (1-\frac{1}{p_q})$特例：$\phi(1) = 1$

16. 用6种颜色涂立方体的6个面，使得每面颜色均不相同的涂法有多少种？

$D={1, 2, 3, 4, 5, 6}, R={c_1,c_2, c_3, c_4, c_5, c_6}, F = {f|f:D\rightarrow R}$D上的置换群:1.不旋转$\sigma_I$,$1^6$型置换1个2.绕相对面中心轴旋转$180^0$,$1^22^2$型的置换3个对应的轮换指标为：$P_G(x_1, x_2, \cdots, x_6) = \frac{1}{4}(x_1^6 + 3x_1^2x_2^2)$F的模式表为：$$\frac{1}{4}((w_1+w_2+\cdots +w_6{)}^6+3(w_1+w_2+\cdots +w_6{)}^2(w_1^2+w_2^2+\cdots +w_6^2{)}^2)$$展开式中$w_1w_2\cdots w_6$的系数就是每面颜色均不相同的涂法数:$\frac{1}{4}(\frac{6!}{1!1!1!1!1!1!}) = 180$

17. 在6种颜色种选取一种或多种颜色涂立方体的面，涂法有多少种？若6种颜色中有一种是红色，则有多少种涂法使得立方体中恰好有3面是红色的？

$D={1, 2, 3, 4, 5, 6}, R={c_1,c_2, c_3, c_4, c_5, c_6}, F = {f|f:D\rightarrow R}$D上的置换群:1.不旋转$\sigma_I$,$1^6$型置换1个2.绕相对面中心轴旋转$180^0$,$1^22^2$型的置换3个对应的轮换指标为：$P_G(x_1, x_2, \cdots, x_6) = \frac{1}{4}(x_1^6 + 3x_1^2x_2^2)$若选择m种颜色，令$x_1 = x_2= \cdots = x_6 = m$,所求的涂法为：$C_6^m\frac{1}{4}(m^6+3m^2m^2) = \frac{1}{4}C_6^m(m^6+3m^4)$立方体中恰好有3面是红色的，只能选择2，3，4种颜色来涂。$5: w_1^3w_2^3, 20:w_1^3w_2^2w_3, 10:w_1^3w_2w_3w_4$F的模式表为：$$\frac{1}{4}((w_1+w_2+\cdots +w_6{)}^6+3(w_1+w_2+\cdots +w_6{)}^2(w_1^2+w_2^2+\cdots +w_6^2{)}^2)$5\cdot \frac{1}{4}(\frac{6!}{3!3!}+3\cdot \frac{2!}{1!1!} \frac{2!}{1!1!}) + 20 \cdot \frac{1}{4}(\frac{6!}{3!2!1!} + 3\cdot \frac{2!}{1!1!} \frac{2!}{1!1!}) + 10\cdot \frac{1}{4}(\frac{6!}{3!1!1!1!}) = 40+360+300 = 700$

18. 在一个有7匹马的旋转木马上用n种颜色着色，问有多少种可供选择的方案（旋转木马只能旋转不能翻转）？

参见习题15题。

$D={1, 2, \cdots, 7}, R={c_1, c_2, \cdots, c_n}, F={f|f:D\rightarrow R}$,D上的对称群$G={\sigma_I, \sigma, \sigma^2, \cdots, \sigma^{r-1}}$,$\sigma$表示绕圆心旋转$\frac{360}{r}$度的置换。$\sigma^i(1\le i \le 6)$的型：由于7是质数，所以i与r互质，型为$7^1$,与r互质的i的个数有$\phi(7) = 6$，其中$\phi(\cdot)$表示欧拉函数。所以,轮换指标为$\frac{1}{7}(x_1^7+6x_7)$令$x_1 = x_2 =\cdots = x_7 = n$,可供选择的方案等于等价类的个数：$\frac{1}{7}(6n + n^7)$

19. 给一根8尺长的棍子着色，每尺着不同的颜色，共有m种颜色可供选择。仅有的变换是翻转$180^0$,因此置换群G只有两个元素。

(1) 标出棍子的每一尺，G是什么？

$G=\sigma_I, (18)(27)(36)(45)$

(2) 给棍子着色，有多少种方案？

轮换指标$P_G(x_1, x_2, \cdots, x_8) = \frac{1}{2}(x_1^8 + x_2^4)$令$x_1 = x_2 = \cdots = x_8 = m$,着色方案数就是等价类的个数：$\frac{1}{2}(m^8 + m^4)$

(3)给三尺着蓝色，三尺着红色，两尺着绿色，有多少种着色方案？

$w_1(c_1) = r, w_2(c_2) = g, w_3(c_3) = b$,F的模式表为:$$\frac{1}{2}((r+g+b{)}^8+(r^2+g^2+b^2{)}^4)$$展开式中$r^3g^2b^3$的系数就是给三尺着蓝色，三尺着红色，两尺着绿色的着色方案：$\frac{1}{2}\frac{8!}{3!2!3!} = 280$

(4) 给三尺着蓝色，两尺着绿色，两尺着黄色，一尺着红色，有多少种着色方案？

$w_1(c_1) = r, w_2(c_2) = g, w_3(c_3) = b, w(c_4) = y$,F的模式表为:$$\frac{1}{2}((r+g+b+y{)}^8+(r^2+g^2+b^2+y^2{)}^4)$$展开式中$rg^2b^3y^2$的系数就是给三尺着蓝色，两尺着绿色，两尺着黄色，一尺着红色的着色方案：$\frac{1}{2}\frac{8!}{3!2!2!1！} = 840$

20. 证明二维欧几里得空间的刚体旋转变换集合$T = {T_{\alpha}}$构成群，其中$T_\alpha :$\left[\begin{array}{c}{x}_1\\ y_1\end{array}\right]$$=$$\left[\begin{array}{cc}cos\alpha & sin\alpha \\ -sin\alpha & cos\alpha \end{array}\right]$$\left[\begin{array}{c}x\\ y\end{array}\right]$$群的基本构成是由非空集合及其上二元关系。该题的非空集合为$T={T_\alpha}$, 但是没有指明相应的二元关系。

21.证明:

(1)$A = {1, -1}$在乘法运算下是一个群;$1\times -1 = -1, 1\times 1 = 1, -1\times -1 = 1, -1\times 1 = 1$封闭性:$\forall x, y \in A$,$x\times y \in A$结合律:乘法满足结合律单位元:$1, \forall x \in A, x \times 1 = x$逆元：$\frac{1}{x}, \forall x \in A, \exists \frac{1}{x}\in A, x\times \frac{1}{x} = 1$

(2)整数集Z在加法运算下是一个群；

封闭性: $\forall x, y \in Z$,$x + y \in A$结合律:加法满足结合律单位元:$0, \forall x \in A, x + 0 = x$逆元：$-x, \forall x \in A, \exists -x \in A, x + (-x) = 0$

(3) 集合$G = {0, 1, \cdots, n-1}$对于modn在加法运算下是一个群封闭性:$\forall x, y \in A$,$(x + y) , mod , n \in A$结合律:加法满足结合律单位元:$0, \forall x \in A, (x + 0), mod , n = x$逆元：0的逆元为0，其他元素的逆元为$n-x$,$\forall x \in A-{0}, \exists n-x \in A, (x + n-x), mod , n = 0$

*补充题-Page207例7。求正方体的24个旋转也确定出6面构成的集合上的24个置换，它们的构成6次24阶置换群及型(仿照例4)

参见8.7节例2