子集

Question

我越来越好奇这个问题的总数..

你有多少种方法可以选择集合P =一个子集{1，2，3，... N}？该子集S应该满足以下条件：

当你选择X（X∈P，x是集合P的元素）来创建S，你不能选择S.

一个* X和B * X

约束：

1 <= n <= 1000 
2 <= a < b <= n 
b % a != 0 (b is not divisible by a) 

例子：

n = 3 , a = 2, b = 3 
so total subsets are 5 ,i.e, {}, {1}, {2}, {3}, {2, 3} 
as if in a particular subset there is 1 so 1*2 = 2 and 1*3 cant be there. 
so {1,2}, {1,3} and {1,2,3} can't be there 

Answer 1

我相信这将是容易计算的complimentary-是S的子集的数量不是人低于。这是S的子集数量，每个子集至少有一对(a,b)，这样a除以b。在计算出数M'后，只需从S的子集总数中减去它即可得到2 ⁿ。

现在要计算不允许的S的子集数量，您将必须应用inclusion-exclusion principle。这个解决方案不是很容易实现，但我不认为有一种替代方法。

Answer 2

更新

这是关系到OEIS，整数序列的在线百科全书sequence A051026 : Number of primitive subsequences of {1, 2, ..., n}。

我不认为有任何简单的方法来计算条款。即使是循环的计算是不平凡的，除非n是素数，其中：

a(n) = 2 * a(n-1) - 1 

---

两个问题就在这里和“A051026”可以认为上述序列的推广的子问题。 “A051026”是具有(a,b,..) = (2,3,4,5...)的实例，例如“所有整数> = 2”。