Combinatoria

La Combinatoria estudia las propiedades y características de ciertos grupos de elementos, pertenecientes a un conjunto finito, que cumplen unas condiciones determinadas.

Dependiendo de las características que cumplan los elementos, los grupos podrán ser: Variaciones, Permutaciones o Combinaciones.

Variaciones

Se llaman Variaciones ordinarias de m elementos tomados de n en n (→ V_m,n), al número de grupos diferentes, de n elementos, que se pueden formar con los m elementos del conjunto, de tal manera que en cada grupo:

a) ⇒ Sí importa el orden de colocación de los elementos (los hace diferentes).
b) ⇒ No se repiten los elementos del conjunto.
c) ⇒ No entran todos los elementos del conjunto.

Queremos saber los números de dos cifras distintas (n=2) que se pueden formar con los dígitos: 1, 3, 5, 7 , (m=4).

Con cada dígito podemos formar 3 números de dos cifras:
13-15-17 → 31-35-37 → 51-53-57 → 71-73-75
Como tenemos 4 dígitos hemos formado en total → 4*3 = 12 números.

Observamos que en cada número:

• Influye el orden de colocación → no es lo mismo 13 que 31.
• Y no se repiten → el enunciado dice dos cifras distintas.
• No entran todos los dígitos → de cuatro dígitos entran dos.

Al cumplir estas condiciones serán Variaciones ordinarias → V_4,2 = 4*3 = 12

(Esto equivale al producto de 2 factores decrecientes a partir de 4).

Generalizando, las variaciones ordinarias, de m elementos tomados de n en n, equivalen al producto de n factores decrecientes a partir de m →
V_m,n = m.(m-1).(m-2).(m-3). ..... (m-n+1)

Ejemplo ¿Cuántas contraseñas de dos caracteres distintos se pueden formar con los caracteres:A, 4, j, 6?

Factorial de un número

Dado un número natural n, llamamos factorial de n, y lo denotamos por n!, al producto de los "n" factores consecutivos desde "n" hasta 1. → n! = n · (n - 1) · (n - 2) · ... · 3 · 2 · 1

Las variaciones ordinarias también se pueden calcular por factoriales con la fórmula →

Variaciones con repetición

En las Variaciones con repetición los elementos se pueden repetir y si influye su orden de colocación. Se representan → VR_m,n

Queremos saber las Variaciones con repetición que se pueden formar con los dígitos: 2, 4 y 6 → (m = 3).

De 1 cifra (n=1) → 2-4-6 → (3) → VR_3,1= 3 → 3¹
De 2 cifras (n=2) → 22-24-26, 42-44-46, 62-64-66 → (9) → VR_3,2= 9 → 3²
De 3 cifras (n=3): Podemos formar, empezando:
por 2 → 222-224-226-244-246-266-264-242-262 → (9)
por 4 → 444-442-446-422-426-466-462-424-464 → (9)
por 6 → 666-662-664-622-624-644-642-646-626 → (9)
Total 9 * 3 = 27 → VR_3,3= 27 → 3³

Siguiendo este procedimiento, es fácil deducir la fórmula para generalizar el cálculo de las Variaciones con repetición de m elementos tomados de n en n

Puede haber casos en los que el número de elementos (n) de los grupos a formar sea superior al de elementos que nos dan (m). Es decir → n > m. En estos casos se tienen que repetir algunos elementos.

Ejemplo Con los dígitos 1 y 5, ¿cuántos números de tres cifras se pueden formar?.

Permutaciones

Se llaman Permutaciones ordinarias o simplemente Permutaciones, al número de grupos diferentes que se pueden formar con todos los elementos de un conjunto, de tal manera que en cada grupo :

a) ⇒ Entran todos los elementos (m = n).
b) ⇒ Influye el orden de colocación.
c) ⇒ No se repiten los elementos.

Las Permutaciones de m elementos, coinciden con las Variaciones de m elementos tomados de m en m. ⇒ P_m = V_m,m = m!

Ejemplo ¿Cuántos números diferentes de 5 cifras distintas se pueden formar con los digitos del número 45378?

Permutaciones Circulares

Las permutaciones circulares ⇒ PC_m, son un caso especial que se emplea para ordenar los elementos en círculo, por ejemplo para sentarse alrededor de una mesa.

Queremos saber de cuántas formas distintas se pueden sentar seis amigos (m=6) en una mesa circular.

a) ⇒ Influye el orden en que se sienten, → cada uno tiene su asiento en la mesa.
b) ⇒ Y no se repiten → un amigo no puede sentarse en dos asientos.
Al cumplir estas condiciones pueden ser Permutaciones ordinarias, P₆ = 6!

Pero hay que tener en cuanta que, una vez sentados, al ser la mesa circular, si todos los amigos se mueven un asiento a su derecha la colocación en la mesa sigue siendo la misma, todos tienen a su derecha y a su izquierda al mismo amigo.

Como hay seis (m=6) asientos, cada una de las formas de sentarse se repite seis veces (m=6). Luego, al total de las formas de sentarse hay que dividirlo por seis (m=6).

