Programador

TÉCNICAS DE CONTEO (Análisis Combinatorio)

La teoría combinatoria estudia los métodos que permiten contar el número de diversos arreglos o selecciones que puede formarse con los elementos de conjuntos finitos. Entre sus aplicaciones prácticas está el cálculo de probabilidades, al permitir enumerar los casos favorables y casos posibles. Tiene también utilidad en otras ramas, como por ejemplo,el cálculo de la complejidad o tiempo de ejecución de un algoritmo o programa informático, al estimar el número de operaciones que se realizan en un procedimiento algorítmico. Definiciones previas: El factorial de un número natural n, que se denota por n!, se define como: n!=1·2·3...n, por convención se define 0!=1.
  El número combinatorio de n en k, que se denota por  k  , se define como:  n

n n!  =  k  k! (n − k )!  

Propiedades a)  0  =  n  = 1    
     n  n

b) 1  =  n − 1 = n    
   

 n

n



c)  k  =  n − k     
   

n

n



PRINCIPIO FUNDAMENTALES Principio de la Adición Si A puede realizarse de n formas diferentes y B puede realizarse de m formas diferentes y ambos no pueden realizarsesimultáneamente (solo se puede llevar a cabo uno de los 2) entonces A o B pueden realizarse de n+m formas diferentes. Este resultado se puede generalizar a más de 2 procesos. Ejemplo: Una repuesto de auto se vende en 6 tiendas de la ciudad A y en 8 tiendas de la ciudad B. ¿En cuantas tiendas se puede adquirir el repuesto? Respuesta: 6+8=14 Principio de la Multiplicación Si un proceso puede dividirse endos etapas o fases (simultáneas o no) y una puede realizarse de n formas diferentes y la otra de m formas diferentes, entonces el proceso puede efectuarse de n·m formas diferentes. Este resultado se puede generalizar a más de 2 etapas o fases. Ejemplos:

Se dispone de 3 vías para viajar de C1 a C2 y de 4 vías para viajar de C2 a C1. ¿De cuántas formas se puede organizar el viaje de ida yvuelta de C1 a C2. Respuesta: 3·4=12 Una matrícula para vehículos consta de 2 letras (considerar 26 letras del alfabeto) y a continuación 3 dígitos. a) ¿Cuántas matrículas pueden hacerse si las 2 letras son diferentes y también los 3 dígitos son diferentes? Respuesta: 26·25·10·9·8 = 468 000 b) ¿Cuántas matrículas pueden hacerse si las letras pueden coincidir e igualmente los dígitos pueden ser iguales?Respuesta: 26·26·10·10·10 = 676 000 TECNICAS DE CONTEO Permutación Si se tiene los elementos a1, a2, ..., an, cada ordenamiento diferente de esos n elementos recibe el nombre de permutación. Es importante resaltar que el orden es una característica importante en la permutación, cuando variamos el orden de los elementos se dice que permutamos dichos elementos y se obtiene otra permutación. Elnúmero total de permutaciones de n elementos es n! Ejemplo: El número total de permutaciones que se puede obtener con las letras A, B y C será: 3!=3.2=6, éstas serán: ABC BAC CAB ACB BCA CBA Permutaciones con repetición Dados n elementos de los cuales k1 son de la clase 1, k2 son de la clase 2,... y km son de la clase m, llamamos permutaciones con repetición de n elementos a los posibles arreglos quepodemos formar con n elementos, donde dos arreglos son distintos si varía el orden de los elementos diferentes. importa el orden entre los distintos pero no entre los iguales. se utilizan todos los elementos (n) de que se dispone. n! k1! k 2 ! ... k m !

k Pn 1 , k 2 , ... , k m =

Formas diferentes en que puede seleccionarse k elementos tomados de un grupo de n elementos Variaciones: Si elorden de los k elementos es importante (ordenamientos diferentes de los k elementos se considera una forma distinta de seleccionar los k elementos) entonces se llama variaciones.

El número de variaciones es igual a Vk =
n

n! (n − k )!

Combinaciones: Si el orden de los k elementos no es importante (ordenamientos diferentes de los k elementos se considera la misma forma de seleccionar...