知乎上的一个问题“如何用100颗相同石头实现最大计数范围？”

这个问题挺有意思，可惜它不够严谨喵。题主强调距离和角度都没有意义，这在数学里不就是拓扑吗。

没错就是序类型（Order Type），但是序类型是不允许三点共线的，我需要改一下定义。

定义三个点的旋转方向为：逆时针、顺时针、共线（就是叉积大于 / 小于 / 等于 0）。

如果两个点集 A, B，它们存在一个双射 f，对任意 i, j, k 都有 $A_i,A_j,A_k$ 的旋转方向和 $f(A_i),f(A_j),f(A_k)$ 相同，那么它们有相同的序类型。

---

序类型计数当然有人研究，就是 OEIS A063666 (opens new window)（当然这是不共线的情况）。精确值没法算，我让 AI 给了个下界 $OT(n)>2^{2.076n\log_2 n}$，100 代进去大概 $2^{1379.26}$ 也就是 $1.58\times 10^{415}$。

---

但是看不懂有什么用呢，所以我给出一个 $7.38\times 10^{253}$ 下界的构造。

题主给的“R^2 上的 m 个点最多可把该平面划分成几个区域”非常有启发喵。我们注意到点集的凸包是一个良好的结构，可以利用凸包对角线对平面划分区域，剩下的点放在不同的区域，就实现计数了。

凸包的 $k$ 个顶点，可以划分的最大区域数为：

$R(k) = 1 + 2\binom{k}{2} + 4\binom{k}{4}$

注意区域包含了：两两对角线交点 $\binom{k}{4}$ 个，边或对角线被截的线段 $\binom{k}{2}+2\binom{k}{4}$ 个，边或对角线截出来的范围 $1+\binom{k}{2}+\binom{k}{4}$ 个。

而剩下 $n-k$ 个点放入 $R(k)$ 个区域，每个区域最多放 1 个（看起来放更多对结果贡献不大），方案数是 $\binom{R(k)}{n-k}$。

但是因为旋转和翻转的对称性，我们除以 $2k$。

import math


def get_regions(k: int) -> int:
    return 1 + math.comb(k, 2) * 2 + math.comb(k, 4) * 4


if __name__ == "__main__":
    n = 100

    sum = 0
    for k in range(4, n + 1):
        r = get_regions(k)
        sum += math.comb(r, n - k) // (k * 2)

    print(float(sum))

方案数 $7.38\times 10^{253}$。

---

以上内容是 AI 教我的，毕竟我对数学的全部理解仅限于科普。其实我一开始想到一个问题定义，AI 看了后告诉我序类型才是正经数学概念。

定义“保共线同痕”为两个点集之间存在一个连续变化，对于任意三个点 A, B, C：

• 如果一开始 A, B, C 共线，那么它们始终共线。
• 如果一开始 A, B, C 不共线，那么它们始终不共线。