Por tanto → PC₆ = P₆ / 6 = 6! / 6 = (6.5.4.3.2.1) / 6 = 5.4.3.2.1 = 5! = 120 formas distintas

Este resultado coincide con las Permutaciones ordinarias de un elemento menos (m-1 = 6-1 = 5) → P₅, de donde se deduce que → PC₆ = P_(6-1) = P₅ = 5! = 120. Generalizando →

Permutaciones con repetición

En las Permutaciones con repetición, los distintos grupos se diferencian solo en el orden de colocación de los elementos y estos se repiten un número indicado de veces.

Queremos calcular los números de 4 cifras que se pueden formar con los dígitos del número 2.225

El número de elementos del conjunto es 4 → m = 4, y el 2 se repite 3 veces. Los números que podemos formar son 4 → 5222 - 2522 - 2252 - 2225

Observamos que:

1º) ⇒ El número 2 se repite tres veces.
2º) ⇒ Los números se diferencian solo en el orden de colocación.

Por tanto son Permutaciones con repetición de 4 elementos y uno de ellos se repite 3 veces. Su representación es → PR₄³ = 4 (los 4 números que hemos obtenido), donde el índice (3) indica el número de veces que se repiten los números.

¿Cómo se calculan?. Con cada uno de los números que hemos formado, por ejemplo 5222, si el dígito que se repite 3 veces fuera distinto 5-134, obtendríamos los números 5-134, 5-143, 5-314, 5-341, 5-413, 5-431 → 6 números distintos, es decir las permutaciones de 3 elementos → P₃ = 3! = 6

Esto implica que si a las PR₄³ las multiplicamos por las P₃ (si no se repitieran 3 dígitos) obtenemos las P₄ (que son las que se obtendrían si no se repitiera ningún dígito).

PR₄³ * P₃ = P₄ → PR₄³ = P₄ / P₃ = 4! / 3! = (4.3.2.1)/(3.2.1) = 4

Para calcular las Permutaciones con repetición de m elementos que se repiten v₁,v₂,v₃,...,v_n veces, se puede generalizar la fórmula →

Ejemplo ¿Cuántos números diferentes de cinco cifras se pueden formar con los dígitos del número 44.666?

Combinaciones

Se llaman Combinaciones ordinarias o simplemente Combinaciones de m elementos tomados de n en n ⇒ (C_m,n) al número de grupos diferentes que se pueden formar con los m elementos de un conjunto, de tal manera que en cada grupo:

1º) ⇒ No importa el orden de colocación de los elementos.

2º) ⇒ No entran todos los elementos del conjunto.

Ejemplo Para asistir a un concurso, queremos saber cuántos equipos de dos alumnos (n=2) se pueden formar con Ana, Luis, Pedro y María que son los cuatro alumnos (m=4) que tienen mejores notas.

Con Ana podemos formar 3 equipos → Ana-Luis, Ana-Pedro, Ana-María.

Con Luis podemos formar 2 equipos (Luis-Ana es el mismo que Ana-Luis) → Luis-Pedro, Luis-María.

Con Pedro podemos formar solo 1 equipo (Pedro-Ana es el mismo que Ana-Pedro y Pedro-Luis es el mismo que Luis-Pedro) → Pedro-María

Con María no podemos formar níngún equipo porque ya está incluida en todos los demás.

En total hemos formado → 3 + 2 + 1 = 6 equipos.

Observamos que en cada equipo:

⇒ No Influye el orden de colocación → Luis-Ana es el mismo que Ana-Luis.

⇒ No se repiten → un alumno no se puede repetir en un equipo.

⇒ No entran todos los alumnos → de cuatro alumnos entran dos.

Al cumplir estas condiciones serán Combinaciones → C_4,2 = 6

Si en cada uno de los 6 equipos formados cambiamos el orden de los dos amigos, (lo hacemos con P₂ = 2!), obtenemos 2 equipos distintos, lo que nos daría un total de 6*2 = 12 equipos. Al influir el orden de colocación serían V_4,2 = 4 * 3 = 12. Por lo tanto →

C_4,2 * P₂ = V_4,2 Despejando → C_4,2 = V_4,2 / P₂ = (4*3) /(2*1) = 12 / 2 = 6

Esta fórmula se puede generalizar para m elementos tomados de n en n→

Ejemplo A la vuelta de las vacaciones se reunen seis amigos, y se intercambian saludos entre todos. ¿Cuántos saludos se intercambiarán?.

Combinaciones con repetición

En las Combinaciones con repeticióndos los elementos se pueden repetir y no influye su orden de colocación. Los grupos se diferencian en algún elemento. Se representan → CR_m,n

Las Combinaciones con repetición, de m elementos tomados de n en n, equivalen a las Combinaciones ordinarias de m+n-1 elementos tomados de n en n →

Ejemplo ¿De cuántas formas podemos elegir tres pasteles en una pasteleria que tiene siete tipos distintos de pasteles?.