permutation - 找到选择项目的总方法，使得没有两个是连续的

Question

一行中有 n 个项目。我们必须在不能选择两个连续项目的限制下找到可以选择项目的方式数。

我试图用递归关系来做，但无法达到任何。请帮我解决问题。

Answer 1

在网上搜索后，我得到了上述问题的解决方案。

假设有 N 个项目。如果 N 是偶数，我们可以选择几乎 N/2 个项目，使得没有两个是连续的，如果 N 是奇数，我们可以选择几乎 (N+1)/2 个项目。设 K 是可以选择的最大项目数。

我们可以选择 1 到 K 个项目。

• 对于选择一个项目，我们可以选择任何项目。

• 为了选择两个项目，我们将 N-2 个项目保持在一个序列中。下面的圆圈代表序列中的项目。从第一项的左侧到最后一项的右侧，我们总共有 N-1 个空格。空格由“_”下划线表示。如果我们选择任意空格中的两个，并将它们替换为 item，那么我们将有 N 个 item，并且选择的两个 item 不会是连续的，因为没有两个空格是连续的。

                _ o _ o _ o _ o _ o _ o _ o _ o _ o _ o _
  

• 为了选择 p 个项目，我们将在序列中保留 N-p 个项目，这将导致 N-p+1 个空格。我们可以从这些 N-p+1 个空间中选择任意 p 个空间。

所以所有可能的方式将变成
^NC₁ + ^N-1C₂ + ^N-2C< sub>3 + ... + ^N-K+1C_K 是前 N 个斐波那契数 (1,1,2,3, 5，...)。
前 N 个斐波那契数的总和也是 F(n+2) - 1