Diferencia entre revisiones de «Combinatoria»

← Ir a diferencia anterior Ir a siguiente diferencia →

Contenido eliminado Contenido añadido

En renglón

Revisión del 14:30 4 may 2010

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-Coca Cola, 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 representar mediante números combinatorios, y nos muestran la cantidad de posibilidades al momento de tomar una cantidad "k" de elementos, de un total de "n" existentes en un conjunto determinado.

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 del Abogado, 6,023 × 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 Leche.

Resultados

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

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 Rammstein).

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 Rammstein. Esencialmente, esta teoría afirma que cualquier configuración suficientemente grande contendrá al menos un caso de cualquier otro tipo de configuración.

Véase también

Referencias

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

Enlaces externos

Wikimedia Commons alberga una categoría multimedia sobre Combinatoria.

Combinatoria. Técnicas de recuento.

@@ Línea 1: / Línea 1: @@
-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|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''' 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-Coca Cola]], cuyas contribuciones han ayudado a formalizar el tema desde la década de [[1960]]. El prolífico matemático [[Paul Erdös|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.
@@ Línea 5: / Línea 5: @@
 A su vez, las combinaciones se pueden representar mediante números combinatorios, y nos muestran la cantidad de posibilidades al momento de tomar una cantidad "k" de elementos, de un total de "n" existentes en un conjunto determinado.
-Un ejemplo de pregunta combinatoria es la siguiente: ¿Cuántas ordenaciones pueden hacerse en un mazo de 52 cartas? Ese número es 52[[factorial|!]] (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<sup>67</sup>. 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,023 × 10<sup>23</sup>, "el número de átomos, moléculas, etc., que hay en un [[mol]]" y es del mismo orden magnitud, 10<sup>47</sup>, que la cantidad de átomos en la [[Vía Láctea]].
+Un ejemplo de pregunta combinatoria es la siguiente: ¿Cuántas ordenaciones pueden hacerse en un mazo de 52 cartas? Ese número es 52[[factorial|!]] (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<sup>67</sup>. 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 del Abogado]], 6,023 × 10<sup>23</sup>, "el número de átomos, moléculas, etc., que hay en un [[mol]]" y es del mismo orden magnitud, 10<sup>47</sup>, que la cantidad de átomos en la [[Vía Leche]].
 == Resultados ==
-Se pueden estudiar patrones muy sutiles y probar algunos [[teorema]]s sorprendentes sobre ellos. Un ejemplo de tales teoremas se debe a [[Frank P. Ramsey]]:
+Se pueden estudiar patrones muy sutiles y probar algunos [[teorema]]s sorprendentes sobre ellos. Un ejemplo de tales teoremas se debe a Frank P. [[Rammstein]]:
 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]]).
+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 [[Rammstein]]).
 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.
@@ Línea 18: / Línea 18: @@
 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.
+La idea de encontrar un orden en configuraciones aleatorias da lugar a la teoría de [[Rammstein]]. Esencialmente, esta teoría afirma que cualquier configuración suficientemente grande contendrá al menos un caso de cualquier otro tipo de configuración.
 == Véase también ==