COMBINACIONES ORDENADAS.
ORIGEN DEL
PROBLEMA.
El germen del problema que se plantea en el siguiente artículo surgió hace años, cuando mi padre me comentó lo frecuente que era que salieran 2 números seguidos en un sorteo de la primitiva. Este comentario hizo que me planteara calcular la probabilidad de que en un sorteo salieran, al menos, 2 números seguidos, y también la probabilidad de que salieran exactamente 2 números seguidos. Estos problemas se relacionaban directamente con el cálculo de las combinaciones de la primitiva en que no hubiera números consecutivos. Enseguida me planteé la posibilidad de calcular las combinaciones en que hubiera, al menos, 3 números consecutivos, y aquéllas en las que hubiera exactamente 3 números consecutivos, etc., etc. El problema, como es lógico, no tenía porqué limitarse a los 49 números de la primitiva, ni a los sorteos de 6 números. Podíamos considerar, de forma general, N números naturales y combinaciones de m números. De igual forma nos interesaría calcular el nº de combinaciones de m números que cumplieran cualquier condición prefijada. Esto tenía que ser definido con total exactitud, a fin de saber exactamente lo que queremos calcular, y es el objeto del siguiente epígrafe.
DEFINICIONES Y
CONCEPTOS.
Dado que en las combinaciones no se considera el orden, a partir de ahora, las combinaciones de números las supondremos ordenadas de menor a mayor.
Fijémonos en una combinación cualquiera de 6 números, tal como la siguiente:
(2, 5, 6, 8, 14, 15 ). En la misma encontramos 1 número aislado ( 2) , 2 números consecutivos ( 5, 6 ), otro número aislado ( 8 ), y otros 2 números seguidos ( 14, 15 ). Cuando hay 2 números seguidos hablaremos de secuencias de 2 números, y cuando nos encontramos con 1 número aislado hablaremos de secuencias de 1 número. Podemos decir que la combinación de 6 números está formada por 4 secuencias: 2 secuencias de 1 número y otras 2 secuencias de 2 números. Nos podría interesar calcular cuántas combinaciones de 6 números están formadas por 2 secuencias de 1 número y otras 2 secuencias de 2 números, en un sorteo de la primitiva.
Cualquier combinación de m números puede ser descrita en función de las secuencias que la integran. De forma general, podemos decir que una combinación de m números elegida entre los N primeros números naturales está formada por n secuencias s1, s2, s3,……., sn. Así, por ejemplo, la combinación anterior ( 2, 5, 6, 8, 14, 15 ) está formada por las siguientes 4 secuencias: s1 ( 2), s2 ( 5, 6), s3 ( 8 ) y s4 ( 14, 15 ).
Así pues, está claro que cualquier combinación de m números está formada por un grupo de n secuencias. Cada secuencia queda definida por el nº inicial de la secuencia y por el nº de números que componen la secuencia. Al nº de números que componen la secuencia lo llamaremos, de ahora en adelante, la longitud de la secuencia. Así, en el ejemplo anterior, s4 vendría definida por el nº inicial (14 ), y por su longitud ( 2). De manera inmediata sabremos que dicha secuencia está formada por los números 14 y 15.
De forma general, a los números iniciales de las secuencias s1, s2, s3,……., sn los nombraremos i1, i2, i3,….., in, y a sus longitudes, l1, l2, l3,……,ln, respectivamente.
De esta forma cualquier secuencia viene definida por su nº inicial y su longitud.
Dos combinaciones serán iguales si están formadas por las mismas secuencias, es decir, si sus números iniciales son iguales y sus longitudes también. Por ejemplo, las combinaciones ( 1,2,3,5,6,9 ) y ( 1,2,3,6,7,9 ) son distintas porque la secuencia 2 tiene diferente inicio. A la diferencia entre el nº inicial de una secuencia y el nº final de la secuencia anterior le llamaremos hueco entre secuencias. Dos combinaciones iguales están formadas por los mismos números y tienen, por tanto, las mismas secuencias. Es decir, tienen los mismos números iniciales, las mismas longitudes y los mismos huecos. Dos combinaciones distintas tendrán diferente alguno de esos elementos.
El problema general que nos interesa resolver es el siguiente: Calcular el nº de combinaciones de m números, elegidas entre N números, que estén formadas por n secuencias cuyas longitudes sean l1, l2, l3,……., ln. Por ejemplo, nos podría interesar calcular las combinaciones de 7 números elegidas entre los primeros 200 números naturales, en que haya 3 secuencias: 2 secuencias de 2 y 1 secuencia de 3.
Puesto que queremos que las longitudes de las secuencias sean iguales para todas las combinaciones, éstas podrán diferir únicamente en el inicio de las secuencias que las componen.
Las combinaciones (1,2,3) y (3,4,5) están formadas, ambas, por 1 única secuencia de longitud 3, pero difieren en su inicio.
Las combinaciones (1, 3, 5) y ( 7, 9, 11 ) están formadas por 3 secuencias de 1 número, y tienen los mismos huecos entre secuencias, pero difieren en los inicios de las secuencias. Dos combinaciones con los mismos huecos pueden ser distintas, como se desprende del ejemplo anterior, pero 2 combinaciones con huecos distintos son diferentes puesto que si son iguales estarían formadas por los mismos números y, obviamente, los huecos serían iguales. Así pues, y esto debe quedar bien claro, 2 combinaciones con secuencias de la misma longitud serán distintas cuando los números iniciales sean diferentes, o cuando los huecos entre secuencias sean diferentes.
DEMOSTRACIÓN.
Puesto que las longitudes de las secuencias que componen la combinación queremos que sean iguales, tendremos que encontrar el nº de formas diferentes de elegir los números iniciales de las secuencias s1, s2, s3,……, sn, entre Los N números. Dado que queremos que las secuencias tengan longitudes l1, l2, l3,………., ln, habrá una serie de números que no podrán ser elegidos. Entre i1 e i2 habrá un mínimo de (l1 – 1) números, que son los que siguen a i1, más 1, que es el hueco mínimo entre la secuencia s1 y la secuencia s2. De igual forma entre i2 e i3 habrá (l2 – 1) + 1 números, y así sucesivamente. Entre in y el final de la secuencia sn habrá ( ln – 1), y no hay que añadir 1 porque es la última secuencia.
Así pues, los números que no se pueden elegir son. ( l1 – 1 ) + 1 ( l2 – 1 ) + 1 +………+
( ln – 1 ) = l1 + l2 + l3 + …….+ ln - 1 = m – 1.
Así pues, de entre los N números habrá que descontar ( m- 1) para elegir los n números iniciales de cada secuencia. Por tanto, el nº de formas diferentes de elegir los n números iniciales de las secuencias viene dado por las combinaciones de (N- m +1) tomadas de n en n. Es decir: C ( N –m +1 ), n.
Estas son las diferentes formas que tenemos de elegir los números iniciales de las secuencias. Ahora bien, si las longitudes de las secuencias no son todas iguales, las permutaciones de las secuencias entre sí darán lugar a nuevas combinaciones.
Veamos un ejemplo:
Calculemos entre los 5 primeros naturales las combinaciones de 3 números en que haya un secuencia de y otra secuencia de 1.
Serán, a saber:
( 1, 3, 4 ) ( 1, 4, 5) ( 2, 4, 5 ). En cada una de estas combinaciones la secuencia de 1 número es la primera y la secuencia de 2 números la 2ª. Podemos obtener nuevas combinaciones colocando la secuencia de 2 números la 1ª y a continuación la secuencia de 1 número, respetando los huecos entre secuencias. Así, obtendremos las siguientes combinaciones:
( 1, 2, 4 ) ( 1, 2, 5 ) ( 2, 3, 5 ).
Las distintas formas en que se puede alterar el orden de las secuencias de cada combinación viene dado por las permutaciones con repetición de las longitudes de las secuencias. Así pues, si las longitudes son l1, l2, l3, ……., ln y llamamos PR a las permutaciones con repetición, el nº total de las combinaciones que buscamos vendrá dado por:
C (N – m + 1 ), n X PR ( l1, l2, l3,……, ln)
En el ejemplo anterior, N =
Si aplicamos nuestra fórmula, tendremos:
C ( 5 -3 +1 ), 2 X PR ( 1, 2 ) = C 3, 2 X 2 = 3 X 2 = 6
CONCLUSIONES.
Los resultados de este cálculo se pueden aplicar, igualmente, a los elementos de un conjunto en el que se pueda definir una relación estricta de orden; es decir, en la que para 2 elementos cualesquiera, a y b, se cumpla a >b ó a < b
APLICACIONES.
Como ejemplo práctico de las aplicaciones de nuestra fórmula vamos a calcular las combinaciones en las que hay, al menos, 2 números seguidos. Éstas serán todas las combinaciones de N tomadas de m en m, menos aquellas en las que no hay 2 números seguidos.
Para calcular las combinaciones de N tomadas de m en m en las que no hay 2 números seguidos aplicamos nuestra fórmula, teniendo en cuenta que todas las secuencias serán de 1, puesto que no queremos que haya 2 números seguidos. Así pues, n = m.
C (N – m +
1 ), m X
PR ( 1, 1, 1……, 1) = C (N – m + 1 ), m X 1
Las combinaciones en las que hay, al menos, 2 números seguidos vendrán dadas por:
C N, m - C ( N – m + 1 ), m
Ésta y muchas otras cuestiones pueden ser resueltas sin dificultad mediante la aplicación de nuestra fórmula.
Si, por ejemplo, en un sorteo de la primitiva queremos conocer las combinaciones en que salen exactamente 2 números seguidos debemos fijarnos en que esto ocurre cuando hay 4 secuencias de 1 y una secuencia de 2, o bien cuando hay 2 secuencias de 1 y 2 secuencias de 2, o bien cuando hay 3 secuencias de 2. Aplicamos nuestra fórmula en los tres casos y luego los sumamos.
Ahora ya podríamos calcular las combinaciones en las que
hay, al menos, 3 números seguidos pues éstas serán las combinaciones en las que
hay, al menos, 2 números seguidos menos las combinaciones en las que hay,
exactamente, 2 números seguidos.
Ernesto Sánchez de Cos [e.sandecos@ono.com]
2006