Combinatoria

De Wikipedia, la enciclopedia libre

Contenidos relacionados con Matemática

La combinatoria es una rama de la matemática que estudia colecciones finitas de objetos que satisfacen unos criterios especificados, y se ocupa, en particular, del "recuento" de los objetos de dichas colecciones (combinatoria enumerativa) y del problema de determinar si cierto objeto "óptimo" existe (combinatoria extremal). Uno de los más destacados combinatorialistas de los últimos tiempos ha sido Gian-Carlo Rota, cuyas contribuciones han ayudado a formalizar el tema desde la década de 1960. El prolífico matemático Paul Erdős trabajó principalmente en problemas extremales. El estudio de cómo contar objetos es a veces considerado por separado como el campo de la enumeración.

Un ejemplo de pregunta combinatoria es la siguiente: ¿Cuántas ordenaciones pueden hacerse en un mazo de 52 cartas? Ese número es 52! (o sea, "cincuenta y dos factorial"). Es el producto de todos los números naturales desde 1 al 52. Puede parecer sorprendente lo extremadamente grande que es este número, alrededor de 8,07 × 10⁶⁷. Es algo más de 8 seguido de 67 ceros. Comparando ese número con otros números enormes, es mayor que el cuadrado del número de Avogadro, 6,02 × 10²³, "el número de átomos, moléculas, etc., que hay en un mol" y es del mismo orden magnitud, 10⁶⁷, que la cantidad de átomos en la Vía Láctea.

[editar] Funciones enumerativas

Contar de cuántas maneras puede formarse cierto patrón es el punto de partida de la combinatoria. Sea S un conjunto de n elementos. Las combinaciones de k elementos de S son subconjuntos de S de k elementos (en los que el orden en que se listan es irrelevante). Las variaciones de k elementos de S son sucesiones de k elementos distintos de S (dos de tales sucesiones son distintas si tienen los mismos elementos pero en distinto orden). Cuando las variaciones son de los n elementos del conjunto, se denominan permutaciones. Las fórmulas que calculan estas cantidades son bien conocidas y ubicuas en la combinatoria.

De un modo más general, dada una colección infinita de conjuntos finitos {S_i}, cuyo índice típicamente recorre los números naturales, la combinatoria enumerativa estudia diversas formas de describir una función enumerativa, f(n), que cuente el número de elementos de S_n para cualquier n. Aunque contar el número de elementos de un conjunto es un problema ubicuo en la matemática, en un problema combinatorio los elementos de S_i por lo general tienen una descripción combinatoria simple y poca estructura adicional.

Las funciones enumerativas más simples son fórmulas cerradas, que se pueden expresar como una composición de funciones elementales, tales como factoraiales, potencias, etc. Como se ha dicho anteriormente, el número de posibles ordenaciones distintas de un mazo de n cartas es

f (n) = n!

Este planteamiento no siempre es satisfactorio (ni práctico) para cualquier problema combinatorio. Por ejemplo, sea f(n) el número de conjuntos distintos formados a partir de los enteros del intervalo [1,n] que no contienen dos enteros consecutivos; así, con n = 4, tendremos {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}, luego f(4) = 8. La función f(n) resulta ser el número de Fibonacci de orden n+2, cuya expresión en una fórmula cerrada es

$f(n) = \frac{\phi^{n+2}}{\sqrt{5}} - \frac{(1-\phi)^{n+2}}{\sqrt{5}}$ ,

donde φ = (1 + √5) / 2 es la razón áurea. Sin embargo, dado que estamos buscando un número entero, la presencia de √5 en el resultado puede considerarse "antiestética" desde un punto de vista combinatorio. De modo alternativo, f(n) se puede expresar a través de la recurrencia

f (n) = f (n - 1) + f (n - 2)

que puede resultar más satisfactoria (desde un punto de vista puramente combinatorio), puesto que muestra más claramente por qué el resultado es el que es.

Otro método es hallar una fórmula asintótica

$f(n) \sim g(n)$ ,

donde g(n) es una función "familiar", y donde f(n) se acerca a g(n) cuando n tiende a infinito. En ciertos casos, una expresión asintótica puede resultar preferible a una fórmula cerrada terriblemente complicada que no proporcione ninguna información acerca del comportamiento del número de objetos contados. En el ejemplo anterior, una fórmula asintótica sería

$f(n) \sim \frac{\phi^{n+2}}{\sqrt{5}}$

