Arreglando los números$1,2,3,\dots,n$

Question

De cuántas maneras números de $1,2,3,\dots,n$ pueden ser dispuestos en una fila tal que $1$ no puede estar en el primer lugar, $2$ no pueden estar en el segundo lugar, $3$ no puede estar en el tercer lugar, etc?

He intentado de esta manera: en primer lugar puede ser $n-1$ números. Ahora, he utilizado un número, por lo que hay $n-1$ números de la izquierda. Si en el primer lugar es $2$, en segundo lugar, puede ser de nuevo $n-1$ números, otra cosa no puede ser $n-2$ números y así sucesivamente. Toma un tiempo muy largo para encontrar a todos los casos y para todos los lugares si $n$ es un número grande. ¿Cuál es la forma más sencilla de resolver esto?

Answer 1

Hay una inclusión-exclusión de la fórmula para el recuento de las alteraciones de $n$ elementos:

$$n! \sum_{i=0}^{n} \frac{(-1)^{i}}{i!}$$

Así que empezamos por permuting la $n$ elementos, que se puede hacer en $n!$ maneras. Entonces se cuenta el número de maneras en que el elemento $i$ va a la ranura $i$. Lo que soluciona un solo elemento en su ranura y permutar los elementos restantes en $(n-1)!$ maneras. Hay $n$ estos elementos podemos arreglar (ie., fix$1$, a continuación, permutar los otros elementos, a continuación, fije $2$ y permutar las otras $n-1$ elementos, etc.), así que restar $n * (n-1)! = n!$ de la cantidad original.

Sin embargo, hemos overcounted, como podríamos haber $1 \mapsto 1, 2 \mapsto 2$ (por ejemplo) en nuestro permutaciones de la fijación de un único elemento. Así que tenemos que agregar de nuevo en cantidades donde $2$ elementos son fijos. Lo que soluciona esos dos elementos y permutar el resto de $n-2$ elementos. Observe que $\frac{n!}{2!}$ cuenta las permutaciones de $n-2$ elementos.

Seguimos con esta inclusión-exclusión en el proceso, lo que nos da la por encima de la recapitulación.

Answer 2

Encontremos el conjunto$A$ de todas las configuraciones que no son aceptables. Si denotamos el conjunto de todas las permutaciones con$i$ en$i^{th}$ puesto por$A_i$, entonces$A = \cup_{i = 1} ^n A_i$. Usando el principio de inclusión-exclusión puedes encontrar que$$|A| = \binom{n}{1}(n-1)! - \binom{n}{2}(n-2)! + \binom{n}{3}(n-3)! - \dots + (-1)^{n+1}\binom {n}{n}0! = \sum_{i = 1}^{n} (-1)^{i+1}\binom{n}{i}(n-i)!

Y tu respuesta final debería ser

PS