【组合数学】Pólya 计数理论

2023-12-22 15:57:47

目录

1. 引言

Pólya 计数理论是数学中的一个分支，主要研究的是对称性在组合计数问题中的应用。该理论以匈牙利数学家乔治·波利亚（George Pólya）的名字命名，他在20世纪初提出了许多关于对称性和组合计数的重要思想。

该理论主要用于解决组合计数问题，即计算对象的数量，但通常存在对称性质。例如计算不同颜色的珠子串成的项链有多少种不同的排列方式，考虑到项链旋转对称性，这个问题就可以用 Pólya 计数理论来解决。

Pólya 计数理论涉及的基础知识主要包括:

  1. 对称群：学习群论中的对称群及其性质，对于理解对称性在计数中的作用至关重要。
  2. 循环指标定理（Cycle Index Theorem）：这是 Pólya 计数理论的核心定理，用于计算具有对称性的结构的计数问题。
  3. 组合学：熟悉组合学的基础概念和技巧，如排列、组合、置换等。

Pólya定理通常更专注于处理置换群的计数问题，强调对称性对对象计数的影响。
Burnside引理则更侧重于计算群作用下不同轨道（等价类）的数量，它提供了一种更通用的方法来计算群作用的结果。

2. 置换群

“群” 的定义：
给定集合 G 和 G 上的二元运算 “?” ，如果满足以下 4 个条件，则称代数结构 ( G , ? ) ( G, ?) (G,?)为群：

  • 封闭性：“?” 运算在 G 上是封闭的，即对任意 , a , b ∈ G a,b\in G a,b∈G，都有 a ? b ∈ G a\cdot b\in G a?b∈G
  • 结合律：“?” 运算满足结合律，即对任意 , a , b , c ∈ G a,b,c \in G a,b,c∈G ，都有 a ? ( b ? c ) = ( a ? b ) ? c a\cdot (b\cdot c ) = (a\cdot b)\cdot c a?(b?c)=(a?b)?c
  • 存在单位元：存在 e ∈ G e\in G e∈G ，对任意 a ∈ G a\in G a∈G ，满足 e ? a = a ? e = a e\cdot a=a\cdot e=a e?a=a?e=a 称为 G 的单位元
  • 存在逆元：对任意 a ∈ G a\in G a∈G ，存在 a ? 1 ∈ G a^{-1}\in G a?1∈G ，满足 a ? 1 ? a = a ? a ? 1 = e a^{-1}\cdot a=a\cdot a^{-1}=e a?1?a=a?a?1=e 称为 a 的逆元

置换群 （Permutation Group）
是指由一组置换（即一种对象到另一种对象的一一映射）组成的群。这个群包含了所有可能的置换，并且满足群的性质，比如封闭性、结合律、单位元和逆元。

对称群（Symmetric Group）
是一个特定类型的置换群，表示某个集合上所有可能的置换组成的群。具体而言，对称群是由集合上的所有元素的全排列所构成的置换群。如果集合有n个元素，那么其对称群的阶（群的大小）就是 n! ，记作 S? 。

对称群是置换群的一种特殊情况，它描述了一个特定集合上的所有置换的全集。同时，置换群可以表示更一般性的情况，不仅仅局限于描述集合上的置换。

在这里插入图片描述
置换可以表示为不相交的轮换之积，比如 σ = ( 1 2 3 4 5 6 7 8 3 2 1 6 5 7 8 4 ) = ( 13 ) ( 2 ) ( 5 ) ( 4678 ) \sigma =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 3 & 2 & 1 & 6 & 5 & 7 & 8 & 4 \end{pmatrix}=(13)(2)(5)(4678) σ=(13?22?31?46?55?67?78?84?)=(13)(2)(5)(4678)σ 写成 2 个长为 1、1 个长为 2、1 个长为 4 的轮换之积，称它为 1 2 2 1 4 1 1^22^14^1 122141 型的置换
若σ 有 b i b_i bi? 个长为 i ( 1 ≤ i ≤ n ) i(1≤ i≤ n) i(1≤i≤n) 的不相交轮换因子，则称 σ 是 1 b 1 2 b 2 . . . n b n 1^{b_1}2^{b_2}...n^{b_n} 1b1?2b2?...nbn? 型的置换。对于 b i = 0 b_i =0 bi?=0 的那些因子(即不存在长为 i 的轮换因子)，则不必写出

