guia teoria de conteo. alonzo charry

Matemática Discreta Prof. Alonzo Charry

UNIVERSIDAD DR RAFAEL BELLOSO CHACIN

FACULTAD DE INGENIERIA

ESCUELA DE INFORMATICA

CATEDRA: MATEMATICA DISCRETA

UNIDAD II

GUIA: TEORIA DEL CONTEO

PAGINAS: 16

PROF. ALONZO CHARRY

1


UNIDAD II

Teoría del Conteo

Regla de la suma

Si una primera tarea puede realizarse de m formas y una segunda tarea puede realizarse de n formas, y no es posible realizar ambas tareas de manera simultánea, entonces para realizar cualquiera de ellas pueden utilizarse cualquiera de m + n formas.

Ejemplo

Una biblioteca tiene 40 libros de historia y 50 de filosofía. Si un estudiante quiere

aprender acerca de alguno de estos dos temas, por la regla de la suma puede elegir

entre 40 + 50 = 90 libros.

(Nota: el estudiante no quiere estudiar historia y filosofía, sino historia o filosofía.)

La regla puede ampliarse a más de dos tareas, siempre que ningún par de ellas pueda

ocurrir simultáneamente.

Regla del producto

Si un procedimiento se puede descomponer en dos etapas y si existen m

resultados posibles de la primera etapa, y para cada uno de estos resultados, existen n

resultados posibles para la segunda etapa, entonces el procedimiento total se puede

realizar, en el orden dado, de m.n formas.

2


Ejemplos

1. Para una obra de teatro hay 6 hombres y 8 mujeres que aspiran a los papeles

principales. El director puede elegir a la pareja principal de 6.8 = 48 formas.

Esta regla también puede ampliarse a más de dos etapas.

2. Si las placas de los automóviles constan de 2 letras seguidas de 4 dígitos, y

ninguna letra o dígito se puede repetir, ¿cuántas placas diferentes son posibles?

27.26.10.9.8.7 = 3.538.080.

Si se pueden repetir las letras y los dígitos, serán posibles 27.27.10.10.10.10 =

7.290.000 placas diferentes.

Definición

Factorial

Para un natural n, se define n! (n factorial) como:

0! = 1

n! = n(n-1)(n-2)...3.2.1 para n >= 1

Notar que n! = n(n-1)!

Definición

Permutación

Dado un conjunto de n elementos, se denomina permutación a cada uno de los

conjuntos que se pueden formar con estos elementos tales que cada uno de ellos

difiere de otro en el orden en que son considerados los elementos.

Dicho de otro modo, dada una colección de n objetos distintos, cualquier disposición

lineal de estos objetos se denomina permutación de la colección.

3


Pongamos un ejemplo: un grupo de 5 personas va a sentarse en fila para una foto.

¿Cuántas disposiciones lineales son posibles?

5 4 3 2 1

------ ------ ------ ------ ------

1a pos 2a pos 3a pos 4a pos 5a pos

Cualquiera de las 5 personas puede ocupar la primera posición de la fila. Para la

segunda posición podemos elegir entre 4 personas. Continuando de esta manera, sólo

tenemos una persona para ocupar la quinta posición. Esto produce un total de 5.4.3.2.1

= 120 disposiciones posibles de las 5 personas. Se obtiene exactamente la misma

respuesta si las posiciones se ocupan en otro orden (por ejemplo, 3ª posición, 1ª

posición, 4ª, 5ª y 2ª).

En general, si existen n objetos distintos, el número de permutaciones para los n

objetos es

n(n-1)(n-2)...1 = n!

| | | |

| | | n-ésima pos

| | 3ª pos

| 2ª pos

1ª pos

Pn = n!

Se lee "permutaciones de n".

Ejemplo

Dadas las letras a, b, c existen seis formas de disponerlas: P3 = 3! = 3.2.1 = 6.

Las seis permutaciones son:

a b c

a c b

b a c

4


b c a

c a b

c b a

Definición

Arreglos

Dado un conjunto de n elementos, se denomina arreglos de tamaño r a todos los

conjuntos de r elementos escogidos de entre los n, tales que un conjunto difiere de otro

en al menos un elemento o en el orden en que se consideran los elementos.

Consideremos el ejemplo siguiente: en un grupo de 10 personas, se elegirá a 5 y

se les ubicará en fila para una foto. ¿Cuántas disposiciones son posibles?

