给定大小的非相邻集的数量

Question

如果给定集合L={1,2,3,...,N}和一个整数k，是否可以有效地计算“的数量”大小为 k 的非相邻子集？如果对于 S 中的每个 x，既不是 x-1 也不是 ，则子集 S 是不相邻的x+1 位于 S 中。

例如，对于 L={1,2,3,4} 和 k=2 ，答案是 3，因为我们有 {1,3},{1,4},{2,4}。对于k=3，答案是零。

一种方法是生成所有大小为 2 的非相邻子集，然后尝试所有可能的并集（因为非相邻集具有其所有子集都不相邻的属性），但这让我觉得非常浪费，并且也许有一个甜蜜优雅有效的解决方案。

Answer 1

以这种方式思考：如果您知道集合 L'={1, 2, 3, ..., N - 1} 的答案是什么，您可以使用该信息来构建集合L的答案？
这个想法是，当您将 N 添加到 L' 时，新的解决方案由 L' 可用的所有子集加上 1 个新子集组成对于 L' 中小于或等于 N - 2*(k - 1) 的每个元素，因此如果 L' 的解> 的大小为 V'，那么V L 的解为 V = V' + (N - 2*(k - 1))
如果您再进一步计算，您会发现该解可以表示为前 N - 2k + 2 个自然整数的和。

对于小于或等于N - 2*(k - 1)部分，添加的新数字N只会添加到最终数字小于或等于的子集该表达式的结果，因为正在构建的新子集中必须有 k 个元素（包括数字 N 本身，因此有 k - 1代码> 需要更多）彼此之间至少用 2 个数字分隔，其中与数字 N 的距离为 2*(k - 1)，表达式如此。

Answer 2

这可能与 Win32 的解决方案相同，但我不确定。所以我单独发一下。

取 S(n) 为大小为 n 的连续序列的非相邻子集的数量（即，S(n) 是您正在寻找的解决方案）。

让我们计算 S(n+1)，即向序列添加元素时的值。当我们添加元素 k 时，我们会增加该序列的非相邻子集的数量。我们可以将这些新子集分为以下几类。

• 仅包含我们添加的新元素的子集。只有其中之一 ({k})。
• 我们可以添加 k 并且仍然保留我们的非相邻标准（加上 k）的子集。我们可以将 k 添加到任何不包含 k-1 的子集，同时保持不邻接。另一种说法是，我们可以将 k 添加到最多包含 k-2 的子集。并且最多包含 k-2 个子集的数量等于 S(n-1)。

因此，当我们将 k 添加到序列中时，新的非相邻子集的数量为 1 + S(n-1)。换句话说，1 + S(n-1) = S(n+1) - S(n)。我们可以重新整理这个公式，得到 S(n+1) = 1 + S(n-1) + S(n)。

递归解决方案不是很有帮助，因此我们可以尝试对其进行概括。我不擅长这一步，但是Wolfram|Alpha 为，我们发现通式等于以下。

• S(n) = 1/2 * (3 * Fib(n) + Lucas(n) - 2)

以下是一些示例数据点。

n | S(n)
0 | 0
1 | 1
2 | 2
3 | 4
4 | 7
5 | 12
6 | 20
7 | 33
8 | 54
9 | 88

Answer 3

用S(m,n)表示{1,...,n}中大小为m的非相邻子集的数量。那么以下内容成立：

S(m,n) = S(m,n-1) + S(m-1,n-2)

因此，可以通过添加边界条件

S(1,n) = n
S(m,1) = I(m==1)
S(m,2) = 2*I(m==1)

（其中 I() 是指示函数），在 O(Nk) 中通过 DP 来解决它。

Answer 4

让：

S(n,k) 是 {1,...n} 大小为 k 的非相邻子集的集合

显然，< code>S(n-1,k) 是大小为 k 的不相邻子集的集合，并且它是 S(n,k) 的子集>。

另外，S(n-2,k-1) 是一组大小为 k-1 的不相邻子集，并且这些子集都不包含 n -1。因此，我们可以安全地将 {n} 添加到每个子集中，以获得大小为 k 的子集。并且由于它们不包含 n-1 （与 n 唯一相邻的元素），因此它们也是不相邻的。

因此：

S(n,k) = S(n-1,k) U ({n} XS(n-2,k-1))

使用一些实数，让我们尝试求解 S(6,3)。

S(6,3) = S(5,3) U ({6} X S(4,2))
 S(5,3) = {1,3,5}                   # Only one solution
  S(4,2) = S(3,2) U ({4} X S(2,1))
   S(3,2) = {1,3}                   # Only one solution
    S(2,1) = {1} {2}                # All sets of 1 element are non-adjacent
   {4} X S(2,1) = {1,4} {2,4}       # Add {4} to each
  S(4,2) = {1,3} {1,4} {2,4}
 {6} X S(4,2) = {1,3,6} {1,4,6} {2,4,6}
S(6,3) = {1,3,5} {1,3,6} {1,4,6} {2,4,6}

这符合你的答案。

现在，计算这个数字：

令N(n,k)为S(n,k)中的元素数量

然后：

N(n,k) = N(n-1,k) + N(n-2,k-1)

我还没有确定封闭形式，但这里有一些计算值：

 n    k=1   k=2   k=3   k=4   k=5   k=6   k=7   k=8   k=9  k=10  k=11  k=12  k=13
 1     1                                                                        
 2     2                                                                        
 3     3     1                                                                  
 4     4     3                                                                  
 5     5     6     1                                                            
 6     6    10     4                                                            
 7     7    15    10     1                                                      
 8     8    21    20     5                                                      
 9     9    28    35    15     1                                                
10    10    36    56    35     6                                                
11    11    45    84    70    21     1                                          
12    12    55   120   126    56     7                                          
13    13    66   165   210   126    28     1                                    
14    14    78   220   330   252    84     8                                    
15    15    91   286   495   462   210    36     1                              
16    16   105   364   715   792   462   120     9                              
17    17   120   455  1001  1287   924   330    45     1                        
18    18   136   560  1365  2002  1716   792   165    10                        
19    19   153   680  1820  3003  3003  1716   495    55     1                  
20    20   171   816  2380  4368  5005  3432  1287   220    11                  
21    21   190   969  3060  6188  8008  6435  3003   715    66     1            
22    22   210  1140  3876  8568 12376 11440  6435  2002   286    12            
23    23   231  1330  4845 11628 18564 19448 12870  5005  1001    78     1      
24    24   253  1540  5985 15504 27132 31824 24310 11440  3003   364    13      
25    25   276  1771  7315 20349 38760 50388 43758 24310  8008  1365    91     1
26    26   300  2024  8855 26334 54264 77520 75582 48620 19448  4368   455    14