GATE | GATE-CS-2006 |问题24

给定一组元素N={1,2，…，N}和两个任意子集a⊆N和B⊆N、 有多少N！从N到N的置换π满足min（π（A））=min（π（B）），其中min（S）是整数集合S中的最小整数，而π（S）是通过将置换π应用于S的每个元素而获得的整数集合？

（A） （n–| A）∪ B |）| A | | B| （B） |A| ^2. +|B| ^2. )n ^2. （C） n|A.∩B |/| A∪B| （D） |A∩B| ^2. nC | A∪B| 答复: （C） 说明： 首先让我们了解问题是什么。π是一个从N到N的函数，它只是置换N的元素，所以会有N！这样的排列。现在给定一个特定的π，也就是给定一个特定的置换方案，我们必须从这些n中找出置换的数目！A和B在应用π后的最小元素相同的置换。 例如，如果N={1,2,3}，π是{2,3,1}，如果A是{1,3}，那么π（A）={2,1}。 现在，一个∪ B是| A∪ B |。我们可以选择排列方式∪ 北卡罗来纳州的B | A∪B |方法。请注意，这里我们只是选择元素进行置换，而不是实际置换。让这个选择集为P。一旦我们为排列选择了数字，我们就必须从每个元素中选择映射∪ B到P的某个元素。 首先，为了达到所要求的条件，我们必须把P中的最小数映射到A中的任意一个数∩ B、 所以min（π（A））=min（π（B））。我们可以在| A |内完成∩B |方式，因为我们可以选择| A的任何元素∩B |映射到P中的最小数。 现在我们来讨论排列。我们可以把P中的数排列在| A中∪B-1 |！方法，因为一个数字（最小值）已经固定。 此外，我们还可以置换剩余的n–| A∪B-1 | in（n–| A）∪B-1 |）！方法，所以方法总数= nC | A∪B|∗|A.∩B|∗|A.∪B−1|!∗（n）−|A.∪B−1|)!=n|A.∩B | | A∪B| 所以选项（C）是正确的。 注意：网络上的一些答案键显示答案为选项（D），这显然是不正确的。假设| A∪ B |=3和| A∩ B |=1，n=4，则选项（D）的计算结果为14=0.25，这是没有意义的。

资料来源： http://www.cse.iitd.ac.in/~mittal/gate/gate_math_2006。html 这个问题的小测验