数组合数学

组合数学6-polya计数

字数统计: 6.4k字   |   阅读时长: 27分
, ,

摘要: Polya 定理、立方体旋转、欧拉定理、母函数型 Polya、图的计数

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型以及相关公式；在 组合数学2-母函数,递推关系 中我们详细学习了母函数、递推关系；在文章 组合数学3-特殊计数序列,指数型母函数 中我们详细学习了指数型母函数、特殊计数序列。

在文章 组合数学5-群论 中，我们学习了置换群及其应用。核心概念有共轭类、对换、等价类、Burnside 引理。

本文是组合数学第六部分，从 Burnside 的困境入手，逐渐深入 Polya 计数的理论。主要内容如下：

  • Burnside引理回顾
    • 等价类的最终结论: Burnside引理
    • $l = \frac{1}{|G|}\sum\limits_{j=1}\limits^{g}c_{1}(a_{j})$
    • 例子: 正方形顶点二着色只考虑旋转的等价类个数
  • Burnside的困境
    • 正方形顶点红蓝二着色，只考虑旋转的转动群，有多少个不同图像
    • 6种色给正方体着色，一面一色，没面不同，有多少中涂法
      • 组合计数
      • Bernside
    • Burnside的问题
      • 需要画出所有图像
      • 颜色多了或者着色对象复杂，Burnside则只能停留在理论
  • Polya定理
    • Polya与Bunside的应用
      • 原来: 是找出所有图像再找出这些图像的置换群
      • 现在: 直接考虑结构(e.g. 将正方形顶点打标)
      • 原来: 找图像群一阶循环个数
      • 现在: 着色对象结构的置换群中循环个数
    • Polya定理描述
      • $l = \frac{1}{|\bar{G}|}\sum\limits_{j=1}\limits^{g}m^{c(\bar{p_{j}})}$
    • Polya定理应用
      • 等边三角形 3 顶点用 3 色着色的方案数
      • 三种不同色的珠子，串成四个珠子的环形项链，求方案数
  • 立方体旋转
    • 正六面体转动群
      • 面置换: 6 个面
      • 顶点置换: 8 个顶点
      • 棱置换: 12条棱
    • 正六面体每个面任意做一条对角线，求方案数
  • 欧拉定理
    • 如何思考空间中的凸多面体，如何记忆图像
    • 欠角: 凸多面体与一个顶点相关的面角之和与 360 的差
    • 凸多面体各定点的欠角和为 720
    • 足球有多少个正五边形，多少个正六边形
    • 用火柴搭一个足球有多少方案
    • 八个骰子，叠成正六面体，求方案数
  • 母函数型Polya
    • Polya可以给出方案数，但不能给出具体方案
    • 母函数型Polya的两个部分
      • Polya: 计数
      • 母函数: 对状态枚举
    • 对三个相同的球用r,y,g,b四种颜色染色，求所有可能的颜色组合
    • 三种色的珠子，用4珠子串成环形项链，求可能方案
    • 等边三角形用 r,g,b 三种颜色着色，求可能方案
    • 4个红珠子，放在正六面体4个顶点上，有多少方案
    • 正四面体，点4着色，面3着色，棱2着色，求方案数
    • 四个球 a,a,b,b 放入 3 个不容盒子，求方案数，如果不允许空盒，求方案数
      • 法1: 容斥计数
      • 法2: 母函数型 Polya
  • 图的计数
    • n个顶点的简单图有多少种(完全图的边二着色)
    • 完全图的置换: 与立方体的区别是不再是刚体
    • 4个顶点不同构的图
    • 4个顶点不同构的有向图
  • Polya 的书《数学的发现》

Burnside 引理回顾

等价类的最终结论即Burnside引理

Burnside引理

$G = \{a_{1}, a_{2}, …, a_{g}\}$ 为目标集 [1,n] 上的置换群。每个置换都写成不相交循环的乘积。$c_{1}(a_{k})$ 是在置换 $a_{k}$ 的作用下不动点的个数，也就是长度为 1 的循环的个数。G 将 [1,n] 划分成 l 个等价类。

例子：正方形顶点二着色只考虑旋转的等价类个数

