Combinatoria argumento para probar la relación de recurrencia para el número de alteraciones

Question

Dar una combinatoria argumento para probar que el número de alteraciones satisface la siguiente relación:

$$d_n = (n − 1)(d_{n−1} + d_{n−2})$$

para $n \geq 2$.

Yo soy capaz de demostrar de esta manera algebraica, pero no es capaz de ver la combinatoria ejemplo.

Answer 1

Esto es directamente de la Wikipedia y creo que es comprensible, suficiente, y de ahí que publicar aquí de nuevo.

Supongamos que hay $n$ personas numeradas $1, 2, ..., n$. Vamos a no ser n los sombreros también numeradas $1, 2, ..., n$. Tenemos que hallar el número de maneras en la que nadie se pone el sombrero con el mismo número como su número. Supongamos que la primera persona que lleva sombrero de $i$. Hay $n − 1$ formas de la primera persona para hacer esa elección. Ahora hay dos posibilidades, dependiendo de si o no la persona $i$ toma hat $1$ en la devolución:

1. Persona $i$ no toma el sombrero de $1$. Este caso es equivalente a resolver el problema con $n − 1$ personas $n − 1$ sombreros: cada uno de los restantes $n − 1$ de la gente tiene, precisamente, $1$ prohibida la elección de entre el resto de los $n − 1$ sombreros ($i$'s prohibida la elección es hat $1$).
2. Persona $i$ se lleva el sombrero de $1$. Ahora el problema se reduce a $n − 2$ personas y $n − 2$ sombreros.

Answer 2

Este es el primer método dado en esta respuesta. En respuesta, tres métodos para calcular el número de alteraciones se dan.

Answer 3

Supongamos que $f:[n]\to[n]$ es un bijection sin puntos fijos. A continuación,$f(n)\in\lbrace 1,\ldots,n-1\rbrace$. Todos estos casos son de la misma hasta el reetiquetado, así que supongo $f(n)=n-1$. Ahora defina $g:[n-1]\to[n-1]$$g(x)=f(x)$, a menos que $f(x)=n$, en cuyo caso se definen $g(x)=n-1$. Si $g$ no tiene puntos fijos, bien. De lo contrario, ya que $f$ no tiene puntos fijos, debe ser que $g(n-1)=n-1$, es decir, $f(n-1)=n$. Por lo tanto $f$ sólo swaps $n$ $n-1$ $f|_{[n-2]}$ no debe tener puntos fijos.

Ahora acaba de comprobar que cada uno de los términos en la fórmula son contabilizados y nada se cuentan dos veces.