Download Combinatoria

COMBINATORIA
Introducción a la Combinatoria
Recuento
A menudo se presenta la necesidad de calcular el número de maneras distintas en que un suceso se
presenta o puede ser realizado. Otras veces es importante determinar la probabilidad de ocurrencia de
un evento específico. En ambos casos se apela al sentido común, o se establecen métodos que
permitan sistematizar tales cálculos. Con frecuencia el sentido común ayuda a entender por qué se
eligió un procedimiento dado, mientras que la formalización del cálculo las vías para encontrar las
soluciones apropiadas.
Iniciaremos nuestro estudio de teoría combinatoria enunciando los principios aditivo y multiplicativo
de conteo.
Principio aditivo de conteo: Sean A y B dos sucesos que no pueden ocurrir simultáneamente. Si A
ocurre de a maneras distintas y B ocurre de b maneras distintas, el número de maneras en el cual
puede ocurrir A o B es a + b
Principio multiplicativo de conteo: Si un suceso A puede ocurrir en a maneras e,
independientemente, un segundo suceso B puede ocurrir en b maneras, entonces el número de
.
maneras en A y B, pueden ocurrir es a b.
A este principio también se le denomina principio fundamental de conteo.
Ejemplo
Se tienen 6 banderas de señalización, dos rojas, dos verdes y dos azules. ¿Cuántas señales distintas
pueden hacerse con una o dos banderas a la vez?
* Solución:
Si denotamos las banderas rojas, verdes y azules por R, V y A respectivamente, vemos que con una
bandera a la vez se pueden hacer 3 señales distintas: R , V , A
Con dos banderas a la vez se puede hacer las siguientes señales (sacando, por ejemplo, una primera y
después la otra) es decir
RR, RV, RA, VR, VV, VA, AR, AV, AA
Entonces, si se utilizan dos banderas, se pueden hacer 9 señales distintas. Luego, con una o dos
banderas se podrán realizar 3+9= 12 señales diferentes. Observa que, como se establece en la
definición, se trata de dos sucesos A y B descritos como:
A: Se hacen señales con una sola bandera ; B: Se hacen señales con dos banderas.
Y que ambos no pueden ocurrir simultáneamente, ya que si se decide hacer señales con una bandera
se descarta la segunda alternativa y viceversa
Ejemplo
¿Cuántas cartillas de futbol distintas se pueden hacer?
Tenemos en cuenta que en cada partido puede haber 3 resultados: Local, Empate o Visita que hay 14
partidos y que los resultados de cada uno es independiente de los demás, por tanto tendremos
3 .3 ………3 = 314
Ejemplo
¿Cuántos resultados distintos puede haber en un sorteo de la lotería sin tener en cuenta el comodín?
En una bolsa tenemos 49 bolas numeradas del 1 al 49. El primer número lo escojo entre 49 posibles
números, el segundo número lo escojo entre 48 (pues las bolas, una vez extraídas no se devuelven a
la bolsa), el tercero entre 47, y así sucesivamente, por lo tanto, en principio habría
49*48*47*46*45*44= 10.068.347.520.
Esta sería la solución si el orden de extracción de las bolas, se tuviese en cuenta, pero no es así. El
número que hemos sacado en la primera extracción podría haber salido en la segunda, tercera, cuarta,
quinta o sexta extracción (en total 6), por lo tanto habrá que dividir por 6. El número que hemos
sacado en la segunda extracción, podría haber salido en la tercera, cuarta, quinta o sexta extracción,
(en total 5), habrá que dividir entre 5 y así seguiríamos razonando hasta la última extracción.
Por ello habrá que dividir por 6*5*4*3*2*1 el número anterior para obtener la solución.
10.068.347.520/720=13.983.816
Ejercicios Propuestos
1. Lanzamos DOS dados indistinguibles ¿Cuántos resultados diferentes se pueden observar? ¿Y si
los dados son distinguibles?
2. Cuatro personas quieren jugar partidos de tenis individuales. Disponen de dos pistas. ¿De cuantas
maneras se pueden distribuir si no tenemos en cuenta la elección de la pista? ¿Y de cuantas si se
tiene en cuenta la elección de la pista donde juega cada pareja?
Conceptos de combinatoria
En todo problema combinatorio hay varios conceptos claves que debemos distinguir:
1. Población: Es el conjunto de elementos que estamos estudiando.
2. Muestra: Es un subconjunto de la población.
Los diferentes tipos de muestra vienen determinados por dos aspectos:
Orden: Es decir, si es importante que los elementos de la muestra aparezcan ordenados o no.
Repetición: La posibilidad de repetición o no de los elementos.
Teniendo en cuenta que
n! = n.(n-1).(n-2)…….3.2.1
PERMUTACIONES
Permutaciones SIN repetición:
Las permutaciones sin repetición de n elementos se definen como las distintas formas de ordenar
todos esos elementos distintos, por lo que la única diferencia entre ellas es el orden de colocación de
sus elementos, es decir :
Sí entran todos los elementos.
Sí importa el orden.
No se repiten los elementos
El número de estas permutaciones está dado por:
Ejemplos
1. Calcular las permutaciones de 6 elementos.
P6 = 6! = 6 · 5 · 4 · 3 · 2 · 1 = 720
2. ¿Cuántos números de 5 cifras diferentes se puede formar con los dígitos: 1, 2, 3, 4, 5?
m=5 n=5
Sí entran todos los elementos.
Sí importa el orden.
No se repiten los elementos.
El enunciado nos pide que las cifras sean diferentes.
3. ¿De cuántas formas distintas pueden sentarse ocho personas en una fila de butacas?
Sí entran todos los elementos. Tienen que sentarse las 8 personas.
Sí importa el orden.
No se repiten los elementos. Una persona no se puede repetir.
Permutaciones CON repetición
Permutaciones con repetición de n elementos donde el primer elemento se repite a veces , el segundo
b veces , el tercero c veces, ...; n = a + b + c + ...; son los distintos grupos que pueden formarse con
esos n elementos de forma que :
Sí entran todos los elementos.
Sí importa el orden.
Sí se repiten los elementos.
El número de estas permutaciones está dado por:
Ejemplos
1. Calcular las permutaciones con repetición de:
.
2. Con las cifras 2, 2, 2, 3, 3, 3, 3, 4, 4; ¿cuántos números de nueve cifras se pueden formar?
m=9 a=3 b=4 c=2 a+b+c=9
Sí entran todos los elementos.
Sí importa el orden.
Sí se repiten los elementos.
3. En el palo de señales de un barco se pueden izar tres banderas rojas, dos azules y cuatro verdes.
¿Cuántas señales distintas pueden indicarse con la colocación de las nueve banderas?
Sí entran todos los elementos.
Sí importa el orden.
Sí se repiten los elementos.
EJERCICIOS PROPUESTOS
a) ¿Cuántos números de 5 cifras distintas se pueden formar con los dígitos 1,2,3,4,5?
b) ¿Cuantos números de 4 cifras se pueden formar con los dígitos 0,1,2,3?
c) ¿Cuántos números de 6 cifras se pueden formar si en ellos siempre hay 1 uno, 2 doses y 3
treses?
Variaciones
Variaciones SIN repetición
Las variaciones sin repetición de n elementos tomados de p en p se definen como las distintas
agrupaciones formadas con p elementos distintos, eligiéndolos de entre los n elementos de que
disponemos, considerando una variación distinta a otra tanto si difieren en algún elemento como si
están situados en distinto orden.
No entran todos los elementos.
Sí importa el orden.
No se repiten los elementos
El número de variaciones que se pueden construir se puede calcular mediante la fórmula
Ejemplos
1. Calcular las variaciones de 6 elementos tomados de tres en tres.
2. ¿Cuántos números de tres cifras diferentes se puede formar con los dígitos: 1, 2, 3, 4, 5 ?
m = 5n = 3 m ≥ n
No entran todos los elementos. De 5 dígitos entran sólo 3.
Sí importa el orden. Son números distintos el 123, 231, 321.
No se repiten los elementos. El enunciado nos pide que las cifras sean diferentes.
3. ¿Cuántos números de tres cifras diferentes se puede formar con los dígitos: 0, 1, 2, 3, 4, 5 ?
m = 6n = 3 m ≥ n
Tenemos que separar el número en dos bloques:
El primer bloque, de un número, lo puede ocupar sólo uno de 5 dígitos porque un número no
comienza por cero (excepto los de las matriculas, los de la lotería y otros casos particulares),
m=5 n=1
El segundo bloque, de dos números, lo puede ocupar cualquier dígito menos el inicial.
m=5 n=2
4. A un concurso literario se han presentado 10 candidatos con sus novelas. El cuadro de honor lo
forman el ganador, el finalista y un accésit .¿Cuántos cuadros de honor se pueden formar?
m = 10 n = 3
No entran todos los elementos. De 10 candidatos entran sólo 3.
Sí importa el orden. No es lo mismo quedar ganador que finalista.
No se repiten los elementos. Suponemos que cada candidato presenta una sola obra.
Variaciones CON repetición
Las variaciones con repetición de n elementos tomados de p en p se definen como las distintas
agrupaciones formadas con p elementos que pueden repetirse, eligiéndolos de entre los n elementos
de que disponemos, considerando una variación distinta a otra tanto si difieren en algún elemento
como si están situados en distinto orden
No entran todos los elementos si m > n. Sí pueden entrar todos los elementos si m ≤ n
Sí importa el orden.
Sí se repiten los elementos.
.
El número de variaciones que se pueden construir se puede calcular mediante la fórmula:
Ejemplos
1. ¿Cuántos números de tres cifras se puede formar con los dígitos: 1, 2, 3, 4, 5 ?
m=5 n=3
No entran todos los elementos. De 5 dígitos entran sólo 3.
Sí importa el orden. Son números distintos el 123, 231, 321.
Sí se repiten los elementos.
2. ¿Cuántos números de tres cifras se puede formar con los dígitos: 0, 1, 2, 3, 4, 5?
m=6 n=3
Tenemos que separar el número en dos bloques:
El primer bloque, de un número, lo puede ocupar sólo uno de 5 dígitos porque un número no
comienza por cero (excepto los de las matriculas, los de la lotería y otros casos particulares).
m=5 n=1
El segundo bloque, de dos números, lo puede ocupar cualquier dígito.
m=6 n=2
3. ¿Cuántas cartillas de una columna han de rellenarse para asegurarse el acierto de los 15 resultados?
m = 3 n = 15 m < n
Sí entran todos los elementos. En este caso el número de orden es mayor que el número de
elementos.
Sí importa el orden.
Sí se repiten los elementos.
4. ¿Cuántos números de tres cifras distintas se pueden formar con los dígitos 1,2,3,….,9?
3
V9
=
9!
(9 − 3)!
= 9.8.7 = 504
5. Con las letras del alfabeto español (25 letras) ¿Cuántas palabras (con o sin sentido) de 6 letras
distintas pueden formarse?- ¿Cuántas empiezan por vocal?
6
V 25 , 5V 524
Combinaciones
Combinaciones SIN repetición
Las combinaciones sin repetición de n elementos tomados de p en p se definen como las distintas
agrupaciones formadas con p elementos distintos, eligiéndolos de entre los n elementos de que
disponemos, considerando una variación distinta a otra sólo si difieren en algún elemento, (No
influye el orden de colocación de sus elementos).
No entran todos los elementos.
No importa el orden.
No se repiten los elementos.
El número de combinaciones que se pueden construir se puede calcular mediante la fórmula:
Ejemplos
1. Calcular el número de combinaciones de 10 elementos tomados de 4 en 4.
2. En una clase de 35 alumnos se quiere elegir un comité formado por tres alumnos. ¿Cuántos
comités diferentes se pueden formar?
No entran todos los elementos.
No importa el orden: Juan, Ana.
No se repiten los elementos.
Combinaciones CON repetición
Las combinaciones con repetición de n elementos tomados de p en p se definen como las distintas
agrupaciones formadas con p elementos que pueden repetirse, eligiéndolos de entre los n elementos
de que disponemos, considerando una variación distinta a otra sólo si difieren en algún elemento, (No
influye el orden de colocación de sus elementos).
No entran todos los elementos.
No importa el orden.
Sí se repiten los elementos.
El número de combinaciones que se pueden construir se puede calcular mediante la fórmula:
Ejemplo
1. En una bodega hay cinco tipos diferentes de botellas. ¿De cuántas formas se pueden elegir cuatro
botellas?
No entran todos los elementos. Sólo elije 4..
No importa el orden. Da igual que elija 2 botellas de anís y 2 de ron, que 2 de ron y 2 de anís.
Sí se repiten los elementos. Puede elegir más de una botella del mismo tipo.
2. Como respuesta a un anuncio de trabajo se presentan 12 personas para cubrir tres plazas de
administrativo ¿Cuantas grupos diferentes de personas se pueden seleccionar?
Debemos elegir grupos de 3 de entre los 12, no influye el orden
3
=
C 12
12!
12.11.10
=
= 220
(12 - 3)!3!
3.2
3. ¿Cuántos triángulos distintos se pueden formar con 8 puntos en el plano si tres de ellos nunca
están alineados?
Para que dos triángulos sean distintos se tienen que diferenciar al menos en un vértice y el orden en
que tomamos los vértices no influye
C 38 =
8!
8.7.6
= 56
=
(8 − 3)!.3!
3.2
¿CÓMO LAS DIFERENCIAMOS?
PERMUTACION
O
VARIACION
¿Tomamos
todos los
elementos?
SI
SI
¿Importa el orden
en que colocamos
los elementos?
NO
COMBINACION
¿Puede haber
elementos
repetidos?
PERMUTACION
COMBINACION
CON
REPETICION
NO
VARIACION
COMBINACION
ORDINARIA
¿Puede haber
elementos
repetidos?
NO
PERMUTACION
ORDINARIA
¿Puede haber
elementos
repetidos?
NO
VARIACION
ORDINARIA
SI
SI
VARIACION
CON
REPETICION
SI
PERMUTACION
CON
REPETICION
EJERCICIOS PROPUESTOS I
1. ¿De cuántas maneras diferentes pueden sentarse 10 personas alrededor de una mesa?
2. ¿Cuántas palabras (con sentido o no) pueden formarse que tengan exactamente las mismas letras
de la palabra CASTO y que empiecen y terminen por vocal?
3. Con exactamente, las letras de la palabra FRANCISCO ¿cuántas palabras pueden formarse con la
condición de que empiecen por N y terminen por una consonante?
4. ¿Cuántas palabras, con significado o no, pueden formarse con todas las letras de la palabra
"problema"?
5. Con las letras de la palabra ALELUYA se forman todas las palabras posibles. ¿Cuántas hay?,
¿Cuántas empiezan por consonante?
6. ¿De cuantas maneras se pueden colocar en una fila 4 chicos y 4 chicas de manera que alternen
personas de sexo diferente? ¿Y si todas las chicas tienen que estar juntas?
7. ¿Cuántas palabras de 12 letras se pueden formar con la palabra AYUNTAMIENTO, de tal manera
que siempre comiencen y terminen por vocal? Solución: 13608000
8. En un departamento de una empresa trabajan cuatro hombres y tres mujeres. Desean que les hagan
una fotografía de forma que estén todos los hombres juntos y también las mujeres. ¿De cuántas
formas distintas pueden colocarse? Solución: 288
9. ¿En cuántas formas puede un director de televisión programar seis diferentes comerciales de un
patrocinador durante los seis periodos de tiempo asignado a mensajes comerciales durante un
programa? Solución: 720
10. ¿De cuantas maneras pueden formarse cinco personas para tomar el autobús? ¿De cuantas
maneras si dos de las personas se niegan a hacerlo una detrás de otra? Solución: 120, 72
11. ¿Cuántas permutaciones diferentes hay de las letras de la palabra "statistics"? ¿Cuántas de ellas
comienzan y terminan con la letras?. Solución: 50400, 3360
EJERCICIOS PROPUESTOS II
1.
¿De cuántas formas se puede elegir un comité de 3 personas de un grupo de 20? ¿Y de cuántas si
uno debe ser el presidente, otro el vicepresidente y otro el secretario?
2.
¿Cuántos números distintos de 5 cifras se pueden formar con las cifras 1,2,3,5,7,8,9
3.
Se tienen 10 banderas distintas. ¿Cuantas señales distintas se pueden hacer , usando como
máximo cinco banderas?
4.
En una reunión hay tres chicas y siete chicos ¿Cuántos grupos de 5 personas pueden formarse?
¿Cuántos si en cada grupo debe haber 2 y solo dos chicas?.
5.
¿Cuántos números de cuatro cifras pueden formarse con dos cifras pares (no entra el cero) y dos
impares?.
6.
Cuántas señales distintas pueden hacerse con cinco banderas distintas agrupándolas de tres en
tres y sin que se repita ninguna? ¿Y agrupándolas de todas las formas posibles (es decir, de una
en una, de dos en dos, etc)?
7.
En un club de fútbol hay 23 jugadores, de los que 3 son porteros. ¿Cuántas alineaciones
diferentes puede hacer el entrenador si cualquiera de los jugadores de campo puede jugar como
defensa, medio o delantero?
8.
¿Cuántos equipos de baloncesto de 5 jugadores cada uno pueden hacerse en un club de 11
jugadores, con la condición de que los jugadores A, B y C no pueden estar simultáneamente en el
mismo equipo?
9.
Con seis pesas de 1, 2, 5, 10, 20, y 50 kg ¿Cuántas pesadas diferentes pueden obtenerse
tomándolas de tres en tres?
10. Se tienen 14 letras diferentes. ¿De cuántas en cuántas habrá que tomarlas para que el número de
sus combinaciones sea el mayor posible?
11. A una persona se le sirven en cada comida cuatro platos, de los nueve que son de su agrado.
¿Cuántas comidas diferentes puede hacer esa persona?
12. En una fila de cine de 10 butacas, ¿cuántas posiciones diferentes pueden ocupar tres individuos?
EJERCICIOS PROPUESTOS III
1.
Un estudiante tiene que contestar 8 de las 10 preguntas de un examen. ¿De cuántas formas
diferentes puede contestar? ¿Y si las tres primeras son obligatorias? ¿Y si de las cinco primeras
ha de contestar a cuatro?
Solución: 45, 21, 25
2.
Para jugar al dominó, siete fichas hacen un juego. Sabiendo que tiene 28 fichas, ¿cuántos juegos
diferentes se pueden hacer?
Solución: 1184040
3.
En las variaciones sin repetición que podemos formar con las nueve cifras significativas tomadas
de tres en tres, ¿cuántas veces está la cifra 7?
Solución: 168
4.
Con una baraja de 52 cartas, ¿cuántos grupos diferentes de cinco cartas se pueden hacer?
Solución: 2598960
5.
De un grupo de 12 alumnos deben formarse tres equipos de cuatro participantes para que asistan
a tres pruebas diferentes. ¿Cuántas clasificaciones distintas pueden realizarse?
Solución: 34650
6.
¿Cuántas palabras de 10 letras diferentes pueden formarse con cinco vocales y cinco consonantes
de las 21 existentes, de manera que no haya dos vocales juntas ni dos consonantes juntas?
Solución: 586051200
7.
¿Cuántos resultados distintos se obtienen al lanzar tres dados iguales a la vez? ¿Y si los dados
son distintos?
Solución: 56, 216
8.
Con los dígitos pares, ¿cuántos números inferiores a 1 000 se pueden escribir?
Solución: 84
9.
Se disponen ocho monedas en una fila. La mitad de ellas son de $ 500 y la otra mitad de $100
¿De cuántas formas distintas se pueden ordenar?
Solución: 70
10. Una prueba de opción múltiple consta de 15 preguntas y cada una tiene tres alternativas. ¿En
cuántas formas diferentes puede marcar un estudiante su respuesta a estas preguntas?
Solución: 14348907