Lo esencial en Combinatoria (página 2)

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

¡Error!Marcador no definido.

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.

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?

Capítulo 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.

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:

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.

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.

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)… 2×1

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)… 2×1

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)… 2×1 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)… 2×1

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)… 2×1

P (k+1)= (k+1) k (k -1) (k -2)… 2×1 como se quería.

El número P(N)= N(N-1) (N-2)… 2×1 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)… 2×1

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:

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:

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 = 6×6 = 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.

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= 9×9=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?

1. 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:

1. de uno en uno.
2. de dos en dos.
3. 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:

Observamos que N < p. Acudiendo al Principio Multiplicativo podemos plantear que

axbxcxdxe=3x3x3x3x3=243

En las variaciones con repetición resultan útiles estos tipos de análisis entre N y p. En el resto de los experimentos combinatorios la relación entre N y p es más simple.

En ocasiones se hace necesario recurrir a analizar la correspondencia entre los conjuntos que se desea comparar para poder determinar quién es N y p.

Veamos el ejemplo siguiente:

Ejemplo 18: ¿De cuántas formas se pueden depositar 3 cartas en 2 buzones?

Denotemos a las cartas por C1, C2 y C3, así como a los buzones por B1 y B2.

Analicemos algunas muestras del experimento.

Muestra 1 Muestra 2 Muestra 3

Como se aprecia, en los esquemas se ha establecido una correspondencia desde el conjunto de las cartas (conjunto de partida, de donde salen las flechas) hasta el conjunto de los buzones (conjunto de llegada, donde llegan las flechas). El conjunto de llegada representa a N y el de partida, representa a p. La comparación entre las muestras 1 y 2 denotan diferencias en el orden y denotan repetición. Se trata de un experimento de variaciones con repetición.

N=2, p=3.

V (2,3)=23=8 formas

Si aumentamos el número de cartas y el de buzones, aumentarán los valores asignados a N y p, pero el análisis de la situación será similar al planteado.

El ejemplo 12 se puede realizar haciendo un análisis similar.

Designando a los dados por D1 y D2 respectivamente y los resultados por 1, 2, 3, 4, 5, 6. Establecemos una correspondencia desde el conjunto de los dados hasta el de los resultados.

La siguiente ilustración servirá para el análisis:

En las muestras de este experimento se aprecian las características de las variaciones con repetición. El conjunto de partida en nuestro experimento está compuesto por los dados (p) y el de llegada por los resultados (N): por lo cual N=6, p=2.

V (6,2)=62=36 formas

Al aumentar el número de dados, aumentará el valor de p, mientras que N permanecerá igual. De esta forma podemos obtener los distintos casos en los cuales se cumple que: N >p, N<p, N=p.

Ejemplo 19: Se lanza una moneda sobre un tapete. ¿Cuántos resultados se pueden obtener?

Supongamos que la moneda está marcada por una C de un lado y por una E del otro. Al lanzarla podemos obtener la muestra siguiente:

Resulta fácil observar que la correspondencia se efectúa desde el conjunto de la moneda hasta el conjunto de los resultados; con lo que podemos decir que N=2 y p=1.

V (2,1)= 21= 1

Ejemplo 20: ¿Cuántos resultados son posibles de obtener si se lanzan sobre una mesa dos monedas?

En este ejemplo tenemos una situación similar al anterior, pero; aumenta el número de monedas. En este, como en el anterior, está claro que el conjunto de partida (N) es el de las monedas y el de llegada el de los resultados (p). Observemos que N aumenta y p permanece igual.

N=2, p=2

V (2,2)=22= 4 formas

Los problemas sobre variaciones con repetición se pueden validar a través del Principio Multiplicativo o mediante el Conteo si el número de muestras es pequeño, como en los dos últimos ejemplos.

Ejercicios del capítulo II.

1. Forme las variaciones sin repetición de los números 1, 2, 3,4 tomados:

1. De2 en 2.
2. De 3 en 3
3. De 4 en 4.

2. En el ejercicio anterior diga por qué no es posible obtener variaciones sin repetición tomando las muestras de 5 en 5.

3. ¿De cuántas maneras se pueden depositar 4 cartas en 7 buzones, sin depositar más de una carta encada buzón?

4. De la Habana a Guantánamo cubren la ruta 6 ómnibus.¿ de cuántas maneras se puede hacer el viaje tomando al regreso un ómnibus distinto al de ida?

5. ¿Cuántas señales se pueden hacer con 5 banderas de colores diferentes si cada señal se puede hacer con 1, 2, o 3 banderas?

6. Con los dígitos 1, 2, 3, 4, 5,6. ¿Cuántos números menores que 1000 pueden formarse que no tengan cifras repetidas?

7. ¿Cuántos números de 5 cifras diferentes existen en el sistema decimal?

8. Un edificio tiene cinco puertas por las que se puede entrar y salir de él. ¿De cuántas formas se puede entrar y salir del edificio por puertas diferentes?

9. ¿Cuántos números de tres cifras están formados por dígitos impares diferentes?