习题1、 求正四面体关于顶点集合{1，2，3，4}的置换群

在这里插入图片描述

3. Burnside 引理

共轭类

定义 3.1：设 D,R 是有限集合，从 D 到 R 的映射全体记为 F = { f ∣ f : D → R } F=\{f|f:D\rightarrow R\} F={f∣f:D→R}
G 是 D 上的一个置换群，对 任 意 f 1 , f 2 ∈ F f_1,f_2\in F f1?,f2?∈F ， 若 存 在 σ ∈ G ， 使 得 对 任 意 d ∈ D ， 等 式 f 1 ( d ) = f 2 ( σ ( d ) ) f_1(d)=f_2(\sigma (d)) f1?(d)=f2?(σ(d)) 均成立，则称 f 1 f_1 f1? 和 f 2 f_2 f2? 是 G 等价的。

G 等价关系是 F 上的等价关系，满足三个条件：自反、对称、传递。

定义 3.2：对任意 s,t ∈ G ，若存在 g ∈ G ，使得 s = g ? 1 t g s=g^{-1}tg s=g?1tg ，则称 s 与 t 是G 共轭的

引理 3.1：两个置换 s,t ∈ Sn 关于 Sn 是共轭的，当且仅当它们是同型的

引理 3.2：Sn 中属于 1 b 1 2 b 2 . . . n b n 1^{b_1}2^{b_2}...n^{b_n} 1b1?2b2?...nbn? 型的元素个数为 n ! b 1 ! b 2 ! . . . b n ! ? 1 b 1 2 b 2 . . . n b n \cfrac{n!}{b_1!b_2!...b_n!\cdot1^{b_1}2^{b_2}...n^{b_n}} b1?!b2?!...bn?!?1b1?2b2?...nbn?n!?
其中 b 1 + 2 b 2 + . . . + n b n = n b_1+2b_2+...+nb_n=n b1?+2b2?+...+nbn?=n 。
分母中：

  • b 1 ! b 2 ! . . . b n ! b_1!b_2!...b_n! b1?!b2?!...bn?! 表示互不相交的轮换乘积可以交换： b k b_k bk? 个长为 k 的轮换因子在全排列中是不同的全排列
  • 1 b 1 2 b 2 . . . n b n 1^{b_1}2^{b_2}...n^{b_n} 1b1?2b2?...nbn? 表示轮换因子的书写方式：长为 k 的轮换可以写成 k 种形式，而长为k的轮换因子有 b k b_k bk?个

例如，S3 中有 3 个共轭类，分别是 1 3 1^3 13 型 1 个， 3 1 3^1 31 型 2 个， 1 1 2 1 1^12^1 1121 型 3 个。

k 不动置换类

定义 3.3：设 G 是 {1,2, …,n} 上的置换群，令 Z k = { σ ∣ σ ∈ G , σ ( k ) = k } Z_k=\{\sigma|\sigma\in G,\sigma (k)=k\} Zk?={σ∣σ∈G,σ(k)=k} 是 G 中使元素 k 保持不动的置换全体

例如 G = { σ I , ( 1 , 2 ) , ( 3 , 4 ) , ( 1 , 2 ) ( 3 , 4 ) } G=\{\sigma_I,(1,2),(3,4),(1,2)(3,4)\} G={σI?,(1,2),(3,4),(1,2)(3,4)}，则 Z 1 = Z 2 = { σ I , ( 3 , 4 ) } Z_1=Z_2=\{\sigma_I,(3,4)\} Z1?=Z2?={σI?,(3,4)}； Z 3 = Z 4 = { σ I , ( 1 , 2 ) } Z_3=Z_4=\{\sigma_I,(1,2)\} Z3?=Z4?={σI?,(1,2)}。 即 1 不动置换类和 2 不动置换类为(34)，3 不动置换类和 4 不动置换类为(12)。

Burnside 引理

