Hallar el número de formas de ordenar n números

[GaToMi]

Este ejercicio lo saqué del foro fmat, me pareció interesante.
Creo que cada vez me gusta más la combinatoria jajaja.

Hallar el número de de formas de ordenar los números 1,2,…,n que no dejan fijo a ninguno de los números, es decir, el número k no está en el k-ésimo lugar de la ordenación. ¿Cuál es la probabilidad de que al tomar una ordenación al azar, la elegida no deje fijo a ningún elemento?

[Juan Pablo Sancho]

Mira esta página:
Principio de inclusión exclusión

[Luis Fuentes]

Hola

 O aquí:

https://es.wikipedia.org/wiki/Subfactorial

Saludos.

[GaToMi]

Lo que yo hice fue esto

Spoiler (click para mostrar u ocultar)

a) En total hay n! permutaciones distintas del conjunto. Notemos que de un total de n posiciones, cada número aparece en cada posición (n-1)! veces, lo que nos da un total de n! permutaciones, es decir, el total de permutaciones de los n elementos. Como se pide que el elemento k no ocupe la posición k-ésima, entonces hay que descontar una posición, es decir, de un total de (n-1) posiciones, cada número aparecerá en cada posición (n-2)! veces, lo que nos da el total de formas de ordenar estos elementos sin que deje fijo a ningún número, es decir, (n-1)(n-2)!=(n-1)! ordenaciones.

b) La probabilidad de que al tomar una ordenación al azar, la elegida no deje fijo a ningún elemento, es

[texx]P=\displaystyle\frac{(n-1)!}{n!}=\displaystyle\frac{1}{n}[/texx]

[Luis Fuentes]

Hola

 No acabo de entender tu argumento, pero no está bien. Por ejemplo para [texx]n=4[/texx] las permutaciones que no dejan fijo ningún elemento son [texx]9\neq (4-1)![/texx]:

[texx]2143,2341,2413,3142,3412,3421,4123,4312,4321[/texx]

Saludos.

[GaToMi]

Es verdad, después de pensar un poco sobre el razonamiento que hice, me di cuenta de que habían cosas raras. Lo seguiré intentando, gracias

[feriva]

Lo seguiré intentando, gracias

Hola, GaToMi.

Como el problema es general, la respuesta es la de los hilos que te han dado; pero para entenderlo mejor puedes desarrollar un ejemplo.

Vamos con cuatro elementos.

Dejas el 1 fijo y quedan 3 que permutan; tomamos entonces tres factorial

[texx](1),2,3,4[/texx]

[texx]+3![/texx]

Dejas el 2 fijo y lo mismo, tomamos 3 factorial

[texx]1,(2),3,4[/texx]

[texx]+3![/texx]

Ahora bien, al tomar ésas, hemos tomado algunas de las de antes, las que tenían el 1 fijo coincidiendo con el 2 fijo, es decir, de manera que permutan los números que quedan en las otras dos posiciones; así que le quitamos dos factorial

[texx]-2![/texx]

Hacemos lo mismo con el 3 fijo y tomamos tres factorial

[texx]1,2,(3),4[/texx]

+3!

Pero al hacerlo hemos tomado otra vez de más; algunas de las de antes: las del 1 fijo con el 3 fijo, las del 2 fijo con el 3 fijo y las del 1 y el 2, fijos, con el 3 fijo; le quitamos entonces

-2!-2!-1!

Dejamos el 4 fijo

[texx]1,2,3,(4)[/texx]

Incluimos, como siempre, tres factorial

3!

y ahora excluimos las del 1 con el 4 fijos, el 2 con el 4... etc.

-2!-2!-2!-1!-1!

Ya se ha terminado; se hace la cuenta de lo que llevamos:

[texx]4(3!)-6(2!)-3(1!)=24-12-3=9
 [/texx]

Saludos.

[Juan Pablo Sancho]

Te pongo una ayuda:
Sea [texx]\mathbb{N}_n = \{1,2,3, \cdots, n\} [/texx].
Tenemos que la cantidad de aplicaciones biyectivas es [texx]n![/texx].
Sea [texx]\mathcal{X} [/texx] el conjunto de aplicaciones biyectivas de [texx]\mathbb{N}_n [/texx] en [texx]\mathbb{N}_n[/texx] vamos [texx]|\mathcal{X}| = n! [/texx].

Sea [texx] H_i = \{f \in \mathcal{X} | f(i) = i \} [/texx] tenemos que [texx]|H_i| = (n-1)! [/texx].
En general [texx] |H_{i_1} \cap H_{i_2} \cap \cdots \cap H_{i_p}| = (n-p)! [/texx].

