algorithm - 排列数

Question

假设我们有n个元素，a₁，a₂， ...，a_n，排列成一个圆圈。即a₂介于a₁和a_3之间，a₃介于a₂和a_之间>4，a_n介于a_n-1 和 a₁，等等。

每个元素的值可以是 1 或 0。如果有相应的 a_i 的值，则两种排列是不同的不同。例如，当 n=3 时，(1, 0, 0) 和 (0, 1, 0) 是不同的排列，即使它们在旋转或反射下可能是同构的。

因为有n个元素，每个元素可以取两个值，所以总排列数为2ⁿ。

这里是问题:

有多少种可能的排列方式，使得没有两个相邻元素的值都为 1？如果有帮助，请仅考虑 n>3 的情况。

我问这里有几个原因:

1. 这是我在解决编程问题时出现的
2. 听起来这个问题可能受益于 bool 逻辑/位算术
3. 也许没有封闭的解决方案。

Answer 1

我们先问“有多少个长度为n且没有连续两个1的0-1序列？”设答案为 A(n)。我们有 A(0)=1(空序列)、A(1)=2(“0”和“1”)和 A(2)=3(“00”、“01”和“10”，但是不是“11”)。

为了更容易编写循环，我们将 A(n) 计算为两个数字的总和:
B(n)，以0结尾的序列的个数，以及
C(n)，以 1 结尾的此类序列的数量。

那么B(n) = A(n-1)(取任何这样的长度为n-1的序列，并附加一个0)
和 C(n) = B(n-1)(因为如果你在位置 n 有一个 1，你必须在 n-1 有一个 0。)
这给出 A(n) = B(n) + C(n) = A(n-1) + B(n-1) = A(n-1) + A(n-2)。 现在应该很熟悉了:-)

A(n) 就是斐波那契数 F_n+2，其中斐波那契数列定义为
F₀=0, F ₁=1，且 F_n+2= F_n+1+F_n 对于 n ≥ 0。

现在回答你的问题。我们分别统计a₁=0和a₁=1的排列数。对于前者，a₂ … a_n 可以是任何序列(没有连续的 1)，所以数是 A(n-1)=F_n+1。对于后者，我们必须有 a₂=0，然后 a₃...a_n 是任何没有连续 1 的序列 以 0 结尾，即 B(n-2)=A(n-3)=F_n-1。

所以答案是 F_n+1 + F_n-1。

_{实际上，我们可以比这个答案走得更远。请注意，如果您将答案称为
G(n)=Fn+1+Fn-1，则
G(n+1)=Fn+2+Fn，且
G(n+2)=Fn+3+Fn+1，所以即使G(n)也满足和斐波那契数列一样的递归! [实际上，类似斐波那契数列的任何线性组合都将满足相同的循环，所以这并不奇怪。]所以计算答案的另一种方法是使用:
G(2)=3
G(3)=4
对于 n≥4，G(n)=G(n-1)+G(n-2)。}

现在您还可以使用 closed form F_n=(αⁿ-βⁿ)/(α-β)(其中α和β为(1±√5)/2、x²-x-1=0)的根，得到
G(n) = ((1+√5)/2)ⁿ + ((1-√5)/2)ⁿ。
[您可以忽略第二项，因为它对于大 n 非常接近 0，实际上 G(n) 是最接近 ((1+√5)/2)ⁿ 的整数/strong> 对于所有 n≥2。]