Combinatoria

    Con frecuencia, en la vida ordinaria, dado un conjunto de elementos, hay que considerar, además de la naturaleza de los mismos, el orden en que aparecen. Un ejemplo de ello son las quinielas de fútbol, en las de además de saber qué signos son los apropiados, es necesario conocer, si se desea ganar, el orden en que hay que colocarlos. Además de apostar que la quiniela de la próxima semana va a tener 6 «doses», 5 «unos» y 4 «equis», es necesario conocer el lugar en que debe ir colocado cada signo. La consideración conjunta de ambos factores, elementos y orden de los mismos, conduce al análisis combinatorio, el cual es profusamente utilizado en innumerables aplicaciones prácticas en el campo de la matemática pura y en diversos aspectos de la aplicada, como son el cálculo de probabilidades, la estadística y la teoría de los juegos. Análogamente, también es empleado por la física.

    En el análisis combinatorio, también conocido como combinatoria, se distinguen dos partes: la combinatoria sin repetición, en la que, como su nombre indica, cada elemento sólo puede aparecer una vez en cada ordenación y la combinatoria con repetición, en la que los elementos disponibles pueden repetirse.

    Combinatoria sin repetición

    A continuación se consideran tres posibilidades de seleccionar elementos dentro de un conjunto referencial: variaciones, permutaciones y combinaciones.

    Variaciones

    Se llama variaciones de m elementos, tomados de n en n, a los distintos grupos que se puede formar con esos m elementos, de forma que en cada uno entren n, considerándose que dos grupos son distintos cuando difieren en algún elemento o en el orden de colocación de los mismos. Las variaciones de m elementos, tomados de n en n, se representan por el símbolo Vm,n.

    Así por ejemplo, si existen los elementos a, b, c, d, e y se desea formar las variaciones de esos cinco elementos, tomados de tres en tres, algunos (no todos) de los grupos posibles serían: a, b, c; a, b, d; b, a, d; e, c, a. Observemos que los grupos segundo y tercero, pese a poseer los mismos elementos, son variaciones distintas, ya que difieren en el orden. Las variaciones se calculan mediante la fórmula:

    Vm,n = m · (m – 1) · (m – 2)(m – n + 1)

    Por ejemplo:

    V5, 3 = 5 · 4 · 3 = 60

    Permutaciones

    Se denomina permutaciones de n elementos a los diferentes grupos que se puede formar con esos n elementos, de forma que en cada uno de ellos entren los n disponibles, considerándose que un grupo es distinto de otro por el orden de colocación de dichos elementos. Las permutaciones de nelementos se simbolizan por Pn.

    De esta manera, si se consideran los elementos a, b, c, d, algunas de las permutaciones posibles (no todas) serían: a, c, d, b; a, d, c, b y c, a, b, d. Nótese que en cada grupo entran todos los elementos disponibles, por lo que un grupo sólo puede diferenciarse de otro en el orden de colocación de los elementos.

    Las permutaciones de n elementos se calculan mediante la fórmula:

    Pn = n!

    El símbolo n! se lee diciendo «factorial de n» y el cálculo del mismo se verifica tomando el producto de n factores decrecientes en una unidad cada uno respecto al anterior, partiendo de n y llegando hasta 1. Por convenio, 0! = 1 y 1! = 1.

    Por ejemplo:

    P5 = 5! = 5 · 4 · 3 · 2 · 1 = 120

    Desde el punto de vista de las aplicaciones prácticas, es conveniente tener en cuenta que:

    n! = n · (n – 1)!

    ya que:

    Del mismo modo, si interesa, puede decirse que:

    n! = n · (n – 1) · (n – 2)!

    En general, el factorial de un número es expresable tomando los factores que se desee y multiplicando esos factores por el factorial del factor siguiente al último tomado. Por ejemplo, 7!, podría escribirse:

    7! = 7 · 6! ; 7! = 7 · 6 · 5! ; 7! = 7 · 6 · 5 · 4!

    Clase de una permutación. Dado un conjunto, se llama permutación principal a la formada por los elementos de dicho conjunto colocados en un orden preestablecido. Aunque este orden es arbitrario, se acostumbra a tomar, cuando se trata de letras, el orden alfabético y, cuando se trata de números, el que marca la serie de números naturales.

    En otra permutación distinta de la principal, dos elementos, consecutivos o no, forman sucesión cuando se hallan en el mismo orden que en la permutación principal y forman inversión en caso contrario. Una permutación se denomina de clase par o impar, según presente, respectivamente, un número par o impar de inversiones. Por ejemplo, tomando como permutación principal a, b, c, d, la permutación b, a, c, d es de clase impar, ya que presenta una inversión (la existente entre b y a), mientras que la permutación c, b, d, a es de clase par, puesto que ofrece cuatro inversiones (c y b; c y a ; b y a ; d y a). En general, dado un conjunto de n elementos, existe, como se ha dicho, n! permutaciones de los mismos. De ellas, son de clase par y son de clase impar.

    En toda permutación se verifica que si dos elementos cambian sus puestos entre sí, la permutación cambia de clase. El concepto de orden de una permutación tiene gran importancia para el cálculo de determinantes.

    Permutaciones circulares. Las permutaciones circulares se presentan cuando dentro de un mismo grupo no se puede distinguir entre un primero y un último elemento. Si se consideran, por ejemplo, las distintas posibilidades de sentarse cinco personas alrededor de una mesa circular, cualquiera de ellas puede ser la primera y, lógicamente, cualquiera puede ser la última. Las permutaciones circulares de n elementos se representan por PCny se calculan mediante la fórmula:

    PCn = (n – 1)!

    Por ejemplo, si se desea, resolviendo el ejemplo anterior, saber de cuántas maneras pueden sentarse alrededor de una mesa camilla cinco personas, la contestación sería que de 24 formas, puesto que:

    PC5 = (5 – 1)! = 4! = 4 · 3 · 2 · 1 = 24

    Combinaciones

    Dado un conjunto de m elementos, recibe el nombre de combinaciones de esos m elementos, tomados de n en n, los diversos grupos que se puede formar con los m elementos, de manera que en cada grupo entren n, considerándose que dos grupos son distintos cuando se diferencian en algún elemento. Las combinaciones de m elementos, tomados de n en n, se representan por Cm,n.

    Por ejemplo, dado el conjunto formado por a, b, c, d, algunas de sus combinaciones ternarias (tomando los elementos de tres en tres) serían a, b, c ; a, b, d ; c, a, d. Como se puede observar, todas ellas se diferencian, al menos, en un elemento. Con el criterio de definición de las combinaciones, las ordenaciones a, b, c y c, a, b serían iguales, ya que están formadas por los mismos elementos y, como se ha dicho, en las combinaciones, el orden no influye. El cálculo de las combinaciones se hace con la fórmula:

    Por ejemplo:

    Notación de Euler. Consiste en representar Cm,n por el símbolo , con lo que:

    El matemático italiano Tartaglia desarrolló, entre otras cuestiones, un método muy simple (llamado triángulo de Tartaglia) para la resolución de triángulos aritméticos.

    Al símbolo se le llama número combinatorio. Dentro de él, a m se le llama numerador y a n orden. De la equivalencia señalada, se deduce que:

    Propiedades de los números combinatorios. Los números combinatorios poseen diversas propiedades que es conveniente conocer. Entre ellas destaca, en primer término, la propiedad de la equivalencia:

    De la cual se deduce que todo número combinatorio debe ser entero.

    Otra propiedad importante de los números combinatorios es que dos de ellos del mismo numerador y órdenes complementarios son iguales. Como aclaración a este enunciado, es necesario recalcar que dos números combinatorios son complementarios cuando, teniendo el mismo numerador, la suma de sus órdenes es igual a dicho numerador. En definitiva, la propiedad afirma que:

    Otra propiedad notable es la llamada igualdad de Euler, la cual afirma que la suma de dos números combinatorios de igual numerador y órdenes consecutivos es otro número combinatorio que tiene por numerador el de los anteriores, aumentado en una unidad, y por orden el mayor que esté presente. Es decir:

    Por otra parte, como es fácilmente comprobable, cualquier número sobre cero es igual a la unidad; cualquier número sobre sí mismo es igual a 1 y cualquier número sobre 1 es el propio número. Es decir:

    El triángulo aritmético. Las propiedades de los números combinatorios permiten escribir éstos, adoptando la siguiente estructura triangular:

    Como puede observarse, los números combinatorios que aparecen en la periferia o «lados» del triángulo son de la forma o bien en ambos casos iguales a la unidad. Además, cualquier número combinatorio es igual a la suma de los que se hallan inmediatamente encima de él. Por ejemplo:

    A veces, en la práctica, hay dudas acerca del tipo de ordenación a emplear (variaciones, combinaciones o permutaciones). Para superar este obstáculo, es aconsejable formar un grupo cualquiera y aplicar el siguiente organigrama.

    De manera más práctica, el triángulo anterior puede ser escrito a través de un método más cómodo, propuesto por Niccolò Fontana, más conocido por su apodo, Tartaglia, por lo que se llama triángulo de Tartaglia (también se le denomina triángulo de Pascal), basado en dos sencillas reglas, reflejo de la observación anteriormente mencionada:

    1. Todas las filas del triángulo empiezan y acaban por 1.

    2. Cada elemento se obtiene sumando los dos inmediatos superiores.

    Así, aplicando estas reglas, el triángulo es:

    Este triángulo es de suma importancia a la hora de calcular la potencia enésima de un binomio.

    Relación entre variaciones, combinaciones y permutaciones. Las variaciones sin repetición de m elementos, tomados de n en n, representan el producto de las combinaciones de m elementos, tomados de n en n, por las permutaciones de n elementos. Es decir:

    Vm,n = Cm,n · Pn

    Variaciones con repetición

    Si es posible la repetición, las variaciones de m elementos, tomados de n en n, se simbolizan por VRm,n y se calculan aplicando la siguiente fórmula:

    VRm,n = mn

    Así por ejemplo, en una quiniela, en la que 3 elementos (1, 3, 2) se toman 15 veces, con lo que obligadamente se repetirán, las posibilidades que pueden darse serían:

    VR3,15 = 315 = 14.348.907

    Si se desea saber cuántos números de cuatro cifras se pueden formar con los nueve dígitos significativos del sistema decimal, la solución sería:

    VR9,4 = 94 = 6.561

    Permutaciones con repetición

    Las permutaciones de n elementos, en las que el primero se repite r veces, el segundo s veces, el tercero t veces, etc., se representan por Pnr,s,t ... y se calcula mediante la fórmula:

    debiéndose verificar siempre que:

    r + s + t + ... = n

    Por ejemplo:

    Imaginemos la siguiente pregunta: ¿de cuántas maneras pueden colocarse en línea 12 bolas, de las que 7 son blancas, 3 son amarillas y 2 son azules? La respuesta sería:

    Combinaciones con repetición

    Las combinaciones con repetición de m elementos, tomados de nen n, se calculan utilizando la fórmula:

    Por ejemplo, las combinaciones con repetición de 7 elementos, tomados de tres en tres serían: