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 回答