La Combinatoria es la parte de las Matemáticas que estudia las diversas formas de realizar agrupaciones con los elementos de un conjunto, formándolas y calculando su número.
Existen distintas formas de realizar estas agrupaciones, según se repitan los elementos o no, según se puedan tomar todos los elementos de que disponemos o no y si influye o no el orden de colocación de los elementos:
• Variaciones sin repetición.
• Variaciones con repetición.
• Permutaciones sin repetición.
• Permutaciones con repetición.
• Combinaciones sin repetición.
• Combinaciones con repetición.
2.- - Combinaciones sin repetición Definición: Dado un conjunto de n elementos distinguibles, se llama combinación sin repetición de p elementos, con
p < n, elegidos entre los n, a cualquier subconjunto de p elementos distintos del conjunto. Notación: El n´umero de combinaciones sin repetición de p elementos elegidos entre los n se nota habitualmente C
p
n
.
Valor: C
p
n =
n
p
.
Ejemplo: Un estudiante debe responder a seis de las diez preguntas de las que consta un examen, ¿entre cuantos
grupos de preguntas distintas puede elegir? Solución:
Se trata de determinar el n´umero de grupos distintos de seis preguntas escogidas del conjunto de las diez, sabiendo
que dos grupos con las mismas preguntas, a´un en distinto orden, coinciden
3. - Combinaciones con repetición Definición: Dado un conjunto de n elementos distinguibles, se llama combinación con repetición de p elementos
escogidos entre los n a cualquier colección de p elementos del conjunto, con repeticiones eventuales de algunos de
ellos. Notación: El n´umero de combinaciones con repetición de p elementos elegidos entre los n se nota habitualmente
CRp
n
.
Valor: CRp
n =
n − 1 + p
p
.
Ejemplo: ¿De cu´antas formas pueden elegirse simultáneamente tres bolas de una urna en la que hay al menos tres
bolas bolas blancas y tres negras indistinguibles? Solución:
Cada grupo es una disposici´on no ordenada de tres colores formada por los colores blanco y negro con repetici´on de
alguno de ellos. Por tanto, se trata de determinar el n´umero de grupos de tres elementos no ordenados del conjunto
{b, n}.
4.1 -Principios básicos de recuento
En esta primera sección del tema daremos la definición formal de cardinal de un conjunto y
los principios básicos que se utilizan para computar este cardinal para conjuntos concretos
4.1.1 Cardinal de un conjunto
Contar los elementos de un conjunto A es establecer una biyeccion entre A y un conjunto finito
{1, . . . , n}. Definición 4.1.1. Diremos que el cardinal de un conjunto A es n si se puede establecer una
biyeccion f : {1, . . . , n} −→ A. Se denota |A| = n. Se define |∅| = 0.
Se dice que A 6= ∅ es infinito si no existe ninguna biyeccion f : {1, . . . , n} −→ A para ningún n ∈ N.
4.1.2 Principio de la unión Si se puede escoger un elemento de un conjunto A de m formas distintas, y un elemento de
un conjunto B de n formas distintas, entonces es posible escoger un elemento de A o de B de
m + n formas distintas (si A y B son disjuntos).
Teorema 4.1.2 (Principio de la unión). Si A1, A2, . . . , An son conjuntos finitos disjuntos dos
a dos se tiene que
|A1 ∪ A2 ∪ · · · ∪ An| = |A1| + |A2| + · · · + |An|.
Ejemplo 4.1.3. El numero de palabras del diccionario es igual al n´umero de palabras que
empiezan por a m´as el n´umero de palabras que empiezan por b m´as . . . m´as el n´umero de
palabras que empiezan por z.
4.1.3 Principio del complementario
Teorema 4.1.4 (Principio del complementario). Si B es un conjunto finito y A es un subconjunto
de B se tiene que
|B \ A| = |B| − |A|.
4.1.4 Principio del producto
Si se puede escoger un elemento de un conjunto A de m formas distintas, y un elemento de un
conjunto B de n formas distintas, entonces es posible escoger un elemento de A y otro de B
de mn formas distintas.
Teorema 4.1.5 (Principio del producto). Si A1, A2, . . . , An son conjuntos finitos no vacios
se tiene que
|A1 × A2 × · · · × An| = |A1| · |A2| · · · |An|.
Ejemplo 4.1.6. El n´umero de palabras posibles de cuatro letras formadas solo por vocales es
5 · 5 · 5 · 5.
fuentes consultadas:
http://www.dma.fi.upm.es/docencia/grado_ii/matemática_discreta_1/resumen/técnicas_contar.pdf.
http://www.dma.fi.upm.es/docencia/grado_ii/matemática_discreta_1/resumen/técnicas_contar.pdf
No hay comentarios:
Publicar un comentario