10.¿De cuántas formas puede confeccionarse una bandera de tres colores si el color rojo debe ocupar siempre el lugar intermedio y se dispone de los colores azul, blanco, rojo, amarillo y verde?

11.¿Cuántos diccionarios diferentes pueden editarse para que se puedan hacer traducciones directamente entre dos cualesquiera de los idiomas :español, ruso, inglés, francés y alemán?

12. Una sociedad científica está integrada por 25 personas. Es necesario elegir al presidente, al vicepresidente, al secretario y el tesorero.¿De cuántas formas puede realizarse la elección si cada miembro puede ocupar sólo un cargo?

13. Hay 6 pares de de guantes de distintas medidas.¿De cuántas maneras se pueden escoger entre ellos un guante de la mano izquierda y otro de a derecha de forma que estos sean de distintas medidas?

14. ¿De cuántas maneras se puede confeccionar una bandera de franjas, de tres colores, si se tiene 5 rollos de tela cada una con un color diferente?¿De cuántas formas una franja debe ser siempre azul?

15. Un padre tiene 5 naranjas distintas dos a dos las que entrega a sus 8 hijos de forma tal que cada uno obtiene una naranja o nada.¿De cuántos modos lo puede hacer?

16. En u club deportivo hay 30 atletas. ¿De cuántas maneras puede formarse un equipo para participar en la carrera de relevos de 4 por 100 metros?

17¿De cuántas maneras se pueden disponer los jugadores de un equipo de football? ¿De cuántas formas si el arquero y el delantero son siempre los mismos?

18. ¿De cuántas maneras se pueden poner en fila 6 personas si a una de ellas no se le permite ocupar los extremos?

19. ¿De cuántas formas se puede colocar una obra de 5 tomos en un estante? ¿De cuántas formas si uno de ellos ocupa siempre el extremo izquierdo?

20.¿Cuántos números de 4 cifras diferentes pueden formarse con las cifras del número 2547? ¿Cuántos son pares?

21. ¿De cuántas maneras se pueden colocar en un tablero de ajedrez 8 torres de forma que no se puedan comer una a otra?

22. Los dígitos 0, 3, 4,5 pueden combinarse de varias formas para obtener número de 4 cifras diferentes. ¿Cuántas formas existen de hacerlo? ;teniendo en cuenta que el número que obtengas sea divisible por:

a)2

b)3

c)2 y 5

d)3 y 10.

23. La fórmula para el cálculo de las variaciones sin repetición puede escribirse usando factoriales de la siguiente forma:

V(N,p)=N! ⁄ (N-p)!

• Pruebe que n(n-1)(n-2)…(n-p+1)= N! ⁄ (N-p)!

24. Se sabe que V(N,N)=P(N). Fundamente por qué 0!=1.

25. ¿De cuántas formas se pueden colocar 8 llaves en un llavero?

26. ¿De cuántas formas se pueden distribuir en un reloj los números del 1 al 12?

27. ¿De cuántas formas se pueden distribuir 12 personas alrededor de una mesa si los extremos están siempre ocupados por los anfitriones?

28¿Cuántas palabras diferentes se pueden formar permutando las letras de la palabra MATEMATICA?

29. ¿Cuántas palabras de 8 letras se pueden formar con las letras de la palabra PARABOLA?

30. Se quiere diseñar un piso para un restaurante y se dispone de 5 baldosas blancas, seis rosadas y siete rojas para cubrir una superficie de 18 metros cuadrados. Cada baldosa tiene un metro cuadrado. ¿De cuántas formas diferentes puede diseñarse el piso?

31. ¿De cuántas formas se pueden permutar las letras de la palabra morocho de forma que la c vaya siempre detrás de una o?

32. ¿De cuántas formas se pueden permutar las letras de la palabra MARACUYA, de forma que las tres a vayan juntas

33. ¿De cuántos modos se pueden permutar las letras de la palabra goloso de forma que las tres o no estén juntas?

34. ¿Cuántos números de tres cifras se pueden formar con los dígitos que componen al número 12 335 233?

35. Una empresa dispone de 15 ómnibus para trasladar sus empleados desde la casa hasta el trabajo. ¿De cuántas formas puede hacerse el viaje de vuelta a las oficinas si este se hace?

a) En el mismo ómnibus.

b) en ómnibus diferentes.

36. Seis personas pasan una noche en una ciudad donde existen 4 hoteles. Si dos de ellos no pueden alojarse en el mismo hotel;¿De cuántas maneras distintas pueden elegir un hotel?

37¿Cuántas palabras de 5 letras (con sentido o no) se pueden formar con todas las letras del alfabeto latino?

1. Sin que se repitan las letras.
2. Repitiendo las letras.

38. Un pastel necesita 6 ingredientes diferentes.¿De cuántas maneras se pueden mezclar?

39. Se tienen tres pares de calcetines de colores diferentes.¿De cuántas maneras pueden combinarse los colores para cada pie si en cada caso los colores pueden ser diferentes (iguales)?

40. ¿De cuántas formas se pueden distribuir las letras de la palabra TEENEGER?

