Tecnicas de conteo

Técnicas de Conteo
La combinatoria es el arte de contar, es decir, calcular inteligentemente cardinalidades de conjuntos y de enumerarlos, esto es, determinar los elementos de un conjunto descrito por alguna propiedad. Nosotros tenemos que contar objetos para resolver muchos tipos de problemas. Por ejemplo, el conteo se puede emplear para determinar la complejidad de los algoritmos, paradeterminar si hay suficientes números de teléfonos diferentes en una población, determinar la cantidad de contraseñas que pueden ser establecidas en una computadora, entre muchas otras aplicaciones.

Principios básicos de Conteo.
En esta unidad se presentan dos principios básicos de conteo. También se mostrará cómo pueden ser usados para resolver distintos problemas de conteo.

Regla de la suma.Si la primera tarea puede efectuarse de n1 maneras y la segunda tarea de n2, y estas dos tareas no pueden efectuarse al mismo tiempo, entonces hay n1+n2 maneras para hacer cualquier tarea.

Ejemplos:
Suponga que ya sea un miembro de la academia de matemáticas o un estudiante de matemáticas puede ser seleccionado como representante del comité universitario. ¿Cuántas diferentes selecciones puedenhacerse para escoger a este representante si hay 37 miembros de la academia de matemáticas y 83 estudiantes?
Solución: La primer tarea, escoger un miembro de la academia de matemáticas, puede ser efectuada en 37 maneras. La segunda tarea, escoger un estudiante, puede ser efectuada en 83 maneras. Usando la regla de la suma se concluye que 37 + 83 = 120 maneras para seleccionar un representantedel comité.

Es posible extender la regla de la suma a más de dos tareas. Suponga que las tareas T1,T2, …,Tm pueden ser realizadas de n1,n2,…,nm maneras, respectivamente, y ninguna de estas tareas puede efectuarse al mismo tiempo. Entonces el número de maneras para realizar una de estas tareas es n1+n2+…+nm.

Ejemplo:
Un estudiante puede escoger un proyecto computacional de una de treslistas. Las listas contienen 23, 15 y 19 proyectos, respectivamente. ¿Cuántos posibles proyectos hay para escoger?
Solución: El estudiante puede escoger un proyecto de la primer lista de 23 maneras, de la segunda 15 maneras y de la tercera de 19 maneras. Por lo tanto, hay 23 + 15 + 19 =57 proyectos para ser escogidos.

Ejemplo:
¿Cuál es el valor de k después de que el siguiente código ha sidoejecutado?
k = 0
for i1 = 1 to n1
k = k + 1
for i2 = 1 to n2
k = k + 1

for im = 1 to nm
k = k + 1
Solución: El valor inicial de k es cero. Este código está formado por m diferentes ciclos. Por cada vuelta que se le da a un ciclo, 1 es sumado a k. Sea Ti la tarea de atravesar por todo el i-ésimo ciclo. La tarea Ti puede efectuarse de ni maneras, debido a que el i-ésimo ciclo esatravesado ni veces. Como ningún ciclo puede realizarse al mismo tiempo, entonces la regla de la suma muestra que el valor final de k, el cual es el número de maneras de efectuar las tareas, es n1 + n2 + …+nm

La regla de la suma puede ser expresada en términos de conjuntos de la siguiente manera: A1, A2, …, Am con conjuntos disjuntos, entonces el número de elementos en la unión de estosconjuntos es la suma de elementos de cada uno de ellos.
|A1A2…Am|= |A1| + |A2| + |Am|

Regla del producto
Suponga que un procedimiento puede desglosarse en dos tareas. Si hay n1 maneras de realizar la primera tarea y n2 maneras de realizar la segunda tarea después de que la primera tarea fue llevada a cabo, entonces hay n1n2 maneras para hacer el procedimiento.
Ejemplo:
Las sillas de un auditorioestán etiquetadas con una letra y un número entero positivo que no excede a 100. ¿Cuál es el número de más grande de sillas que contienen una etiqueta diferente?
Solución: El procedimiento de etiquetar las sillas consiste en dos tareas diferentes, nombrémoslas, asignar una de las 26 letras del alfabeto y asignar uno de los 100 posibles enteros en la silla. La regla del producto muestra que...