View
243
Download
8
Category
Preview:
DESCRIPTION
Contenido de la Unidad VI
Citation preview
UNIVERSIDAD FERMIN TORO
VICE-RECTORADO ACADEMICO
FACULTAD DE INGENIERIA
ESCUELA DE TELECOMUNICACIONES
Métodos de Conteo y
Relación de
Recurrencia
Valentina Denis
Ibeth Lozada
Estructura Discreta I SAIA C
Hay dos principios básicos en combinatoria:
Si se desea escoger un objeto que puede tener r tipos distintos, y para el primer tipo hay t1 opciones, para el segundo tipo hay t2 opciones, para el tercer tipo t3 opciones, y así sucesivamente hasta tr opciones para el ultimo tipo, entonces el objeto puede escogerse de t1 +t2 ...+tr maneras. Lo que el principio anterior dice, es que el total de opciones es la suma del número de opciones en cada tipo.
La Multiplicación. Si una tarea se ha de realizar en n etapas, y si la primera etapa tiene k1 maneras de realizarse, la segunda tiene k2 maneras, y así sucesivamente hasta kn , maneras de realizar la ultima, entonces el numero de formas de realizar la tara es k 1× k2 ×...×kn.
Supongamos que hay que escoger un libro de entre
tres materias: matemáticas, historia y biología. Hay
seis libros de matemáticas, 9 de historia y 4 de
biología . Entonces tenemos
Si una persona ha de escoger como vestirse, teniendo 4 camisas, 6
pantalones, 5 pares de calcetines y 2 pares de zapatos, entonces
tiene 4 × 6 × 5 ×2 = 240 formas de vestirse, ya que cada elección
de la camisa (4 opciones) tiene 6 opciones para el pantalón, lo que
da 4 × 6 = 24 opciones para la camisa y pantalón. Para cada una
de esas 24 tiene 5 pares de calcetines, totalizando 120 formas, y
para cada una de esas tiene dos opciones de los zapatos, de modo
que se duplica el total y al final tiene
Calcula las posibles agrupaciones que se pueden
establecer con todos los elementos de un grupo, por lo tanto, lo que diferencia a
cada subgrupo del resto es el orden de los elementos.
Calcula el número de subgrupos de 1, 2, 3, etc. elementos que se pueden
establecer con los "n" elementos de una muestra.
Cada subgrupo se diferencia del resto en los elementos que lo componen o en el orden de dichos elementos (es lo que le
diferencia de las combinaciones).
Determina el número de subgrupos de 1, 2, 3, etc. elementos que se pueden
formar con los "n" elementos de una nuestra. Cada subgrupo
se diferencia del resto en los elementos que lo componen,
sin que influya el orden.
Combinaciones Calcular las posibles combinaciones
de 2 elementos que se pueden
formar con los números 1, 2 y 3
El termino " n ! " se denomina
"factorial de n" y es la
multiplicación de todos los
números que van desde "n" hasta
1.
Se pueden establecer 3 parejas diferentes: (1,2), (1,3) y
(2,3). En el cálculo de combinaciones las parejas (1,2) y
(2,1) se consideran idénticas, por lo que sólo se cuentan una
vez. Para calcular el número de combinaciones se aplica la
siguiente fórmula:
Por ejemplo: 4 ! = 4 * 3 * 2 * 1 = 24
Variaciones Calcular las posibles variaciones de 2 elementos
que se pueden establecer con los número 1, 2 y 3.
Ahora tendríamos 6 posibles parejas: (1,2), (1,3), (2,1), (2,3), (3,1) y
(3,3). En este caso los subgrupos (1,2) y (2,1) se consideran distintos.
Para calcular el número de variaciones se aplica la siguiente fórmula:
La expresión "Vm,n" representa las variaciones
de "m" elementos, formando subgrupos de "n"
elementos. En este caso, como vimos en la
lección anterior, un subgrupo se diferenciará del
resto, bien por los elementos que lo forman, o
bien por el orden de dichos elementos.
Permutaciones Calcular las posibles formas en que se pueden
ordenar los número 1, 2 y 3.
Hay 6 posibles agrupaciones: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1,
2) y (3, 2, 1)
Para calcular el número de permutaciones se aplica la siguiente fórmula:
La expresión "Pm" representa las
permutaciones de "m" elementos,
tomando todos los elementos. Los
subgrupos se diferenciaran únicamente
por el orden de los elementos.
Es una lista ordenada de objetos,
cada uno de ellos denominado término
(también elemento o miembro) de la sucesión
y al número de elementos ordenados
(posiblemente infinitos) se le denomina la
longitud de la sucesión.
A diferencia de un conjunto, el
orden en que aparecen los términos sí es
relevante y un mismo término puede
aparecer en más de una posición. De
manera formal, una sucesión puede
definirse como una función sobre el
conjunto de los números naturales (o un
subconjunto del mismo) y es por tanto una
función discreta.
Una sucesión infinita de
números reales en azul (imagen). La
sucesión no es ni creciente, ni
decreciente, ni convergente, ni es una
sucesión de Cauchy. Sin embargo, sí
es una sucesión acotada.
Sucesión monótona
creciente
Una sucesión es monótona
creciente si se cumple que
para todo n natural an <=
an+1 (a1 <= a2 <= a3 <= ...
<= an).
Ejemplo:
an = n es monótona
creciente.
a1 = 1, a2 = 2, a3 = 3, a4 =
4, ...
Sucesión monótona
decreciente
Una sucesión es monótona
decreciente si se cumple que
para todo n natural an >= an+1
(a1 >= a2 >= a3 >= ... >=
an).
Ejemplo:
an = 1/n es monótona
decreciente.
a1 = 1, a2 = 1/2, a3 = 1/3, a4
= 1/4, ...
Límite finito de una
sucesión
Consideremos la sucesión an
= 1/n.
a1 = 1
a2 = 1/2 = 0.5
a3 = 1/3 ≈ 0.33
a4 = 1/4 = 0.25
a5 = 1/5 = 0.2
a6 = 1/6 ≈ 0.17
a7 = 1/7 ≈ 0.14
a8 = 1/8 ≈ 0.12
a9 = 1/9 ≈ 0.11
a10 = 1/10 = 0.1
A medida que aumenta n,
los términos de la sucesión
son cada vez más cercanos a
0
Límite infinito de una sucesión
Consideremos la sucesión an = n2.
a1 = 1
a2 = 4
a3 = 9
a4 = 16
...
a10 = 100
...
a100 = 10.000
Al crecer n, an no tiende a un límite
definido, sino que crece más allá de
toda cota. Se dice que an tiende a
infinito.
|
La sucesión (A, B,
C) es una sucesión
de letras que
difiere de la
sucesión (C, A, B).
En este caso se
habla de
sucesiones finitas
(de longitud igual
a 3). Un ejemplo
de sucesión
infinita sería la
sucesión de
números positivos
pares: 2, 4, 6, 8, ...
En ocasiones se identifica a las
sucesiones finitas con
palabras sobre un conjunto.
Puede considerarse
también el caso de una
sucesión vacía (sin
elementos), pero este caso
puede excluirse
dependiendo del contexto.
Ejemplo:
an = 1/n
a1 = 1, a2 = 1/2, a3 =
1/3, a4 = 1/4, ...
Definición:
((an),(bn)) es un par de sucesiones monótonas convergentes si a) an es creciente y bn decreciente. b) Para todo n natural an <= bn c) Para todo ε>0 existe h natural / bh - ah < ε
Ejemplo:
an = -1/n, bn = 1/n
an es creciente.
Debemos probar que an+1 >= an, o sea an+1 - an >= 0
-1/ n +1 - -1/n = -n + n + 1/ n (n +1) = 1/ n2 + n } 0
·
bn es decreciente.
Debemos probar que bn+1 <= bn, o sea bn - bn+1 >= 0
1/n - 1/n + 1= n+1 –n/n(n+1)= 1/n2 + n }0
Para todo n an < bn
-1/n < 1/n + 1 pues -n < n para todo n.
Dado ε>0, existe h / bh - ah < ε
1/h - -1/h= 2/h < ε
Para que se cumpla basta tomar un h > 2/ε
Es una ecuación que define
una secuencia recursiva; cada término de
la secuencia es definido como una función
de términos anteriores
Una relación de recurrencia para la
sucesión es una ecuación que relaciona
con alguno de sus predecesores .
Las condiciones iniciales para
la sucesión son valores dados en forma
explícita para un número finito de
términos de la sucesión.
Resolver una
relación de recurrencia
consiste en determinar
una fórmula explícita
(cerrada) para el término
general , es decir una
función no recursiva de
n.
Iteración
Para resolver una relación de recurrencia asociada a la sucesión: por iteración, utilizamos la relación de
recurrencia para escribir el n-ésimo término en términos
de algunos de sus predecesores. Luego
utilizamos de manera sucesiva la relación de
recurrencia para reemplazar cada uno de los términos por algunos de sus predecesores. Continuamos hasta llegar a
alguno de los casos base.
Recurrencias Lineales
El adjetivo lineal indica que cada término de la secuencia
está definido como una función lineal de sus
términos anteriores. El orden de una relación de
recurrencia lineal es el número de términos
anteriores exigidos por la definición.
En la relación el orden es dos, porque debe haber al menos dos términos anteriores (ya
sean usados o no).
Recommended