2
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

Combinatoria enumerativa

Embed Size (px)

DESCRIPTION

combinarotia

Citation preview

Page 1: Combinatoria enumerativa

Combinatoria enumerativaLa 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

Page 2: Combinatoria enumerativa

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.