Caminos
-
Upload
carlos-francia -
Category
Documents
-
view
216 -
download
0
description
Transcript of Caminos
![Page 1: Caminos](https://reader035.fdocumento.com/reader035/viewer/2022072114/563db9cb550346aa9a9ffd07/html5/thumbnails/1.jpg)
UNIVERSIDAD DE EL SALVADOR
FACULTAD MULTIDISCIPLINARIA DE OCCIDENTE
Apuntes de
INTRODUCCIÓN
A LA
MATEMÁTICA DISCRETA Para la titulación de
LICENCIATURA EN ESTADÍSTICA
DEPARTAMENTO DE
MATEMÁTICAS
![Page 2: Caminos](https://reader035.fdocumento.com/reader035/viewer/2022072114/563db9cb550346aa9a9ffd07/html5/thumbnails/2.jpg)
CAMINOS
Analizaremos un ejemplo básico de cuenta de caminos siguiendo líneas en figuras. En una
cuadricula de 3x3, sea “A” el vértice inferior izquierdo y “B” el vértice superior derecho.
¿Cuántos caminos hay de “A” a “B” siguiendo las líneas de la figura si solo se puede avanzar
hacia a la derecha y hacia arriba?
l
B
m n
h
i j k
d
e f g
↑ A → a b c
Para llegar a “a”, “b” y “C” hay 1 forma.
Para llegar a “d”, “h” y “l” hay 1 forma.
Para llegar a “e” hay 2 formas.
Para llegar a “f” hay 3 formas.
Para llegar a “g” hay 4 formas.
Para llegar a “i” hay 3 formas.
Para llegar a “j” hay 5 formas.
Para llegar a “k” hay 10 formas.
Para llegar a “m” hay 4 formas.
Para llegar a “n” hay 10 formas.
![Page 3: Caminos](https://reader035.fdocumento.com/reader035/viewer/2022072114/563db9cb550346aa9a9ffd07/html5/thumbnails/3.jpg)
Comprobemos lo anterior con la siguiente cuadricula:
Por lo tanto hay 10 caminos distintos para llegar de “A” hasta “B” y en cualquier camino de “A”
hacia “B” hay 6 decisiones; 3 hacia la derecha y 3 hacia arriba.
EJEMPLO 1:
En una cuadricula de 5x2. ¿Cuántos
caminos hay de “A” hacia “B” si siempre
hay que ir hacia la derecha o hacia arriba?
Existen 21 caminos distintos para llegar de “A” a “B”. Además hay 7 decisiones; 2 hacia arriba y
5 hacia la derecha.
EJEMPLO 2:
Para una cuadricula de 4x4 ¿Cuántos caminos hay de “A”
hasta “B”?. El total de caminos de “A” a “B” con
movimientos → ↑ se denota por el combinatorio:
1
B
4 10 20
1
3 6 10
1
2 3 4
↑ A → 1 1 1
1 B
3 6 10 15 21
1
2 3 4 5 6
↑
A → 1 1 1 1 1
B
↑
A →
![Page 4: Caminos](https://reader035.fdocumento.com/reader035/viewer/2022072114/563db9cb550346aa9a9ffd07/html5/thumbnails/4.jpg)
EJEMPLO 3: Construir las cuadriculas correspondientes para y
En general:
De una forma explicita:
PROPIEDADES:
1.
2.
3.
4.
Las figuras que representan cada una de las propiedades son:
1.
Hay 1 manera para llegar de “A” a “B”
Para el combinatorio la cuadricula
B
↑
A →
correspondiente es:
Para el combinatorio la cuadricula
correspondiente es:
B
↑
A →
A B
1 1 1
![Page 5: Caminos](https://reader035.fdocumento.com/reader035/viewer/2022072114/563db9cb550346aa9a9ffd07/html5/thumbnails/5.jpg)
2.
Hay “n” caminos diferentes
3.
Hay una forma de llegar de “A” a “B”
4.
Hay n caminos de “A” hasta “B”
B
…
↑ A →
B
. . .
A
B
↑
A →
![Page 6: Caminos](https://reader035.fdocumento.com/reader035/viewer/2022072114/563db9cb550346aa9a9ffd07/html5/thumbnails/6.jpg)
EJEMPLO 4: Construir una figura para:
a)
b)
c)
d)
Desarrollo
a)
b)
c)
d)
B
A
A
B
![Page 7: Caminos](https://reader035.fdocumento.com/reader035/viewer/2022072114/563db9cb550346aa9a9ffd07/html5/thumbnails/7.jpg)
EJEMPLO 5:
De los caminos posibles de “A” a “B”:
a) ¿Cuántos pasan por C1?
A → C1 → B
b) ¿Cuántos pasan por C2?
A → C2 → B
![Page 8: Caminos](https://reader035.fdocumento.com/reader035/viewer/2022072114/563db9cb550346aa9a9ffd07/html5/thumbnails/8.jpg)
c) ¿Cuántos pasan por C1 y C2?
A → C1 → C2 → B
d) ¿Cuántos pasan por C1 ó C3?
e) ¿Cuántos no pasan por C1 ni por C2?
f) ¿Cuántos pasan por C1, C2 y C3?
A → C1 → C2 → C3 → B
Solución: 0
No es posible.
![Page 9: Caminos](https://reader035.fdocumento.com/reader035/viewer/2022072114/563db9cb550346aa9a9ffd07/html5/thumbnails/9.jpg)
g) Representar gráficamente el literal e).
EJEMPLO 6: Para la cuadricula
a) ¿Cuántos caminos hay de “A” a “B”?
A → P → B
![Page 10: Caminos](https://reader035.fdocumento.com/reader035/viewer/2022072114/563db9cb550346aa9a9ffd07/html5/thumbnails/10.jpg)
b) ¿Cuántos caminos de “A” a “B” hay pasando por C1 ó C2?
EJEMPLO 7: Para la cuadrícula
¿Cuántos caminos de “A” a “B” pasan por C1 ó C2?
A → C1 → P + A → C2 → P - A → C1 → C2 →P
C → B
D → B
C → B
D → B
C → B
D → B
![Page 11: Caminos](https://reader035.fdocumento.com/reader035/viewer/2022072114/563db9cb550346aa9a9ffd07/html5/thumbnails/11.jpg)