Principios Básicos

Principio de Multiplicación (Regla del producto)

Sean A₁,A₂,…, A_n conjuntos finitos, entonces |A₁ x A₂ x … x A_n| = |A₁| . |A₂|  ….  . |A_n|

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 A₁,A₂,…, A_n conjuntos finitos y disjuntos, entonces |A₁ ∪ A₂ ∪ … ∪ A_n| = |A₁| + |A₂| +  ….  + |A_n|

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 A₁, A₂ 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 | = $\frac{10!}{7!}$

El número de permutaciones de r objetos de n en ordén pero sin repetición es: P(n, r) = $\frac{n!}{\left(n-r!\right)}$

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 10³.

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

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) = $\left(\genfrac{}{}{0ex}{}{n}{r}\right)=$$\frac{n!}{r!.\left(n-r\right)!}$
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

$$\left(\genfrac{}{}{0ex}{}{0}{0}\right)=\frac{0!}{0!.0!}=1$$

$$\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\frac{n!}{0!.n!}=1$$

$$\left(\genfrac{}{}{0ex}{}{n}{1}\right)=\frac{n!}{1!.n!}=1$$

$$\left(\genfrac{}{}{0ex}{}{n}{n}\right)=\frac{n!}{0!.n!}=1$$

Números combinatorios complentarios

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!.\left(n-k\right)!}=\frac{n!}{\left(n-k\right)!.k!}=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$$

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) =  $\frac{6!}{3!.3!}$. $\frac{3!}{2!.1!}$. 1 = $\frac{6!}{3!.2!}$  = 60

El número de permutaciones diferentes de n objetos; donde hay n₁objetos indistinguibles de tipo 1, n₂ objetos indistinguibles de tipo 2, …, n_k objetos indistinguibles de tipo k; es:
$\frac{n!}{n_1!.n_2!\dots .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) = $\frac{52!}{47!.5!}$. $\frac{47!}{42!.5!}$$\frac{42!}{47!.5!}$. $\frac{37!}{32!.5!}$=  $\frac{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 n_i objetos, i = 1,2, …, k; es:
$\frac{n!}{n_1!.n_2!\dots .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