组合数学Pólya定理习题解答

换句话说，如果一个封闭曲线与区域内的任意直线都没有交点，那么这个封闭曲 线必然完全位于区域外。
波利亚定理的重要性
波利亚定理在几何学中有着广泛的应 用，它可以帮助我们解决一些与图形 和空间有关的问题。
例如，在几何图形中，我们可以通过 应用波利亚定理来判断一个点是否在 某个区域内，或者判断一个封闭曲线 是否与某个区域相交。
第二步
根据已知条件和数学原理，推导出与结论 相关的中间结论，这是证明的关键环节。
B
C
第三步
通过逻辑推理和数学推导，逐步推导出最终 结论，这一步需要严谨的逻辑推理和精确的 数学表达。
第四步
对推导出的结论进行验证，确保其正确性和 可靠性，这一步也是证明的重要环节。
D
定理证明的结论
波利亚定理的证明结论是：在一定条件下，一个数学问题可 以通过逐步转化和化简，最终转化为一个更简单或更易于解 决的问题，从而找到问题的解。
03
多变量版本的波利亚定理
该定理将单变量版本的波利亚定理扩展到多变量函数，提供了解决多变
量问题的新工具。
定理在其他数学领域的应用
在几何学中的应用
波利亚定理在几何学中有着广泛的应用，例如在计算几何形状的 面积和体积，解决几何问题等方面。
在组合数学中的应用
波利亚定理在组合数学中有着重要的应用，例如在解决组合问题、 计数问题、排列问题等方面。
B
C
波利亚定理的证明方法有多种，其中最常用 的是数学归纳法。
波利亚定理在数学教育中也具有重要意义， 它有助于培养学生的逻辑推理能力和数学思 维能力。
D
对波利亚定理的展望
随着数学的发展，波利亚定理的应用范围将不断扩大， 将有更多的数学问题可以通过波利亚定理得到解决。

9
II. 母函数形式的Pò lya定理
我们这里给出的Polya计数定理其实是一 种特殊形式. 一般形式的Polya定理还可以 用来解决有条件限制而且互相不等价的染 色方案数目. 还有一个问题是如何列举出所有不同类型 的染色方案? 显然Polya定理无法告诉我 们这些. 它只能告诉我们总数. 母函数形式Polya定理可以满足这个要求.
22
III. Boole函数及其等价分类
布尔(Boole)函数在现代计算机逻辑 电路的设计中有很重要的应用. n个变量的Boole函数f(x1,x2,…,xn)就 是集合Z2n={(x1,x2,…,xn)|xi=0或1; i=1, 2,…,n} 到集合Z2={0,1}的一个映射. n个变量的不同Boole函数总数: 2 2
24
例如: f(x1,x2,x3)=x1+x2x3与g(x1,x2,x3)=x2+x3x1 等价, 因为g(x1,x2,x3)= f(x2,x3,x1). 取补型等价. 例如f(x1,x2,x3)与f(x1,x2,x3) 取补等价. 取补与下标置换混合等价. 可以利用Polya定理, 通过这些等价所对应 的置换群得出等价类型的数目. 我们不打 算详细推导这些情况. 下面只针对下标置换等价意义下布尔等价 类的计数给出一个例子.
( b1 b 2 b m )
c1 ( g )
( b1 b 2 b m )
n n n
cn ( g )
由此可以知道, 总的染色方案的列举 只要在轮换指标中令:
x i b1 b 2 b m
i i i
15
即可得到能列举出方案情况的母函数 形式的Polya定理:
10
先通过一个简单例题说明思想.

x15 4x5 5x1x22
(6.14)
1) 用y代表黑色，w代表白色，若用wk+yk代入式(6.14) 中的xk(k=1,2,3,4,5),则可得含参数w与y的多项式P， 展开此多项式后形如wiyn(i任意，n固定)的所有项的
系数之和，即为an。所以若在多项式P中令w=1，
22-15
解(续1)
22-2
设N是n个对象的集合，G是N上的置换群，用m种色
b1,b2,…,bm对n个对象着色，则着色方案的列举可表达为
P
|
1 G
|
G
s c1 1
(
s) c2 2
(
)
s cn () n
(6.12)
其中ck(σ)为σ中k-循环的个数，
sk b1k bk2 bkm , k 1,2, ,n
展开P经合并同类项后，
6
ri2 2 6
6
ri2
3
8
6
ri3
2
i1 i1
i1
i1
将P展开，r1r2r3r4r5r6项系数即为所求，因该项只能出
(r1+r2+r3+r4+r5+r6)6
的展开式中。而
r1r2r3r4r5r6相当于在6个(r1+r2+r3+r4+r5+r6)中每一个取
ri作乘积，且6个ri均不相同，故有6!个r1r2r3r4r5r6 ，
使任何一种已着色的方体变为自身，这表明G中除恒等
置换I外，对任何置换均无1-循环。所以有
c1(I)=6!,
c1(τ)=0，τ∈G,τ≠I
由Burside引理，不同方案数为
t 1 6!0 0 0 0 0 30

• 2.证：设|G|=g,则a,a2,a3,…,ag,ag+1 中必有相 证 k l 同元。a = a , 1≤k＜l≤g+1 a l-k =e. 1≤l-k≤g 对于给定的a，存在最小的正 r r 整数r,a =e .于是 H={a ,a ,…,a2 (=e)}是G的 子群，若H≠G,则存在a1不属于H, 显然， . H∩Ha1=φ,|H+Ha1|=2r 若 . H+Ha1=G,则2r=g,r|g 否则 . 存在a2不属于H+Ha1, . Ha2∩(H+Ha1)=φ 于是 . . . . H+Ha1+Ha2+…+Hak=G, r(k+1)=g,r|g. 证毕。 题
• 15.(a)本质上有多少种确实是2个输入端 的布尔电路？写出其布尔表达式。 (b)本质上有多少种确实是3个输入端 的布尔电路？ 解 • 16.用8个相同的骰子垛成一个正6面体， 有多少方案？ 解 • 17.正六面体的6个面和8个顶点分别用红、 蓝两种颜色的珠子嵌入。试问有多少种 不同的方案数?(旋转使之一致的方案看作 是相同的). 解
• 5.解：相当于4.7节中例2中求b 5r3的系数， 为[C(8,5)+8C(2,1)]/24=3 题 • 6.解：正5边形的运动群 题 。 1 绕心转 ±72 。 (5) 2个 1 ±144 (5) 2个 翻转 。 2 180 (1)(2) 5个 不动 5 (1) 1个 不同方案数为m=(3 1 3 +4·3 +5·3 )/10=39 5 • 7.解：使重合的运动包括绕中心旋转和绕 水平对称轴翻转共产生2n个置换群。
• 16.解：相当于正六面体每个角上放一个 骰子。骰子按讲义4.6中关于正立方体的 不同旋转均不会产生重合现象，共24种 方案。因此本题相当于正六面体的顶点 24着色。但绕顶点-顶点的对称轴旋转不 会产生重合的图象。 参照习题11可得不同的方案数为 M=[24 6+6·243+3·244+0·8·242+6·243]/24 =8011008 题