1

時計回りの円の中に 1 から N までの番号が付けられた N 個の点が固定されています。任意の 3 点を選択して三角形を作成します。

三角形はいくつでも作成できますが、2 つの三角形が交差してはならず、1 つの点で共有できる三角形は 1 つだけです。では、そのような構成はいくつ可能ですか?

たとえば、10 個のポイントがあるとします。

  • 点 1、2、3 は三角形を作成でき、この三角形のみが存在する場合は 1 つの構成になります。
  • 三角形 (2,3,4) のみがその他の構成になります。
  • 三角形 (1,2,3) と (4,5,6) は他の配置を形成します。
  • (2,4,5) は三角形にもなり得ます
  • (2,4,5) と (1,3,6)は、2 つの円が交差するため、構成にすることはできません。

部分的に解決できました：

  • 三角形が 1 つだけの場合、nC3 ウェイで任意の 3 点を選択して三角形を作成できます。
  • 2 つの三角形の場合、nC6 ウェイで任意の 6 点を選択でき、3 つのウェイで 2 つの三角形を形成できます。

より多くの三角形を解くことができません。

4

1 に答える 1

2

以下の考慮事項については、「三角形がまったくない」ことも有効な構成として扱いたいと思います。最後に 1 を引いて、それを取り除くことができます。

これを再帰的に考えてみましょう。n 個の点が与えられた場合、2 つのオプションがあります。「三角形をまったく使用しない」を選択して戻るか、3 つの点を選択して 1 つの三角形を形成してから再帰するかです。3 つの角がある場合は、円が 3 つの範囲に分割されます。後続のすべての三角形は、1 つの範囲からコーナーを持たなければなりません。これらの範囲のいずれかに制限すると、最初の三角形と交差しなくなります。再帰のために、これらの範囲のそれぞれを小さな円のように扱うことができます (交差点に関するステートメントがそこでも有効であることを自分で確認してください)。

OK、上記はすべての可能な順序付けられた三角形のシーケンスを生成します。秩序を気にしないなら、どうにかして排除しなければなりません。1 つの可能性は、各カウントをn で割ることです。ここで、nは最終的に生成される三角形の数です。もう 1 つの方法は、三角形の完全な順序 (つまり、最小コーナー インデックスによる順序) を修正し、再帰が以前に選択された三角形よりも小さい三角形を生成しないようにすることです。

これらのアイデアを使用すると、いくつかのポイントの三角形構成を列挙する小さなスクリプトを作成できるはずです。いくつかのケースを手動でチェックできる場合もあります。おそらく、そのスクリプトがあれば十分です。そうでない場合は、そのシーケンス (「三角形がまったくない」ため、オフセットの有無にかかわらず) をOn-Line Encyclopedia of Integer Sequences™</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 に答える