安排数量

Question

假设我们有ñ元素,一₁,一₂,...,一_ñ,排成一个圆圈.也就是说,一个₂之间一个₁和一个₃,一个₃之间一个₂和一个₄,一个_Ñ是间一_{Ñ -1}和一个₁,等等.

如果有对应的1或0的两个布置是不同的每个元件可以采取的值一个_我其值不同的.例如,当n = 3时,(1,0,0)和(0,1,0)是不同的排列,即使它们在旋转或反射下可能是同构的.

因为有n个元素,每个元素可以取两个值,所以排列的总数是2 ⁿ.

这是一个问题:

有多少种安排是可能的,这样两个相邻的元素都没有值1？如果有帮助,只考虑n > 3的情况.

我问这里有几个原因:

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

Answer 1

让我们首先问一个问题"有多少0-1个长度为n的序列,没有两个连续的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)简单地是Fibonacci数F _{n + 2},其中Fibonacci序列由
F ₀ = 0,F ₁ = 1定义,并且对于n≥0 ,F _{n + 2} = F _{n + 1} + F _n.

现在提出你的问题.我们将分别计算₁ = 0和₁ = 1 的排列数.对于前者,₂ ... a _n可以是任何序列(没有连续的1),因此数字是A(n-1)= F _{n + 1}.对于后者,我们必须有一个₂ = 0,然后一个₃ ... a _n是没有以0结尾的连续1的任何序列,即B(n-2)= A(n-3)= F _{n- 1}.

所以答案是F _{n + 1} + F _n-1.

_{实际上,我们可以比那个答案更进一步.注意,如果你把答案称为
G(n)= F n + 1 + F n-1,则
G(n + 1)= F n + 2 + F n,
G(n + 2)= F n + 3 + F n + 1,所以即使G(n)也满足与Fibonacci序列相同的复发![实际上,Fibonacci样序列的任何线性组合都会满足相同的复发,因此并不是那么令人惊讶.]因此计算答案的另一种方法是使用:
G(2)= 3
G(3)= 4
G(对于n≥4,n)= G(n-1)+ G(n-2).}

现在你也可以使用闭合形式 ˚F _Ñ =(α ^Ñ -β ^Ñ)/(α-β)(其中,α和β是(1±√5)/ 2,x的根部² -X-1 = 0),得到
G(n)=((1 +√5)/ 2)ⁿ +((1-√5)/ 2)ⁿ.
[你可以忽略第二项,因为对于大n,它非常接近0,实际上G(n)是所有n≥2 的最接近((1 +√5)/ 2)^n的整数.