Número de formas de visitar N lugares

Question

Un turista quiere visitar $N$ ciudades, cada una de ellas numerada desde $1$ a $N$ pero quiere visitarlos en un extraño orden.

A extraño orden es tal que ninguna ciudad numerada $i$ es el $i$ -a visitar en su itinerario de viaje.

Quiere visitar cada ciudad exactamente una vez.

¿Cuál es el número de posibles extraño órdenes para su viaje?

Answer 1

Teniendo en cuenta que la secuencia en la que visita estos $n$ ciudades, es $$a_1, a_2, \dots, a_n$$ entonces $a_i \neq i$ . Este es un derangement cuya fórmula viene dada por $$!n=\left[\frac{n!}{e}\right]$$ donde $[x]$ es la función entera más cercana y $!n$ es el número de desviaciones para una secuencia con $n$ elementos.

Esta secuencia también aparece en el Enciclopedia en línea de las secuencias de números enteros que también le proporciona relaciones de recurrencia, a saber $$!n=(n-1)[!(n-1)+!(n-2)]$$ por el número de desórdenes.

Answer 2

Sugerencia: busque los arreglos de la caridad. $D_n=N!(1-1\frac{1}{2!}...+\frac{(-1)^n}{n!})$