引理 3.3：设 G = { a 1 , a 2 , . . . , a n } G = \{a_1,a_2, ...,a_n\} G={a1?,a2?,...,an?} 是 D={1,2, …, n} 上的置换群，则 G 诱导出来的等价类个数为 l = 1 ∣ G ∣ ∑ i = 1 g c ( a i ) l=\cfrac{1}{|G|}\sum_{i=1}^gc(a_i) l=∣G∣1?i=1∑g?c(ai?)其中， c ( a i ) c(a_i) c(ai?) 表示在置换 a i a_i ai? 作用下保持不变的元素个数

习题2、 G = { σ I , ( 14 ) ( 23 ) , ( 12 ) ( 34 ) ( 56 ) , ( 13 ) ( 24 ) ( 56 ) } G=\{\sigma_I,(14)(23),(12)(34)(56),(13)(24)(56)\} G={σI?,(14)(23),(12)(34)(56),(13)(24)(56)} 是D = {1，2，3，4，5，6} 上的置换群。求G在D上的等价类个数

在这里插入图片描述

习题3、一个正方形均分成 4 个格子，用两种颜色对 4 个格子着色，能得到多少种方案？经过旋转吻合的两种方案属于同一种方案

解：因为每格有两种颜色可供选择，故有如图所示的 16 种可能方案
在这里插入图片描述每个图都绕过中心的轴逆时针方向旋转 90°，180°，270°时，得到 16 种图像的一种排列，可以看作是原 16 种图像的一种置换。

  1. 不动置换： p 1 = ( c 1 ) ( c 2 ) ( c 3 ) ( c 4 ) ( c 5 ) ( c 6 ) ( c 7 ) ( c 8 ) ( c 9 ) ( c 10 ) ( c 11 ) ( c 12 ) ( c 13 ) ( c 14 ) ( c 15 ) ( c 16 ) p_1=(c_1)(c_2)(c_3)(c_4)(c_5)(c_6)(c_7)(c_8)(c_9)(c_{10})(c_{11})(c_{12})(c_{13})(c_{14})(c_{15})(c_{16}) p1?=(c1?)(c2?)(c3?)(c4?)(c5?)(c6?)(c7?)(c8?)(c9?)(c10?)(c11?)(c12?)(c13?)(c14?)(c15?)(c16?)
  2. 旋转 90°： p 2 = ( c 1 ) ( c 2 ) ( c 3 c 4 c 5 c 6 ) ( c 7 c 8 c 9 c 10 ) ( c 11 c 12 ) ( c 13 c 14 c 15 c 16 ) p_2=(c_1)(c_2)(c_3 c_4 c_5 c_6)(c_7 c_8 c_9 c_{10})(c_{11} c_{12})(c_{13} c_{14} c_{15} c_{16}) p2?=(c1?)(c2?)(c3?c4?c5?c6?)(c7?c8?c9?c10?)(c11?c12?)(c13?c14?c15?c16?)
  3. 旋转 180°： p 3 = ( c 1 ) ( c 2 ) ( c 3 c 5 ) ( c 4 c 6 ) ( c 7 c 9 ) ( c 8 c 10 ) ( c 11 ) ( c 12 ) ( c 13 c 15 ) ( c 14 c 16 ) p_3=(c_1)(c_2)(c_3 c_5)(c_4 c_6)(c_7 c_9)(c_8 c_{10})(c_{11})(c_{12})(c_{13} c_{15})(c_{14} c_{16}) p3?=(c1?)(c2?)(c3?c5?)(c4?c6?)(c7?c9?)(c8?c10?)(c11?)(c12?)(c13?c15?)(c14?c16?)
  4. 旋转 270°： p 4 = ( c 1 ) ( c 2 ) ( c 6 c 4 c 5 c 3 ) ( c 10 c 8 c 9 c 7 ) ( c 11 c 12 ) ( c 16 c 14 c 15 c 13 ) p_4=(c_1)(c_2)(c_6 c_4 c_5 c_3)(c_{10} c_8 c_9 c_7)(c_{11} c_{12})(c_{16} c_{14} c_{15} c_{13}) p4?=(c1?)(c2?)(c6?c4?c5?c3?)(c10?c8?c9?c7?)(c11?c12?)(c16?c14?c15?c13?)

