COMBINATORIA
COMBINATORIA: La Combinatoria estudia las ordenaciones o agrupaciones de un determinado número de elementos.En todo problema combinatorio hay varios conceptos claves que debemos distinguir:
1 POBLACION:Es el conjunto de elementos que estamos estudiando. Denominaremos con m al número de elementos de este conjunto.
2 MUESTRA:Es un subconjunto de la población. Denominaremos con n al número de elementos que componen la muestra.Los diferentes tipos de muestra vienen determinados por dos aspectos:
ORDEN:Es decir, si es importante que los elementos de la muestra aparezcan ordenados o no.
REPETICIÓN: La posibilidad de repetición o no de los elementos.
VARIACIONES
VARIACIONES ORDINARIAS
Se llama variaciones ordinarias de m elementos tomados de n en n (m ≥ n) a los distintos grupos formados por n elementos de forma que:
No entran todos los elementos.
Sí importa el orden.
No se repiten los elementos.
VARIACIONES CON REPETICIÓN
Se llamann variaciones con repetición de m elementos tomados de n en n a los distintos grupos formados por n elementos de manera que:
No entran todos los elementos si m > n. Sí pueden entrar todos los elementos si m ≤ n
Sí importa el orden.
Sí se repiten los elementos.
2 MUESTRA:Es un subconjunto de la población. Denominaremos con n al número de elementos que componen la muestra.Los diferentes tipos de muestra vienen determinados por dos aspectos:
ORDEN:Es decir, si es importante que los elementos de la muestra aparezcan ordenados o no.
REPETICIÓN: La posibilidad de repetición o no de los elementos.
VARIACIONES
VARIACIONES ORDINARIAS
Se llama variaciones ordinarias de m elementos tomados de n en n (m ≥ n) a los distintos grupos formados por n elementos de forma que:
No entran todos los elementos.
Sí importa el orden.
No se repiten los elementos.
VARIACIONES CON REPETICIÓN
Se llamann variaciones con repetición de m elementos tomados de n en n a los distintos grupos formados por n elementos de manera que:
No entran todos los elementos si m > n. Sí pueden entrar todos los elementos si m ≤ n
Sí importa el orden.
Sí se repiten los elementos.
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.
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).
- 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).
- 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 coheficiente binomial ).
- 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.
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.
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.