Burnside 引理

在分析群对于集合作用时，Burnside 引理是一个非常重要的定理：

Burnside 引理

设有限群 作用于有限集 上，则 在 作用下的轨道数目为

其中 为元素 在 上的不动点数目。

对于这一引理的证明，有许多参考¹²，这里不再赘述。

布尔函数计数问题

问题背景

布尔函数是一类重要的函数，满足 的映射形式。通常我们用 0 和 1 来表示 中的两个元素，而 中的元素可以用长度为 的二进制串来表示。一些常见的 2 元布尔函数及其真值表如下：

1. 逻辑与：

   x	y	f(x, y)
   0	0	0
   0	1	0
   1	0	0
   1	1	1

2. 逻辑或：

   x	y	f(x, y)
   0	0	0
   0	1	1
   1	0	1
   1	1	1

3. 逻辑同或：

   x	y	f(x, y)
   0	0	1
   0	1	0
   1	0	0
   1	1	1

布尔函数还可以用开关线路来表示，如下图所示：

可以看出来这三个开关线路中两个开关是可以交换的，即有些布尔函数在自变量的置换下是等价的。因此便引出了布尔函数的计数问题：对于 元布尔函数，有多少个本质不同的布尔函数？

观察 2 元布尔函数

我们先来看看所有的 元布尔函数的真值表：

考虑两个元素的置换，即置换群 ，那么符合 的布尔函数被认为是实质相同的。可以看出，上表中符合该条件的成对布尔函数有：

• 和
• 和
• 和
• 和

因此， 元布尔函数的本质不同的函数个数为 。

那么如何用 Burnside 引理来分析呢？将 中元素按置换类型分类计数，并列出其作用于 上的不动点数目：

对 类型的置换，不动点的数目即先对每个自变量进行选择 ( 共 4 个)，再对结果进行选择，因此有 个不动点；对 类型的置换，不动点的数目即先对捆绑在一起的 2 个自变量进行选择 (00、01 和 10、11 共 个)，再对结果进行选择，因此有 个不动点。

因此，由 Burnside 引理， 元布尔函数的本质不同的函数个数为：

3 元布尔函数

对于 元布尔函数，我们直接将 的元素按置换类型分类计数：

与 元布尔函数相比， 元布尔函数的表中出现了 类型的置换。考虑将 3 个自变量捆绑后在循环移位下本质不同的组合有 4 个：000、001、011、111，因此有 个不动点。

因此，由 Burnside 引理， 元布尔函数的本质不同的函数个数为：

更一般的情形

显然，对于 元布尔函数，我们的任务都是在对 中元素按类型分类后寻找不动点的数目。而这里的不动点数目则拆分为了每个轮换对应的组合的数目。例如，轮换对应了 6 个组合：0000、0001、0011、0101、0111、1111，因此一个 的置换会对应于 的不动点数目。

另：或许找这种组合对应于一个类似的应用问题，但我暂时还没有想到。