set - 设置组合题

Question

将此作为家庭作业，但不确定从哪里开始！

给定集合{1,2,3,4}，您可以从该集合中形成长度为 2 的六种组合，即：

{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}

如果我要选择其中一种组合，（{1,2}例如），我怎么知道有多少其他组合与它不相交？在这种情况下，它是四个：{1,3},{1,4},{2,3}{2,4}

不太确定如何在数学上进行此操作，任何指向正确方向的指针都将不胜感激。

Answer 1

可以从一组n项目中形成的子集的数量一次取r项目是

total = P(n, r) = n! / (r! * (n - r)!)

让s成为选定的组合。为了找到不与 不相交的子集的数量s，我们首先找到与 不相交的子集的数量s- 那些没有任何项目的集合s（让我们称之为 number k）。因此k，一次可以从一组n - r项目中形成的子集的数量r。

k = P(n - r, r) = (n - r)! / (r! * (n - r - r)!)
  = (n - r)! / (r! * (n - 2r)!)

因此，与所选集合不相交的子集数为：

total - k = P(n, r) - P(n - r, r)

请记住，这包括选定的子集s。从中减去 1 得到不相交集的数量s。

考虑以下示例：

//Let n = 6 and r = 2
total = P(n, r) = n! / (r! * (n - r)!) = 6! / (2! * 4!) = 15

k = P(n - r, r) = (n - r)! / (r! * (n - 2r)!) = 4! / (2! * 2!) = 6
answer = 15 - 6 = 9; answer excluding the selected set s = 8

//Super set: 
  {123456}
//Possible sub sets: 
  {12,13,14,15,16,23,24,25,26,34,35,36,45,46,56}  //15 items

//Let the selected set be {12}, then sets without 1 and 2: 
  {34,35,36,45,46,56} //6 items

//9 sets (including the selected set) are not disjoint with the selected set

Answer 2

也许从阅读一些关于组合学的书籍或文章开始..

如果你会编程，这个库会帮助你。

Answer 3

我会做这样的事情：

For each item in my combination ( 1 then 2 ) do the following
* For each item in the set (1, 2, 3, then 4) do the following
** if set item is different from both combination item 1 and 2
*** print out combination item and print out set item

Answer 4

尝试Combinatorics或更好的Permutations。

Answer 5

如果a和b都没有出现在Y中，则集合X = { a , b } 和Y是不相交的。因此，如果a出现在Y中或b出现在Y中，则X和Y不是不相交的。

要找出有多少其他集合不与 { a , b } 不相交，请考虑所有可能性： 通常，所有具有两个不与 { a , b }不相交元素的集合的形式为 { a , x } 或{ b , x }，对于原始集合中的任何x。如果原始集合有n 个元素，则 { a , x }有n 个可能性， { b , x } 有n个可能性，总共有 2*n*。

但是，{ a , b } 既是 { a , x } 形式（对于x = b）和 { b , x } 形式（对于x = a），所以我们计算了两次。我们必须将它计数为零次，因为 { a , b } 与我们开始时的集合相同。所以我们减去 2，总共 2*n* - 2。

但我们仍在计算 { a , a } （对于x = a）和 { b , b } （对于x = b）。但是它们每个只包含一个元素（{ a , a } = { a } 和 { b , b } = { b }），所以我们不应该计算它们。因此我们减去 2，总共 2*n* - 4。

对于您的示例，{1, 2, 3, 4} 给出 n = 4，因此不与 {1, 2} 不相交的元素数为 2*4 - 4 = 4。