Combinatoria

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

La combinatoria es una rama de la matemática perteneciente al área de matemáticas discretas que estudia la enumeración, construcción y existencia de propiedades de configuraciones que satisfacen ciertas condiciones establecidas. Además, estudia las ordenaciones o agrupaciones de un determinado número de elementos.

Historia[editar]

Los conceptos básicos sobre la combinatoria y los resultados enumerativos han aparecido a lo largo del mundo antiguo. En el siglo 6 AC, en la antigua India, el físico Sushruta asegura en el Susruta-samhita que es posible formar 63 combinaciones a partir de 6 sabores distintos, tomados de uno en uno, de dos en dos, etc., así calculando todas las 26 − 1 posibilidades. El historiador griego Plutarco debatió con Crisipo de Solos (3er siglo AC) e Hiparco de Nicea (2º siglo AC) sobre un problema enumerativo un tanto delicado, el cuál se demostró más adelante que guardaba relación con el número Schröder–Hiparcos.[1][2]

En la Edad Media, la combinatoria continuó siendo estudiada, sobre todo fuera de la civilización Europea. El matemático indio Mahāvīra (c. 850) acuñó una fórmula para el número de permutaciones y combinaciones,[3][4]​ y es posible que estas fórmulas ya resultaran familiares a los matemáticos indios a principios del siglo 6 DC.[5]​ El filósofo y astrónomo Rabbi Abraham ibn Ezra (c. 1140) estableció la simetría de los coeficientes binomiales, mientras que una fórmula concreta fue hallada más adelante por el talmudista y matemático Gersónides, en 1321.[6]​ El triángulo aritmético— un diagrama gráfico mostrando las relaciones entre los coeficientes binomiales— ya había aparecido en tratados matemáticos tan atrás como el siglo 10, y con el tiempo serían mejor conocidos como el Triángulo de Pascal.

Durante el Renacimiento, junto al resto de las matemáticas y las ciencias, la combinatoria disfrutó de un renacer. Trabajos de Pascal, Newton, Jacob Bernoulli y Euler se volvieron fundamentales en el emergente campo. En los tiempos modernos, los trabajos de J. J. Sylvester (a finales del siglo 19) y Percy MacMahon (a principios del siglo 20) ayudaron a asentar las bases para la combinatoria enumerativa y combinatoria algebráica. La teoría de grafos también disfrutó de una explosión de interés al mismo tiempo, en especial conexión con el teorema de los cuatro colores.

En la segunda mitad del siglo 20, la combinatoria sufrió un crecimiento rápido, que llevó al establecimiento de docenas de nuevos diarios y conferencias sobre este tema.[7]​ En parte, el crecimiento fue estimulado por las nuevas conexiones y aplicaciones en otros campos, desde álgebra hasta probabilidades, desde el análisis funcional a la teoría de números, etc. Estas conexiones terminaron por romper los bordes entre la combinatoria y partes de la matemática y la informática teórica, pero al mismo tiempo causó cierta fragmentación dentro del campo.

Áreas de la combinatoria[editar]

No existe una clasificación tajante de lo que constituye una subárea, sino que todas comparten cierto grado de traslape entre sí, al igual que con otras ramas de la matemática discreta. Diferentes autores proponen varias divisiones de la combinatoria por lo que cualquier listado es meramente indicativo. Por ejemplo, algunos autores consideran la teoría de grafos como una subárea de la combinatoria, mientras que otros la consideran un área independiente.

Entre las subdivisiones más comunes se encuentran las siguientes.

Combinatoria enumerativa[editar]

La combinatoria enumerativa o enumeración estudia los métodos para contar (enumerar) las distintas configuraciones de los elementos de un conjunto que cumplan ciertos criterios especificados.

Ésta fue una de las primeras áreas de la combinatoria en ser desarrollada, y como otras áreas más recientes se estudian sólo en cursos especializados, es común que se haga referencia a esta subárea cuando se menciona combinatoria en entornos escolares.

En todo problema combinatorio hay varios conceptos claves que debemos distinguir:

  • 1. Población:

Se llama así al conjunto de los elementos que estamos estudiando. Designaremos con una m al número de elementos del conjunto.

  • 2. Muestra:

Se trata de un subconjunto de la población. Se denominará con la letra n al número de elementos que forman la muestra.

Los tipos de la muestra vienen determinados por dos aspectos:

Orden

Determina si es importante o no que los elementos de la muestra aparezcan ordenados.

Repetición

La posibilidad de repetición o no de los elementos.


Factorial de un número natural

Es el producto de los “n” factores consecutivos desde “n” hasta 1. El factorial de un número se denota por n!.

