不会洗牌的数学家不是好魔法师

　　在前一篇文章中，我们介绍了魔术师可以用洗牌来做什么。但是，数学家在洗牌的时候会怎么做呢？为此我们咨询了来自西澳大利亚大学的教授谢丽尔·普拉格（Cheryl Praeger），普拉格主要从事群论的相关研究——这是一个和对称性相关的数学领域。普拉格2020年在艾萨克·牛顿研究所进行过一次相关话题的有趣讨论。在她回到澳大利亚之后，我们和她有过交流，她向我们分享了一些关于群论和洗牌的关系的迷人见解。

　　谢丽尔·普拉格

　　数学家利用完美洗牌可以做什么？

　　我们首先来数一下通过洗牌操作可以产生多少种可能的置换。我们从一副k张牌组成的牌组开始，可以知道在洗牌操作之后，第一张牌所处的位置有k种不同的选择。而留给第二张牌的空位只剩下了k-1个，留给第三张牌的空位只剩下了k-2个，以此类推。那么所有可能的重排的总数是 k x (k-1) x (k-2) x ... x 2 x 1，或者叫做 k的阶乘，记作 k!。k张牌组成的牌组的所有可能的置换构成了一个对称群，这个群中的元素个数是k!。举个例子，对于6张牌构成的牌组，对称群中有720（6! = 6x5x4x3x2x1 = 720）种可能的置换。

　　而普拉格感兴趣的则是通过完美洗牌（牌组被分成两等份，洗牌之后牌被一张一张交叠在一起）能够获得的置换。完美洗牌有两种方式：外洗法（第一张牌和最后一张牌位置固定）和内洗法（第一张牌和最后一张牌在洗牌之后都移动了一位），具体操作这篇文章有提到。我们考虑这两种完美洗牌的方式的任意组合——你可以只做一次内洗操作，或者做三次内洗操作加一次外洗操作，再或者连续做八次外洗操作都可以。

　　这样你通过所有的内洗操作和外洗操作的组合得到的卡牌的置换就构成了一个群，我们叫它“洗牌群”（shuffle group）。它并不包含牌组所有可能的置换。举个例子，6张牌构成的牌组，它的对称群里有720种可能的置换，而洗牌群里就只有24种。但是这两个群都有一个重要的数学特性。

　　威尔·休斯敦展示如何完美洗牌（来源：https://youtu.be/2TTrHmFC2bM）

　　洗牌群

　　洗牌群和对称群都有所谓的群结构。从数学上讲，群是以满足四个规则的、以特定方式组合的对象（object）的集合（详细信息可以看这里)。例如，在我们的洗牌群中，对象是由两种类型的完美洗牌方式组合生成的洗牌。

　　洗牌群是封闭的：如果您将群中的任意两个洗牌组合在一起，得到的洗牌也将是完美洗牌的组合，一般的洗牌群也是如此。

　　每个洗牌都有逆元：一种洗牌再配上它的倒序洗牌，相当于没有进行洗牌操作。例如，我们在上一篇文章对于一副52张牌的牌，一次外洗法，再配上连续7次外洗法，你就会回到原来的牌组顺序。所以单次外洗的逆元是7次外洗组合起来。对于任何大小相等的牌组的洗牌群和更大一点的对称群，都满足作为群的所有规则。

　　对于群论学家来说，一个关键的操作是如何将一个有限的群分解成它的基本组成部分——我们称之为称为单群（simple group）。“通常你可以把一个群分成两部分，这样每个部分都又构成一个群，你可以继续这样做下去。”普拉格说，“它就像一棵树的分枝，分枝后面还有分枝，直到得到一个不可能再分裂它的阶段，这就像到了树的叶子。当你找到树上的叶子时，我们称之为单群，因为到了这一步它们就不能被进一步划分了。”

　　以这种方式研究一个群的话会发现很多有用的信息。比方说，你可以通过将树上所有单群的大小相乘来判断群的大小。“将一个群分解成单群是一个非常有用的工具，也是群论学家首先要寻找的东西之一。”

　　中心对称

　　一个早期的关于洗牌群的有趣结论在20世纪80年代被数学家佩尔西·戴康尼斯（Persi Diaconis）、罗纳德·葛立恒（Ronald Graham）和威廉·康特（William Kantor）所证明。“他们发现并解释了一个非常优美的性质就是所谓的中心对称性。”普拉格说，“你可以把这副牌中的最顶上和最底下两张牌看作是是相互关联的。在任何一系列完美的洗牌操作之后——假设最上面的牌移到了第三的位置，那么最后一张牌就会升到倒数第三的位置——这是一种对称性，无论对两张牌中的一张做了什么，另一张都会模仿它。”所以说，如果在一系列完美的洗牌之后，最上面的一张牌的位置在从上到下数的一个特定位置，那么你就可以知道最后一张牌在从下往上数的同一位置。

　　戴康尼斯、葛立恒和康特的论文

　　每一对处在对称位置的牌都会出现同样的事情：位于牌组中心附近相同距离的两张牌相互关联，并且总是一起通过内洗或者外洗来移动。“一对牌被一同洗来洗去，就好像他们有某种无形的联系。而完全随机的洗牌——不是这些完美的洗牌，则根本就没有这种特性。”这种中心对称性对洗牌群中牌组的可能的置换产生了一些实际的限制。

　　戴康尼斯、葛立恒和康特证明了，对于具有中心对称性的洗牌群，它的单群是非常受限制的。一个影响是对于于洗牌群的大小，这取决于相关联的单群的大小。对于大多数的牌组，洗牌群将是巨大的（这是相对于牌组中牌的数目而言的，尽管它比完全对称群要小得多）。而且通常洗牌群的规模会随着牌组中牌的数目呈现指数级增长。

