PUERTA | PUERTA-CS-2006 | Pregunta 24

Dado un conjunto de elementos N = {1, 2, …, n} y dos subconjuntos arbitrarios A⊆N y B⊆N, ¿cuántos de los n! Las permutaciones π de N a N satisfacen min(π(A)) = min(π(B)), donde min(S) es el entero más pequeño del conjunto de enteros S, y π(S) es el conjunto de enteros obtenido aplicando la permutación π a cada elemento de S?

(A) (n – |A ∪ B|) |A| |B|
(B) (|A| ² +|B| ² )n ²
(C) n! |A∩B| / |A∪B|
(D) |A∩B| ^2nC |A∪B|

Respuesta: (C)
Explicación: Primero, entendamos qué pregunta se está haciendo. Entonces π es una función de N a N, que simplemente permuta los elementos de N, ¡entonces habrá n! tales permutaciones. Ahora, dado un π particular, es decir, dado un esquema de permutación particular, ¡tenemos que encontrar el número de permutaciones de estos n! permutaciones en las que los elementos mínimos de A y B después de aplicarles π son iguales.
Entonces, por ejemplo, si N = {1,2,3}, π es {2,3,1} y si A es {1,3}, entonces π(A) = {2,1}.
Ahora el número de elementos en A ∪ B es |A ∪ B|. Podemos elegir permutaciones para A ∪ B en nC|A∪B| maneras. Tenga en cuenta que aquí solo estamos eligiendo elementos para la permutación, y no permutando en realidad. Deje que este conjunto elegido sea P. Ahora, una vez que hayamos elegido los números para las permutaciones, tenemos que seleccionar el mapeo de cada elemento de A ∪ B a algún elemento de P.
Entonces, antes que nada, para lograr la condición requerida especificada en cuestión, tenemos que asigne el número mínimo en P a cualquiera de los números en A ∩ B, de modo que min(π(A)) = min(π(B)). Podemos hacer esto en |A∩B| maneras, ya que podemos elegir cualquier elemento de |A∩B| para ser mapeado al número mínimo en P.
Ahora llegamos a la permutación. ¡Podemos permutar números en P en |A∪B-1|! maneras, ya que un número (mínimo) ya está fijado.
Además, también podemos permutar los n restantes – |A∪B-1| en (n – |A∪B-1|)! maneras, por lo que no total. de vías =
nC|A∪B|∗|A∩B|∗|A∪B−1|!∗(n−|A∪B−1|)!=n!|A∩B||A∪B|
Entonces la opción (C) es correcta.
Nota: Algunas claves de respuesta en la web han mostrado la respuesta como opción (D), lo cual es claramente incorrecto. Supongamos que |A ∪ B| = 3, y |A ∩ B| = 1 y n = 4, entonces la opción (D) se evalúa como 14 = 0,25, lo que no tiene sentido.

Fuente: http://www.cse.iitd.ac.in/~mittal/gate/gate_math_2006.html
Prueba de esta pregunta