正方形红蓝二着色的旋转置换群

枚举的结果：等价类的个数为 6，下面看 Burnside 引理的做法

首先把置换写出类，然后看置换的个数，和 1 阶循环的个数

Burnside 的困境

首先我们回顾以下转动群:

正方形顶点，红蓝二着色，只考虑旋转的转动群 G。

首先画出图像，共 16 个。

转动群 $G = {a_{1}, a_{2}, a_{3}, a_{4}}$，共 4 个置换。分别对应度数为 0, 90, 180, 270 的情况。

将 G 中的 4 个置换写成循环的形式。然后看一阶循环的个数，然后套用 Burnside 引理即可求出等价类的个数。

下面看一个 Burnside 解决不了的问题:

6 种颜色，给正方体着色，一面一色，每面的颜色都不同，问有多少种涂法。

首先本题可以用组合数的方法解决:

先把正六面体固定住，顶面与底面的颜色选法为 6 * 5 = 30，当顶面与底面已经选定后，剩下的四个面构成了一个圆，用圆排列的公式套进去，即可得到总的方案数为

如果要用 Burnside 引理，则需要先找到置换群 $G = {a_{1}, …, a_{g}}$，而要写出所有的置换 $a_{j}$，就要先写出所有的图像，通过图像去看有哪些置换。

当我们画出所有图像后，我们需要研究下面两件事，这里我们没有画出具体图像，但是我们可以知道共有 $6!$ 种图像。

  1. G 中有多少个置换
  2. 对于每个置换 $a_{j}$，我们还要找到有多少个一阶循环。

对于第一个问题，我们通过以下三步做

step1: 每个面打标号 (1, 2, 3, 4, 5, 6)
step2: 找转轴，对面轴、对棱轴、对角线轴
step3: 分析正六面体的置换方法

具体的转轴如下

  1. 不动，共 1 个
  2. 对面轴转 180, -180，共 $2 \times 3 = 6$ 个
  3. 对面轴转 90，共 3 个
  4. 对棱轴转 180，共 6 个
  5. 对角线轴转 120, -120，共 $2 \times 4 = 8$ 个

我们没有将 $6!$ 所有图象列出来，我们只是分析了有多少个不同的置换，以及各个置换有多少个不动点(一阶循环)。

因此总共的置换个数 $|G|=24$，因为各个面颜色不同，因此 2 ~ 5 这些置换中均无一阶循环，而 1 这个置换中有 $6!$ 个一阶循环。

由 Burnside 引理

如果各个面可以同色，则问题规模(着色图像集)就大了。(从 $6!$ 变成了 $6^{6}$)

此外在各个置换下的不动点情况就复杂了。

Polya定理

从例子看 Polya 与 Burnside 的变化

原来是先找出所有图像，再找出这些图像的置换群。以【正方形顶点二着色只考虑旋转】为例，有 16 种图像，其旋转置换群中有 4 个置换(4 种旋转)。

现在是直接考虑结构，也可以写出置换群。例如将正方形顶点打标。

这样写出来的是【正方形四顶点着色结构】的置换群 $\bar{G}$。

这个置换群中的置换有 4 个

结构置换群中的置换 旋转类型 与 Burnside 中各项的对应
$\bar{p_{1}} = (1)(2)(3)(4)$ 0 $2^{4}$
$\bar{p_{2}} = (4, 3, 2, 1)$ 90 $2^{1}$
$\bar{p_{3}} = (1, 3)(2, 4)$ 180 $2^{2}$
$\bar{p_{4}} = (1, 2, 3, 4)$ 270 $2^{1}$

在结构置换群中的置换中，同意括号内着同色，执行对应旋转后图像不变。

通过结构群中置换与 Burnside 中各项 $c_{1}(a_{j})$ 的对应，我们发现

其中 $c(\bar{p_{j}})$ 为 $\bar{p_{j}}$ 中的循环个数。由于是二着色，m = 2。

这样不用找图像群的一阶循环个数了，而只需要找【着色对象结构的置换群中循环个数】。

Polya 定理完整描述

下面我们看一下 Polya 定理的完整描述。与 Burnside 引理对比。

  • Burnside 引理