10 9 8 7 6

------ ------ ------ ------ ------

1a pos 2a pos 3a pos 4a pos 5a pos

Cualquiera de las 10 personas puede ocupar la primera posición de la fila. Para

ocupar la segunda posición tenemos 9 personas. Siguiendo de esta manera, hay 6

personas de donde elegir para que ocupen la quinta posición. Esto produce 10.9.8.7.6

= 10.240 disposiciones posibles.

En general, si existen n objetos distintos, y r es un entero, con 0 <= r <= n,

entonces el número de arreglos de tamaño r para los n objetos es

n!

n(n-1)(n-2)...(n-r+1) = ------

| | | | (n-r)!

| | | r-ésima pos

| | 3ª pos

| 2ª pos

1ª pos

5


n n!

Ar = ------

(n-r)!

Se lee "arreglos de n en r".

Ejemplo

Dadas las letras a, b, c podemos formar 6 arreglos de tamaño 2.

3 3! 3.2.1

A2 = --- = ----- = 6

1! 1

Los 6 arreglos son:

a b

b a

a c

c a

b c

c b

Definición

Combinaciones

Dado un conjunto de n elementos, se denomina combinaciones de tamaño r a

todos los conjuntos que se pueden formar con r elementos tomados de entre los n

elementos, de modo que cada conjunto difiera de los demás en por lo menos un

elemento.

Siguiendo con el mismo ejemplo, si en un grupo de 10 personas se elegirá a 5

para tomarles una foto, ¿cuántos grupos de 5 pueden formarse, si el orden no importa?

6


Si el orden importara, habría A105 disposiciones diferentes. Pero en este caso no

interesa el orden, así que si una de las posibilidades es Juan, María, Luis, Ana y Pedro,

entonces la permutación Luis, Pedro, María, Ana y Juan corresponde a la misma

combinación. Cada grupo de 5 personas puede ordenarse de 5! formas diferentes. Así,

cada combinación corresponde a 5! permutaciones. Por lo tanto, el número de

combinaciones satisface P5.(nº de combinaciones) = A105

o sea que el número de combinaciones es igual a

10

A5

---- = 252

P5

En general, dados n objetos distintos, el número de combinaciones de tamaño r

de estos objetos, con 0 <= r <= n, se denota Cnr y corresponde a

n

n Ar n!

Cr = ---- = --------

Pr r!(n-r)!

Se lee "combinaciones de n en r".

Ejemplo

Dadas las letras a, b, c existen 3 combinaciones de tamaño 2.

3 3!

C2 = ---- = 3

2!1!

Las 3 combinaciones son:

a b

7


a c

b c

Combinaciones complementarias

Demostración:

n n! n! n

Cn-r = ---------------- = -------- = Cr

(n-r)!(n-(n-r))! (n-r)!r!

Ejemplo

Resolver la siguiente ecuación:

10 10

Cx+2 = C3x

Hay dos posibilidades:

que las combinaciones sean idénticas, es decir que x+2 = 3x => 2x = 2 => x = 1.

O que sean combinaciones complementarias, en cuyo caso x + 2 + 3x = 10, o

sea 4x = 8, o sea x = 2.

Teorema de Stieffel

Demostración:

n n n! n! n!(r-1)!(n-r+1)! + n!r!(n-r)!

Cr + Cr-1 = ------- + ------------ = -----------------------------

r!(n-r)! (r-1)!(n-r+1)! r!(n-r)!(r-1)!(n-r+1)!

8


n!(r-1)!(n-r)!(n-r+1+r)! n!(n+1) (n+1)! n+1

= ------------------------ = --------- = --------- = Cr

| r!(n-r)!(r-1)!(n-r+1)! r!(n-r+1) r!(n+1-r)

|

sacamos factores comunes: n!(r-1)!(n-r)!

Ejemplo

Hallar m en la siguiente ecuación:

6 6 7

Cm-1 + Cm-2 = C2

7 7

Cm-1 = C2

=> m - 1 = 2 => m = 3

m - 1 + 2 = 7 => m = 6

Tanto m=3 como m=6 son solución de la ecuación

9


Ejercicios

Recordar que con frecuencia existen varias vías para resolver un problema dado.

Tener en cuenta también que resulta muy útil hacer esquemas o dibujos para visualizar

mejor los problemas.

Reglas de la suma y el producto

1. ¿Cuántas palabras de tres letras se pueden formar con cinco consonantes y tres