由Burnside 引理，不同等价类的个数为 l = 1 4 ( 16 + 2 + 4 + 2 ) = 6 l=\cfrac{1}{4}(16+2+4+2)=6 l=41?(16+2+4+2)=6，其 c ( p 1 ) = 16 , c ( p 2 ) = 2 , c ( p 3 ) = 4 , c ( p 4 ) = 2 c(p_1)=16,c(p_2)=2, c(p_3)=4,c(p_4)=2 c(p1?)=16,c(p2?)=2,c(p3?)=4,c(p4?)=2。不同的图像如图所示：

在这里插入图片描述

4. Pólya 计数定理

等价类集合中所有等价类权的和通常称为该等价类集合的模式表（pattern inventory）。

模式表用于描述一组对象在某种等价关系下的分类情况，这些对象根据特定的性质或规则被分成不同的等价类。

一个直观的例子是将一组物体按照颜色进行分类。假设有一些球，有红色、蓝色和绿色三种颜色的球。现在要按照颜色来分组，但是每个等价类（颜色）的大小（球的数量）可以不同。例如，可能有3个红球、4个蓝球和2个绿球。

这个情况下，对于这组球，等价类集合是按颜色分类的，分为了3个等价类：红色、蓝色和绿色。而模式表就是每个等价类中物体数量的总和，即各颜色球的数量之和：3（红色） + 4（蓝色） + 2（绿色）= 9。

引理 4.1： 设 G 是 D={1,2,…,n } 上的置换群，R = { r 1 , r 2 , . . . , r m r_1,r_2,...,r_m r1?,r2?,...,rm? }(可理解为m种着色)， F = { f ∣ = f : D → R } F=\{ f | =f: D → R\} F={f∣=f:D→R}则 F 上的全部模式表为 P G ( ∑ r ∈ R w ( r ) , ∑ r ∈ R w 2 ( r ) , . . . , ∑ r ∈ R w n ( r ) ) P_G(\sum_{r\in R}w(r),\sum_{r\in R}w^2(r),...,\sum_{r\in R}w^n(r)) PG?(∑r∈R?w(r),∑r∈R?w2(r),...,∑r∈R?wn(r))

4.1 对点着色问题

习题4、对图中的顶点进行 m 着色，问有多少种方案?

在这里插入图片描述
解：1) 不动置换 σ I σ_I σI? ，即 1 9 1^9 19 型置换有 1 个
2) 以 i i i 为中心，旋转 90°，180°，270°，则分别有(aceg) (bdfh)，(ae)(bf)(cg)(dh)，(agec)(hfdb)．这类旋转可以确定 1 1 4 2 1^14^2 1142 型 2 个， 1 1 2 4 1^12^4 1124 型 1 个
3) 以 bf，hd 为轴翻转 180°，则有(ac)(dh)(eg)，(ag)(bf)(ce)．这类旋转可以确定 1 3 2 3 1^32^3 1323 型 2 个
4) 以 ae，cg 为轴翻转 180°，则有(cg)(hb)(df)，(ae)(hf)(bd)．这类旋转可以确定 1 3 2 3 1^32^3 1323 型 2 个
所以，该置换群的轮换指标为 P G ( x 1 , x 2 , . . . , x 9 ) = 1 8 ( x 1 9 + 2 x 1 x 4 2 + x 1 x 2 4 + 4 x 1 3 x 2 3 ) P_G(x_1,x_2,...,x_9)=\cfrac{1}{8}(x^9_1+2x_1x_4^2+x_1x_2^4+4x_1^3x_2^3) PG?(x1?,x2?,...,x9?)=81?(x19?+2x1?x42?+x1?x24?+4x13?x23?)
等价类个数即着色方案数为 l = P G ( m , m , . . . , m ) = 1 8 ( m 9 + 2 m 3 + m 5 + 4 m 6 ) l=P_G(m,m,...,m)=\cfrac{1}{8}(m^9+2m^3+m^5+4m^6) l=PG?(m,m,...,m)=81?(m9+2m3+m5+4m6)