$G = {a_{1}, a_{2}, …, a_{g}}$ 为目标集 [1, n] 上的置换群。每个置换写成不相交循环的乘积。
G 将 [1, n] 划分为 l 个等价类
$c_{1}(a_{j})$ 为在置换 $a_{j}$ 下不动点(一阶循环)个数，则

  • Polya 定理

$\bar{G} = {\bar{p_{1}}, \bar{p_{2}}, …, \bar{p_{g}}}$ 为【n个对象】的置换群。
$c(\bar{p_{j}})$ 为置换 $\bar{p_{j}}$ 的循环个数。
m 中颜色对 n 个对象着色，则

注意【$G$ 和 $\bar{G}$，的置换个数相等】，例如都是 4 种旋转。

其中

  • $G$ 对应所有图像(n 个对象染色后的方案集合)
  • $\bar{G}$ 对应所有结构(n 个对象)

桥梁就是

Polya 定理例题

等边三角形，3 顶点，用 3 色着色，求方案数。

首先看一下对象，由于是三角形，对 3 个顶点着色，对象就是 3 个顶点，记为 [1, 3]。

然后看一下 3 个对象 [1, 3] 上的结构置换群。注意本题没说只考虑旋转

(1) 旋转

旋转有 3 种，也就是 0, 120, 240。分别记为 $\bar{p_{1}}, \bar{p_{2}}, \bar{p_{3}}$，画图分析后，写出

(2) 翻转

翻转也有 3 种，也就是 3 个转轴的翻转，记为 $\bar{p_{1}}, \bar{p_{2}}, \bar{p_{3}}$，画图分析后，写出

通过以上分析，我们知道 $|\bar{G}| = 6, m = 3$，以及各个 $c_{\bar{p_{j}}}$

三种不同色的珠子，串成四个珠子的环形项链，求方案数

首先看对象个数，由于一共是 4 个珠子，n = 4

然后看 [1, 4] 中，结构置换群的置换个数，注意本题也没说只考虑旋转。

(1) 旋转

旋转一共有 4 种，也就是 0, 90, 180, 270，分别记为 $\bar{p_{1}}, \bar{p_{2}}, \bar{p_{3}}, \bar{p_{4}}$。

(2) 翻转

翻转共有 4 种，也就是共有 4 个转轴。分别记为 $\bar{p_{5}}, \bar{p_{6}}, \bar{p_{7}}, \bar{p_{8}}$。

通过以上分析，我们知道 $|\bar{G}| = 8, m = 3$，以及各个 $c_{\bar{p_{j}}}$

立方体旋转

例如: 正六面体转动群

  • 面置换: 6 个面
  • 棱置换: 12 条棱
  • 顶点置换: 8 个顶点

顶点置换

考虑 [1, 8] 上的置换群中的置换

用k阶循环的形式表示置换 该置换的个数
$(1)^{8}$ 1

(2) 面面中心转动

置换形式 用k阶循环的形式表示置换 该置换的个数
旋转 90 $(4)^{2}$ 2 种方向, 3 种转轴, 6
旋转 180 $(2)^{4}$ 1 种方向, 3 种转轴, 3

(3) 棱中对棱中转

置换形式 用k阶循环的形式表示置换 该置换的个数
旋转 180 $(2)^{4}$ 6 种转轴, 6

(4) 对角线为轴转

置换形式 用k阶循环的形式表示置换 该置换的个数
旋转 120 $(1)^{2}(3)^{2}$ 2 种方向, 4 种转轴, 8

综合以上各个置换的形式及其个数。$|\bar{G}| = 24$，顶点置换的问题就好解了，下面看一个问题

用 2 种色对 8 个顶点着色，求方案数

面置换

(1) 不动

用k阶循环的形式表示置换 该置换的个数
$(1)^{6}$ 1

(2) 面面中心旋转

置换形式 用k阶循环的形式表示置换 该置换的个数
旋转 90 $(1)^{2}(4)^{1}$ 2 种方向, 3 种转轴, 6
旋转 180 $(1)^{2}(2)^{2}$ 1 种方向, 3 种转轴, 3

