Advanced Mathematics Support Programme(AMSP)例题分析

本月的每月一题，笔者将介绍一个有趣的问题。它出现在两个多月以前的AMSP（Advanced Mathematics Support Programme）一次培训的讨论课当中，由笔者的一位朋友提供，但并非AMSP官方给出的培训题。之前我们不太关注这项培训，但是自从这个题目的出现，笔者发现此项目非常适合中等难度的竞赛，如果有条件或者在英国读书的学生是很推荐参加的。

题目的叙述比较简单，其中Note部分是对这个题目的一些严谨补充：

Somepeople stand in a circle with their eyes closed. On command, they allopen their eyes. Each person picks some other person at random andstares fiercely at that person. If two people find that they arestaring at each other, they screamand drop out of the circle. Sometimes several pairs might drop out atonce. If nobody drops out, it is called a “quiet round.” If there are n people in the circle, what is the probability that the next round will be aquiet round?

一群人闭眼站成一圈。他们会根据一声命令同时睁开眼睛，并且每个人都会随机地选一个其他人，盯着他的眼睛看。如果两个人发现他们在互相盯着看对方，他们会尖叫并退出这个圆圈。有时候会有很多对人同时尖叫并退出圆圈的情况，但如果没有人退出圆圈，则这是一个“安静回合”。如果有n个人站在圆圈中，下一个回合是“安静回合”的概率是多少？

Note：Assume that the game is just starting out, and has n peopleplaying.
Around consists of

1)everyone has their eyes closed

2)everyone opens their eyes on command and stares at someone else atrandom.

3)if two people find that they are staring at each other, the screamand are out.

4)end of round.

So a quiet round is one in which no one screams. ("next" doesnot necessarily mean that there was a round before it)

据本题的提供者所说，这是今年AMSP中一位教授给出的题目，当时整个地区（AMSP依据东英格兰、伦敦和西部等地划分为地区性质的培训）没有一位学生做出。这位教授认为此题是根据MAA出版的老杂志当中的一些结论改编的，其最初的结果应当属于MAA官方。这道题目本身其实很简单，读者可以自己试着解它。

分析：这个题目在杂志上的原题应当是抽象代数中的结论，但是经过改编以后，本题又和置换群Sn不太一样，因为如果同时有多个人看向同一个人,这就不是一个置换了。但我们仍然可以借助映射的手段，将这个题目做一个等价：

其中条件(i)指的是一个人不能看向他自己，(ii)指的是每个人看向的人，不能看向自己。

这个题目的前身，应当是修改其中的staring条件：每个人恰好被一个人看向了。这样的话它就变成了Sn中不含对换的置换数全体。这个问题也可以等价成2-regulargraph的简单图数。

这个问题的推广形式是n-vertex,k-regular simple graph的个数，它在AIME和AMC难题当中常常以小的n和k形式出现,并有时伴随了BurnsideLemma的考点（需要考生自己去计算它的同构群）。

McKayand Wormald是第一个提出最一般的结果的数学家，他们得到了n-vertex,k-regular simple graph的个数趋近于：

其中

这里我们讨论它的渐进值是因为这个值不是一个简单的二元函数(on n,k)。但是在k=2的时候，我们可以再次（在每月一题当中，这个技术出现了很多次）使用我们最熟悉的工具，人类最好的伙伴：递推（recursion）来解决这个1990年图论研究的热门问题的初级版本。

首先借用Conway提出的PartitionFunction：

Definition P(n), the partition function, gives the number of ways of writing the integer as a sum of positiveintegers, where the order of addends is not considered significant.

例如：

4=4

=3+1

=2+2

=2+1+1

=1+1+1+1.

从而P(4)=5。

设an是n-vertex,2-regular simple graph 的个数。

因为an的组合性质等价于把n分成每个部分都不小于3的全部方法，故根据容斥原理我们有

Homework：熟悉GeneratingFunction的读者可以尝试推导它的生成函数，也许会用到q-Pochhammer。