jueves, 5 de agosto de 2010

TEORÍA COMBINATORIA

Teoría combinatoria

El origen de los problemas de conteo o “teoría combinatoria” se relaciona con juegos de azar, más concretamente con los juegos de cartas y dados. El tratamiento teórico de los problemas de conteo se inicia en el siglo XVII con los matemáticos Blaise Pascal (1623-1662) y Pierre de Fermat (1601-1665). El problema es que dio origen a la teoría que tiene que ver con la división de las apuestas en un juego de lanzamientos de monedas.

Actualmente la teoría combinatoria es en parte el cerebro organizador de las ciencias computarizadas, y el modelo que nos dota de un mejor razonamiento para implementar programas eficientes. En este sentido, la combinatoria es el área de mayor expansión en las matemáticas modernas, y un reciente grupo de científicos han recomendado cursos de combinatoria en colegios y universidades.

Especialistas de distintas ramas indagan cada día más en tópicos de combinatoria en la certeza de hallar en sus métodos una mayor compresión y evaluación de sus temas de análisis. Problemas de enumeración, estructuras lógicas, probabilidades finitas, optimización y algoritmos en investigación sobre operaciones discretas son del interés de todo hombre de ciencias y la computación juega en ellas un papel fundamental. Igualmente, en la teoría de invariantes, en la teoría de representación de grupos, en la teoría de funciones simétricas, las reglas combinatorias explican y amplifican numerosas propiedades que a la vez son de gran aplicabilidad en física, química y biología.

1) Variaciones

Son aquellas formas de agrupar elementos de un conjunto teniendo en cuenta que influye el orden en que se colocan y si permitimos que se repitan los elementos, podemos hacerlo hasta tantas veces como elementos tenga la agrupación.

Existen dos tipos:

· Variaciones sin repetición: de h elementos tomados de p en p se definen como las distintas agrupaciones formadas con p elementos distintos, eligiéndolos entre los n elementos que disponemos, considerando una variación distinta a otra tanto si difieran en algún elemento como si están situados en distinto orden.

El número de variaciones que se pueden construir se pueden calcular mediante la fórmula:

SÍNTESIS ÓPTIMA DE



Ejemplo: ¿Cuántos números de tres cifras distintas se pueden formar con las nueve cifras significativas del sistema decimal?

Al tratarse de números el orden importa y además nos dice "cifras distintas" luego no pueden repetirse.



Por tanto, se pueden formar 504 números:

· Variaciones con repetición: de h elementos tomados de p en p se definen como la distintas agrupaciones formadas con p elementos que pueden repetirse, eligiéndolos de entre los u elementos de que disponemos, considerando una variación distinta a otra tanto si difieren en algún elemento como si están situados en distinto orden.

El número de variaciones que se pueden construir se puede calcular mediante la fórmula:




Ejemplos:

¿Cuantos números de tres cifras se pueden formar con las nueve cifras significativas del sistema decimal?

Al tratarse de números el orden importa y además no dice nada sobre "cifras distintas" luego si pueden repetirse.



Por tanto, se pueden formar 729 números

¿Cuantas palabras distintas de 10 letras (con o sin sentido) se pueden escribir utilizando sólo las letras a, b?

Al tratarse de palabras el orden importa y además como son palabras de 10 letras y sólo tenemos dos para formarlas, deben repetirse.




Por tanto, se pueden formar 1024 palabras

2) Permutaciones

Son también llamadas ordenaciones. Son aquellas formas de agrupar elementos de un conjunto teniendo en cuenta que influye el orden en que se colocan, tomamos todos los elementos de que se disponen, serán permutaciones sin repetición cuando todos los elementos de que disponeos son distintos y serán permutaciones con repetición si disponemos de elementos repetidos (ese es el número de veces que se repite el elemento en cuestión).

Es por ello que también se llama ordenaciones.

· Permutaciones sin repetición de h elementos se define como las distintas formas de ordenar todos esos elementos distintos, por lo que la única diferencia entre ellas es el orden de colocación de sus elementos.

El número de estas permutaciones será:

Ph= h!

Ejemplo:

Con las letras de la palabra DISCO ¿cuantas palabras distintas se pueden formar?

Evidentemente, al tratarse de palabras el orden importa. Y además n = m, es decir tenemos que formar palabras de cinco letras con cinco elementos D, I, S, C, O que no están repetidos.


Por tanto, se pueden formar 120 palabras

· Permutaciones con repetición de h elementos tomados de a en a, de b en b, de c en c, entre otros., cuando en los h elementos existen elementos repetidos (un elemento aparece a veces, otro b veces otro c veces, entre otros) verificándose que a + b + c…=n

El número de permutaciones será:

3) Combinaciones

Son aquellas formas de agrupar elementos de un conjunto teniendo en cuenta que no influye el orden en que se colocan y si permitimos que se repitan los elementos, podemos hacerlo hasta tantas veces como elementos tenga la agrupación.

Existen dos tipos de combinaciones:

· Combinaciones sin repetición: de h elementos tomados de p en p se definen como las distintas agrupaciones formadas con p elementos distintos, eligiéndolos de entre los h números de que disponemos, considerando una variación distinta a otra sólo si difieren en algún elemento (no influye el orden de colocaciones de sus elementos).

El número de combinaciones que se pueden construir se pueden calcular mediante la fórmula:



Ejemplo:

Cuantos grupos de 5 alumnos pueden formarse con los treinta alumnos de una clase. (Un grupo es distinto de otro si se diferencia de otro por lo menos en un alumno)

No importa el orden (son grupos de alumnos). No puede haber dos alumnos iguales en un grupo evidentemente, luego sin repetición.



Por tanto, se pueden formar 142506 grupos distintos.


· Combinaciones con repetición: de h elementos tomados de p en p se definen como las distintas agrupaciones formadas con p elementos que pueden repetirse, eligiéndolos de entre los h elementos de que disponemos, considerando una variaciones distinta a otra si difieren en algún elemento (no influye el orden de colocación de sus elementos).

El número de combinaciones que se pueden construir se puede calcular mediante:



Ejemplo:

En una confiteria hay cinco tipos diferentes de pasteles. ¿De cuántas formas se pueden elegir cuatro pasteles)

No importa el orden (son pasteles). Puede haber dos o más pasteles en un grupo, luego con repetición.
Por tanto, se pueden formar 142506 grupos distintos :


No hay comentarios:

Publicar un comentario en la entrada