Revista, Técnicas, Cursos, Problemas => De oposición y olimpíadas => Mensaje iniciado por: GaToMi en 11/02/2019, 07:48:51 pm



Título: Hallar el número de formas de ordenar n números
Publicado por: GaToMi en 11/02/2019, 07:48:51 pm
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?


Título: Re: Hallar el número de formas de ordenar n números
Publicado por: Juan Pablo Sancho en 11/02/2019, 08:40:51 pm
Mira esta página:
Principio de inclusión exclusión  (https://es.wikipedia.org/wiki/Principio_de_inclusi%C3%B3n-exclusi%C3%B3n)


Título: Re: Hallar el número de formas de ordenar n números
Publicado por: Luis Fuentes en 12/02/2019, 03:50:22 am
Hola

 O aquí:

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

Saludos.


Título: Re: Hallar el número de formas de ordenar n números
Publicado por: GaToMi en 12/02/2019, 09:13:38 am
Lo que yo hice fue esto

Spoiler (click para mostrar u ocultar)


Título: Re: Hallar el número de formas de ordenar n números
Publicado por: Luis Fuentes en 12/02/2019, 01:06:23 pm
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.


Título: Re: Hallar el número de formas de ordenar n números
Publicado por: GaToMi en 12/02/2019, 01:52:11 pm
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 :)


Título: Re: Hallar el número de formas de ordenar n números
Publicado por: feriva en 12/02/2019, 03:07:50 pm
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.


Título: Re: Hallar el número de formas de ordenar n números
Publicado por: Juan Pablo Sancho en 12/02/2019, 04:06:58 pm
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)


Título: Re: Hallar el número de formas de ordenar n números
Publicado por: GaToMi en 12/02/2019, 04:33:31 pm
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.


Título: Re: Hallar el número de formas de ordenar n números
Publicado por: feriva en 12/02/2019, 07:30:08 pm
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.