La solución está en el spoiler:

Spoiler (click para mostrar u ocultar)

Tenemos que [texx]\displaystyle \bigcup_{i=1}^n H_i [/texx] es el conjunto de funciones que almenos tienen una coincidencia,entonces buscamos [texx]\displaystyle |\mathcal{X} \setminus \bigcup_{i=1}^n H_i| [/texx]

Como   :
[texx]\displaystyle |\bigcup_{i=1}^n H_i| = {n \choose 1} (n-1)! - {n \choose 2} \cdot (n-2)! + \cdots + (-1)^{n-1} \cdot {n \choose n-1} = \sum_{i=1}^n (-1)^{i-1} \dfrac{n!}{i!}  [/texx]

Entonces la solución es:

[texx]\displaystyle n! - n! \cdot \sum_{i=1}^n (-1)^{i-1} \dfrac{1}{i!} = n! \cdot \sum_{i=2}^n \dfrac{(-1)^i}{i!} [/texx].
Nos queda que probabilidad de encontrar una función sin coincidencias es:
[texx]  \sum_{i=2}^n \dfrac{(-1)^i}{i!} \sim \dfrac{1}{e} [/texx].

[GaToMi]

Creo que es un problema demasiado avanzado para los conocimientos que tengo, sin embargo me parece interesante, cuando adquiera los conocimientos necesarios volveré jajaja.
Saludos y gracias por la ayuda a todos.

[feriva]

Creo que es un problema demasiado avanzado para los conocimientos que tengo, sin embargo me parece interesante, cuando adquiera los conocimientos necesarios volveré jajaja.
Saludos y gracias por la ayuda a todos.

Dejando lo de la probabilidad aparte, que puede ser más complicado no hace falta saber mucho, es que es un problema pesado para cualquiera

Te propongo otro problema parecido.

Cuando yo pensé en esto no conocía el método de inclusión-exclusión, sin embargo, lo que quería lograr me llevó a aplicarlo sin conocerlo.

Quería contar la cantidad de primos quitando los compuestos.

Pongamos que queremos saber cuántos compuestos hay hasta 20. Lo primero que se le ocurre a uno es tomar los pares; dividimos 20 entre 2 y son 10 pares; pero quitamos el 2 que es primo y quedan 9 pares.

Seguimos por quitar los múltiplos de 3... dividimos 20/3 y la parte entera es 6, y quitando el primo 3 son 5 compuestos más.

Hasta aquí hemos ido incluyendo los compuestos, pero hay múltiplos de 3 que son pares, como el 6, y ya los hemos tomado antes. Por tanto, hay que excluir los múltiplos de 2 y 3, o sea, de 6, de esos cinco múltiplos de 3; hacemos 20/6 y la parte entera es 3; se quedan en 5-3=2

Hasta ahora van 9+2=11 compuestos.

Seguimos con los de 5, que son 20/5=4; y quitando el primo 5, son 3. Seguidamente hay que excluir los pares, los múltiplos de 10, que son [texx]\dfrac{20}{2\cdot5}=2
 [/texx], y quitar también los múltiplos de 3 y 5, de 15, que son [texx]\dfrac{20}{3\cdot5}=1
 [/texx]. Ahora, al quitar éstos, podríamos haber quitado múltiplos pares recién quitados, o sea, mútiplos de [texx]2\cdot3\cdot5
 [/texx], pero ese producto da 30, que es mayor que 20, así que no hay que exlcuir nada aquí.

Por tanto, son 3-3=0 múltiplos de 5; quiere decir que los múltiplos de 5 que hay son también pares o mútiplos de 3 o ambas cosas y que ya están considerados.

Quiere decir también, además, que el cuadrado de este primo ya se pasa de 20, [texx]5^{2}=20
 [/texx] igual a 25>20, era una errata y que hemos terminado; así que son 11 compuestos:

[texx]1,2,3,{\color{blue}4},5,{\color{blue}6},7,{\color{blue}8,9,10},11,{\color{blue}12},13,{\color{blue}14,15,16},17,{\color{blue}18},19,{\color{blue}20}
 [/texx].

Con las permutaciones es parecido lo que he hecho: se deja fija la primera “casilla”, la del 1, se permutan en las otras y se hallan las permutaciones que hay, después se deja fija la del 2, se hallan las permutaciones y se excluyen las que ya se habían tomado antes...

No hay una fórmula digamos cerrada para esto como para las permutaciones, las combinaciones etc., en la práctica no hay más remedio que hacerlo siguiendo el conteo.

Saludos.