习题5、有一个3×3的正方形棋盘,若用红蓝两色对这9个方格进行着色,要求两个位红色,其余为蓝色,问有多少种方案？

在这里插入图片描述
解：令 D={a,b,c,d,e,f,g,?,i} , R = { c 1 , c 2 } R=\{c_1,c_2\} R={c1?,c2?} ,6个棋盘格染2种颜色的方法是 F：D→R，由此确定D上的置换为

  1. 不动置换 σ I σ_I σI? ，即 1 9 1^9 19 型置换有 1 个
  2. 以 i i i 为中心，旋转 90°，180°，270°，则分别有(aceg) (bdfh)，(ae)(bf)(cg)(dh)，(agec)(hfdb)．这类旋转可以确定 1 1 4 2 1^14^2 1142 型 2 个， 1 1 2 4 1^12^4 1124 型 1 个
  3. 以 bif，hid 为轴翻转 180°，则有(ac)(dh)(eg)，(ag)(bf)(ce)．这类旋转可以确定 1 3 2 3 1^32^3 1323 型 2 个
  4. 以 aie，cig 为轴翻转 180°，则有(cg)(hb)(df)，(ae)(hf)(bd)．这类旋转可以确定 1 3 2 3 1^32^3 1323 型 2 个

所以，该置换群的轮换指标为 P G ( x 1 , x 2 , . . . , x 9 ) = 1 8 ( x 1 9 + 2 x 1 x 4 2 + x 1 x 2 4 + 4 x 1 3 x 2 3 ) P_G(x_1,x_2,...,x_9)=\cfrac{1}{8}(x^9_1+2x_1x_4^2+x_1x_2^4+4x_1^3x_2^3) PG?(x1?,x2?,...,x9?)=81?(x19?+2x1?x42?+x1?x24?+4x13?x23?)
F的全部模式表 P G ( c 1 + c 2 , c 1 2 + c 2 2 , . . . , c 1 9 + c 2 9 ) = 1 8 [ ( c 1 + c 2 ) 9 + 2 ( c 1 + c 2 ) ( c 1 4 + c 2 4 ) 2 + ( c 1 + c 2 ) ( c 1 2 + c 2 2 ) 4 + 4 ( c 1 + c 2 ) 3 ( c 1 2 + c 2 2 ) 3 ] P_G(c_1+c_2,c_1^2+c_2^2,...,c_1^9+c_2^9)\\=\cfrac{1}{8}[(c_1+c_2)^9+2(c_1+c_2)(c_1^4+c_2^4)^2+(c_1+c_2)(c_1^2+c_2^2)^4+4(c_1+c_2)^3(c_1^2+c_2^2)^3] PG?(c1?+c2?,c12?+c22?,...,c19?+c29?)=81?[(c1?+c2?)9+2(c1?+c2?)(c14?+c24?)2+(c1?+c2?)(c12?+c22?)4+4(c1?+c2?)3(c12?+c22?)3]根据题意， c 1 2 c 2 7 c_1^2c_2^7 c12?c27? 系数为 1 8 [ ( 9 2 ) + 4 [ ( 3 0 ) ( 3 1 ) + ( 3 2 ) ( 3 0 ) ] + ( 4 1 ) ] = 1 8 ( 36 + 24 + 4 ) = 8 \cfrac{1}{8}[\binom{9}{2}+4[\binom{3}{0}\binom{3}{1}+\binom{3}{2}\binom{3}{0}]+\binom{4}{1}]=\cfrac{1}{8}(36+24+4)=8 81?[(29?)+4[(03?)(13?)+(23?)(03?)]+(14?)]=81?(36+24+4)=8

习题6、对正六角形的6个顶点用5种颜色进行着色。试问有多少种不同的方案,旋转使之重合作为相同处理？