　　如果你有一副6张牌，在它的洗牌群中有24种可能的置换。一副10张牌的洗牌群有1920个置换。一组26张牌的洗牌组中有超过25万亿种可能的置换。这些数字说明，洗牌群的规模随着牌组规模的增加呈指数级增长。

　　但是当牌组的规模大小是2的幂次时，一件令人惊奇的事情发生了，数学家称之为幂律特例（power case）。对于一套14张牌的牌组，它的洗牌群中有超过32万个置换。但是对于16张牌的牌组的洗牌群——16张是24——只有64种可能的置换！一套30张牌的牌组就有千万亿（1015)种可能的置换，但一套32张牌组成的牌组——32是25——它的洗牌群中只有160个可能的置换。当牌组的规模大小是2的幂次时，它会产生一个非常小的洗牌群。

　　“这个幂次的例子真的是不可思议，”普拉格说，“在这种情况下，洗牌群的大小要比典型的规模小了很多倍。”她解释说，在幂指数的情况下，洗牌群的唯一组成部分是循环群——它们是最小的单群。构建洗牌群的模块都如此之小，意味着洗牌群也显著地变小了：“所以没什么奇怪的！”(更多关于循环群的信息可以看这里)

　　一些有趣的工作

　　事实证明，类似的幂律特例也适用于“多手（many handed）完美洗牌”，这是普拉格与她的同事卡门·阿马拉（Carmen Amarra）和卢克·摩根（Luke Morgan）在2019年探索过的。当他们访问她的研究小组时，普拉格想起了一张藏在抽屉底部的、写满了旧数据的纸。“它在我的抽屉里放了几十年了！”现在正是研究一下的最佳时机。

　　这些数据来自于20世纪80年代肯特·莫里森（Kent Morrison）和约翰·坎农（John Cannon）为多手洗牌做的研究。想象一下，现在我们不是把一副牌分成两个相等的牌堆，而是把它分成像三个相等的牌堆，然后把这三个牌堆完美地交织在一起。又或者我们把一堆东西分成四堆，或者七堆，或者十一堆，然后把这些等份的东西完美地混在一起。

　　“但是后来很多问题涌现了出来，”普拉格说。“你把牌分成k等分的牌堆——然后下一步呢？”你可以按照每个等份从牌堆上分开的顺序，一次一张地从每一个等份的顶部拿起一张牌，这可能就像是进行外洗操作。但是换个方式，如果你决定从第二堆开始拿第一张牌，接着到第七堆拿一张牌，然后到第十五堆，再到第二十七堆呢！现在就有了很多可能的拿牌顺序——当你有很多等分的小牌组时，什么算是一次完美的洗牌？

　　普拉格和她的同事们决定用一种新的方式来思考多手洗牌的问题：他们不仅考虑了你将纸牌分成了多少堆，而且还考虑了如何指定允许的牌堆顺序，这些顺序决定了你在洗牌过程中交叉牌的方式。

　　他们将初始牌组的最上面一个等份标记为0，第二个等份标记为1，依此类推，第k个等份标记为k-1。然后他们就可以研究从牌堆中选择牌的顺序对最终洗牌时牌的重组的影响。

　　通过这种新方法，普拉格、阿马拉和摩根证明了一个难题：在某些情况下，类似于幂律特例的事情也发生在这种多手洗牌中（感兴趣的朋友可以看看这篇论文)。“在我和卡门还有卢克的这次合作中，我们把一副牌组分成k等份，每份有n张牌。我们观察到，当小牌组的大小（n）是小牌组数目（k）的幂时，也存在类似幂律特例的特殊情况。这就像前面提到的2的幂次的标准情况：你又得到了一个非常非常小的洗牌群。”

　　数学家们观察到了这种多手洗牌中的幂律特例。同时也有一些实验证据表明，在非幂律特例的情形下，洗牌群似乎总要大得多。莫里森和另一位数学家史蒂夫·梅德韦杰夫（Steve Medvedoff）在一个猜想中指出，对于多手洗牌的情况下，非幂律特例的洗牌群都将是巨大的。普拉格和她的同事们能够用他们的新方法来证明这个关于非幂律特例的猜想。他们希望涵盖将牌组分成任意数量的等份来进行多手洗牌的情况，从而更广泛地证明这一猜想，但是这一过程中仍有许多开放性的问题亟待处理。

　　开放性的问题和新的视野

　　另外由于他们的新方法，普拉格、卡门和卢克能够发现一些有趣的新结果。他们的新方法考虑到了在洗牌时牌堆的置换。特别是，他们发现“洗牌群”保留了你允许的堆置换的许多性质。如果我们在允许的洗牌方式下定义一种牌堆的传递性的置换群（这意味着你可以通过置换从一个顺序的牌堆变到任意一个其他顺序的牌堆），那么你得到的“洗牌群”也将是可传递的。你可以用某一种洗牌的组合来把任何一张牌移动到牌堆的任何其他位置。这个传递属性只是他们发现“洗牌群”保留的一些群属性中的第一个。同样，还有许多悬而未决的问题。

　　洗牌的数学是表现数学家如何工作的一个很好的例子。在这一情形下，他们从标准的纸牌游戏中进行一次完美洗牌开始，将牌分成两堆——我们已经知道有两种类型的完美洗牌，即“内洗法”和“外洗法”。然后，在研究了这一设定的数学理论之后，他们又对设定和结论进行了外推：将牌堆分成三个、四个，甚至是任何数量相等的堆。他们从一张简单的纸牌开始，起初可能只是是在桌上和朋友一起玩，但是，和往常一样，他们不可避免地开始以数学的眼光看问题。

　　作者：Rachel Thomas

　　翻译：Dannis

　　审校：zhenni

　　原文链接：

　　https://plus.maths.org/content/mathematics-shuffling