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 (→ Vm,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 → V4,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 →
Vm,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?

Datos. Tenemos 4 caracteres → m = 4; nos piden grupos de 2 → n = 2.
  • Sí importa el orden → No es lo mismo 4j que j4.
  • No se repiten → El enunciado dice caracteres distintos.
  • No entran todos los caracteres → De 4 tomamos 2.
    • Solución.
  • Según los datos, serán Variaciones ordinarias y el resultado es →
    • V4,2 = 4 . 3 = 12 contraseñas

    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

    4! = 4 . 3 . 2 . 1 = 24
    De acuerdo con la convención matemática de producto vacío,
    el valor de 0! debe definirse como: 0! = 1

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

    Vm,n = m! / (m-n)!

    V6,3 = 6! / (6-3)! = 6! / 3! = (6.5.4.3.2.1) / (3.2.1) = 6.5.4 = 120


    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 → VRm,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) → VR3,1= 3 → 31
    De 2 cifras (n=2) → 22-24-26, 42-44-46, 62-64-66 → (9) → VR3,2= 9 → 32
    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 → VR3,3= 27 → 33

    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

    VRm,n = mn

    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?.

    Datos. Tenemos 2 dígitos → m = 2; nos piden números de 3 cifras → n = 3.
  • Para formarlos se tiene que repetir algún dígito → n > m
  • Sí importa el orden → No es lo mismo 115 que 151.
    • Solución. Por tanto serán Variaciones con repetición
    VR2,3 = 23 = 8 números


    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. ⇒ Pm = Vm,m = m!

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

    Datos. Tenemos 5 digitos → m = 5; nos piden números de 5 cifras → n = 5.
  • Sí importa el orden → No es lo mismo 45378 que 45873.
  • Entran todos los caracteres → m = n.
  • No se repiten → El enunciado dice cifras distintas.
    • Solución. Según los datos, serán Permutaciones ordinarias y el resultado es →
    P5 = 5! = 5 . 4 . 3 . 2 . 1 = 120 números distintos


    Permutaciones Circulares

    Las permutaciones circulares ⇒ PCm, 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, P6 = 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 → PC6 = P6 / 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) → P5, de donde se deduce que → PC6 = P(6-1) = P5 = 5! = 120. Generalizando →

    PCm = P(m-1) = (m-1)!

    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 → PR43 = 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 → P3 = 3! = 6

    Esto implica que si a las PR43 las multiplicamos por las P3 (si no se repitieran 3 dígitos) obtenemos las P4 (que son las que se obtendrían si no se repitiera ningún dígito).

    PR43 * P3 = P4 → PR43 = P4 / P3 = 4! / 3! = (4.3.2.1)/(3.2.1) = 4

    Para calcular las Permutaciones con repetición de m elementos que se repiten v1,v2,v3,...,vn veces, se puede generalizar la fórmula →

    PRmv1,v2,v3,...,vn = m! / (v1!.v2!.v3!...vn!)

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

    Datos. Tenemos 5 dígitos → m = 5; nos piden grupos de 5 cifras → n = 5; el 4 se repite 2 veces (v1 = 2) y el 6 se repite 3 veces (v2 = 3)
  • Sí importa el orden → No es lo mismo 44666 que 46466.
  • Un dígito se repite 2 veces y otro 3 veces.
  • Solución. Según los datos, serán Permutaciones con repetición de 5 dígitos que se repiten v1 = 2 veces y v2 = 3 veces
  • PR52,3 = P5 / (P2.P3) = 5! / (2!.3!) = (5.4.3.2.1) / (2.1.3.2.1) = 5.4 / 2.1 = 10


    • Combinaciones

    Se llaman Combinaciones ordinarias o simplemente Combinaciones de m elementos tomados de n en n ⇒ (Cm,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 → C4,2 = 6

    Si en cada uno de los 6 equipos formados cambiamos el orden de los dos amigos, (lo hacemos con P2 = 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 V4,2 = 4 * 3 = 12. Por lo tanto →

  • C4,2 * P2 = V4,2 Despejando → C4,2 = V4,2 / P2 = (4*3) /(2*1) = 12 / 2 = 6

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

    combinaciones

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

    Datos. Tenemos 6 amigos → m = 6; cada amigo saluda a otro, cada saludo se hace entre dos → n = 2. En cada saludo observamos que:
  • ⇒ No importa el orden → Es igual que Luis salude a Ana que Ana a Luis.
  • ⇒ No se repiten los amigos → No se puede saludar un amigo a si mismo.
  • ⇒ No participan todos → De 6 participan 2.
    • Solución. Según los datos, serán Combinaciones → C6,2 y el resultado es →
    C6,2 = V6,2 / P2 = (6.5) / (2.1) = 30 / 2 = 15 saludos.

    El Número Combinatorio (m sobre n) → combinaciones
    equivale a Cm,n     → combinaciones = combinaciones=  combinaciones

    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 → CRm,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 →

    CRm,n = Cm+n-1, n

    Calcular CR6,4 → C6+4-1, 4 = C9,4 = (9*8*7*6) / (4*3*2*1) = 3024 / 24 = 126

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

    Datos. Tenemos 7 tipos de pasteles → m = 7; nos piden grupos de 3 → n = 3.
  • ⇒ No influye el orden → es lo mismo nata y crema que crema y nata.
  • ⇒ Sí se pueden repetir → podemos pedir 2 o 3 iguales.
  • ⇒ No entran todos los pasteles → De 7 tomamos 3.
    • Solución. Serán Combinaciones con repetición y el resultado es →
  • CR7,3 = C7+3-1, 3 = V9, 3 / P3 = (9.8.7) / (3.2.1) = 504 / 6 = 84 formas.


    • Aprende Combinatoria
    << Determinantes
    Matemáticas >>