在这里插入图片描述
解：令 D={a,b,c,d,e,f} , R = { c 1 , c 2 , c 3 , c 4 , c 5 } R=\{c_1,c_2,c_3,c_4,c_5\} R={c1?,c2?,c3?,c4?,c5?} 6个点染5种颜色的方法是 F：D→R，由此确定D上的置换为

  1. 不动置换 σ I σ_I σI? ，即 1 6 1^6 16 型置换有 1 个
  2. 以六边形中点为中心，旋转 60° 和 300°，有(abcdef) 这类旋转可以确定 6 1 6^1 61 型 2 个；旋转 120° 和 240°，有(ace)(bdf) 这类旋转可以确定 3 2 3^2 32 型 2 个；旋转 180°，有(ad)(be)(cf) 这类旋转可以确定 2 3 2^3 23 型 1 个
  3. 以绕对角连线旋转180°，则有(a)(d)(be)(cf),(ad)(b)(e)(cf),(ad)(be)( c)(f)．这类旋转可以确定 1 2 2 2 1^22^2 1222 型 3 个
  4. 以对边中点连线为轴翻转 180°，则有(ab)(cf)(de),(af)(be)(cd),(bc)(ad)(fe)．这类旋转可以确定 2 3 2^3 23 型 3 个

所以，该置换群的轮换指标为 P G ( x 1 , x 2 , . . . , x 6 ) = 1 12 ( x 1 6 + 2 x 6 + 2 x 3 2 + 3 x 1 2 x 2 2 + 4 x 2 3 ) P_G(x_1,x_2,...,x_6)=\cfrac{1}{12}(x^6_1+2x_6+2x_3^2+3x_1^2x_2^2+4x_2^3) PG?(x1?,x2?,...,x6?)=121?(x16?+2x6?+2x32?+3x12?x22?+4x23?)
F的全部模式表 在这里插入图片描述

根据题意， c 1 2 c 2 c 3 c 4 c 5 ， c 1 c 2 2 c 3 c 4 c 5 ， c 1 c 2 c 3 2 c 4 c 5 ， c 1 c 2 c 3 c 4 2 c 5 ， c 1 c 2 c 3 c 4 c 5 2 c_1^2c_2c_3c_4c_5，c_1c_2^2c_3c_4c_5，c_1c_2c_3^2c_4c_5，c_1c_2c_3c_4^2c_5，c_1c_2c_3c_4c_5^2 c12?c2?c3?c4?c5?，c1?c22?c3?c4?c5?，c1?c2?c32?c4?c5?，c1?c2?c3?c42?c5?，c1?c2?c3?c4?c52? 项的系数之和为 1 12 ( 5 ? 6 ! 2 ! 1 ! 1 ! 1 ! 1 ! ) = 150 \cfrac{1}{12}(5\cdot \cfrac{6!}{2!1!1!1!1!})=150 121?(5?2!1!1!1!1!6!?)=150

4.2 对面着色问题

习题7、骰子的 6 个面分别有 1，2，3，4，5，6 个点，问有多少种不同的方案？

在这里插入图片描述

解：问题相当于对正六面体的 6 个面用 6 种颜色对之着色，要求各面的颜色都不一样

  1. 不旋转，可确定 1 6 1^6 16 型置换 1 个
  2. 以相对两面中心连线为轴的旋转．这种轴共有 3 条，对于每条轴可做 ± 90°，180° 旋转．这类旋转可以确定 1 2 4 1 1^24^1 1241 型置换 6 个， 1 2 2 2 1^22^2 1222 型置换 3 个
  3. 以相对两边中点连线为轴的旋转．这种轴共有 6 条，对于每条轴可做 180°旋转．这类旋转可以确定 2 3 2^3 23 型置换 6 个
  4. 以正六面体对角线为轴的旋转．这种轴有 4 条，对于每条轴可做 ± 120°旋转．这类旋转可以确定 3 2 3^2 32 型置换 8 个

所以正六面体可产生 24 种置换，该置换群轮换指标为
P G ( x 1 , x 2 , . . . , x 6 ) = 1 24 ( x 6 + 6 x 1 2 x 4 + 3 x 1 2 x 2 2 + 8 x 3 2 + 6 x 2 3 ) P_G(x_1,x_2,...,x_6)=\cfrac{1}{24}(x^6+6x_1^2x_4+3x_1^2x_2^2+8x^2_3+6x_2^3) PG?(x1?,x2?,...,x6?)=241?(x6+6x12?x4?+3x12?x22?+8x32?+6x23?)
用 Pólya 计数定理求解
在这里插入图片描述

