Teoría Combinatoria

La Combinatoria es una rama de las matemáticas cuyo objeto es estudiar las posibles agrupaciones de objetos que podemos llevar a cabo de un modo rápido teniendo en cuenta las relaciones que deben existir entre ellas.

Por ejemplo:
Con 5 colores diferentes ¿cuántas banderas tricolores podemos hacer? Una bandera de otra se diferencia en tener un color diferente o en el orden de colocación de los colores.

Estas 3 banderas son diferentes y pertenecen a Luxemburgo, Rusia y Yugoslavia.
Si te dicen que con 5 colores diferentes podemos hacer 10 banderas tricolores probablemente dudarías un poco.

Con las cifras 1, 2, 3, 4, 5 y 6 ¿cuántos números de tres cifras, diferentes, por supuesto, puedo formar? Un número es diferente de otro si tiene una cifra distinta o el orden de sus cifras es diferente. 321 y 123 son números distintos aunque tengan las mismas cifras.
Con los datos anteriores podríamos formar 20 números diferentes.

¿De cuántas maneras diferentes pueden sentarse los 25 alumnos de la clase en los pupitres?

Si te dicen que de muchas, te quedas igual, pero si te dicen que de  maneras diferentes quizá no lo creas, sí, el número tiene 26 cifras. Parece imposible.

La Teoría Combinatoria es la parte de Matemáticas que se encarga de crear grupos de datos, objetos, etc., y además de llevar a cabo los cálculos necesarios.

Áreas de la Combinatoria

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

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.

Esta 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.

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

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 clarificar, 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.

EJEMPLOS DE EJERCICIOS DE COMBINATORIA:

1_¿De cuántas formas diferentes se pueden cubrir los puestos de presidente, vicepresidente y tesorero de un club de fútbol sabiendo que hay 12 posibles candidatos?

No entran todos los elementos.

Sí importa el orden.

No se repiten los elementos.

2_ Con las letras de la palabra libro, ¿cuántas ordenaciones distintas se pueden hacer que empiecen por vocal?

La palabra empieza por i u o seguida de las 4 letras restantes tomadas de 4 en 4.

Sí entran todos los elementos.

Sí importa el orden.

No se repiten los elementos.

3_ ¿De cuántas formas pueden mezclarse los siete colores del arco iris tomándolos de tres en tres?

No entran todos los elementos.

No importa el orden.

No se repiten los elementos.