我们知道在 LOL（英雄联盟）中，猫咪是可以进入队友身体的，如果 LOL 再出 5V5 克隆模式（我猜不可能），如果某一方选了猫咪这个英雄，场面上会有多少种状态呢（不考虑死亡）？

这个问题在 2019 年 5 月猫咪刚出来的时候就在 好好做人群 讨论并给出了结论，只是没写成程序

答案是：1296 （可以先拉到最后）

问题数学化

每只猫可以进入其他猫咪的身体，求（我们更关心 $a_n$）：

  • $n$ 只不同的猫咪，会有 $a_n$ 种状态

  • $n$ 只相同的猫咪，会有 $b_n$ 种状态

我们想要得到 $a_n$ 和 $b_n$ 的表达式或者递推公式，然后写程序求 $a_n, b_n$

为了方便，我们约定 $a_0 = b_0 = 1$

问题求解

我们可以根据能看到的猫咪数量 $r$ ，来分情况讨论，

我们先考虑相同猫咪的情况，简单一点 下面分析全错！！！

例如，如果 $r=1$，那么其它猫咪都进入了某一只猫咪的身体，有 $b_{n-1}$ 种情况，类似的我们其实可以得到如下公式：

$r$ 只可见的猫，分别真实包含了 $x_1, \cdots, x_r$ 只猫，而这 $x_i$ 只猫有一个在最外面，所以它的内部有 $b_{x_i - 1}$ 种可能。

$b_1 = 1, b_2 = 2$ 是显然的。我们来计算$b_3, b_4, b_5$

$3 = 1+2 = 1 \times 3$，所以

$4 = 1+3 = 2+2 = 1+1+2 = 1 \times 4$, 所以