(3) 棱中对棱中转

置换形式 用k阶循环的形式表示置换 该置换的个数
旋转 180 $(2)^{3}$ 6 种转轴, 6

(4) 对角线为轴转

置换形式 用k阶循环的形式表示置换 该置换的个数
旋转 120 $(3)^{2}$ 2 种方向, 4 种转轴, 8

综合以上各个置换的形式及其个数。$|\bar{G}| = 24$，面置换的问题就好解了，下面看一个问题

正 6 面体 6 个面，2 着色的方案数

下面是一个 Burnside 未解决的问题

正 6 面体 6 个面，6 着色的方案数

骰子6个面，1~6 点数，有多少种组织方式

注意本题与正6面体6个面6着色的不同，这里 1~6 必须全都用上。因此不能套 Polya

注意到当 6 个面颜色都不同的时候，24 个面置换中，只有【不动】这一种置换(记为 e)是有一阶循环(执行一次置换后图像不变)的，其中一阶循环个数为 6! (6! 种图像)。 因此适合用 Burnside 做。 本题也可以用母函数型 Polya，后面会介绍。 如果考虑 2, 3, 6 的方向问题，由于 2, 3, 6 各有 2 个方向，因此方案数变为 $30 \times 2^{3} = 240$ ![](https://chengzhaoxi.oss-cn-beijing.aliyuncs.com/resource/组合数学/70.jpg) >正六面体，每个面任意做一条对角线，求方案数 **注意本题与正6面体6个面2着色的不同，这里旋转后，同一面斜线的方向可能改变，但颜色在旋转后是不会改变的。** 因此置换群与正6面体6个面2着色是一样的，但不是简单套 polya 就可以的，这里关注的是旋转后的不动图像

其中没有不动图像的置换，在 Polya 中对应的项不考虑。

欧拉定理

如何思考空间中的凸多面体

  • 欧拉定理: v + f - e = 2
  • 平面多边形内角和为 180(v - 2)
  • 欠角: 与一个顶点相关的面角之和与 360 的差为欠角
  • 凸多面体各顶点的欠角和为720

问题1

用正五边形搭的正多面体有多少顶点，多少条棱，多少个面

问题2

足球有多少个正五边形，多少个正六边形

问题3

用火柴搭一个足球有多少方案

参考棱的二着色，但要考虑火柴的方向

60顶点，90棱，12五边形，20六边形

考虑其结构置换群

(1) 不动, $(1)^{90}$
(2) 5边形面心对面心转 72n, $(5)^(90/5)$, (n=1,2,3,4), 6对面心, 共 24 个置换
(3) 6边形面心对面心转 120n, $(3)^(90/3)$, (n=1,2), 10对面心, 共 20 个置换
(4) 6边形与6边形边界中点为轴转180, $(1)^{2}(2)^{44}$ 共 15 对, 共 15 个置换 (这种情况无不动图像)

8 个骰子，叠成正六面体，求方案数

每个正六面体有 24 种转动，每个骰子占据一个顶点，相当于顶点的 24 着色(对应24种转动方法)。

套用 Polya 即可，注意没有不动图像的置换在 Polya 中对应的项不考虑。

母函数型 Polya

Polya 可以给出着色方案数，但是对每种着色方案，有哪些具体方案是不知道的。

母函数型 Polya 可以解决具体方案的问题，分为两部分

Polya: 负责计数
母函数: 负责枚举

母函数负责枚举的例题

对三个相同的球用 4 种颜色 r,y,g,b 染色，问所有可能的颜色组合。

将 $(r + y + g + b)^{3}$ 展开即可。

母函数型 Polya 引入题

三种颜色的珠子，串成4珠子项链，有哪些方案

之前我们用 Polya 定理求出了方案数，这里要找具体方案，需要把母函数引入进来

这里我们还是要研究置换

(1) 旋转

旋转一共有 4 种，也就是 0, 90, 180, 270，分别记为 $\bar{p_{1}}, \bar{p_{2}}, \bar{p_{3}}, \bar{p_{4}}$。

置换 循环个数 具体循环 母函数
$\bar{p_{1}} = (1)(2)(3)(4)$ $c(\bar{p_{1}}) = 4$ 4个1阶循环 $(r + b + g)^{4}$
$\bar{p_{2}} = (1, 4, 3, 2)$ $c(\bar{p_{2}}) = 1$ 1个4阶循环 $(r^{4} + b^{4} + g^{4})$
$\bar{p_{3}} = (1, 3)(2, 4)$ $c(\bar{p_{3}}) = 2$ 2个2阶循环 $(r^{2} + b^{2} + g^{2})^{2}$
$\bar{p_{4}} = (1, 2, 3, 4)$ $c(\bar{p_{4}}) = 1$ 1个4阶循环 $(r^{4} + b^{4} + g^{4})$

(2) 翻转

翻转共有 4 种，也就是共有 4 个转轴。分别记为 $\bar{p_{5}}, \bar{p_{6}}, \bar{p_{7}}, \bar{p_{8}}$。

置换 循环个数 具体循环 母函数
$\bar{p_{5}} = (1)(3)(2, 4)$ $c(\bar{p_{5}}) = 3$ 2个1阶循环+1个二阶循环 $(r^{2} + b^{2} + g^{2})(r + b + g)^{2}$
$\bar{p_{6}} = (1, 3)(2)(4)$ $c(\bar{p_{6}}) = 3$ 2个1阶循环+1个二阶循环 $(r^{2} + b^{2} + g^{2})(r + b + g)^{2}$
$\bar{p_{7}} = (1, 2)(3, 4)$ $c(\bar{p_{7}}) = 2$ 2个2阶循环 $(r^{2} + b^{2} + g^{2})^{2}$
$\bar{p_{8}} = (1, 4)(2, 3)$ $c(\bar{p_{8}}) = 2$ 2个2阶循环 $(r^{2} + b^{2} + g^{2})^{2}$

8 个置换 Polya 定理求总数

将 Polya 中引进母函数

化简后得到

其中的项是染色方法，系数是方法的方案数。上式中系数相加刚好是 21。

化简过程可以通过 Python 的 sympy 辅助。代码如下

expand 的功能就是对表达式展开。

1
2
3
4
5
6
import sympy
b = sympy.symbols("b")
r = sympy.symbols("r")
g = sympy.symbols("g")
pg = 1/8*((b + r + g)**4 + 2*(b**4 + r**4 + g**4) + 3*(b**2 + r**2 + g**2)**2 + 2*(b**2+r**2+g**2)*(b+r+g)**2)
sympy.expand(pg)

得到的答案如下

1
1.0*b**4 + 1.0*b**3*g + 1.0*b**3*r + 2.0*b**2*g**2 + 2.0*b**2*g*r + 2.0*b**2*r**2 + 1.0*b*g**3 + 2.0*b*g**2*r + 2.0*b*g*r**2 + 1.0*b*r**3 + 1.0*g**4 + 1.0*g**3*r + 2.0*g**2*r**2 + 1.0*g*r**3 + 1.0*r**4

母函数型 Polya 的完整描述

对比 Polya

其中 m 就相当于是使用颜色的方案(使用 m 个颜色)

如果再细化一下，假设对 n 个对象具体用 $b_{1}, b_{2}, …, b_{m}$ 这 m 个颜色，则将

改为

代替即可。

母函数型 Polya 例题

题目1

等边三角形 r, g, b 三着色，有多少种方案

还是首先考虑置换群

置换 个数 母函数
$(3)^{1}$ 2 个 $2(r^{3} + g^{3} + b^{3})$
$(1)^{1}(2)^{1}$ 3 个 $3(r + g + b)(r^{2} + g^{2} + b^{2})$
$(1)^{3}$ 1 个 $(r + g + b)^{3}$

用三个 r 的方案数，找 $r^{3}$ 的系数

用两个 g 一个 b 的方案数，找 $g^{2}b$ 的系数

题目2

4个红珠子，放在正6面体4个顶点上，有多少方案。

还是首先研究置换群: 正六面体顶点着色的置换群

置换形式 置换 该置换的个数 母函数
不动 $(1)^{8}$ 1 $(r+b)^{8}$
面面中心,旋转 90 $(4)^{2}$ 2 种方向, 3 种转轴, 6 $(r^{4}+b^{4})^{2}$
面面中心,旋转 180 $(2)^{4}$ 1 种方向, 3 种转轴, 3 $(r^{2}+b^{2})^{4}$
棱中对棱中, 旋转 180 $(2)^{4}$ 6 种转轴, 6 $(r^{2}+b^{2})^{4}$
对角线为轴旋转 120 $(1)^{2}(3)^{2}$ 2 种方向, 4 种转轴, 8 $(r+b)^{2}(r^{3}+b^{3})^{2}$

综合以上各个置换的形式及其个数。$|\bar{G}| = 24$

用 r, b 这 2 种色对 8 个顶点着色的方案数可以直接用 Polya，如下

但这里我们限定必须是 4 个红色，4 个蓝色，就需要用母函数型 Polya 展开，找 $r^{4}b^{4}$ 的系数

首先我们写出母函数型 Polya

化简后找到 $r^{4}g^{4}$ 的系数即可。

题目3

骰子6个面，1~6 点数，有多少种组织方式

首先研究置换群: 正六面体面着色的置换群

六种颜色记为 a, b, c, d, e, f，写出母函数型 Polya 后，找 abcdef 的系数即可。

置换形式 置换 该置换的个数 母函数
不动 $(1)^{6}$ 1 $(a + b + c + d + e + f)^{6}$
面面中心, 旋转 90 $(1)^{2}(4)^{1}$ 2 种方向, 3 种转轴, 6 $(a + b + c + d + e + f)^{2}(a^{4} + b^{4} + c^{4} + d^{4} + e^{4} + f^{4})$
面面中心, 旋转 180 $(1)^{2}(2)^{2}$ 1 种方向, 3 种转轴, 3 $(a + b + c + d + e + f)^{2}(a^{2} + b^{2} + c^{2} + d^{2} + e^{2} + f^{2})^{2}$
棱中对棱中旋转 180 $(2)^{3}$ 6 种转轴, 6 $(a^{2} + b^{2} + c^{2} + d^{2} + e^{2} + f^{2})^{3}$
对角线为轴旋转 120 $(3)^{2}$ 2 种方向, 4 种转轴, 8 $(a^{3} + b^{3} + c^{3} + d^{3} + e^{3} + f^{3})^{2}$

用 sympy 展开，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import sympy
a = sympy.symbols("a")
b = sympy.symbols("b")
c = sympy.symbols("c")
d = sympy.symbols("d")
e = sympy.symbols("e")
f = sympy.symbols("f")
pg = 1/24*((a+b+c+d+e+f)**6
           + 6*(a+b+c+d+e+f)**2 * (a**4+b**4+c**4+d**4+e**4+f**4)
           + 3*(a+b+c+d+e+f)**2 * (a**2+b**2+c**2+d**2+e**2+f**2)**2
           + (a**2+b**2+c**2+d**2+e**2+f**2)**3
           + (a**3+b**3+c**3+d**3+e**3+f**3)**2
           )
z = sympy.expand(pg)
print(z)

得到的展开式长度非常长，其中 abcdef 的系数为 30。这与我们之前用 Burnside 的结论相同。

题目4

正四面体，点 4 着色，面 3 着色，棱 2 着色，求方案数

同时考虑顶点置换，面置换，棱置换的 Polya

题目5

4个球 a, a, b, b，放入 3 个不同盒子，求方案数
如果不允许空盒子，求方案数

法1: 容斥原理
法2: 母函数型 Polya

图的计数

引子

n个顶点的简单图有多少种(完全图的二着色)

首先还是研究置换群: 完全图的置换，与立方体的区别是它不再是刚体，例如可以只交换上方的两个点而其余点的位置不变，此时边随点动。

  • 不仅仅旋转和翻转
  • 对应点的全置换，即对称群

4顶点完全图对应 $S_{4}$ (所有 4 阶排列)

题目

4个顶点不同构的图的个数

$S_{4}$ 的每个置换，对应 6 条边的集合上的一个置换

4个顶点不同构的有向图的个数

还是枚举顶点置换，考虑边置换

Share