permutation - 有限制的排列 - 由 3 个或更多零组成的集合中没有两个零可以在一起

Question

我有这个作为数据集 -0 1 0 1 0现在如何找出排列的数量，限制没有两个零可以在一起。即 00110、00011、11000 等 -> 所有这些都是假案例

我正在尝试使用5!/2!.3! - (cases where two zeroes are always together).

但我无法找到如何做到这一点。有什么帮助吗？

Answer 1

让我们有 n 个 0 和 m 个 1。一个或多个 1 位于两个 0 之间。像011101101...有4种排列方式：

starts and ends with 0:    01101110
starts with 0 ends with 1: 011011101
starts with 1 ends with 0: 1101101110
starts and ends with 0:    1011011101

在第一种情况下，有 n-1 组 1，在第二和第三中，有 n 组，在最后一种情况下，有 n+1 组。所以，结果是：

A(m,n-1) + 2*A(m,n) + A(m,n+1),

其中 A(i,j) 是如何将 i 个对象排列在 j 个组中的多种方式，以便每个组至少有一个元素。通过一些计算，表明 A(i,j) = C(i-1,j-1)，其中 C 是二项式系数。