vocales de modo que cada palabra comience y termine en consonante?

2. Determine el número de enteros de seis dígitos (que no comiencen con cero) en

los que

3. Ana y María vieron a dos hombres alejarse en automóvil frente a una joyería,

justo antes de que sonara una alarma contra robos. Cuando fueron interrogadas

por la policía, las dos jóvenes dieron la siguiente información acerca de la placa

(que constaba de dos letras seguidas de cuatro dígitos). María estaba segura de

que la segunda letra de la placa era una O o una Q, y que el último dígito era un

3 o un 8. Ana dijo que la primera letra de la placa era una C o una G y que el

primer dígito era definitivamente un 7.

¿Cuántas placas diferentes tendrá que verificar la policía?

4. Tres pueblos, designados como A, B y C, están intercomunicados por un

sistema de carreteras de doble sentido.

a. ¿De cuántas formas puede Juan ir del pueblo A al pueblo C?

b. ¿Cuántos trayectos puede hacer Juan del pueblo A al pueblo C y de

regreso al pueblo A?

c. ¿Cuántos de los trayectos completos de la parte (b) son tales que el viaje

de regreso (del pueblo C al pueblo A) es diferente, al menos

10


parcialmente, de la ruta que toma Juan del pueblo A al pueblo C? (Por

ejemplo, si Juan viaja de A a C por las rutas R1 y R6 podría regresar por

las rutas R6 y R2, pero no por R1 y R6).

Permutaciones

1.

a. ¿Cuántas permutaciones existen para las ocho letras a,b,c,d,e,f,g,h?

b. ¿Cuántas de las permutaciones de (a) comienzan con la letra a?

c. ¿Cuántas de las permutaciones de (a) comienzan con la letra a y

terminan con la letra c?

2. ¿De cuántas formas es posible ordenar los símbolos a,b,c,d,e,e,e,e,e de modo

que ninguna e quede junto a otra?

3.

a. ¿De cuántas maneras se pueden colocar las letras de VISITING?

Si consideramos que las tres I son distintas, podemos formar P8 palabras.

Así, la permutación VI1SI2TI3NG sería distinta de VI2SI1TI3NG. Pero esto

no es lo que queremos, en realidad no hay diferencia entre esas dos

permutaciones. Como las tres I pueden ubicarse de P3 maneras, cada

palabra se está repitiendo P3 veces. Por lo tanto hay P8/P3 = 8!/3! =

6.720 disposiciones diferentes.

b. ¿Cuántas de ellas tienen las tres letras I juntas?

Las restantes 5 letras pueden ordenarse de P5 formas. Las 3 letras I

pueden ubicarse en 6 posiciones diferentes: al principio, al final o en

cualquiera de los 4 espacios entre las otras 5 letras. Así, hay 6.5! = 6! =

720 palabras con las tres I juntas.

11


Combinaciones

1. Un estudiante que realiza un examen debe responder 7 de las 10 preguntas. El

orden no importa. ¿De cuántas formas puede responder el examen?

2. Juan quiere dar una fiesta para algunos de sus amigos. Debido al tamaño de su

casa, sólo puede invitar a 11 de sus 20 amigos. ¿De cuántas formas puede

seleccionar a los invitados?

3. En una reunión de 6 personas, ¿cuántos saludos de mano pueden

intercambiarse, si entre cada 2 personas, se dan la mano una sola vez?

4. Una persona que sale de vacaciones desea llevarse 4 libros para leer: dispone

de 4 novelas policiales y 6 libros de cuentos cortos. ¿De cuántas formas puede

hacer la elección si quiere llevar al menos una novela?

5. ¿Cuántos bytes contienen

a. exactamente dos unos?

b. exactamente cuatro unos?

c. exactamente seis unos?

d. al menos seis unos?

6. ¿De cuántas formas es posible distribuir 12 libros diferentes entre cuatro niños

de modo que

a. cada niño reciba tres libros.

b. los dos niños mayores reciban cuatro libros cada uno y los dos menores

reciban dos libros cada uno.

7. Un comité de 12 personas será elegido entre 10 hombres y 10 mujeres. ¿De

cuántas formas se puede hacer la selección si

a. no hay restricciones?

b. debe haber seis hombres y seis mujeres?

c. debe haber un número par de mujeres?

d. debe haber más mujeres que hombres?

e. debe haber al menos 8 hombres?

