Principios Básicos

Principio de Multiplicación (Regla del producto)

Sean A1,A2,…, An conjuntos finitos, entonces |A1 x A2 x … x An| = |A1| . |A2|  ….  . |An|

Ej:
Tomemos 2 conjuntos:
A = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ; | A | = 10
B = { a, b, c, d, e, f } ; | B | = 5

Supongamos que quiero saber todos las posibles conjuntos formados por 1 elemento de A y otro de B, por ej: { 3, b }, { a, 2 }.

O visto desde lenguajes formales cual es la cantidad de posibles cadenas formadas por primero un elemento de A y después un elemento de B, Ej: “3b”, “2a”, “9c”, “3c".

Existen 10 elementos en A y 5 en B por lo que la solución es: | A | x | B |  = 50

Principio de Adición (Regla de la Suma)

Sean A1,A2,…, An conjuntos finitos y disjuntos, entonces |A1 ∪ A2 ∪ … ∪ An| = |A1| + |A2| +  ….  + |An|

Ej:

Supongamos que tengo que elegir un elemento de A o de B (del ejemplo anterior). Como |A| = 10 y |B| = 5 y A ∩ B = ∅ entonces |A ∪ B| = 15, o sea que existen 15 posibles elementos que puedo elegir.

Principio de Exclusión y Exclusión

Si A1, A2 son conjuntos finitos pero no disjuntos. Entonces |A ∪ B| = |A| + |B| – |A ∩ B|
Esto se generaliza para la unión de varios conjuntos.

Permutaciones

Permutaciones

Supongamos que quiero calcular la cardinalidad del conjunto G formado por las cadenas de 3 caracteres formadas por elementos de C= {n, m, p} tales que no se repita nunca ningún elemento: { “nmp”, “npm”, “mnp”, “mpn”, “pmn”, “pnm” }.
Por el principio de multiplicación, Existen 3 posibilidades para el primero, luego como no se repiten 2 para el segundo y 1 para el tercero.
| G | = 3! = 6

La forma de poner n objetos en ordén es: P(n, n) = n!

R-Permutaciones

Supongamos ahora que quiero saber la cardinalidad del conjunto H formado por todas las cadenas de 3 carácteres formadas por elementos de A= { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } sin que se repita nunca ningún elemento. Hay 10 posibilidades para el primer espacio, 9 para el segundo y 8 para el tercero, por lo que:

| H | = 10!7!

El número de permutaciones de r objetos de n en ordén pero sin repetición es: P(n, r) = n!(nr!)

Permutaciones con repetición

Supongamos que quiero saber la cardinalidad del conjunto formado por todas las cadenas de 3 caracteres formadas por elementos de A = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } en las que se puedan repetir los elementos. Por la regla del producto existen 10 posibilidades para el primer carácter, 10 para el segundo y 10 para el tercero, por lo que el resultado es 103.

El número de permutaciones de r objetos de n en ordén con repetición es: nr

Selecciones

r-combinaciones

Una r-combinación de elementos de un conjunto es una selección sin ordenar de r elementos del conjunto, es decir, de subconjuntos de r elementos.

El número de r-combinaciones de n elementos, donde n es un entero no negativo y r es un entero tal que 0 <= r <= n es: C(n, r) = (nr)=n!r! . (nr)!
Ej:

Supongamos que quiero calcular la cardinalidad del conjunto J formado por todos los posibles subconjuntos de 2 elementos que contienen elementos de D = {w, x, y, z},  C(4,2) = 6, ya que J = { {w, x}, {w,y} , {w,z}, {x, y}, {x, z}, {y, z}}.

Relación entre r-permutaciones y r-combinaciones

Las r-permutaciones de un conjunto de cardinalidad n se pueden obtener formando las C(n,r) r-combinaciones del conjunto ( o sea todas los posibles subconjuntos de tamaño r formados por los n elementos del conjunto ) y luego ordenando estos elementos de todas las formas posibles, como cada subconjunto tiene tamaño r esto puede hacerse de P(r, r) formas de lo que sigue que:

P(n, r) = C(n, r) . P(r, r)

Selecciones con repetición

En un conjunto con n elementos hay C(n + r – 1, r) combinaciones con repetición.

Ej:

Supongamos que en un grupo de monedas hay 3 tipos distintos de 1, 5 y 10 centavos y hay por lo menos 5 de cada una de ellas. Cuantos posibles combinaciones de 5 monedas es posible extraer de este grupo?  Es importante recalcar que las monedas de cada valor son indistinguibles entre si  y no importa el orden en que se seleccionan las monedas, por lo que hay 5 combinaciones con repetición de 3 elementos.
Supongamos que cuando elejimos las monedas las metemos en una caja con 3 compartimentos, 1 para cada  tipo de moneda, entre cada compartimento hay una barra que las separa, de esta manera algunas de las posibles combinaciones podrian representarse como:
** | * | **
* | | ****
|*****|
***|*|*
…. etc.
Se ve que el numero de seleccionar 5 monedas de entre 3 tipos distintos corresponde al numero de formas de colocar 2 barras y 5 asteriscos. Por lo que el número de formas de seleccionar las monedas es equivalente al número de formas de seleccionar 5 asteriscos de entre 7 posiciones posibles, que se puede hacer de C(7, 5) maneras.

Equivalencias de Números Combinatorios

(00)=0!0! . 0! =1

( n 0 ) = n ! 0 ! . n ! = 1

( n 1 ) = n ! 1 ! . n ! = 1

( n n ) = n ! 0 ! . n ! = 1

Números combinatorios complentarios

( n k ) = n ! k ! . ( n k ) ! = n ! ( n k ) ! . k ! = ( n n k )

Permutaciones con Objetos Indistinguibles y Distribuciones de Objetos en Cajas

Ej 4.5.8 de MD
¿Cuantas permutaciones se pueden realizar con las letras de la palabra “PAPAYA¨? . No se puede usar la formula general de Permutaciones porque la letra “A” se repite 3 veces y la letra “P” se repite 2. Por lo que debe pensarse así: se pueden seleccionar las posiciones de las 3 letras “A” de C(6, 3) formas distintas, las “P” se pueden colocar en C(3,2) formas distinras quedando C(1, 1) para la “Y”. Por la regla del Producto queda:
C(6,3) . C(3, 2) . C(1,1) =   6 ! 3 ! . 3 ! . 3 ! 2 ! . 1 ! . 1 = 6 ! 3 ! . 2 !   = 60

El número de permutaciones diferentes de n objetos; donde hay n1objetos indistinguibles de tipo 1, n2 objetos indistinguibles de tipo 2, …, nk objetos indistinguibles de tipo k; es:
n ! n 1 ! . n 2 ! . n k !

Ej 4.5.9 de MD
¿De cuántas formas se pueden distribuir a cuatro jugadores manos de 5 cartas usando una baraja de 5 cartas? . Observese que al primero se le pueden distribuir C(52, 5), al segundo C(47, 5), al terceso C(42, 5) y al cuarto C(37, 5) (Quedando 32 cartas en el maso como una 5ta clase posible). Por la regla del producto queda:
C(52, 5) . C(47, 5) . C(42, 5) . C(37, 5) = 52 ! 47 ! . 5 ! . 47 ! 42 ! . 5 ! 42 ! 47 ! . 5 ! . 37 ! 32 ! . 5 ! =   52 ! 5 ! . 5 ! . 5 ! . 5 ! . 32 !

El número de formas de distribuir n objetos distinguibles en k cajas distinguibles de forma que en la caja i-ésima haya ni objetos, i = 1,2, …, k; es:
n ! n 1 ! . n 2 ! . n k !

Referencias

Matemática Discreta y sus aplicaciones; Rosen, Kenneth H.; 5ª edición, Mc Graw Hill, 2004

Algebra I; Rojo, Armando; 21ª ed, Magister Eos; 2006