Lo Esencial En Combinatoria

Lo esencial en Combinatoria. R. Reytor. Isbn. 9789591607430 Índice. Pág. Prólogo…………………………………………………………………………….. 3 Una introducción necesaria………………………………………………………4 Un poco de historia ………………………………………………………………6 Capítulo 1. Reglas generales de la combinatoria……………………………...9 1.1.- Principio Aditivo………………………………………………………………10 1.2 Principio Multiplicativo…………………………………………………………12 1.3.- Ejercicios…………….……………………………………………………......15 Capítulo II.- Variaciones y permutaciones……………………………………….18 2.1 Variaciones sin repetición…………………………………………………….22 Formación y número de variaciones sin repetición………………………23 2.1 Permutaciones sin repetición………………………………………………..28 2.3 Permutaciones circulares…………………………………………………….34 2.4 Permutaciones con repetición……………………………………………….37 2.5 Formación y número de permutaciones con repetición…………………..38 2.6 Variaciones con repetición…………………………………………………..40 2.6 Ejercicios del capítulo II……………………………………………………..49 Capítulo III. Combinaciones…………………………………………………….56 3.1 Formación y número de combinaciones sin repetición………………….57 3.2 Combinaciones con repetición…………………………………………….61 3.3 Relación entre las combinaciones con y sin repetición………………..63 3.4 Ejercicios del capítulo III……………………………………………………64 Soluciones y respuestas……………………………………………………… 68 Prólogo. El desarrollo del pensamiento combinatorio es un trabajo arduo y de mucha paciencia; en este sentido juega un gran papel el sistema de impulsos que se tenga como resorte para enseñar la combinatoria. En no pocas ocasiones; al terminar de recibir un tema sobre combinatoria, los estudiantes no poseen las armas suficientes para enfrentarse por sí solos a la resolución de problemas, porque el sistema de impulsos en la apropiación de estos conceptos ha sido insuficiente. La labor del profesor es importante en este sentido porque al destacar las características que tienen los conceptos definidos o propiciar una adecuada descripción o caracterización de estos, está garantizando el éxito en el proceso de enseñanza. Este texto ha tenido la intención de destacar el tratamiento dado a los conceptos combinatorios con la finalidad de fijarlos convenientemente dando especial atención al proceso de identificación de estos, sobre todo, cuando estamos en presencia de problemas. Existen, desde luego, algunas tendencias a tratar de algoritmizar el trabajo con problemas combinatorios proponiendo sucesiones de indicaciones para su solución, pero; cuando estas indicaciones tienen un marcado carácter heurístico, activan aún más el proceso de aprendizaje. El éxito en la enseñanza de la combinatoria radica esencialmente en el sistema impulsor que se utilice para fijar estos conceptos. Este, sin dudas, ha sido el carácter que se ha intentado imprimir al presente texto. De haberlo logrado; el objetivo se habrá cumplido. El autor. Una introducción necesaria. La combinatoria es una sección de las Matemáticas que resulta útil para diversos representantes de variadas especialidades. Con los problemas combinatorios deben enfrentarse los biólogos, físicos, químicos, los matemáticos, lingüistas, ingenieros y muchos otros usuarios. El estudio de la combinatoria constituye la base que sostiene el análisis y solución de muchos problemas relacionados con la teoría de las probabilidades y sus aplicaciones prácticas. En este trabajo se expone con un lenguaje simple la combinatoria y los métodos para resolver los problemas que sobre este tema se proponen. La exposición se ha hecho de forma que pueda ser comprendida por individuos que tengan una instrucción media. Puede resultar útil a los estudiantes y profesores de institutos de segunda enseñanza, los estudiantes de las facultades de pedagogía en las especialidades de Matemática, Física, Química, Biología y Educación Primaria de los institutos superiores pedagógicos de Cuba sobre todo en los primeros cursos de sus especialidades respectivas donde deben enfrentarse en el trabajo práctico con variados problemas combinatorios. Aquí se exponen las Reglas Generales de la combinatoria, los Principios Aditivo y Multiplicativo, las variaciones, permutaciones y combinaciones con y sin repetición. se definen estos conceptos y se describen, enfatizando en las características que permiten identificarlos en el trabajo práctico, se deducen las fórmulas para el cálculo combinatorio y se enuncian en forma de teoremas con sus respectivas demostraciones. Se hace especial énfasis en el tratamiento que debe dárseles a los conceptos combinatorios definidos y en su aplicación a la solución de problemas. Se incluyen además ejemplos y ejercicios variados que ayudarán a fijarlos y sistematizarlos. Aunque en este texto se ha respetado el rigor matemático en el tratamiento de los conceptos; el objetivo principal de este es el de analizar bajo ciertos puntos de vista la naturaleza de los elementos combinatorios presentes en los problemas y mostrar algunas formas para resolverlos. Un poco de historia. La parte de las matemáticas que estudia los problemas sobre cuántas o cuáles combinaciones (bajo ciertas condiciones) pueden realizarse con determinados objetos se denomina combinatoria. Los historiadores sitúan el surgimiento de la combinatoria en los albores del siglo XVI; y se acunó casi exclusivamente en la aristocracia de la época; pues esta sociedad, generalmente ocupaba su tiempo en juegos de azar en los cuales ganaban o perdían cuantiosas fortunas. Jugando a los dados o las cartas se ganaban o perdían cuantiosas fortunas. Jugando a los dados o las cartas se ganaban o perdían brillantes, prendas valiosas, caballos de pura raza, etc. En este tiempo se encontraban difundidos diversos tipos de loterías en las cuales ocupaban sus días los caballeros y damas de la época. Es comprensible pues, que en sus inicios, los problemas tratasen fundamentalmente sobre juegos de azar; tratando de averiguar de cuántas formas podrían obtenerse sucesos favorables en un determinado número de pruebas. Así por ejemplo se trató de averiguar de cuántas maneras se podía extraer un número específico al arrojar varios dados o de cuántas maneras se podía extraer dos reyes de una baraja de 52 cartas. Estos y otros juegos fueron el motor impulsor de la combinatoria y las probabilidades; teoría que se desarrolla paralelamente a esta. La historia recoge el nombre de Tartaglia como uno de los pioneros en la combinatoria. Este célebre italiano confeccionó una tabla que mostraba todas las formas en que pueden caer “n” dados; pero no previó que una misma suma de puntos podía obtenerse de diferentes formas ( por ejemplo 4+1+3= 4+2+2). El estudio teórico de la combinatoria se considera un hecho a partir del año 1600 (siglo XVII) cuando los franceses Blas Pascal y Fermat comenzaron a recoger muestras de experimentos que realizaban en las mesas de juegos y a registrarlos estadísticamente para estudiar las leyes y regularidades bajo las cuales se regían. Un papel particularmente importante lo jugó aquí el problema sobre la división de una apuesta; propuesta a Pascal por un amigo suyo llamado Meré; jugador apasionado por demás. El problema consistía en la siguiente: si se lanzaba una moneda; el campeonato continuaría hasta que un jugador ganase 6 partidos; pero se interrumpiría cuando uno ganase 5 y el otro 4. ¿Cómo dividir entonces la apuesta? Era evidente que la razón 5:4 no era justa. Pascal resolvió el problema aplicando algunos métodos combinatorios y además propuso un método de solución para el caso general, cuando a un jugador le quedaran “r “partidos hasta ganar y al otro jugador le quedaran “s “partidos. Una solución similar a este problema fue dada por Fermat. El desarrollo posterior de la combinatoria se encuentra ligada a los nombres de matemáticos famosos como Jacobo Bernoullí, Leibniz y Euler. Sin embargo; para estos, también el rol fundamental lo constituyeron las aplicaciones a los distintos tipos de juegos. Ya en los últimos años, la combinatoria entró en un período de intenso desarrollo relacionado con el crecimiento general del interés hacia los problemas de la matemática discreta. Los métodos combinatorios son usados para resolver problemas de transporte, problemas sobre confección de horarios, planes de producción y la mecanización de estas así como para determinar las características genéticas en la obtención de razas de animales en laboratorios. La combinatoria es utilizada para confeccionar y descifrar claves, así como para resolver problemas de la teoría de la información. Y también; ¿por qué no? Para decidir en un futuro no muy lejano la forma más eficaz de conservar la vida en nuestro planeta. Capítulo I. Reglas generales de la combinatoria. Los problemas combinatorios se clasifican según la cantidad de operaciones que se necesite efectuar para resolverlos en: • Problemas combinatorios simples: los que se resuelven mediante una sola operación combinatoria. • Problemas combinatorios compuestos: los que se resuelven aplicando más de una operación combinatoria. En el desarrollo de los capítulos siguientes ejemplificaremos estas clasificaciones. En la matemática discreta existen problemas que se resuelven aplicando determinadas fórmulas (según la naturaleza de los elementos combinatorios presentes en ellos) pero la mayoría puede resolverse mediante dos principios generales: 1. El Principio Aditivo o Regla de la Suma. 2. El Principio Multiplicativo o Regla del Producto. El Principio Multiplicativo generalmente se asocia con el procedimiento utilizado en los primeros años escolares para encontrar la cantidad de elementos que contiene determinado conjunto; de ahí que la mayoría de los maestros lo reconozcan como “Método de Conteo”. Como a menudo el número de combinaciones o arreglos que se pueden hacer con los elementos de un conjunto admite que en cada elección aparezca una y solo una clase de combinaciones, entonces el Principio Aditivo se puede expresar de la manera siguiente:´ 1.1.-Principio Aditivo “El número total de combinaciones que se pueden hacer con todas las clases de elementos de un conjunto, es igual a la suma de las combinaciones de cada una de las clases”. Nota: se entiende como clase a todos los subconjuntos que se forman con los elementos del conjunto en cuestión. A través del análisis y solución del siguiente ejemplo puede apreciarse la aplicación de este método. Ejemplo 1: Marcos tiene 3 camisas y 4 pantalones. ¿De cuántas formas Marcos puede combinar las camisas y los pantalones? Designemos a las camisas por las letras a, b, c. y a los pantalones por x, y, z, u. si establecemos la distribución que puede hacerse entre las camisas y los pantalones se observa que: Observe usted que cada muestra formada aparece una y solo una vez. El número total de muestras se obtiene fácilmente sumando todas las combinaciones obtenidas mediante el proceso anterior: 1+1+1+1+1+1+1+1+1+1+1+1= 12 12 veces porque el número de combinaciones de cada clase es uno. Ejemplo 2: En un equipo de estudio hay 3 niñas y 2 niños. ¿Cuántas parejas diferentes pueden formarse para estudiar? De manera análoga a la anterior; podemos formar dos conjuntos de diferente naturaleza: el conjunto de las niñas: Diana, Claudia, Susana y el de los niños: Rafael, Alejandro. La selección de dúos puede realizarse usando un diagrama de red de la forma siguiente: Las líneas de unión entre los círculos son 10. Evidentemente el número total de muestras posibles se obtiene realizando el conteo de las líneas formadas. 1+1+1+1+1+1+1+1+1+1= 10 10 veces Ejemplo 3: ¿Cuántos números de tres cifras no repetidas hay que? a) Comiencen por 23. Analizamos previamente que el lugar de las unidades puede ser ocupado en cada muestra por uno y sólo uno de los dígitos 0, 1, 2, 3, 4, 5, 6, 7, 8,9. Si formamos cada muestra, se obtiene: 230, 231, 234, 235, 236, 237, 238 ,239. Como puede apreciarse el número de combinaciones de cada clase es 1 por lo tanto el número total de combinaciones de todas las clases es 8. El principio aditivo” permite conocer la composición de todas las muestras de un experimento” cuestión que resulta importante sobre todo en los primeros grados de la enseñanza por la contribución que hace en la esfera del desarrollo del pensamiento combinatorio en los escolares. Lógicamente “su inconveniencia radica en que es racional su aplicación sólo en casos en que el número total de muestras que componen el experimento no sea muy elevado”. Los ejemplos anteriores pueden ser abordados haciendo otros análisis, en los cuales se puede llegar a conocer el número total de muestras que componen un experimento sin necesidad de formar cada una de las muestras que los integran. En este sentido enunciaremos el siguiente principio. 1.2.- Principio Multiplicativo. “Si una cosa cualquiera puede ocurrir de m maneras diferentes y si después de haber ocurrido una cualquiera de esas maneras, otra cosa puede ocurrir de n maneras diferentes, entonces las dos cosas en ese orden, pueden ocurrir de m por n maneras”. En este principio se afirma que si dos cosas ocurren una después de la otra, el número total de formas en que pueden ocurrir ambas, se obtiene multiplicando el número de formas de la primera por el número de formas de la segunda. Ejemplo 4: ¿Cuántas sílabas de dos letras, que comienzan por una consonante, existen en el idioma español? En este caso la aplicación del método aditivo a de conteo hace lenta la labor por el número de muestras que tiene el experimento. La primera cosa es la elección de la primera letra (una consonante) y la segunda, la elección de una vocal. Como en español existen 24 consonantes y solo 5 vocales, la segunda elección puede ocurrir de 5 formas. En total pueden obtenerse de 24× 5 = 120 sílabas. El principio multiplicativo puede extenderse a más de dos cosas. Ejemplo 5: “Los números 2, 3, 4 y 5 se pueden multiplicar unos por otros en diferente orden. Escribe todas las posibilidades que hay considerando el 2 como primer facto”. En este caso tenemos 3 cosas diferentes. La primera consiste en colocar al segundo factor del producto (considerando el orden de izquierda a derecha); para lo cual existen tres posibilidades, la segunda, colocar el tercer factor, para lo que podemos contar con una posibilidad. En función del principio multiplicativo tendremos que los números pueden multiplicarse de 3×2×1 = 6 maneras diferentes. Resulta claro observar que fácilmente pueden obtenerse todas las muestras que componen este experimento. En ocasiones pueden aplicarse ambos métodos para resolver determinados problemas. Ejemplo 6: ¿Cuántos números de dos o de tres cifras no repetidas pueden formarse con los dígitos del 1 al 4? Aplicando el Principio Multiplicativo; para determinar todos los números de 2 cifras no repetidas llegamos al planteamiento: 4×3 = 12 números de 2 cifras no repetidas. Análogamente para determinar la cantidad de números de 3 cifras no repetidas obtenemos (4×3) ×2= 24 números. Aplicando a continuación el Principio Aditivo se obtiene: 12+24= 36 números de dos o de tres cifras no repetidas. La combinatoria permite la aplicación de varados métodos de análisis para la solución de problemas; en el siguiente ejemplo se muestra una forma en la que puede resolverse un problema. Ejemplo 7: Para hacer un viaje desde la ciudad A hasta la ciudad B pueden utilizarse 3 ómnibus y para ir desde la ciudad B hasta la ciudad C sólo 2. ¿De cuántas formas diferentes se puede viajar desde la ciudad A hasta la ciudad C? El siguiente diagrama muestra la forma en que puede realizarse el viaje. En este diagrama cada segmento representa un viaje entre dos de las ciudades señaladas en el problema. Para realizar el viaje completa es necesario seleccionar dos segmentos. Puede observarse con claridad que existen tantas posibilidades como segmentos hay entre la ciudad A y la C; es decir 6.a este resultado se llega fácilmente aplicando el Principio Multiplicativo. En la práctica no es necesario utilizar un diagrama como este; pero si se hace; ayuda a la comprensión del problema, que en casos más complejos resulta esencial. Este tipo de diagrama se conoce como Diagrama de Árbol porque cada punto se ramifica en la misma forma en que lo hace un árbol. Ejercicios. 1. ¿De cuántas maneras se puede escoger una vocal y una consonante de la palabra número? 2. A la cima de una montaña conducen 5 caminos. ¿De cuántas formas puede subir y bajar un campista utilizando tales caminos? ¿Y si el ascenso y descenso tienen lugar por caminos diferentes? 3. ¿De cuántas formas se pueden escoger dos fichas de dominó, de las 28 que hay en una mesa de juego, de forma tal que se puedan aplicar la una con la otra? 4. En una reunión hay 18 personas. Todas se saludan entre sí y ningún par de personas se saluda más de una vez. ¿Cuántos saludos de manos se dan? 5. En una tienda de ropa hay camisas de hombre en 4 tallas diferentes y en tres colores distintos cada talla. ¿Cuántos tipos diferentes de camisas hay en la tienda? 6. De entre tras ejemplares de un texto de Algebra 2 de Geometría y 2 de Trigonometría hay que escoger un ejemplar de cada uno. ¿Cuántos modos hay de hacerlo? 7. ¿De cuántas maneras diferentes pueden escribirse las letras A, B, C, D, una detrás de la otra sin repetir ninguna? 8. ¿Cuántos números de dos cifras se pueden formar con los números 1, 2, 3 ,4 ,5 ,6 ,7? ¿Cuántos de ellos tienen sus dos cifras iguales? 9. ¿Cuántos números de tres cifras pueden formarse con las cifras del número 24 356? ¿Cuántos de ellos son pares? 10. ¿Cuántos números de tres cifras existen que son múltiplos de dos? 11. ¿Cuántos números de 4 cifras existen? 12. ¿Cuántos números naturales de 4 cifras existen que no contienen la cifra 7? 13. ¿Cuántos números impares tienen 3 cifras y son menores que 500? 14. ¿Cuántos números naturales entre 100 y 999 tienen sus cifras diferentes? 15. ¿Cuántos de los primeros 1000 números enteros positivos tienen todas sus cifras diferentes? 16. ¿Cuántos números naturales de tres cifras existen tales que la suma de sus dígitos es 5? ¿Cuáles son? 17. ¿De cuántas formas se puede indicar en un tablero de ajedrez dos casillas: una blanca y otra negra? 18. En una corporación trabajan 67 personas. De estas, 47 dominan el idioma inglés, 35 el francés y 23 ambos idiomas. ¿cuántas personas de la corporación no hablan ni el inglés ni el francés? 19. De un grupo de jóvenes a 19 les gusta las matemáticas, a 17 las artes plástica, a 11 la historia, 12 prefieren matemática y artes plásticas, 7 historia y matemática, 5 artes plásticas e historia. A 2 les gusta las tres asignaturas y a 5 ninguna de ellas. ¿Cuántos jóvenes hay en el grupo? 20. al trasmitir informaciones por telégrafo se utiliza el código Morse. En este código las letras, las cifras y los signos de puntuación se representan por puntos y rayas. Por ejemplo, la letra t se representa por un punto (.) y la L por tres puntos y una raya (.-.). Empleando hasta dos signos, ¿Cuántas letras pueden codificarse? 21. se tienen tres tipos de de sobres sin sellos y cuatro tipos de sellos de un mismo valor. ¿de cuántas maneras se puede escoger un sobre y un sello para enviar una carta? 22. ¿De cuántas maneras se puede escoger una vocal y una consonante en la palabra Martí? 23. ¿De cuántas maneras se puede escoger una vocal y una consonante en la palabra Maceo? 24. En un estante hay tres ejemplares de un texto de de español, 7 de matemática y 6 de historia. ¿de cuántas maneras se puede escoger un ejemplar? 25. Una persona tiene 8 ejemplares de un libro de aritmética y otra posee 9 libros de álgebra. ¿de cuántas maneras se puede escoger un ejemplar? Capitulo II. Variaciones y permutaciones. Los principios combinatorios estudiados anteriormente sirven para resolver la mayor parte de los problemas que se presentan en la teoría combinatoria; sin embargo; existen algunos casos particulares, que se dan con cierta frecuencia y para los cuales resulta posible obtener fórmulas sencillas. Pero si bien es cierto que estas fórmulas agilizan el cálculo, se hace necesario establecer un trabajo de identificación previo del experimento combinatorio presente en el problema. En este sentido podemos incluir a los problemas combinatorios en dos grandes grupos: los problemas que tratan sobre variaciones y los que tratan sobre combinaciones. Estableciendo esta división, estudiaremos cada concepto por separado; destacando las características del término que los define con el objetivo específico de identificarlos en la solución de problemas. De la división anterior estudiaremos primeramente las variaciones. Este grupo de las variaciones, las dividiremos a su vez en 2 subgrupos: variaciones sin repetición y variaciones con repetición. La estrategia que usaremos para la identificación de los experimentos aleatorios la representamos en el siguiente esquema: • Estrategia para la Identificación de un Experimento Aleatorio. La lógica de la estrategia propuesta se basa en la existencia de un experimento combinatorio de naturaleza desconocida. Para su identificación partimos de la formación de algunas muestras del mismo (a lo sumo 3) y analizamos sus características, centrando nuestra atención en el orden. El análisis conduce a la toma de decisión relacionada con el tipo de experimento aleatorio: si el elemento distintivo en el análisis de las muestras es el orden, el experimento aleatorio trata sobre variaciones, de lo contrario; trata sobre combinaciones. Una vez tomada la decisión, se analiza si en las muestras se admite la repetición y nuevamente decidimos: es una variación con repetición o una combinación con repetición. Esta decisión caracteriza las muestras del experimento combinatorio y nos permite identificarlo. Si el experimento aleatorio fuese compuesto; porque estuviese formado por varios experimentos aleatorios simples, comenzamos nuevamente el análisis y repetimos el ciclo. Con esta lógica serán abordados los conceptos del análisis combinatorio. Por su parte, la solución de los problemas combinatorios ha sido una de las barreras más difíciles de vencer por los estudiantes porque no usan una estrategia apropiada para la solución de los mismos. La estrategia para la solución de los problemas combinatorios la expresamos en el siguiente esquema: Esquema General para la solución de un Problema Combinatorio. La lógica de la estrategia tiene su primer momento en la identificación del experimento aleatorio aplicando la Estrategia para la Identificación. El segundo momento es seleccionar la vía para el cálculo del número de muestras que componen el experimento, aplicando cualquiera de los procedimientos de cálculo conocidos en la Teoría Combinatoria: uso de diagramas, Principios Generales o Fórmulas. El tercer momento es la aplicación de la vía de cálculo seleccionada, con la cual conocemos el número de muestras que componen el experimento. La validación de la vía de cálculo aplicada a la solución del problema es el cuarto momento de la estrategia. Este paso adquiere características peculiares en los problemas de la matemática discreta porque resulta muy difícil comprobar la solución en relación con el texto del problema, a no ser en casos muy simples. La validación debe realizarse usando una vía diferente a la escogida para dar la solución y comparar los resultados obtenidos. Sobre las condiciones anteriores, daremos tratamiento a los experimentos aleatorios y a la solución de problemas sobre Teoría Combinatoria. II.I.- Variaciones sin repetición. Definición. Se llaman variaciones sin repetición de n objetos tomados p a p (o variaciones de orden p) a todas las posibles ordenaciones de p objetos tomados de los n objetos dados en las cuales no se admite repetición. Las características que permiten identificar las muestras de un experimento sobre variaciones sin repetición son: Dos muestras difieren: • O en el orden de sus elementos. • O por lo menos un elemento. • Los elementos no se repiten en la misma muestra. Ejemplo1: Formar todos los números de 2 cifras diferentes con los dígitos 1,2, 3, 4. 12 21 31 41 13 23 32 42 14 24 34 43 Como se pudo observar; resulta fácil el análisis de las muestras formadas tomando como patrón las características mencionadas. Las muestras 12 y 21 son diferentes; pues el orden de los elementos tomados es esencial (evidentemente los números 12 y 21 son diferentes). Si seleccionamos las muestras 12 y 14 la diferencia radica en un elemento ( 2 y 4) y las muestras 12 y 43 difieren en todos sus elementos. Es esencial el dominio de estas características para su posterior aplicación al análisis de los problemas combinatorios. • Formación y número de variaciones sin repetición. Las variaciones sin repetición con cierto número de objetos dados, por ejemplo; los números 1, 2, 3, 4; se pueden ir formando sucesivamente, es decir; primero las variaciones donde solo aparece un elemento (variaciones monarias); luego las binarias, las terciarias, etc. El método consiste en añadir a cada variación de cierto orden cada uno de los números que no figuran en ella. Las variaciones monarias son evidentemente: 1, 2 3, 4. Para formar las binarias, se añaden a cada variación monaria, los números restantes, obteniéndose: 12 21 31 41 13 23 32 42 14 24 34 43 Se forman ahora las ternarias, agregando a cada binaria los números que no aparecen en ellas. Aplicando el Principio Multiplicativo tenemos que: hay 12 variaciones binarias y a cada una se le pueden añadir 4-2 números, de lo cual se obtienen 12×2= 24 variaciones ternarias. 123 231 321 412 124 213 312 421 132 241 342 423 134 214 324 432 142 234 314 413 124 243 341 431 Análogamente se realiza el análisis para las variaciones cuaternarias o de cuarto orden. En las variaciones sin repetición el proceso de formación de las muestras concluye cuando el orden (p, cantidad de elementos de la muestra) coincide con la cantidad de elementos del conjunto(N). Siguiendo el proceso descrito anteriormente se pueden formar las variaciones sin repetición de n objetos tomados p a p. Teorema: El número de variaciones sin repetición de “N “objetos tomados p a p es: • V(N)= N(N-1) (N-2)… (N-p+1) Con N ≥ p, N y p son números naturales, N ≥1. Demostración.( inducción completa respecto a n) • Para n=p=1 se tiene V (1,1)= 1. • Para N=p resulta: V (p, p)= p (p-1) (p-2)… (p-(p+2)) (p-(p+1)) se obtienen las variaciones sin repetición de p elementos tomados p a p; por lo cual resulta válida para n=p. • Supongamos que es cierta para n=k. V (k, p) = k (k-1) (k-2)… (k – (p+2)) (k – (p+1)) • De la validez para n=k se deduce la validez para n=k+1 V (K+1, p) = (k+1) K (k-1) (k-2) (k-3)… (k – (p+2)) (k – (p+1)) La fórmula está compuesta por p factores dispuestos en orden decreciente comenzando por n y terminado por p. El siguiente ejemplo muestra el proceso de solución de un problema combinatorio. Ejemplo 2: ¿Cuántos números de tres cifras diferentes se pueden formar con los dígitos que componen el número 24756? En este problema tenemos como elementos a los dígitos 2, 4, 7, 5, 6; en total 5 elementos y debemos formar muestras de 3 elementos diferentes, es importante destacar el hecho de la no repetición de los elementos las muestras. Formemos algunas muestras del experimento. 247, 724,245. Resulta fácil observar el cumplimiento de las características correspondientes a las variaciones sin repetición Dos muestras difieren: • O en el orden de sus elementos(.247, 724) • O por lo menos un elemento. (247 y 245) • Los elementos no se repiten en la misma muestra. Comprobado que el elemento combinatorio presente en el problema sin dudas variaciones sin repetición podemos determinar fácilmente la cantidad de elementos del conjunto (N=5) y la cantidad de elementos que tienen las muestras (p=3). Aplicando la fórmula para el cálculo y efectuando los mismos obtenemos V (5,3)=5x4x3=60 números de tres cifras. Para validar el resultado obtenido podemos aplicar el Principio Multiplicativo: Podemos designar al lugar de las centenas por la variable m, las decenas por n y las unidades por p. El lugar m puede ser ocupado de 5 formas, n de 4 formas y p de 3 formas. El número de veces en que en ese orden pueden ocurrir las cosas es: m x n x p=5x4x3=60 El análisis de los problemas combinatorios es la clave para determinar la naturaleza del experimento aleatorio presente en el mismo. En ocasiones la diferencia entre los elementos combinatorios es tan sutil que no es fácil de apreciar si el análisis es superficial. Ejemplo 3: En un grupo de 8 personas hay que elegir un presidente, un vicepresidente y un secretario. ¿De cuántas formas se puede hacer? Se deben formar grupos de tres personas para los cuales se van a designar responsabilidades, no importa el orden de elección de las personas y sí el orden en que se designen los cargos. Formemos tres muestras del experimento. Como no se repiten los cargos y la designación de las responsabilidades difiere en cada muestra formada, nos muestra que el experimento se trata de variaciones sin repetición. N=8 y p= 3 V (8,3)= 8x7x6=336. La validación y análisis retrospectivo del problema podemos hacerla de manera similar al ejemplo 2. Si se cambia ligeramente la estructura del problema como por ejemplo: En un conjunto de 8 personas hay que elegir a un grupo de tres para participar en un evento. ¿De cuántas formas se puede hacer? Formemos algunas muestras de ese experimento. Primer grupo: Pablo, Juan, Jonás. Segundo grupo: Jonás, Pablo, Juan. Tercer grupo: Pablo, Raquel, Juan. No importa el orden en que se tomen los integrantes de los grupos, puesto que si tienen los mismos integrantes, se trata del mismo grupo: es lo que pasa con el primero y segundo grupos. En el análisis de las muestras podemos darnos cuenta que son diferentes el primero y tercer grupos o el segundo y tercero. En las muestras de este experimento no es el orden lo que determina la diferencia entre ellas. El problema se soluciona a través del cálculo de otros elementos de la combinatoria. Por ahora sólo mencionaremos el caso. Más adelante abordaremos la teoría que permite identificar el experimento presente en el problema y resolver el mismo, así como los recursos matemáticos que nos auxiliarán en el cálculo. II.2.- Permutaciones sin repetición. En párrafos anteriores mencionamos que el proceso de formación de las muestras de un experimento sobre variaciones sin repetición concluye cuando el número de elementos de la muestra coincide con la cantidad de elementos del conjunto. (N=p). “El tipo de variaciones sin repetición en las cuales se cumple que la cantidad de elementos del conjunto coincide con la cantidad de elementos de cada muestra (N=p) se llama permutaciones sin repetición de los N elementos. Se denota P(N)” Las permutaciones de los N elementos de un conjunto pueden entenderse como las variaciones sin repetición de los N elementos de un conjunto tomados N a N. Como hemos definido las permutaciones sin repetición de los N elementos de un conjunto como un caso particular de las variaciones sin repetición, se hace necesario declarar cuáles son las características que permiten diferenciarlas del resto de las variaciones sin repetición. En este sentido enunciaremos a título de características las siguientes: • Dos muestras difieren únicamente en el orden de sus elementos. • En todas las muestras del experimento aparecen los N elementos del conjunto. • Los elementos no se repiten en las muestras. Las permutaciones sin repetición generalmente no presentan muchas dificultades para identificarlas si aplica como regla las características mencionadas. Ejemplo 4: En una serie mundial de baseball participan 6 equipos. ¿Cuántas posiciones finales pueden obtenerse? Formemos algunas muestras del experimento: Designemos los equipos por los números 1, 2, 3, 4, 5,6 y analicemos en las muestras siguientes sus características. Posiciones finales Muestra 1 Muestra 2 Muestra 3 Primer lugar 1 6 1 Segundo lugar 2 5 3 Tercer lugar 3 4 5 Cuarto lugar 4 3 4 Quinto lugar 5 2 2 Sexto lugar 6 1 6 Es fácil apreciar el cumplimiento de las características de las permutaciones sin repetición. Hemos dicho que las permutaciones sin repetición son un caso particular de las variaciones sin repetición de N elementos tomados N a N. Podemos aplicar la fórmula conocida para el cálculo de las variaciones sin repetición teniendo en cuenta que N=p. En este caso podemos plantear: V (6,6)=6x5x4x3x2x1=720 posiciones finales diferentes. La aplicación del Principio Multiplicativo servirá para realizar la validación y análisis retrospectivo de la vía de solución dada. Resulta fácil observar que si en la fórmula: • I) V(N)= N(N-1) (N-2)… (N-p+1) se sustituye p por N; en virtud de ser N=p, resulta • II) V(N)= N(N-1) (N-2)… (N-(N-1))= N(N-1) (N-2)… 2x1 Haciendo uso de la notación declarada para las permutaciones sin repetición y correspondiendo su cálculo con el desarrollo del miembro derecho de II tendremos: P(N)= N(N-1) (N-2)… (N-(N-1))= N(N-1) (N-2)… 2x1 Que es la fórmula para el cálculo de las permutaciones sin repetición de N elementos. Teorema: El número de permutaciones sin repetición de N elementos se denota P(N) y se calcula por la fórmula: P(N)= N(N-1) (N-2)… (N-(N-1))= N(N-1) (N-2)… 2x1 donde N es un número natural mayor o igual que 0. Nota: Asumimos para N=0; que P (0)=1. Demostración. (Inducción completa respecto a N) • Para N=0, P (0)=1. Se cumple para N=0. Para N=k • P (k) = k (k-1) (k-2)… (K-(k-1))= k (k -1) (k -2)… 2x1 De la validez para n=k se infiere la validez para k+1. Multiplicando por k+1 en ambos miembros de la igualdad anterior resulta: P (k) (k+1) = (k+1) k (k -1) (k -2)… 2x1 P (k+1)= (k+1) k (k -1) (k -2)… 2x1 como se quería. El número P(N)= N(N-1) (N-2)… 2x1 se llama factorial de N y se denota por N! .Representa el producto de N números naturales dispuestos en orden decreciente, comenzando por N y terminando en 1. La fórmula para el cálculo de las permutaciones sin repetición de N elementos se reduce a: • P(N)= N!= N(N-1) (N-2)… 2x1 El ejemplo 4 visto anteriormente quedaría resuelto de la forma: P (6)=6x5x4x3x2x1=720 La fórmula para el cálculo de las permutaciones sin repetición se valida con el Principio Multiplicativo. Ejemplo 5: Determine el número de palabras (con sentido o no) que se pueden obtener con las letras de la palabra amor. Formemos algunas muestras de este experimento aleatorio: amor, roma, ramo. Como puede observarse, se cumple que: • Las muestras difieren únicamente en el orden de sus elementos. • En todas las muestras del experimento aparecen los 4 elementos del conjunto.(N=p=4) • Los elementos no se repiten en las muestras. Se trata de una permutación de 4 elementos. Luego: P (4)=4x3x2x1=24 palabras. Si como validación de la vía usada para el cálculo usamos el Principio Multiplicativo podemos razonar del siguiente modo: Usando un modelo de colocación en celdas como la que mostramos: m n p q La primera celda puede ser ocupada de m=4 maneras distintas, después de esto, la segunda celda puede ocuparse de n= 3 formas, la tercera celda, de p=2 formas y la cuarta de q=1 forma; con lo cual podemos expresar: mxnxpxq=4x3x2x1= 24 En los experimentos aleatorios en los cuales el número de muestras no es muy elevado podemos usar también el conteo como método de validación y control de la vía usada para el cálculo. Así por ejemplo, en este caso podemos proceder usando el elemento pivote para la formación de las muestras. El método consiste en dejar libres dos elementos y permutarlos, fijando los restantes. amor mora omra roma amor moar omar roam armo maro orma raom arom maor oram ramo aomr mrao oamr rmao aorm mroa oarm rmoa El conteo de las muestras formadas confirma la solución dada. Ejemplo 6: Coloca las cifras 6, 4, 3,1 en la siguiente tabla de manera que al sumarlas vertical, horizontal y diagonalmente obtengas el mismo resultado. Siempre aparecen los mismos elementos en cada muestra y la diferencia radica sólo en el orden. No se repiten los elementos en cada muestra. Se confirman las características de las permutaciones sin repetición. P (4)=24. Al sumar los números siempre se obtiene 14. Hay varias maneras de llenar la tabla; una de ellas es la siguiente: 1 4 6 3 6 3 1 4 3 6 4 1 4 1 3 6 El orden de colocación de los elementos en la diagonal sirve como pivote para la búsqueda de otras soluciones.¡Encuentre usted la suya! II.3.- Permutaciones circulares. En los ejemplos anteriores hemos imaginado los elementos que forman las permutaciones colocados ordenadamente en línea recta. Hubiera sido lo mismo imaginarlos situados en una curva abierta; pero las condiciones varían si los situamos en una curva cerrada porque el orden que se establece entre sus elementos es relativo: • No cambia si se efectúa una rotación de modo que cada elemento ocupe el lugar del otro. A este tipo de permutaciones se les llama permutaciones circulares o cíclicas. En las permutaciones circulares los elementos se consideran distribuidos sobre una circunferencia. Las permutaciones circulares pueden identificarse si el análisis de situación mencionada conlleva a la confección de una curva cerrada, fijando uno de los N elementos y permutando los N -1 restantes, tal y como se hace en las permutaciones sin repetición. Para formar las permutaciones circulares de N elementos; basta fijar uno de ellos y elegir uno de los dos sentidos posibles en la curva, permutando de todas las formas posibles los N -1 elementos. El número de permutaciones circulares de N elementos se calcula mediante la fórmula: Pc(N)= (N -1)!, N es un número natural mayor o igual que 1. Demostración. • Para n=1. Pc (1) = (1-1)!= o!=1 • Para N=k Pc(k) = (k-1) !=(k-1) (k-2)…(k-(k-2))1 • Para N=k+1. Multiplicando por k en ambos miembros de Pc(k)= (k-1)! obtenemos: Pc(k+1) =(k-1)! K=k (k-1)!=k! Ejemplo 7: Con las letras M,N,O,P se pueden formar las permutaciones circulares siguientes: La saeta indica el sentido de la permutación. Siempre que no se aclare el sentido de la permutación pensaremos que es positivo. En la solución del ejemplo hemos usado un diagrama para formar las muestras del experimento. A través del conteo podemos darnos cuenta que hay 6 permutaciones cíclicas o circulares. Usando la fórmula tendríamos: Pc (4)= (4-1)!=3!=6 Ambos métodos se complementan y validan mutuamente. Ejemplo 8: ¿De cuántas formas se pueden sentar 8 personas alrededor de una mesa? Designemos a las personas por las letras a,b,c,d,e,f,g,h y formemos algunas muestras del experimento Muestra 1 Muestra 2 En ambos casos fijamos un elemento y permutamos los restantes: se trata de una permutación circular de 8 elementos. Pc (8) = (8-1)!= 7!= 5040 Se pueden sentar alrededor de la mesa de 5040 formas. En los problemas combinatorios cuyo total de muestras es muy grande, la validación de la vía de solución dada debe tener un sentido discreto, en el orden que exige la Matemática Discreta. Podemos mencionar algunas muestras del experimento usando el conteo y comprobar el desarrollo del cálculo mediante al Principio Multiplicativo. II.4.-Permutaciones con repetición. Hasta ahora hemos tratado las permutaciones lineales y las circulares, estableciendo las características que permiten identificarlas. En ambos casos permutamos elementos distintos entre sí. En cambio, si algunos fueran iguales debemos hacer otras consideraciones. Las permutaciones con repetición con repetición se identifican fácilmente a través de sus características esenciales. En un experimento sobre permutaciones con repetición, las muestras tienen las siguientes características: • En cada muestra aparecen los N elementos del conjunto. • Las muestras difieren sólo en el orden entre los elementos de diferente naturaleza. Ejemplo 9: El número 3344 tiene 2 números 3 y 2 números 4. si permutamos los cuatro dígitos que lo componen, siempre observaremos la presencia de estos en todas las muestras, sin embargo; si permutamos entre sí los elementos de igual naturaleza, no se apreciarán diferencias entre las muestras. Deberemos permutar los elementos de diferente naturaleza para poder distinguirlas. Formación y número de permutaciones con repetición. Consideremos las permutaciones que podemos hacer con los dígitos que componen al número 1234. Formando todas las muestras de ese experimento podemos observar: 1234 2134 3124 4123 1243 2143 3142 4132 1324 2341 3214 4231 1342 2314 3241 4213 1423 2413 3412 4312 1432 2431 3421 4321 Hay 24 permutaciones. Si en lugar de elegir el número anterior, hubiésemos seleccionado el número 3344, en todas las muestras obtenidas anteriormente podríamos sustituir al 2 por el 4 y al 1 por el 3. En este caso de estas 24 permutaciones serían diferentes sólo 6 de ellas. 3434 4334 3344 4343 3443 4343 3344 4334 3344 4433 3434 4433 3344 4433 3443 4343 3434 4343 3434 4343 3443 4334 3443 4334 El análisis del experimento demuestra el cumplimiento de las características que tienen las muestras de las permutaciones con repetición. En el experimento anterior, de las 24 permutaciones lineales del número 3344 hay 6 dígitos repetidos 4 veces cada uno, entonces el conjunto de cifras cuya diferencia está en el orden de colocación se calcula fácilmente mediante la operación siguiente: 24/4=6. La interpretación del resultado anterior conlleva a plantear para el cálculo de las permutaciones con repetición la siguiente relación: P (4) ⁄ 4 =6 Sabemos que P (4)=4!=24, pero podemos escribir el denominador como 4=2!x2!, cada uno de estos 2! significa la cantidad de permutaciones de cada uno de los elementos que se repiten en el conjunto de valores. Teorema: El número de permutaciones con repetición (Pr) que se pueden hacer con N elementos, de los cuales hay repetidos N1, N2…Nk es: Pr(N1N2...Nk) =N! ⁄ ( N1! x N2! x…xNk!) Siendo N= N1+N2+…+Nk Ejemplo 10: ¿Cuántas señales se pueden hacer con 5 banderas si de ellas hay tres verdes y dos rojas; si cada señal se debe hacer usando todas banderas a la vez? Analicemos las características de las muestras de este experimento: Como puede apreciarse: • En cada muestra aparecen los N elementos del conjunto. • Las muestras difieren sólo en el orden entre los elementos de diferente naturaleza. Se trata de un problema de permutaciones con repetición. N1= 2 N2=3 Pr(2,3)=5! ⁄ 2! 3! =10 Se pueden hacer 10 señales. Como método de validación y control de la vía de solución podemos usar el conteo porque el número de muestras no es muy elevado. Ejemplo 11: ¿De cuántas maneras se pueden colocar las figuras blancas (dos caballos, dos torres, dos alfiles, el rey y la reina) en la primera fila del tablero de ajedrez? Haciendo un análisis similar al del ejemplo anterior podemos comprobar que se trata de un experimento sobre permutaciones con repetición de N= 8 elementos agrupados en subgrupos N1=2, N2=2, N3=2, N4=1 y N5=1de elementos iguales. Pr (2, 2, 2, 1,1) = 8! ⁄ (2!x2!x2!x1!x1!) = 5040 En los problemas combinatorios cuyo total de muestras es muy grande, la validación de la vía de solución dada debe tener un sentido discreto, en el orden que exige la Matemática Discreta. Podemos mencionar algunas muestras del experimento usando el conteo y comprobar el desarrollo del cálculo mediante al Principio Multiplicativo si es posible y si el cálculo no engendra mayores complicaciones que la vía usada para la solución. II.5.- Variaciones con repetición. Dentro de las variaciones, un lugar importante es ocupado por las variaciones con repetición. Algunos textos tratan las variaciones con repetición apoyados en las correspondencias entre conjuntos. En este texto nos apoyaremos en las características que tiene el concepto y lo aplicaremos a la solución de problemas. Resolvamos el siguiente ejemplo: Ejemplo 12 ¿Cuántos resultados son posibles si se lanzan dos dados sobre un tapete? El experimento presupone la existencia de dos conjuntos de elementos iguales uno a uno: cada dado tiene 6 caras y cada cara tiene un valor: un punto, dos puntos, tres, cuatro, cinco o seis puntos respectivamente. Si consideramos el lanzamiento de ambos dados a la vez puede ocurrir que el resultado obtenido en uno de ellos sea cualquiera de los valores mencionados anteriormente; en el otro dado se pueden obtener idénticos resultados. Si consideramos que ambos dados se deben lanzar juntos, entonces una muestra de este experimento estaría constituida por los resultados obtenidos en los dos dados; luego, la repetición es un elemento a tener en cuenta en este experimento. Cada muestra de este experimento contiene dos resultados; cada uno de los cuales corresponde a cada dado. Separando los resultados para estudiarlos, el análisis nos conduciría a: • El primer dado (D1) puede caer de solo 6 formas. • El segundo dado (D2) puede caer de 6 formas. Aplicando el Principio Multiplicativo obtenemos el siguiente resultado: D1XD2 = 6x6 = 62 = 36 resultados. Si aumenta el número de dados, el análisis sería similar. Si en lugar de dos fueran seis los dados, la solución del problema sería: 6x6x6x6x6x6=66= 46 656 Según aumenta el número de dados, aumenta el número de factores Ejemplo 13 ¿Cuántos números de 2 cifras se pueden formar con los dígitos del 1 al 9? Como se trata de un número de dos lugares, podemos usar un modelo de colocación en celdas para estudiar las características de las muestras del experimento. 1 2 2 1 1 1 1 3 Muestra 1 Muestra 2 Muestra 3 Muestra 4 Como se aprecia en las celdas, las muestras del experimento tienen diferencias en: • el orden de sus elementos. (Muestra 1 y Muestra 2 ) • por lo menos un elemento. (Muestra 1 y Muestra 4) Hasta aquí podemos ver que se trata de un tipo de variación; sin embargo en la muestra 3 ambas celdas están ocupadas por el mismo número, lo cual denota repetición. A las características anteriores podemos añadir la siguiente: • los elementos pueden repetirse en la misma muestra. En virtud de la aplicación del Principio Multiplicativo a la solución del problema podemos plantear que: si el primer lugar (m) se puede ocupar de 9 formas diferentes y el segundo (n), de 9 formas también, ambas cosas en ese orden la podemos obtener: m x n= 9x9=92=81 números de 2 cifras. En los ejemplos 11 y 12 destacamos las características de las muestras de los experimentos y observamos que se admitía la repetición. Estas muestras de experimentos sobre variaciones en las cuales se admite la repetición se llaman variaciones con repetición. Definición: “Se llaman variaciones con repetición de N elementos tomados de p maneras, a todas las posibles ordenaciones de los p elementos en los cuales se admite la repetición”. Las características de las muestras de variaciones con repetición son: • Las muestras difieren en el orden. • Los elementos pueden repetirse en las muestras. La primera característica representa el concepto genérico (variaciones); la segunda, la diferencia que caracteriza el género (repetición). Las variaciones con repetición de N elementos tomados de p maneras se calcula mediante la fórmula: Vr(N, p)=N p Se lee variaciones con repetición de N en p, N es la cantidad de elementos del conjunto y p la cantidad de elementos que hay en cada muestra. N y p son números naturales y se cumple que: N > p, N < p, N=p . Ejemplo 14: De una caja que contiene 4 bolas de diferentes colores se extrae una muestra de 3 bolas (una a una), devolviendo cada bola a la caja antes de extraer la siguiente. ¿Cuántas muestras se pueden extraer? En este experimento las muestras están constituidas por la extracción de tres bolas, una a una, devolviendo cada bola a la caja antes de realizar la extracción de la siguiente. Denotemos a las bolas por b1, b2, b3, b4 y formemos algunas muestras. Muestra 1: b1b2 b3 Muestra 2: b3 b2 b1 Muestra 3:b1b1b2 Las muestras corresponden a las variaciones con repetición. N=4 (cantidad de elementos del conjunto) p=3 (cantidad de elementos que hay en cada muestra) Vr (4,3)=43=64 muestras. Ejemplo 15: Una caja de caudales tiene un disco con 12 letras y se han combinado para obtener una palabra de 5 letras que es la clave para abrirla. ¿Cuántas pruebas deben ser efectuadas para encontrar la clave? En el problema se cuenta con un conjunto de 12 letras del cual se deben escoger grupos de 5, admitiéndose la repetición. El experimento resulta de variaciones con repetición de 12 elementos tomados de 5 en 5, las muestras siguientes lo confirman: Supongamos que las letras son: a, e, i, o, u, m, n, p, q, r, s, t Muestra 1: trisa Muestra 2: asirt Muestra3: masa Vr (12,5)=125=248 832 pruebas deben ser efectuadas para encontrar la clave. Podemos validar la vía de solución a través del uso del Principio Multiplicativo. Ejemplo 16: El código Morse es la combinación de puntos y rayas con la finalidad de formar letras. ¿Cuántas letras se pueden formar en las cuales aparezca? a) Un símbolo b) Dos símbolos c) Cuatro símbolos. El experimento está compuesto por muestras de puntos y rayas en las cuales se admite repetición. Se trata de un experimento sobre variaciones con repetición de N=2 elementos tomados: a) de uno en uno. b) de dos en dos. c) De cuatro en cuatro. La solución para cada uno es: a) Vr (2,1)= 21=2 b) Vr (2,2)=22=4 c) Vr (2,4)=24=16 Con este ejemplo mostramos la relación que existe entre N y p, (N ≥ p, N ≤ p). Para el trabajo en los problemas sobre variaciones con repetición es útil identificar inicialmente la cantidad de elementos con los que se debe trabajar (N) porque se mantiene constante durante el experimento. La variación radica en la cantidad de elementos que tienen las muestras (p). Ejemplo 17: ¿Cuántos números de 5 cifras se pueden formar con los dígitos 1,2 y 3? En este ejemplo las muestras del experimento (p) tienen mayor cantidad de elementos que el propio conjunto del cual se forman las muestras (N). Se cumple que N < p. Esto solo se cumple en los experimentos sobre variaciones con repetición. Vr (3,5) = 35=243 números de cinco cifras. Para validar el resultado usando un modelo de colocación: a b c d e Muestra 1 1 2 3 2 1 Muestra 2 1 2 3 3 1 Muestra 3 1 2 3 1 1 Observamos que N p, N0, N ≥ p. Resulta conveniente resaltar las características que presentan las combinaciones sin repetición: • Las muestras de un experimento sobre combinaciones sin repetición no difieren en el orden de colocación de sus elementos. En el proceso de análisis de un problema resulta muy útil aplicar este parámetro de identificación para encontrar la vía de solución. Formación y número de combinaciones sin repetición. Haremos primeramente algunas consideraciones acerca de cómo se puede obtener el número de combinaciones sin repetición de N objetos tomados p a p. Comencemos nuestro análisis partiendo del conjunto: a, b, c, d Las combinaciones de primer orden serían cada uno de los elementos del conjunto: a, b, c, d (cuatro combinaciones de primer orden) Las combinaciones binarias se hallan a partir de las de primer orden, añadiendo a cada combinación de primer orden una letra distinta cada vez y desechando las muestras que sólo difieran en el orden. Por este medio se obtienen seis combinaciones binarias o de segundo orden: ab, ac, ad, bc, bd, cd. Las combinaciones terciarias o de tercer orden se hallan a partir de las de segundo orden, añadiendo a cada combinación binaria una letra distinta cada vez y desechando las muestras que sólo difieran en el orden. Las combinaciones de tercer orden serían: abc, abd, acd, bcd. Combinaciones de cuarto orden: de manera análoga a la descrita en las casos anteriores se obtienen las combinaciones de cuarto orden .Una sola de cuarto orden: abcd. Entre las combinaciones sin repetición, las variaciones sin repetición y las permutaciones sin repetición se establece la siguiente relación: C(N, p)=V(N, p) ⁄ P (p). Esta relación resulta útil para validar la solución dada a un problema sobre combinaciones sin repetición. Ejemplo 2: Un equipo de 5 estudiantes realizó un trabajo de investigación. En la exposición participarán 4 estudiantes. ¿De cuántas maneras se pueden seleccionar los 4 estudiantes? En este problema debemos realizar particiones del conjunto de los 5 estudiantes en subconjuntos de 4. Designemos a los estudiantes por las letras A, B, C, D, E, y formemos algunas muestras del experimento: Muestra 1: A, B, C, D Muestra 2: D, C, B, A Muestra 3: A, B, C, E Los subconjuntos representados en las muestras 1 y 2 contienen a los mismos elementos (se trata del mismo equipo): no difieren en el orden Las muestras 1 y 3 contienen diferencias en al menos un elemento. Esta diferencia indica que estas muestras no se diferencian por el orden de colocación de sus elementos. El experimento analizado es sobre combinaciones. Para calcular su número podemos en este caso usar un modelo de muestreo: Muestra 1: A, B, C, D Muestra 3: B, C, D, E Muestra 4: C, D, E, A Muestra 2: A, B, C, E Muestra 5: B, C, A, D A través del conteo podemos observar que son 5 los equipos que se pueden formar. Ejemplo 3: ¿Cuántas rectas de unión se pueden trazar entre seis puntos de un plano si tres de ellos nunca están alineados? La situación la podemos modelar gráficamente de forma similar a la siguiente: Las muestras de este experimento están constituidas por rectas, cada una de las cuales se trazan por dos puntos. De ahí que la recta AB sea la misma de BA (no se tiene en cuenta el sentido). Aquí se aprecia la característica esencial de las muestras sobre combinaciones: no difieren en el orden. Formando todas las muestras del experimento, obtendremos: AB,AF,AE,AD,AC,BF,BE,BD,BC,FE,FD,FC,ED,EC,DC El conteo de las muestras formadas nos indica que el número de rectas que se pueden trazar es 10. “El número de combinaciones sin repetición que se pueden formar con N elementos tomados de p en p es: C(N, p) = N! ⁄ p!(N – p)! Los ejemplos anteriores se pueden resolver usando esta fórmula. De ese modo la vía de solución del ejemplo 2 se reduce a: N=5, p= 4 C (5, 4) = 5! ⁄ 4! (5 – 4)!=5 Por su parte, la solución del ejemplo 3 es: N= 6, p=2 C (6, 2) = 6! ⁄ 2! (6 – 2)!= 6! ⁄ 2! 4!=15 Ejemplo 4: En un departamento docente hay 8 personas. Deben extraerse tres para participar en un evento. ¿De cuántas maneras se puede realizar la selección? Designemos a las personas por a, b, c, d, e, f, g, h. Formemos algunas muestras del experimento. Muestra 1: a, b, c Muestra 2: c, b, a Muestra 3: a, b, d Las muestras 1 y 2 no difieren en el orden: son las mismas personas. Se trata de un experimento sobre combinaciones. N=8, p=3. C (8, 3) = 8! ⁄ 3! (8 – 3)!= 56 maneras. Como vía de validación y control en los problemas sobre combinaciones puede aplicarse el conteo, siempre que el número de muestras no sea muy elevado. Es posible validar el resultado usando la fórmula que relaciona a las variaciones sin repetición con las combinaciones sin repetición: • C(N, p)= V(n, p) ⁄ P(p). La aplicación del Principio Multiplicativo no resulta conveniente para la validación de los resultados de los problemas sobre combinaciones. III.2.- Combinaciones con repetición. “En una dulcería se venden 4 tipos de pasteles diferentes. ¿De cuántas formas se pueden comprar 3 pasteles? Como se puede apreciar este problema tiene otra estructura que los ya resueltos. No se trata de una variación porque el orden en que se dispongan los pasteles en una caja es indiferente. Por esta razón la naturaleza del problema se halla más cerca de las combinaciones que de las variaciones, sin embargo en las muestras de este experimento los elementos pueden aparecer repetidos. Estamos en presencia de un caso especial de las combinaciones conocido como combinaciones con repetición. Para una mejor comprensión del problema consideremos una vez más el conteo. Formemos para ello las muestras que componen este experimento; considerando al conjunto formado por las letras a, b, c, d como los tipos de pasteles. Formando todas las muestras de tres pasteles, obtendríamos el siguiente resultado: aaa,aab,aac,aad,abb,abc,abd,acc,acd,add,bbb,bbc,bbd,bcc,bcd,bdd,ccc,ccd,cdd,ddd. Mediante conteo podemos ver que hay 20 muestras diferentes. En este experimento la diferencia entre las muestras no está en el orden sino por lo menos en un elemento. Es preciso observar que los elementos pueden repetirse en una muestra. Definición:” Se llaman combinaciones con repetición de M1,M2,..Mn conjuntos de elementos de diferentes tipos, a todas las selecciones de p elementos pertenecientes a los Mn conjuntos en los cuales se admite la repetición”. Las características que destacan los rasgos de este concepto son: • Las muestras no difieren en el orden entre sus elementos. • Los elementos se pueden repetir en las muestras. Para designar a las combinaciones con repetición de N elementos tomados de p en p usaremos la siguiente notación: Cr(N, p) y la leeremos “combinaciones con repetición de N en p “. Teorema: El número de combinaciones con repetición de N objetos tomados p a p es: Cr(N, p)=(n+p -1)! ⁄ p!(n-1)! Con N ≥ p En lo sucesivo esta fórmula nos permitirá el cálculo de las combinaciones con repetición. Ejemplo 5: ¿De cuántas formas puedo escoger dos bolas de un conjunto de seis, entre las que hay tres rojas y tres azules? Si usamos el muestreo de las particiones del conjunto en subconjuntos de dos bolas, podemos obtener algunas muestras del experimento. • Las muestras no difieren en el orden entre sus elementos.( muestras 3 y 4) • Los elementos se pueden repetir en las muestras.( muestras 1 y 2) Se trata de un experimento sobre combinaciones con repetición. N=6 p= 2 Cr (6, 2)= (6+2 -1)! ⁄ 2!(6-1)!=7! ⁄ 2! 5!=21 formas de escoger 2 bolas. La vía usada para la solución puede validarse a través del conteo, pues el número de muestras del experimento no es elevado. Cuando el número de muestras del experimento combinatorio sea elevado, podemos usar para la validación la siguiente relación: Relación entre las combinaciones sin repetición y con repetición. “El número de combinaciones con repetición de n+1 elementos de diferentes tipos, tomados de m maneras es igual al número de combinaciones sin repetición de n+m elementos tomados m a m.” Es decir: Cr(n+1, m)=C(n+m, m) Los ejercicios y problemas de combinaciones con repetición pueden reducirse al uso de esta fórmula. Ejercicios del capítulo III. 1. De un grupo de 10 personas hay que seleccionar 3 delegados para un evento. ¿De cuántas formas puede hacerse? 2. Hay 20 puntos en un plano de los cuales nunca hay tres de ellos alineados.¿Cuántas rectas de unión se pueden trazar?.¿Cuántos triángulos pueden formarse cuyos vértices sean tres de estos puntos? 3. En una circunferencia hay 20 puntos. Si se consideran estos puntos como vértices: ¿cuántos triángulos inscritos en la circunferencia se pueden trazar? 4. En un plano hay 12 puntos, de los cuales 4 están en línea recta. Determine el número de rectas de unión. 5. En una serie mundial de pelota participan 8 equipos. Si cada par de equipos se enfrenta 9 veces.¿Cuántos juegos se realizan en total? 6. Una compañía está formada por tres oficiales, seis sargentos y sesenta soldados ¿De cuántos modos se puede elegir entre un destacamento formado por un oficial, dos sargentos y 20 soldados? 7. ¿De cuántas formas se pueden escoger 12 personas entre 17, si dos de ellas no pueden ser escogidas juntas? 8. En una urna hay boletas con los números 1, 2, 3, 4…10. De ella se extraen 3 fichas a la vez.¿En cuántos casos la suma de los números escritos es 9?¿En cuántos casos es menor que 9? 9. Dados los segmentos de longitudes 4cm, 6cm, 7cm, 8cm, 9 cm. ¿Cuántos triángulos diferentes pueden construirse? 10. Un examen escrito consta de 10 preguntas. ¿De cuántas maneras puede elegir 8 preguntas para responderlas? 11. Un examen escrito consta de 10 preguntas. ¿De cuántas maneras puede responder erróneamente 2 preguntas? 12. ¿Cuál es el número de diagonales de un polígono? 13. Se tienen segmentos cuyas longitudes son4cm,7cm,8cm,6cm y 9cm.¿Cuántos triángulos diferentes de triángulos se pueden construir? 14. En un estante hay una obra en dos tomos con 5 ejemplares del tomo 1 y 4 del tomo 2.¿De cuántas maneras es posible colocarlos en el estante, de manera que : a) No se establezcan restricciones. b) Los del primer tomo estén juntos y los del segundo tomo también. c) No haya dos tomos juntos. 15.En un concurso universitario de belleza participan 20 mujeres y se van a otorgar 6 premios: 3 ejemplares de un libro, dos de otro y un ejemplar de un tercero.¿De cuántos modos se pueden entregar lo premios si a nadie se le otorgan dos ejemplares del mismo libro pero se le pueden entregar dos o tres libros diferentes? 16. Debe construirse una escalera desde el punto A hasta el punto B. la longitud de AC es igual a 4.5 m y la de BC es 1.5 m. La altura de cada escalón es iguala 30 cm. y su ancho, a un múltiplo entero de 50. ¿De cuántas maneras se puede construir la escalera? 17.¿Cuántos triángulos existen, cuyos vértices sean a la vez vértices de un hexágono convexo? 18.¿ Cuántos triángulos se pueden construir con segmentos cuyas longitudes son 4cm,5cm,6cm y 7 cm? 19. En el plano se han trazado 4 rectas entre las cuales no hay dos paralelas y no hay 3 que pasen por un mismo punto. ¿Cuántos triángulos se forman? 20. En el plano se han trazado n líneas entre las cuales no hay dos paralelas ni tres se cortan en el mismo punto ¿Cuántos puntos de intersección tienen estas rectas? 21. Se tienen dos dados homogéneos cuyos lados están marcados con los números 1, 2, 3 ,4 ,5 ,6. ¿Cuántas sumas diferentes pueden ser obtenidas al arrojar estos dados sobre un tapete? 22. Una persona tiene 7 libros de Aritmética l y otra tiene 9 de Álgebra. ¿De cuántas maneras pueden intercambiarse dos libros de uno por dos del otro? 23. Una madre tiene tres naranjas y dos guayabas. Cada día durante 5 días seguidos, le regala a su hijo una fruta. a) ¿De cuántas maneras puede repartir las naranjas? b) ¿De cuántas maneras puede repartir las guayabas? c) ¿De cuántas maneras puede repartirlas totalmente? 24. En una oficina postal se puede comprar tarjetas de felicitaciones de 10 tipos. a) ¿De cuántas formas se pueden comprar en ella 8 tarjetas? b) ¿De cuántas formas si las 8 son diferentes? 25. En una estación ferroviaria se expiden 8 tipos de boletos para viajar. ¿De cuántas maneras pueden comprarse 3 o 4 boletos? 26. ¿Cuántos triángulos escalenos (isósceles) se pueden formar con segmentos de 3cm, 4cm, 5cm y 6cm? Soluciones y respuestas. Respuestas a los ejercicios del capítulo I. 1. 9 2. 25,20 3. 7x6+21x12=294 4. 153 5. 12 6. 147 7. 24 8. 49x7 9. 125;75 10. 450 11. 9000 12. 5832 13. 200 14. 14648 15. 738 16. 15(500,401,410,140,104,302,320,230,203,212,221,122,311,131,113) 17. 1024 18. 8 19. 30 20. 62 21. 20 22. 6 23. 6 24. 126 25. 72 Respuestas a los ejercicios del capítulo II. 3. V(7,4) 4. 30 5. 5+20+60 6. 6+30+120 7. 9V(9,4) 8. 20 9. V(5,3),V(5,3)-12 10. V(4,2) 11. V(5,2) 12. V(25,4) 13. V(6,2) 14. 60,12 15. Siendo distintas dos a dos las naranjas, se tiene V(8,5) 16. V(30,4) 17. P(11);P(9) 18. P(6)-2P(5) 19. P(5);5P(4) 20. P(4);12,12 21. P(8) 22. 3P(3), a) 10,b)18 ,c)6, d)6 25. P (7) 26. P (11) 27. P (10) 28 Pr (3, 2, 2, 1, 1,1) 29. Vr (6,8) + Pr (3, 1, 1, 1, 1,1) 30. Pr (5, 6,7) 31. Como la C va inmediatamente después de una O las tres O pueden unirse y considerarse como una sola letra. Por esto el número de permutaciones es : Pr (1, 1, 1, 1, 1, 1) 32. Pr (3, 1, 1, 1,1 ,1) - P(5) 33. Pr (3, 1, 1, 1) - P(4) 34. Vr(4,5) 35.Vr(15,2), V(15,2) 36. P(6) 37.V(25,5); Vr(25,5) 38. P(6) 39.20 ,5 40. Pr(3,1,1,1,1,1) 41. P(6) 42 Vr(6,3) 43.Vr(8,3) 44.Vr(9,3) 45.Vr(4,3) 46. 10 ( 40,41,..50) 47.9 Vr(9,4) 48. Vr(10,3) 49.9 ( 18,28,38,48,58,68,78,88,98) 50. 9 Vr(10,3) 51. 90 52.3 V(,3) Respuestas a los ejercicios del capítulo III 1. C(10,3) 2. C(20,2); C(20,3) 3. C(20,3) 4. C(12,2) – C(4,1) +1 5. 9 C(8,2) 6. C(3,1)xC(6,2)xC(60