cuando n es muy grande.

Finalmente, y esto resulta de gran utilidad, f(n) se puede expresar a través de una serie de potencias formal, denominada función generatriz, que puede ser tanto la función generatriz ordinaria

$\sum_{n\ge 0} f(n) x^n$

como la función generatriz exponencial

$\sum_{n\ge 0} f(n) \frac{x^n}{n!}$ .

Una vez determinada, la función generatriz suele permite extraer toda las formas anteriores de expresar f(n). Además, las diversas operaciones naturales con funciones generatrices, tales como la adición, multiplicación, derivación, etc., tienen significado combinatorio, y esto permite extender los resultados de un problema combinatorio con el fin de resolver otros.

[editar] Resultados

Se pueden estudiar patrones muy sutiles y probar algunos teoremas sorprendentes sobre ellos. Un ejemplo de tales teoremas se debe a Frank P. Ramsey:

Supongamos que 6 personas se encuentran en una fiesta. Cada par de personas o bien se conocen previamente, o bien no se conocen. En todo caso, siempre se pueden encontrar 3 de esas 6 personas que o bien se conocen entre sí, o bien ninguna conoce a las otras dos.

La demostración se procede por reducción al absurdo: supongamos que no hay 3 personas que cumplan lo que afirma el teorema. Consideremos cualquier persona de las 6 que van a la fiesta y llamémosla A. De entre las 5 personas restantes tiene que haber 3 que, o bien conocen a A (y A las conoce a ellas), o bien no la conocen. Sin pérdida de generalidad supondremos que hay 3 personas que conocen a A. Pero entonces, de entre esas 3 personas debe haber al menos 2 que se conozcan entre sí (de lo contrario ya habría 3 personas que no se conocen entre sí. Pero entonces, esas dos personas y A son 3 personas que se conocen entre sí. (Este es un caso especial del teorema de Ramsey).

Se puede conseguir una demostración alternativa mediante doble recuento: se cuentan el número de tripletas ordenadas de personas (A,B,C), en las que las personas A y B se conocen, pero no B y C. Supongamos que la persona K conoce a k de las otras 5. Entonces es la persona B de exactamente k(5 k) tripletas (A debe ser una de las k personas que conoce y C una de las 5-k que no conoce). Por lo tanto, es la persona B de 0*5=0, 1*4=4 o 2*3=6 tripletas. Como hay 6 personas, y cada una es la persona B de como mucho 6 tripletas, hay como mucho 36 tripletas.

Considérense ahora 3 personas de las que exactamente 2 de ellas se conocen entre sí. Está claro que podemos formar con ellas dos tripletas distintas: tomando como C la que es desconocida, y poniendo las otras dos en lugar de A y B de las dos formas en que esto puede hacerse. Del mismo modo, si exactamente 2 parejas se conocen entre sí, también se pueden organizar en una tripleta de dos formas distintas: se toma como A la persona que los otros dos conocen, y las otras se colocan como B y C de las dos maneras en que esto es posible. Hay, por lo tanto, como mucho 36/2=18 tripletas en las que exactamente una pareja o dos parejas se conocen entre sí. Como hay 20 tripletes, debe haber como mucho 2 de ellos en los que o bien se conocen todos, o bien todos son desconocidos entre sí.

La idea de encontrar un orden en configuraciones aleatorias da lugar a la teoría de Ramsey. Esencialmente, esta teoría afirma que cualquier configuración suficientemente grande contendrá al menos un caso de cualquier otro tipo de configuración.

[editar] Véase también

Principios combinatorios
- Regla de la suma
- Regla del producto
- Demostración por biyección
- Regla del bibliotecario
- Principio del palomar
- Principio de inclusión-exclusión
- Método de elementos distinguidos
- Teorema de Ramsey
Publicaciones importantes en combinatoria
Lista de temas sobre combinatoria
Teoría musical de conjuntos
Combinatoria infinita
- Teorema de Ramsey infinito
- Teorema de Erdos-Rado

[editar] Referencias

Handbook of Combinatorics, Volumes 1 and 2, R.L. Graham, M. Groetschel and L. Lovász (Eds.), MIT Press, 1996. ISBN 026207169X
Enumerative Combinatorics, Volumes 1 and 2, Richard P. Stanley, Cambridge University Press, 1997 and 1999, ISBN 0-521-55309-1N
The solution of a combinatorial problem