Conteo
COMBINATORIA
Breve reseña histórica
El surgimiento y desarrollo de la combinatoria ha sido paralelo al desarrollo de otras ramas de las matemáticas, tales como el álgebra, teoría de los números, y probabilidad. Desde tiempos muy remotos ha habido problemas de combinatoria que han llamado la atención de los matemáticos. por ejemplo, el problema de los cuadrados mágicos que son arreglos de números con la propiedad de que la suma de los elementos de cualquier columna, renglón o diagonal es el mismo número, aparece en un viejo libro chino fechado 2200 a. C.
Los cuadrados mágicos de orden 3 fueron estudiados con fines místicos. Los coeficientes binomiales, que son los coeficientes enteros de la expansión de (a + b) fueron conocidos en el siglo XII. El triángulo de Pascal que es un arreglo triangular de los coeficientes binomiales fue desarrollado en el siglo XIII.
Se puede considerar que en el Occidente la combinatoria surge en el siglo XVII con los trabajos de Blaise Pascal y de Pierre Fermat sobre la teoría de juegos de azar. Estos trabajos, que formaron los fundamentos de la teoría de la probabilidad, contenían asimismo los principios para determinar el número de combinaciones de elementos de un conjunto finito, y así se estableció la tradicional conexión entre combinatoria y probabilidad.
El término "combinatoria" tal y como lo usamos actualmente fue introducido por Wilhem Leibniz en su Dissertatio de Arte Combinatoria. De gran importancia para la consolidación de la combinatoria fue el artículo de Ars Conjectandi (el arte de conjeturar por J. Bernoulli; este trabajo estaba dedicado a establecer las nociones básicas de probabilidad. Para esto fue necesario introducir también un buen número de nociones básicas de combinatoria pues se usaron fuertemente como aplicaciones al cálculo de probabilidades. Se puede decir que con los trabajos de Leibniz y Bernoulli se inicia el establecimiento de la combinatoria como una nueva e independiente rama de las matemáticas.
El matemático suizo Leonard Euler fue quien desarrolló a principios del siglo XVIII una auténtica escuela de matemática combinatoria. En sus artículos sobre la partición y descomposición de en- teros positivos en sumandos, estableció las bases de uno de los métodos fundamentales para el cálculo de configuraciones combinatorias, que es el método de las funciones generadoras. También se le considera el padre de la teoría de gráficas por el planteamiento y solución del problema de los "Puentes de Königsberg" usando por primera vez conceptos y métodos de teoría de gráficas. Los primeros problemas de teoría de gráficas surgieron de la búsqueda de solución a algunos problemas cotidianos y también en el planteamiento de algunos acertijos matemáticos tales como el problema de los Puentes de Königsberg, el arreglo de reinas en un tablero de ajedrez con alguna restricción, problemas de transporte, el problema del agente viajero, etcétera.
El problema de los cuatro colores formulado a mediados del siglo XIX (cuatro colores son suficientes para colorear las regiones de un mapa de tal manera que regiones con frontera tengan asignados distinto color) pasó de ser un mero acertijo matemático a ser fuente de importantes problemas y resultados en teoría de gráficas de interés tanto teórico como en aplicaciones. Este ha sido uno de los problemas teóricos más desafiantes en la historia de la combinatoria debido a la simplicidad de su planteamiento.
En Inglaterra a finales de siglo XIX Arthur Cayley (motivado por el problema de calcular el número de isómeros de hidrocarburos saturados) hizo importantes contribuciones a la teoría de enumeración de gráficas. Por este tiempo el matemático George Boole usó métodos de combinatoria en conexión con el desarrollo de la lógica simbólica y con las ideas y métodos que Henri Poincaré desarrolló en relación con problemas de topología. Uno de los factores más importantes que han contribuido al gran desarrollo que ha tenido la combinatoria desde 1920 es la teoría de gráficas, la importancia de esta disciplina estriba en el hecho de que las gráficas pueden servir como modelos abstractos para modelar una gran variedad de relaciones entre objetos de un conjunto. Sus aplicaciones se extienden a campos tan diversos como la investigación de operaciones, química, mecánica estadística, física teórica y problemas socio-económicos. La teoría de redes de transporte se puede ver como un capítulo de la teoría de las gráficas.
INTRODUCCIÓN A LA COMBINATORIA
A menudo se presenta la necesidad de calcular el número de maneras distintas en que un suceso se presenta o puede ser realizado. Otras veces es importante determinar la probabilidad de ocurrencia de un evento específico. En ambos casos se apela al sentido común, o se establecen métodos que permitan sistematizar tales cálculos. Con frecuencia el sentido común ayuda a entender por qué se eligió un procedimiento dado, mientras que la formalización del cálculo las vías para encontrar las soluciones apropiadas.
Iniciaremos nuestro estudio de teoría combinatoria enunciando los principios aditivo y multiplicativo de conteo.
Principio aditivo de conteo: Sean A y B dos sucesos que no pueden ocurrir simultáneamente. Si A ocurre de a maneras distintas y B ocurre de b maneras distintas, el número de maneras en el cual puede ocurrir A o B es A +B
Principio multiplicativo de conteo: Si un suceso puede ocurrir en a maneras e, independiente- mente, un segundo suceso puede ocurrir en b maneras, entonces el número de maneras en que ambos, A y B, pueden ocurrir AB.
A este principio también se le denomina principio fundamental de conteo.
Ejemplo:
Se tienen 6 banderas de señalización, dos rojas, dos verdes y dos azules. ¿Cuántas seña- les distintas pueden hacerse con una o dos banderas a la vez?
Solución: Si denotamos las banderas rojas, verdes y azules por R, V y A, respectivamente, vemos que con una bandera a la vez se pueden hacer 3 señales distintas:
R , V , A
Con dos banderas a la vez se puede hacer las siguientes señales (sacando, por ejemplo, una prime- ra y después la otra) es decir
RR, RV. RA, VR, VV, VA, AR, AV, AA
Entonces, si se utilizan dos banderas, se pueden hacer 9 señales distintas. Luego, con una o dos banderas se podrán realizar 3+9= 12 señales diferentes. Observa que, como se establece en la definición, se trata de dos sucesos A y B descritos como:
A: Se hacen señales con una sola bandera
B: Se hacen señales con dos banderas.
Y que ambos no pueden ocurrir simultáneamente, ya que si se decide hacer señales con una bandera se descarta la segunda alternativa y viceversa.
Ejemplo:
En una liga de 28 equipos. ¿Cuántas quinielas de futbol distintas se pueden hacer?
Tenemos en cuenta que en cada partido puede haber 3 resultados(Gana A, Empate, Gana B): 1, x, 2, que hay 14 partidos y que los resultados de cada uno son independientes de los demás, por tanto, tendremos
Ejemplo:
¿Cuántos resultados distintos puede haber en un sorteo de la lotería en el que se deben elegir 6 números de 49 (del 1 al 49) sin repetición de número?
En una bolsa tenemos 49 bolas numeradas del 1 al 49. El primer número lo escojo entre 49 posibles números, el segundo número lo escojo entre 48 (pues las bolas, una vez extraídas no se devuelven a la bolsa), el tercero entre 47, y así sucesivamente, por lo tanto, en principio habría
49*48*47*46*45*44= 10.068.347.520
Esta sería la solución si el orden de extracción de las bolas, se tuviese en cuenta, pero no es así. El número que hemos sacado en la primera extracción podría haber salido en la segunda, tercera, cuarta, quinta o sexta extracción (en total 6), por lo tanto, habrá que dividir por 6. El número que hemos sacado en la segunda extracción, podría haber salido en la tercera, cuarta, quinta o sexta extracción, (en total 5), habrá que dividir entre 5 y así seguiríamos razonando hasta la última ex- tracción.
Por ello habrá que dividir por 6*5*4*3*2*1 el número anterior para obtener la solución.
10.068.347.520/720=13.983.816
Ejemplo:
¿Cuántas quinielas distintas se pueden hacer si creemos que el resultado de 4 partidos será un 1, el de 5 partidos puede ser un 1 o una x, y los 6 partidos restantes puede darse cualquiera de los tres signos?
Los cuatro resultados 'fijos' los podemos elegir entre un signo, los 5 'dobles' entre dos y los 6 'tri- ples' entre 3, por lo tanto, la solución sería:
$1\cdot 1\cdot 1\cdot 1\cdot 2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3=23328$
Hasta ahora, los ejemplos realizados los hemos realizado mediante conteo, nuestro objetivo es formalizar y obtener expresiones matemáticas que nos den los resultados buscados.
PERMUTACIONES
PERMUTACIONES SIN REPETICIÓN:
Las permutaciones sin repetición de n elementos se definen como las distintas formas de ordenar todos esos elementos distintos, por lo que la única diferencia entre ellas es el orden de colocación de sus elementos.
El número de estas permutaciones será: $P_n=n!$
PERMUTACIONES CON REPETICIÓN:
Llamamos permutaciones con repetición de n elementos tomados de a en a , de b en b , de c en c , etc, cuando en los n elementos existen elementos repetidos (un elemento aparece a veces, otro b veces, otro c veces, etc) verificándose que a+b+c+...=n.
El número de estas permutaciones será:
$PR_{n}^{a,b,c}=\frac{n!}{a!\cdot b!\cdot c!}$
Teniendo en cuenta que
$n!=n\left( n-1 \right) \left( n-2 \right) \cdot ....\cdot 3\cdot 2\cdot 1$
Ejemplos
a) ¿Cuántos números de 5 cifras distintas se pueden formar con los dígitos 1,2,3,4,5?
$P_5=5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120$
b) ¿Cuántos números de 4 cifras se pueden formar con los dígitos 0,1,2,3?
$P_4-P_3=4!-3!=18$
Hemos restado P3 para descontar los números que empiezan por cero, ya que estos no son de cuatro cifras.
c) ¿Cuántos números de 6 cifras se pueden formar si en ellos siempre hay 1’s, 2 ’s y 3 ’s?
$P_{6}^{1,2,3}=\frac{6!}{1!\cdot 2!\cdot 3!}=\frac{6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{1\cdot 2\cdot 1\cdot 3\cdot 2\cdot 1}=60$
PERMUTACIONES CON REPETICIÓN:
Llamamos permutaciones con repetición de n elementos tomados de a en a , de b en b , de c en c , etc, cuando en los n elementos existen elementos repetidos (un elemento aparece a veces, otro b veces, otro c veces, etc) verificándose que a+b+c+...=n.
El número de estas permutaciones será:
Teniendo en cuenta que:
Ejemplos
a) ¿Cuántos números de 5 cifras distintas se pueden formar con los dígitos 1,2,3,4,5?
b) ¿Cuántos números de 4 cifras se pueden formar con los dígitos 0,1,2,3?
Hemos restado P3 para descontar los números que empiezan por cero, ya que estos no son de cuatro cifras.
c) ¿Cuántos números de 6 cifras se pueden formar si en ellos siempre hay 1’s, 2 ’s y 3 ’s?
VARIACIONES
Definición: Las variaciones sin repetición de n elementos tomados de r en r se definen como las distintas agrupaciones formadas con r elementos distintos, eligiéndolos de entre los n elementos de que disponemos, considerando una variación distinta a otra tanto si difieren en algún elemento como si están situados en distinto orden.
El número de variaciones que se pueden construir se puede calcular mediante la fórmula
Definición: Las variaciones con repetición de n elementos tomados de r en r se definen como las distintas agrupaciones formadas con r elementos que pueden repetirse, eligiéndolos de entre los n elementos de que disponemos, considerando una variación distinta a otra tanto si difieren en algún elemento como si están situados en distinto orden.
El número de variaciones que se pueden construir se puede calcular mediante la fórmula:
Ejemplos
a) ¿Cuántos números de tres cifras distintas se pueden formar con los dígitos 1,2,3,….,9?
Se trata de variaciones sin repetición, ya que las cifras de cada número deben ser distintas.
b) Con las letras del alfabeto español (27 letras)
a)¿Cuántas palabras (con o sin sentido) de 6 letras distintas pueden formarse?
b)¿Cuántas empiezan por vocal?
Se trata de variaciones con repetición
COMBINACIONES
Definición: Las combinaciones sin repetición de n elementos tomados de r en r se definen como las distintas agrupaciones formadas con r elementos distintos, eligiéndolos de entre los n elementos de que disponemos, considerando una variación distinta a otra sólo si difieren en algún elemento, (No influye el orden de colocación de sus elementos).
El número de combinaciones que se pueden construir se puede calcular mediante la fórmula:
Definición: Las combinaciones con repetición de n elementos tomados de r en r se definen como las distintas agrupaciones formadas con r elementos que pueden repetirse, eligiéndolos de entre los n elementos de que disponemos, considerando una variación distinta a otra sólo si difieren en algún elemento, (No influye el orden de colocación de sus elementos).
El número de combinaciones que se pueden construir se puede calcular mediante la fórmula:
Ejemplos
a) Como respuesta a un anuncio de trabajo se presentan 12 personas para cubrir tres plazas de administrativo ¿Cuántos grupos diferentes de personas se pueden seleccionar?
Debemos elegir grupos de 3 de entre los 12 , no influye el orden
b) ¿Cuántos triángulos distintos se pueden formar con 8 puntos en el plano si tres de ellos nunca están alineados?
Para que dos triángulos sean distintos se tienen que diferenciar al menos en un vértice y el orden en que tomamos los vértices no influye
c) ¿Cuántos conjuntos de tres letras existen elegidas entre a, b, c, d, e, f, g si en cada conjunto puede haber más de una letra igual?
Tenemos en cuenta que el conjunto a, b, c coincide con el conjunto b, c, a y que los elementos se pueden repetir, es decir a, a, b es un conjunto de tres letras, luego
¿Cómo las diferenciamos?
EJERCICIOS
1. Supongamos que hay ocho diferentes lugares de capacitación administrativa para asignar a ocho empleados en el programa preliminar de capacitación administrativa de una empresa. ¿De cuántas maneras diferentes pueden ser asignados los ocho individuos a los ocho lugares distintos?
2. En referencia a la situación descrita en el ejercicio 1, supongamos que sólo se dispone de seis diferentes lugares para los ocho candidatos. ¿De cuántas maneras diferentes pueden asignar- se los seis lugares distintos a seis de los ocho individuos?
3. En referencia a la situación descrita en el ejercicio 2, supongamos que seis de los lugares disponibles pueden considerarse comparables y en realidad iguales para efectos prácticos. ¿De cuántas maneras pueden elegirse seis de los ocho candidatos para ocupar los seis lugares?
4. Un grupo de proyecto de dos ingenieros y tres técnicos debe formarse a partir de un grupo departamental que incluye a cinco ingenieros y nueve técnicos. ¿Cuántos diferentes grupos de proyecto pueden formarse con los catorce empleados disponibles?
5. Una clave de acceso a un banco consta de dos letras de alfabeto seguidas por dos dígitos. ¿Cuántas claves diferentes hay?
6. ¿Cuántas permutaciones hay de cada uno de los siguientes conjuntos, sin permitir repetición?
a. {r, s, t, u} r=2
b. {1, 2, 3, 4, 5} r = 3
c. {a, b, 1, 2, 3, c} r = 3
7. Para cada conjunto A, encuentre el número de permutaciones de A tomando r elementos a la vez, pudiendo repetir elementos.
a. A = {1, 2, 3, 4, 5, 6, 7}, r = 3
b. A = {a, b, c, d, e, f}, r = 2
c. A = {x/x es un número entero y x <16}, r = 4
8. ¿De cuántas maneras 6 hombres y 6 mujeres pueden sentarse en línea si:
a. Cualquier persona puede sentarse en seguida de cualquier otra.
b. Los hombres y las mujeres deben ocupar asientos alternos.
9. Encuentre el número de permutaciones de la palabra BOUGHT con y sin repetición de términos.
10. ¿De cuántas maneras puede seleccionarse un comité de tres miembros de facultad y dos de estudiantes, tomándolos de siete miembros de facultad y ocho estudiantes?
11. ¿De cuántas formas se puede elegir un comité de 3 personas de un grupo de 20? ¿Y de cuán- tas si uno debe ser el presidente, otro el vicepresidente y otro el secretario?
12. ¿Cuántos números distintos de 5 cifras se pueden formar con las cifras 1,2,3,5,7,8,9?
13. En una reunión hay tres chicas y siete chicos ¿Cuántos grupos de 5 personas pueden formar- se? ¿Cuántos si en cada grupo debe haber 2 y solo dos chicas?
14. ¿Cuántos números de cuatro cifras pueden formarse con dos cifras pares (no entra el cero) y dos impares?