Análisis Combinatorio (Lógica Computacional)


ANÁLISIS COMBINATORIO

PRINCIPIOS BÁSICOS DEL PROCESO DE CONTAR:

•Teorema 1: (Principio de multiplicación):
Sean S={a1;a2;...;am} un conjunto de “m” elementos y T={b1;b2;...;bn} un conjunto de
“n” elementos, el número de pares (aj;bk) que pueden ser formados tomando un elemento de S y un elemento de T es: “nm”.

Ejemplo:

Cuatro universidades desean contratar los servicios de unempleado para cada una de las áreas: Biblioteca, mantenimiento y personal. ¿Cuántas oportunidades de trabajo se presentan?

Ejemplo:

Para ir de la ciudad “A” a la ciudad “C” existen tres caminos diferentes y de la ciudad “B” a la ciudad “C” hay cinco caminos diferentes. ¿De cuántas formas diferentes se podrá ir desde “A” hasta “C” pasando necesariamente por “B”?.

•Teorema 2: (Agrupamientomúltiples):
Sean S1={a1;a2;...;an1} un conjunto de “n1” elementos, S2={b1;b2;...;bn2} un conjunto de
“n2” elementos, ..., Sr={x1;x2;...;xnr} un conjunto de “nr” elementos entonces es posible formar: : n=n1 x n2 x... x nr grupos ordenados con r elementos cada uno de la forma: (aj1;bj2;...;xjr), donde aj1es un elemento de S1; bj2es un elemento de S2;...; xjr es un elemento de Sr.

Ejemplo: Unconductor de automóvil puede tomar cualquiera de las tres rutas para ir de la ciudad “A” hasta la ciudad “B”, estando en “B” puede tomar cualquiera de las cinco rutas para ir de la ciudad “B” a la ciudad “C”, finalmente estando en “C” puede tomar cualquiera de las dos rutas para ir de la ciudad “C” a la ciudad “D”. ¿De cuántas formas diferentes podrá ir desde “A” hasta “D” pasando por “B” y “C”.•¿Cuántos números de tres cifras se pueden formar con los dígitos 2; 4; 6; 9? (No se permiten repeticiones de cifras)

•Teorema 3: (Principio de Adición):
Si dos decisiones son mutuamente excluyentes y la primera se puede tomar de “m” maneras y la segunda de “n” maneras una o la otra se pueden tomar de “m+n” maneras.

Ejemplo:

•Un estudiante debe viajar a la ciudad “A” o a la ciudad“B”. Para ir a la ciudad “A” existen cuatro caminos diferentes y para ir a la ciudad “B” existen cinco caminos diferentes. ¿De cuántas formas diferentes podrá realizar el viaje?
•Para ir de la ciudad “P” a la ciudad “Q” hay tres caminos diferentes, para ir de la ciudad
“Q” a la ciudad “R” hay dos caminos diferentes y para ir de la ciudad “P” a la ciudad “R” hay tres caminos diferentes.
¿De cuántasformas se podrá ir de “P” a “R”?

ARREGLOS:
•ARREGLO SIMPLE:
Un arreglo simple de “n” objetos diferentes tomados de “k” en “k” es una ordenación de “k” objetos entre los “n” dados, de tal modo que estos grupos difieren en algún elemento o en su ordenación.

•Teorema 4:
El número de todos los arreglos a formarse con “n” objetos tomados de “k” en “k” es obtenido por la fórmula:Ejemplo:

¿De cuántas maneras diferentes se pueden sentar ocho personas en una banca con capacidad para cinco personas?

•ARREGLO CON REPETICIÓN:
Son aquellos arreglos en que cualquiera de sus elementos puede repetirse en el mismo grupo, el número de veces que se indique.

•Teorema 5:
El número de todos los arreglos con repetición a formarse con “n” objetos tomados de “k” en “k” es obtenidopor la fórmula:



Ejemplo:

El Ministerio de transporte desea determinar la numeración para placas de matrícula de automóviles compuesto por dos letras y dos números. ¿Cuántas placas diferentes se podrán construir?

•Para el ejemplo anterior: si las placas están compuestas por dos letras y cuatro números. ¿Cuántas placas diferentes se podrán fabricar?

PERMUTACIONES:
•PERMUTACIÓNSIMPLE:
Son los diferentes grupos que pueden formarse con los “n” objetos dados de modo que intervengan todos los elementos en cada grupo y cuya diferencia está dada en el orden de colocación.
•Teorema 6:
El número de permutaciones distintas que pueden formarse con “n” objetos se obtiene mediante la fórmula:


•¿De cuántas maneras diferentes se podrán sentar cuatro personas en cuatro...