Combinatoria
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.
La combinatoria analiza todo tipo de posibilidades al momento de considerar la cantidad de opciones posibles en un conjunto finito de objetos. Tiene en cuenta la repetición posible de los mismos, y la no repetición, al igual que los intercambios de posiciones de los elementos con respecto a su ubicación y orden específicos. Estos tipos de operaciones se denominan Variaciones, combinaciones y permutaciones.
A su vez, las combinaciones se pueden r
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 todos 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, 2*3=6, 3*2=6, 4*1=4 ó 5*0=0 tripletas. Es decir, que una persona podrá participar en una tripleta en la posición B a lo sumo 6 veces y como hay 6 personas, entoces, 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 en total 20 tripletes posibles, debe haber al menos 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.
BIBLIOGRAFIA:
http://es.wikipedia.org/wiki/Combinatoria
No hay comentarios:
Publicar un comentario