Análisis combinatorio. Como resolver el siguiente problema Sea A:={1,2,…,7}. Una función f:A→A tiene un punto fijo...
- SeaA={1,2,3....7} Una función f:A--->A tiene un punto fijo si para algún x pertenece A, la f(x)=x ¿Cuántas funciones biyectivas f:A--->A tienen al menos un punto fijo?
1 respuesta
·
·
¡Hola CarolinaBoni!
La cantidad de funciones biyectivas de un conjunto en sí mismo son las permutaciones de los elementos del conjunto.
Luego en total hay:
P(7) = 7! = 5040 funciones biyectivas
Calculemos las que no tienen ningun punto fijo.
Bueno calcular no, es bastante difícil. Si te han puesto este problema por fuerza has tenido que estudiar antes una cosa que se llama los desarreglos, que son las permutaciones que no dejan ningún elemento en su sitio. Y la fórmula del númeo de desarreglos es esta:
$$\begin{align}&D(n)=n!·\sum_{k=0}^n \frac{-1^k}{k!}\\&\\&D(7)=7!\left(1-\frac 12+\frac 16-\frac 1{24}+\frac{1}{120}-\frac{1}{720}+\frac{1}{5040} \right)=\\&\\&5040-2520 +840-210+42 -7 + 1=3186\end{align}$$Luego las que tengan algún pnto fijo, serán todas menos las que no tienen ninguno.
5040 - 3186 = 1854
Y eso es todo, saludos.
:
:
Espera, que no es tan difícil. Yo busqué esa fórmula pero no es necesaria, aplicando el principio de inclusión-exclusión tenemos que llegar al resultado.
Tomaremos el número total de funciones, le restaremos las que fijan un punto, sumaremos las que fijan dos puntos, restaremos las que fijan tres puntos y así hasta las que fijan los siete.
Esa cuenta es sencilla
P(7) - C(7,1)·P(6) + C(7,2)·P(5) - C(7,3)·P(4) + C(7,4)·P(3) - C(7,5)·P(2) + C(7,6)P(1) - C(7,7)·P(0) =
7! - 7·6! + 21·5! - 35·4! + 35·3! - 21·2! +7·1! - 1 =
21·120 - 35·24 + 35·6 -21·2 + 7 - 1 =
2520 - 840 + 210 - 42 + 7 - 1 = 1854
Y da el mismo resultado, como debe ser, usando solo cosas que conocemos.
Saludos.
:
:
