Combinatoria Basica
Enviado por lscz • 19 de Abril de 2013 • 689 Palabras (3 Páginas) • 523 Visitas
Introducción
La combinatoria es la disciplina de las matemáticas que se refiere a las técnicas de contar. En realidad lo que trata de responder es a la pregunta ¿Cuantos son? sin tener que contarlos.
En general las técnicas de contar proveen una serie de alternativas al momento de tener que escribir programas complicados que cuenten todos los valores y permiten tener expresiones, que solucionen el problema aplicando fórmulas simples.
Técnicas básicas para contar
En esta parte recordaremos una serie de fórmulas de la combinatoria y mostraremos como son aplicadas en la programación. No desarrollaremos los conceptos matemáticos porque no corresponde a lo que el texto pretende, que es mostrar la forma de resolver problemas.
Regla del Producto
Si un conjunto A tiene |A| posibilidades y el B tiene
|B| posibilidades entonces existen |A| x |B| formas de combinar estos.
Por ejemplo si tengo 4 tipos de automóviles y 3 colores se tienen 12 combinaciones. Estas combinaciones pueden representarse en una matriz cuadrada almacenando en cada celda una combinación. En el caso de tres conjuntos con una matriz de tres dimensiones, vea que el espacio ocupado o el recorrido de los elementos se hace cada vez más grande
Regla de la suma
Si un conjunto A tiene |A| posibilidades y el B tiene |B| posibilidades entonces existen |A| + |B| posibles formas en las que A o
B pueden ocurrir. En el ejemplo anterior si uno de los automóviles, o de los colores es errado, existen 4 + 3 = 7 posibles ítems fallados.
Regla inclusión y exclusión
Esta es una regla generalizada de la suma.
Supongamos que tenemos automóviles de 5 colores y minibuses de 6 colores y queremos conocer cuantos colores diferentes existen. En este caso tenemos dos conjuntos que se superponen. Esto significa sumar la cantidad de colores de ambos y restar los que sean comunes a ambos que se expresa como:
|A| U |B| = |A| + |B| − |A| \ |B|
Permutaciones
Una permutación es un arreglo de n ítems donde cada ítem aparece solo una vez. Existen 3! permutaciones para un conjunto de tres elementos. Si los elementos son 123 las permutaciones vienen a ser 123
132 231 213 312 321. Para un n arbitrario son n!. Hay que observar que a medida que aumenta n el número de permutaciones aumenta muy rápidamente.
Subconjuntos
Un subconjunto es la selección de algunos elementos de
...