12


Arreglos

1. Cuatro nadadores van a disputar la final del campeonato mundial. Los premios

son: 1º-medalla de oro, 2º-medalla de plata y 3º-medalla de bronce. ¿De cuántas

maneras pueden ser distribuidas esas medallas?

2. Con los dígitos 0,1,2,3,4,5

a. ¿Cuántos números de tres cifras se pueden formar?

b. ¿Cuántos son pares?

3.

a. ¿Cuántas palabras pueden formarse con las letras de la palabra

TRIANGULO?

b. ¿Cuántas comienzan con T y terminan en O?

c. ¿Cuántas tienen las 4 vocales juntas?

d. ¿En cuántas la A ocupa lugar impar?

e. ¿En cuántas la A y la O ocupan lugares impares simultáneamente?

13


Principio del palomar

Este interesante principio fue formulado por primera vez de manera formal por

Peter Gustav Lejeune Dirichlet (1805-1859), y en consecuencia se conoce a veces

como el principio de distribución de Dirichlet o el principio de la caja de Dirichlet.

Dirichlet contribuyó mucho en las matemáticas aplicadas y la teoría de números.

Además realizó un trabajo fundamental con respecto a la definición de una función. Su

trabajo enfatizaba la relación entre dos conjuntos de números y no pedía la existencia

de una fórmula o expresión que relacionara los dos conjuntos.

Si m palomas ocupan n nidos y m > n, entonces al menos un nido tiene dos o

más palomas en él.

Ejemplo

Una oficina emplea a 13 oficinistas, por lo que al menos dos de ellos deben

cumplir años durante el mismo mes.

Los 13 oficinistas son las palomas y los 12 meses del año son los nidos. A cada

paloma le corresponde un nido (el mes en que cumple años). Como hay más palomas

que nidos, hay al menos un nido (mes) con dos o más palomas (oficinistas que

cumplen en ese mes).

Ejercicios

1. Demuestre que si 8 personas están en una habitación, al menos dos de ellas

cumplen años el mismo día de la semana.

2. En una lista de 600.000 palabras, donde cada palabra consta de 4 o menos

letras minúsculas, ¿pueden ser las 600.000 palabras distintas?

3. Si una persona puede tener no más de 200.000 cabellos, ¿es posible que en

una ciudad de 300.000 habitantes haya dos personas con la misma cantidad de

cabellos en la cabeza?

14


4. ¿Cuántas veces debemos tirar un sólo dado para obtener el mismo resultado

a. al menos dos veces?

b. al menos tres veces?

c. al menos n veces, para n >= 4?

5. Cualquier subconjunto de tamaño 6 del conjunto A={1,2,3,4,5,6,7,8,9} debe

contener dos elementos cuya suma es 10. Justificarlo.

Los pares de elementos de A que suman 10 son: {1,9}, {2,8}, {3,7} y {4,6}. Estos

son los nidos. Las palomas son los 6 números del subconjunto. Cada número va

al "nido" correspondiente, por ejemplo, el 1 va a {1,9}, el 2 va al {2,8}, y así.

Como 6 > 4, hay al menos dos números que van al mismo nido, es decir, hay

dos números que suman 10. (Si uno de los números es el 5, no lo consideramos,

de todas maneras hay 5 palomas y 4 nidos.)

1 2 8 3 7 4

{1,9}, {2,8}, {3,7} y {4,6}

Aplicación en Algoritmos

15


¿Cuánto vale la variable k después de correr el siguienteprograma (escrito en Python)?k = 0for i in [0,..,19]:

k=k+1k = 0for j in [0,..,29]:

k=k+1

¿Cuánto vale la variable k después de correr el siguienteprograma?k = 0for i in [0,..,19]:

for j in [0,..,29]:k=k+1

¿Cuánto vale la variable n después de correr el siguienteprograma?n = 0for i in [1,..,14]:

for j in [1,..,i]:for k in [1,..,j]:

n=n+1

Bibliografía:

Matemáticas Discretas. Autor: Richard JohnsonBaugh. Editorial Iberoamérica. Capitulo 3. Métodos de conteo

Matemáticas Discretas. Autor: Ramón Espinosa Armenta. Editorial Alfaomega. Capitulo 8. Conteo

http://www2.uca.es/matematicas/Docencia/ESI/1711003/Apuntes/Leccion3.pdf

16

guia teoria de conteo. alonzo charry

Documents