类似的对 5 做分解可知：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#正整数拆分 n = x_1 + x_2 + ... + x_r, 且 x_i >= low
#low 表示递归的时候最小取值
#ans 保存递归得到的前部分
def naturalcut(n, r, low, ans = []): 
	if r <= 1: 
		yield ans+[n]
	else:
		for i in range(low, 1 + n//r):
			yield from naturalcut(n-i, r-1, i, ans +[i])

def allcut(n):
	b = []
	for i in range(1,1+n):
		b += list(naturalcut(n,i,1))
	return b

# 上面两个函数和后面代码出现两个类似的函数完全是一致的，只是表现形式不一样
# 上面的简单明了，后面的效率更高一点，所以两个都保存了。

def getbn(n):
	if n <= 1:	return 1;
	bn=[1]
	for t in range(1,1+n):
		bn.append(0)
		for x in allcut(t):
			product = 1
			for i in x:
				product *= bn[i-1]
			bn[-1] += product
	return bn

for i,x in enumerate(getbn(8)):
    print(str(i)+'只相同猫咪有 '+ str(x)+'种状态')

我们现在考虑不同猫咪的情况

我们依然根据猫咪在场上的数量 $p_1 + \cdots +p_r$ ，对猫咪进行讨论，则有

真实包含了 $x_i$ 只猫的猫有 $p_i$ 只 (这也是为什么$x_i$ 严格递增)，

$x_i^{p_i}$ ：每只猫都要选择一个出来当最外面的猫

$a_{x_i - 1}^{p_i}$ ： 去掉最外面的猫，里面有 $x_i - 1$ 只猫

最后一个式子，经典排位组合问题就不提了。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#正整数拆分 n = x_1p_1 + ... + x_rp_r, 且 low<=x_1<...<x_r
#low 表示递归的时候最小取值
#ans 保存递归得到的前部分
def naturalcuts(n, r, low, ans = []): 
	if r == 1: 
		for i in range(1,1+n//low):
			if n%i == 0:	yield ans + [(n//i,i)]
	elif r >1:
		x = n - r*(r-1)//2;
		for i in range(low, 1 + x//r):
			for j in range(1, x//i - r +2):
				yield from naturalcuts(n-i*j,r-1,i+1,ans + [(i,j)])

def allcuts(n):
	a = []
	for i in range(1,1+n):
		a += list(naturalcuts(n,i,1))
	return a

import math 
def getan(n):
	an = [1];
	for t in range(1,1+n):
		an.append(0)
		factn = math.factorial(t)
		for item in allcuts(t):
			product = factn
			for x,p in item:
				product //= math.factorial(x)**p
				product //= math.factorial(p)
				product *= an[x-1]**p
				product *= x**p
			an[-1] += product
	return an

print(getan(10))	#9只不同猫咪状态数是 100000000（正好一亿）!!! 这也太整了吧

代码能如此简洁多亏了，Python 的这个生成器写法太优美了！！！

当然了，如果只是 5 只猫咪，那我们其实也可以枚举出所有情况得到 $a_n = 1296, b_n = 20$：

0

以下内容更新于 2020/3/17

在和我大学同学 祺祺 讨论之后，他猜测 $a_n = (n+1)^{n-1}$，一开始我是不相信的，不过数据对比之后发现，卧槽，秀啊。所以说明有一种更优美的理解：

假定 LOL 峡谷地图实际上在一只超大的 $0$ 号猫咪肚子里面，那么这些猫咪就构成了以 $0$ 为根的树，我们求得这 $n+1$ 个（有编号）节点无根树个数，然后我们把 $0$ 号节点变成根，就得到了我们所有的状态。

$n$ 个节点的无根树个数是 $n^{n-2}$，最早于 A.Cayley 在 1889 年首先公布并证明（现在看来不算严谨的证明），后来有了树的 Prufer 编码，就可以漂亮的解决证明这个问题了。可参考 Matrix67 的博客 或下面说明

Prufer 编码

$n$ 个节点的无根树（也就是简单无向图），可以唯一的给出一个长度为 $n-2$ 的编码，同样每一个长为 $n-2$ 的编码都可以唯一的产生一棵 $n$ 个节点的无根树 （这就证明了上面结论）

给定一颗 $n>2$ 个节点的无根树，每次找出无根树中，度数为 $1$ 的节点中编号最小的节点 $A$，记录节点 $A$ 的邻接点，然后删除节点 $A$ 和它的边。这样一直继续下去，直到只剩下两个节点。

度数为 $i$ 的节点恰好在 Prufer 编码中出现 $i-1$ 次

给你一个长度为 $n-2$ 的 Prufer 编码，我们只要找出 没有在当前编码中最小的 跟编码中第一个节点相连即可。重复下去即可得到无根树。

后来我发现，我 $b_n$ 算错了！！！，因为很多情况算重复了，为了算 $b_n$

上述公式包括 正整数拆分 和 给相同的球染色问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#正整数拆分 n = x_1p_1 + ... + x_rp_r, 且 low<=x_1<...<x_r
#low 表示递归的时候最小取值
#ans 保存递归得到的前部分
def naturalcuts(n, r, low, ans = []): 
	if r == 1: 
		for i in range(1,1+n//low):
			if n%i == 0:	yield ans + [(n//i,i)]
	elif r >1:
		x = n - r*(r-1)//2;
		for i in range(low, 1 + x//r):
			for j in range(1, x//i - r +2):
				yield from naturalcuts(n-i*j,r-1,i+1,ans + [(i,j)])

def allcuts(n):
	a = []
	for i in range(1,1+n):
		a += list(naturalcuts(n,i,1))
	return a

import math 

def getbn(n):
	if n <= 1:	return 1;
	bn=[1]
	for t in range(1,1+n):
		bn.append(0)
		for item in allcuts(t):
			product = 1
			for x,p in item:
				product *= math.comb(bn[x-1]+p-1,p)
			bn[-1] += product
	return bn

print(getbn(10))

这正好是 $n+1$ 个无编号的有根树个数