4.3 重复球放盒子

习题8、将两个相同的白球和两个相同的黑球放入两个不同的盒子里,问有多少种不同的方法？列出全部方案.又问每盒中有两个球的方法有多少种？

解：令 D = { w 1 , w 2 , b 1 , b 2 } , R = { c 1 , c 2 } D=\{w_1,w_2,b_1,b_2\},R=\{c_1,c_2\} D={w1?,w2?,b1?,b2?},R={c1?,c2?}，四个球往两个盒子里放的放法是 F：D→R。
由于 w 1 , w 2 w_1,w_2 w1?,w2?是两个相同的白球， b 1 , b 2 b_1,b_2 b1?,b2?是两个相同的黑球，由此确定出D上的置换群为
G = { σ I , ( w 1 w 2 ) , ( b 1 b 2 ) , ( w 1 w 2 ) ( b 1 b 2 ) } G=\{σ_I,(w_1w_2),(b_1b_2),(w_1w_2)(b_1b_2)\} G={σI?,(w1?w2?),(b1?b2?),(w1?w2?)(b1?b2?)}
其轮换指标为 P G ( x 1 , x 2 , x 3 , x 4 ) = 1 4 ( x 1 4 + 2 x 1 2 x 2 + x 2 2 ) P_G(x_1,x_2,x_3,x_4)=\cfrac{1}{4}(x_1^4+2x_1^2x_2+x_2^2) PG?(x1?,x2?,x3?,x4?)=41?(x14?+2x12?x2?+x22?)
F 上的等价类个数由Pólya 计数 可得 l = P G ( 2 , 2 , 2 , 2 ) = 1 8 ( 2 4 + 2 ? 2 2 ? 2 + 2 2 ) = 9 l=P_G(2,2,2,2)=\cfrac{1}{8}(2^4+2\cdot 2^2\cdot2+2^2)=9 l=PG?(2,2,2,2)=81?(24+2?22?2+22)=9
这 9 个不同方案为： ( ? , w w b b ) , ( w , w b b ) , ( b , w w b ) , ( w w , b b ) , ( w b , w b ) , ( w w b b , ? ) , ( w b b , w ) , ( w w b , b ) , ( b b , w w ) (\oslash ,wwbb),(w,wbb),(b,wwb),(ww,bb),(wb,wb),(wwbb,\oslash ),(wbb,w),(wwb,b),(bb,ww) (?,wwbb),(w,wbb),(b,wwb),(ww,bb),(wb,wb),(wwbb,?),(wbb,w),(wwb,b),(bb,ww)

F的全部模式表 P G ( c 1 + c 2 , c 1 2 + c 2 2 , c 1 3 + c 2 3 , c 1 4 + c 2 4 ) = 1 4 [ ( c 1 + c 2 ) 4 + 2 ( c 1 + c 2 ) 2 ( c 1 2 + c 2 2 ) + ( c 1 2 + c 2 2 ) 2 ] P_G(c_1+c_2,c_1^2+c_2^2,c_1^3+c_2^3,c_1^4+c_2^4)\\=\cfrac{1}{4}[(c_1+c_2)^4+2(c_1+c_2)^2(c_1^2+c_2^2)+(c_1^2+c_2^2)^2] PG?(c1?+c2?,c12?+c22?,c13?+c23?,c14?+c24?)=41?[(c1?+c2?)4+2(c1?+c2?)2(c12?+c22?)+(c12?+c22?)2]盒1与盒2中各放两个球的方案数是 c 1 2 c 2 2 c_1^2c_2^2 c12?c22?项的系数，即为 1 4 [ ( 4 2 ) + 2 + 2 + 2 ] = 3 \cfrac{1}{4}[\binom{4}{2}+2+2+2]=3 41?[(24?)+2+2+2]=3
具体方案为： ( w w , b b ) , ( w b , w b ) , ( b b , w w ) (ww,bb),(wb,wb),(bb,ww) (ww,bb),(wb,wb),(bb,ww)

文章来源:https://blog.csdn.net/cold_code486/article/details/135114849
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。