Determine la cantidad de elementos$f$ de$S_n$ para los cuales$f(1) \ne 1$ y$f(2) \ne 2$.

Question

$S_n$ es el grupo formado por el conjunto de todos los bijections de ${1,2,...,n}$ ${1,2,...,n}$.

$n\geq 2$, Determinar el número de elementos $f$ de $S_n$de % que $f(1) \ne 1$ y $f(2) \ne 2$.

Lo traté de resolverlo es mediante el hecho de que $$|A \cup B|=|A|+|B|-|A\cap B|$$ Where $ | A | $ is the amount of possible functions such that $f (1) \ne 1 $ and $ | B | $ is the amount of possible functions such that $f (2) \ne 2 $. With this in mind, I let $ | A | = n ^ n n $ and $ | B | = n ^ n-n$ pero ahora estoy estancado. Por favor ayuda!

Answer 1

Normalmente, $S_n$ denota el conjunto de las permutaciones de $\{1,2,\ldots,n\}$, que es el bijections de que el juego en sí. Voy a suponer que quieres decir $S_n$ en el resto de su pregunta. Si usted realmente quiere decir $F_n$ usted tendrá que modificar el argumento de forma adecuada.

Mejor dejar a $A$ $B$ denotar los conjuntos de elementos de $S_n$ con $f(1)=1$ $f(2)=2$ respectivamente. El número de elementos de $S_n$ con ambos $f(1)\ne1$ $f(2)\ne2$ es entonces $$|S_n|-|A\cup B|=|S_n|-|A|-|B|+|A\cap B|.$$

Como estamos tratando con permutaciones, $|S_n|=n!$. Ahora $A$ es, básicamente, el conjunto de las permutaciones de $\{2,3,\ldots,n\}$ por lo $|A|=(n-1)!$. Del mismo modo $|B|=(n-1)!$. A continuación, $A\cap B$ está formado por las permutaciones con $f(1)=1$$f(2)=2$. Estos permutar $\{3,4,\ldots,n\}$ libremente, por lo que hay $(n-2)!$ de ellos, etc.

Answer 2

Lo haría así: % Let $A_i$ser un conjunto de funciones con $f(i)=i$. $|A_i|= (n-1)!$ Y $|A_i\cap A_j|=(n-2)!$. Usted está interesado en $|A_1'\cap A_2'|$

$$|A_1'\cap A_2'| = n!-|A_1\cup A_2| = n!-2(n-1)!+(n-2)!$$ $$= (n-2)!(n^2-n-2n+2+1)=(n-2)!(n^2-3n+3)$$

Answer 3

Usted cometió dos errores importantes en lo que empezaste.

En primer lugar, dejando $A$ representan el conjunto de funciones que $f(1)\neq 1$ $B$ el conjunto de funciones donde $f(2)\neq 2$, el importe $|A\cup B|$ que representa a la cantidad de funciones que $f(1)\neq 1$ O $f(2)\neq 2$. La declaración del problema como usted escribió que en realidad está buscando a $|A\cap B|$.

En segundo lugar, en su intento calculado $|A|=n^n-n$. Esto también es incorrecto. En el cálculo de $|A|$, enfoque con el principio de la multiplicación (un.k.una. regla del producto). Elija el valor de $f(1)$. A continuación, elija el valor de $f(2),f(3),\dots$. Usted debe encontrar que el $|A|=(n-1)\times (n-1)\times (n-2)\times (n-3)\times \cdots=(n-1)\times (n-1)!$

Es posible que parte de la confusión aquí es de olvidar que el $S_n$ representa el conjunto de las permutaciones.

Como un acercamiento a cómo calcular el $|A\cap B|$, con una mezcla de principio de la multiplicación y la adición principio.

Ruptura de los casos. Cualquiera de las $f(1)=2$ o $f(1)\neq 2$.

En el primer caso, tenemos una opción para$f(1)$, $f(2)$ $n-1$ opciones. Cada valor tiene un decrecimiento en el número de opciones que van desde $n-2$$1$, dando $1\times (n-1)\times (n-2)!$ funciones en este caso.

En el segundo caso, tenemos $n-2$ opciones para$f(1)$, $f(2)$ $n-2$ opciones. Cada valor tiene un decrecimiento en el número de opciones que van desde la $n-2$$1$, dando $(n-2)\times (n-2)\times (n-2)!$ funciones en este caso.

Esto da un total de $((n-1)+(n-2)^2)(n-2)!$ total de tales funciones.

---

Si usted tiene la intención de ser $F_n$ en lugar de $S_n$, entonces la mayoría de mis críticas anteriores siguen siendo válidas y que tendría lugar $|A|=(n-1)\times n^{n-1}=n^n-n^{n-1}$, no$n^n-n$, y tendrías $|A\cap B|=(n-1)^2n^{n-2}$