n! = n · (n - 1) · (n - 2) · (n - 3)... · 3 · 2 · 1

0! = 1

Ejemplo:

Calcular factorial de 5 5! = 5 · 4 · 3 · 2 · 1 = 120


Ejemplo.


¿De cuántas formas se puede obtener 8 al tirar 2 dados?

Imagina que queremos contar de cuantas formas se puede obtener 8 al tirar un par de dados. Uno puede realizar el clásico diagrama de coordenadas:


Y concluir que hay 5 formas de obtener el 8. Con el mismo diagrama, podemos encontrar el resultado f(k) para cualquier suma k:

f(2)=1, f(3)=2, f(4)=3, f(5)=4, f(6)=5, f(7)=6, f(8)=5, f(9)=4, f(10)=3, f(11)=2, f(12)=1.

Pero ¿qué pasa si queremos tirar tres dados? ¿cinco dados? ¿20 dados? ¿m dados? Ya no es práctico usar la representación de coordenadas, necesitamos un nuevo modelo.

Consideremos sólo un dado. ¿De cuantas formas podemos obtener el valor k? Pues de 1 forma si k=1,2,3,4,5,6 y 0 de cualquier otra forma. Vamos a codificar todos los resultados posibles en una única expresión: a + + + + +


Entre las cuentas, puede perder uno de punto de vista la idea central: estamos representando una sucesión de varios valores (formas de tirar un dado) mediante un solo objeto algebraico (un poliomio), y manipulaciones con este objeto nos dan información acerca de la combinatoria del problema.

El método puede modificarse para resolver problemas similares (por ejemplo, si quisiéramos saber de cuántas formas se puede obtener 30 al tirar 3 dados normales y dos dados en forma de icosaedro, intentaríamos encontrar el coeficiente de en el desarrollo de (a + + + + + ) · (a + + + ... + )

Este es un caso particular del método de funciones generadoras, en el que una serie de potencias representa una cantidad (posiblemente infinita) de valores de una sucesión.


Ejemplo.

Considérese el conjunto . Podemos imaginar que estos elementos corresponden a tarjetas dentro de un sombrero.

  • Un primer problema podría consistir en hallar el número de formas diferentes en que podemos sacar las tarjetas una después de otra (es decir, el número de permutaciones del conjunto).
Por ejemplo, dos formas distintas podrían ser: EIAOU o OUAIE.
  • Después, se puede preguntar por el número de formas en que se puede sacar sólo 3 tarjetas del sombrero (es decir, el número de 3-permutaciones del conjunto).
En este caso, ejemplos pueden ser IOU, AEI o EAI.
  • También se puede preguntar sobre cuáles son los posibles grupos de 3 tarjetas que se pueden extraer, sin dar consideración al orden en que salen (en otras palabras, el valor de un coeficiente binomial).
Aquí, consideraríamos AOU y UAO como un mismo resultado.
  • Otro problema consiste en hallar el número de formas en que pueden salir 5 tarjetas, una tras otra, pero en cada momento se regresa la tarjeta escogida al sombrero.
En este problema los resultados posibles podrían ser EIOUO, IAOEU o IEAEE.

La combinatoria enumerativa estudia las técnicas y métodos que permiten resolver problemas anteriores, así como otros más complejos, cuando el número de elementos del conjunto es arbitrario. De esta forma, en el primer ejemplo la generalización correspondiente es determinar el número de formas en que se pueden ordenar todos los elementos de un conjunto con n elementos, siendo la respuesta el factorial de n.

Combinatoria extremal[editar]

El enfoque aquí es determinar qué tan grande o pequeña debe ser una colección de objetos para que satisfaga una condición previamente establecida;

Ejemplo.

Considérese un conjunto S. con n elementos. A continuación se empieza a hacer un listado de subconjuntos de tal manera que cualquier pareja de subconjuntos del listado tenga algún elemento en común.

Para esclarecer, sea y un posible listado de subconjuntos podría ser

Conforme aumenta el listado (y dado que hay una cantidad finita de opciones), el proceso se hace cada vez más complicado. Por ejemplo, no podríamos añadir el conjunto {A, D} al listado pues aunque tiene elementos en común con los últimos 3 subconjuntos del listado, no comparte ningún elemento con el primero.

La pregunta sobre qué tan grande puede hacerse el listado de forma que cualquier pareja de subconjuntos tenga un elemento en común es un ejemplo de problema de combinatoria extremal (o combinatoria extrema). La respuesta a este problema es que si el conjunto original tiene n elementos, entonces el listado puede tener como máximo subconjuntos.

Véase también[editar]

Referencias[editar]

Enlaces externos[editar]