41. ¿De cuántas formas se pueden disponer las letras de la palabra MURCIELAGO sin alterar el orden de las vocales?

42. Se lanzan 3 dados homogéneos que en cada cara tienen un número entre 1 y 6. ¿Cuántos resultados se pueden obtener?

43. ¿Cuántos números de tres cifras existen que no contengan ni un ocho ni un uno?

44. En un club deportivo se imprimieron carnés para sus miembros utilizando los dígitos del 1 al 9. ¿Cuántos miembros tenía el club si los carnés tenían números diferentes?

45. Cuatro estudiantes universitarios rinden un examen en la Universidad de La Habana. ¿De cuántas maneras se les puede otorgar las calificaciones si se sabe que ninguno de ellos fue desaprobado?

46. ¿Cuántos y cuáles son los números de dos cifras que tienen un 4 en el lugar de las decenas?

47. ¿Cuántos números de 6 cifras tienen el 7 en el lugar de las centenas?

48. ¿Cuántos números de 4 cifras tienen un 6 en las unidades de millar?

49. ¿Cuántos y cuáles números de dos cifras tienen un 8 en las unidades?

50. ¿Cuántos números de tres cifras tienen un tres en las centenas?

51. ¿Cuántos números de tres cifras tienen un cero en el lugar de las decenas?

52. Los dígitos 0, 3, 4, 5 pueden combinarse de varias maneras para obtener números de 4 cifras. ¿Cuántos números pueden obtenerse?

53. Demuestre por inducción completa respecto a N.

"El número de variaciones con repetición de n elementos tomados p a p es:

Vr(N, p)=N p, con N y p números naturales.

Sugerencia: Multiplicar ambos miembros de la hipótesis de inducción por el término (k+1) p ⁄ kp con k ≠ 0 y aplicar propiedades de la potenciación.

Capítulo III: Combinaciones.

En el cálculo combinatorio un lugar importante lo ocupan las combinaciones. Estos elementos tienen características propias que lo diferencian de las variaciones tratadas anteriormente.

Haremos la introducción de las combinaciones a través del siguiente ejemplo:

Ejemplo 1. "En un equipo de estudio hay 3 niñas y 2 niños. ¿Cuántas parejas diferentes pueden formarse para estudiar?

La solución dada al ejemplo en el capítulo 1 fue la siguiente:

La selección de dúos puede realizarse usando un diagrama de red de la forma siguiente:

Los dúos que se forman utilizando el diagrama de red arrojan las siguientes muestras:

AD,AS,AC,AR,DS,SC,CR,DC,SR,DR.( 10, según el conteo)

Las muestras de este experimento tienen las siguientes características:

Las muestras no difieren en el orden de sus elementos. Si elegimos por ejemplo la muestra AD e invertimos el orden por DA estaríamos formando el mismo equipo. Lo mismo ocurre con las restantes muestras del experimento.

Las muestras formadas en el experimento se llaman combinaciones sin repetición.

Definición: Se llaman combinaciones sin repetición de N objetos tomados p a p a todos los subconjuntos de p elementos tomados de los N objetos.

Denotamos a las combinaciones sin repetición por:

C(N, p) y lo leemos "combinaciones sin repetición de N elementos tomados de p maneras" o combinaciones de N en p. N y p son números naturales, N>0, 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 :

1. No se establezcan restricciones.
2. Los del primer tomo estén juntos y los del segundo tomo también.
3. 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. 7×6+21×12=294
4. 153
5. 12
6. 147
7. 24
8. 49×7
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.

1. V(7,4)
2. 30
3. 5+20+60
4. 6+30+120
5. 9V(9,4)
6. 20
7. V(5,3),V(5,3)-12
8. V(4,2)
9. V(5,2)
10. V(25,4)
11. V(6,2)
12. 60,12
13. Siendo distintas dos a dos las naranjas, se tiene V(8,5)
14. V(30,4)
15. P(11);P(9)
16. P(6)-2P(5)
17. P(5);5P(4)
18. P(4);12,12
19. P(8)
20. 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,20)
7. C(17,12) – C(15,10)
8. 3; C(10,3) -4
9. C(5,3)
10. C(10,8)
11. C(10,10) + C(10,9) + C(10,8)
12. C(N,2) – N
13. C(5,3)
14. P(9), 2P(4) x P(5), P(4) x P(5)
15. C(20,3) x C(20,2) x C(20,1)
16. De las consideraciones hechas se aprecia que la escalera debe tener 5 escalones. Además como 4.5 dividido por 0.9 es igual a 9 tendremos 10 lugares donde se puede hacer un escalón. Hay que escoger 5 lugares entre 10 posibles, esto es: C(10,5)
17. C(6,3)
18. Cr(4,3)
19. C(4,3)
20. C(n,2)
21. C(6,2) +6
22. C(7,2) x C(9,2)
23. C(5,3); C(5,2) ; 2xC(5,3)
24. Cr(10,8) ; C(10,8)
25. Cr(8,3) + Cr(8,4)

Autor:

Rolando Reytor Rodríguez