1

有固定的 N 个点，编号为 1 到 N，按顺时针方向在圆周上。我们想通过选择任意三个点来创建三角形。

我们可以创建尽可能多的三角形，但没有两个三角形应该相互交叉，一个点只能共享一个三角形。那么有多少这样的配置是可能的呢？

例如，假设有 10 个点：

  • 点 1,2,3 可以创建一个三角形，如果只有这个三角形存在，它将是一种配置。
  • 只有三角形 (2,3,4) 将是其他配置。
  • 三角形 (1,2,3) 和 (4,5,6) 将形成其他配置。
  • (2,4,5) 也可以是三角形
  • (2,4,5) 和 (1,3,6)不能是一个配置，因为两个圆圈会相互交叉。

我可以部分解决：

  • 对于只有一个三角形，我们可以以 nC3 方式选择任意三个点并创建一个三角形。
  • 对于两个三角形，我们可以用 nC6 方式选择任意六个点，并且可以用 3 种方式形成两个三角形

我无法解决更多数量的三角形。

4

1 回答 1

2

出于以下考虑，我也想将“根本没有三角形”视为有效配置。你可以在最后减去一个来摆脱它。

所以递归地考虑这个。给定n个点，你有两个选择：要么选择“根本没有三角形”并返回，要么选择三个点形成一个三角形，然后递归。如果您有三个角，它们会将您的圆圈分成三个范围。所有后续三角形都必须具有来自单个范围的角，否则它们会重叠。如果您将它们限制在其中一个范围内，它们将不会与您的第一个三角形相交。对于递归，您可以将这些范围中的每一个视为一个小圆圈（自己检查关于交叉点的陈述在那里仍然有效）。

好的，上面将生成所有可能的三角形有序序列。如果您不关心顺序，则必须以某种方式消除它。一种可能性是将每个计数除以n！其中n是最终生成的三角形的数量。另一种方法是固定三角形的完整顺序（即按最小角索引排序），并确保递归永远不会生成小于之前选择的三角形。

有了这些想法，您应该能够编写一个小脚本来枚举几个点的三角形配置。您甚至可以手动检查一些案例。也许拥有该脚本就足够了。如果没有，您可以将该序列（由于“根本没有三角形”而带有或不带有偏移）提供给整数序列在线百科全书™</a>，并查看它们是否有适合您的公式。或者自己找一个，可能在生成函数的帮助下。如果一切都失败了，你可能想把它带到Math SE上。

编辑：
除非我在实现自己的小脚本时出错，否则您要求的序列，包括“根本没有三角形”实例，是OEIS A071879。还有一个公式。我使用以下 python 代码生成了该序列：

c = [1, 1, 1]
for n in range(3, 30):
    s = 1
    for i1 in range(0, n - 2):
        for i2 in range(i1 + 1, n - 1):
            for i3 in range(i2 + 1, n):
                s += c[i2 - i1 - 1]*c[i3 - i2 - 1]*c[n - i3 - 1]
    assert len(c) == n
    c.append(s)
    print(s)
于 2012-08-02T20:09:58.787 回答