Prof Piero Analisis Combinatorio
-
Upload
carlos-lujan -
Category
Documents
-
view
156 -
download
0
Transcript of Prof Piero Analisis Combinatorio
ANALISIS COMBINATORIO
FACTORIAL DE UN NUMERO (n!)El factorial de un número n, entero y positivo, se define como el producto
consecutivo desde la unidad hasta el numero n inclusive.
Es decir:
n! = 1 x 2 x 3 x 4 x …………. x (n-1) x n
n! = n x (n – 1) x …………… x 4 x 3 x 2 x 1
Ejemplos:
2! = 2 x 1 = 2
3! = 3 x 2 x 1 = 6
4! = 4 x 3 x 2 x 1 = 24
5! = 5 x 4 x 3 x 2 x 1 = 120
6! = 6 x 5 x 4 x 3 x 2 x 1 = 720
NOTA:
Por convención: 0! = 1! = 1
Como expresar un factorial en términos de otro factorial menor:
7!
9! = 9 x 8 x 7 x 5 x 4 x 3 x 2 x 1
8!
Es decir:
9! = 9 x 8!
9! = 9 x 8 x 7!
Generalizando:
El factorial de un número se puede descomponer en el producto de 2, 3, 4, 5 ó
más factores.
n! = n = (n – 1)! = n x (n – 1) x (n – 2)!
PRINCIPIOS DE CONTEOEn lo que respecta a técnicas de conteo, tenemos dos principios importantes:
El principio de Adición
El principio de Multiplicación
EL PRINCIPIO DE ADICIÓNSi un evento A ocurre de n maneras y otro evento B ocurre de m maneras,
entonces: el número de maneras en que puede ocurrir el evento A o al evento B
es de n + m maneras.
Un evento ocurre de una forma u otra, más no de ambas formas a la vez (no
suceden en forma simultánea).
Ejemplo Jorge desea viajar de Lima a Tacna, para lo cual tiene las siguientes
posibilidades:
VIA TERRESTRE : LIMA – AREQUIPA – TACNA
LIMA – CUZCO – TACNA n = 2
VIA AÉREA : LIMA – AREQUIPA – TACNA
LIMA – JULIACA – TACNA m = 3
LIMA – CUZCO – TACNA
El número de maneras en que Jorge puede viajar de Lima a Tacna es de:
n + m = 2 + 3 = 5 maneras
Se aplica el principio de adición porque Jorge no puede viajar en simultáneo por
vía terrestre y vía aérea, tiene que escoger una de las alternativas.
EL PRINCIPIO DE MULTIPLICACIÓNSi un evento A ocurre de n maneras diferentes seguido de otro evento B que
ocurre de n maneras distintas, entonces el número de maneras en que pueden
ocurrir A y B es: n x m.
Los eventos ocurren uno a continuación de otro originando un evento compuesto.
Ejemplo:
Luisa piensa en ir a una reunión para lo cual tiene m = 5 vestidos de colores:
blanco, azul, amarillo, rojo y celeste; y n = 4 faldas de color: negro, azul, rojo y
turquesa.
¿Dé cuántas maneras puede ir Luisa a dicha reunión?
Como, Luisa escogerá primero la blusa y luego la falda para vestirse, estamos en
el caso del principio de multiplicación, entonces el número de maneras en que
Luisa puede vestirse es:
n x m = 5x 4 = 20 maneras
TECNICAS DE CONTEO
PERMUTACIONES.- Son los diferentes ordenamientos que se dan con un grupo
de n elementos.
Hay tres tipos de permutaciones.
Permutación Lineal.- Los n elementos son ordenados en línea recta o uno a
continuación de otro.
La permutación de los n elementos esta dada por:
Pn = n!
Ejemplo:
Se desea colocar 5 libros en un estante ¿De cuántas maneras se pueden colocar
sabiendo que todos los libros son diferentes?
Solución:
Graficando, tenemos:
n = 5 libros
Como los n = 5 libros, son todos diferentes se podrán colocar de:
P5 = 5! = 5 x 4 x 3 x 2 x 1 = 120 maneras
L1 L2 L3 L4 L5
Permutación Circular.- Se llama permutación circular cuando los elementos se
ordenan formando una línea cerrada (por lo general en forma de circunferencia) o
cuando se ordenan alrededor de un objeto.
El número total de maneras en que se pueden ordenar n elementos en forma
circula esta dada por:
PCn = (n – 1)! (PC: Permutación Circular)
Ejemplo:
7 ejecutivos se sientan alrededor de una mesa circular para tener una reunión de
negocios ¿De cuántas maneras pueden sentarse alrededor de dicha mesa?
Solución:
Sean los ejecutivos que
Van al almuerzo:
E1, E2, E3, E4, E5, E6, E7
Los disponemos en el gráfico en forma
Arbitraria (ver gráfico circular)
Fijamos a uno de los ejecutivos: E1
Entonces el número de maneras en
que se pueden sentar los 7 ejecutivos
esta dada por:
PCn = (n-1)! ==> PC7 = (7 – 1)! = 6!
PC7 = 6 x 5 x 4 x 3 x 2 x 1
PC7 = 720 maneras
PERMUTACIÓN CON REPETICIÓNSe ordenan n elementos, en los cuales hay grupos que se repiten.
Tenemos:
K1 = elementos que se repiten del grupo 1.
K2 = elementos que se repiten del grupo 2.
K3 = elementos que se repiten del grupo 3.
E1
E4
E3
E2
E7
E6
E5
FIJO
.
.
.
Kr = elementos que se repiten del grupo r.
El numero de maneras en que pueden ser ordenados estos elementos esta dado
por:
¿
Donde: k1 + k2 + k3+ …… + kr = n
Ejemplo:
Se desea colocar en una vitrina 15 copas de las cuales 7 son de color blanco, 5
son de color azul y 3 de color amarillo. Son idénticas en tamaño y color. De
cuántas maneras pueden ser colocadas en dicha vitrina las 15 copas.
Solución:
Es un caso de permutación con repetición.
Tenemos:
n = 15 (número total de copas)
K1 = 7 (número de copas de color blanco)
K2 = 5 (número de copas de color azul)
K3 = 3 (número de copas de color amarillo)
El número de maneras en que pueden ser colocadas dichas copas en la vitrina
es:
¿
¿
¿
7 3
¿
¿
COMBINACIONESSon los diferentes agrupamientos que se obtienen con n elementos tomados de K
en K (sin importar el orden).
El número total de combinaciones que se obtienen al tomar grupos de K
elementos de un total de n elemento esta dada por:
C kn=(nk )= n !
k ! (n−k ) !
EjemploEn un salón de clase donde hay 10 alumnos y 8 alumnas se va a formar un
comité compuesto por 4 alumnos y 2 alumnas para realizar una actividad ¿De
cuántas maneras puede ser escogido dicho comité?
Solución:
Para elegir las 2 alumnas: C28=
8 !2!6 !=
(8 ) (7 )(6 !)(2 )(6 !)
=28
Para elegir los 4 alumnos:C410=
10 !4 !6 !=
(10 ) (9 ) (8 ) (7 )(6 !)(4 ) (3 ) (2 )(1)(6 !)
=1680
El número total de maneras esta dada por:
c28 xc4
10=(28 ) (1680 )=47040maneras
VARIACIONES
4
3
Es el número de ordenaciones que se pueden hacer al tomar K elementos de un
total de n elementos pero teniendo en cuenta los siguientes pasos:
1. Se toman K elementos de un total de n elementos sin importar el orden
(combinaciones).
2. Los K elementos escogidos son ordenados (permutación)
Estos nos permite afirmar lo siguiente:
V kn=Ck
n Pk ( por el principio demultiplicación)
V kn= n !k ! (n−k )!
k !
V kn= n!
(n−k ) !
Ejemplo:
Una señora tiene 6 retazos de tela de diferentes colores: azul, negro, rojo, blanco
azul y amarillo. Con dicho retazos debe hacer 1 bandera de 3 franjas horizontales.
De cuántas maneras podrá elaborar dicha bandera.
Solución:
Tenemos los siguientes pasos:
1. De los 6 retazos la señora recogerá 3 retazos. Es decir n = 6 y k = 3
(combinación)
2. Al elaborar la bandera, los k = 3 retazos escogidos serán dispuestos en un
determinado orden (permutación) para ser bordados.
El número total de maneras en que la señora puede elaborar dicha bandera es:
V 36=
6 !(6−3 ) !
=6 !3 !=
(6 ) (5 ) (4 )(3 !)3! =120maneras
EJERCICIOS
1.- Eva María tiene 2 pares de zapatos diferentes, 3 pantalones diferentes y 4
blusas también diferentes.
¿Cuántos días como mínimo deberá repetir su forma de vestir durante el mes de
Noviembre?
Solución:
Por el principio de multiplicación las maneras diferentes en que podrá vestir
durante el mes de noviembre será:
(2) (3) (4) = 24 maneras diferentes
Como el mes de Noviembre tiene 30 días, el mínimo número de días en que
repetirá su vestimenta será:
30 – 24 = 6 días
2.- Se tienen 6 parejas de esposos los cuales asistieron a una reunión social ¿De
cuántas maneras puede formarse una pareja de baile, tal que no sean esposos?
Solución:
Tenemos las siguientes parejas de esposos:
H1 M1
H2 M2
H3 M3
H4 M4
H5 M5
H6 M6
Como H1 no puede bailar con M1, entonces puede bailar con M2, M3, M4, M5, M6 (5
posibilidades)
De igual forma ocurre con H2, H3, H4, H5, H6que no pueden bailar con M2, M3, M4,
M5, M6.
Entonces el número de parejas que pueden formarse para bailar sin que sean
esposos es:
Número de parejas = 6 x 5 = 30 parejas
3.- El grupo Agua Bella esta formado por 3 cantantes, 5 músicos y 2 bailarinas.
Para salir al escenario deben hacerlo en fila, debiendo estar las bailarinas a los
extremos y los cantantes no deben estar al lado de las bailarinas ¿De cuántas
formas diferentes pueden salir al escenario?
Solución:
Veamos el siguiente gráfico:
6 posibles sitios para los contantes
B1 C1 C2 C3 B2
B1 C1 C2 C3 B2
B1 C1 C2 C3 B2
B1 C1 C2 C3 B2
El número de formas en que pueden salir al escenario será:
Distribución de músicos
Número de formas = V 36 P5P2
Distribución de bailarinas
Distribución de cantantes
Número de formas =6 !3 !5 !2 !
Número de formas =(6 ) (5 ) (4 )(3! )
3 ! 5! 2!5 !=120
2! = 20
Número de formas = (6) (5) (4) (120) (2)
Número de formas = 28800
4.- Determinar de cuántas maneras pueden sentarse 6 varones y 6 mujeres
alrededor de una mesa redonda de tal modo que al lado de un varón este una
mujer.
Solución:
Tenemos 6 hombres: H1, H2, H3, H4, H5, H6
12 personas
Tenemos 6 mujeres:M1, M2, M3, M4, M5, M6
Si fijamos a 1 hombre (en este caso H1)
(por ser permutación circular),
Tenemos:
P5P6 = 5! 6!
Como se pueden fijar a 6 hombres tenemos:
6P5P6 = (6) (5!) (6!)
Lo mismo podemos hacer con las mujeres, entonces el total de maneras en que
podemos ordenar a 6 varones y 6 mujeres alrededor de una mesa redonda de tal
modo que al lado de un varón este una mujer es:
Nº de maneras = 12 (5!) (6!)
Nº de maneras = 12 (120) (720) = 1036800
5.- Se tiene 5 bolas diferentes y 5 cajas de igual apariencia ¿De cuántas formas
pueden ubicarse las bolas en las cajas de tal modo que resulte una caja vacía?
Solución:
Tenemos 5 bolas diferentes: B1, B2, B3, B4, B5.
Estas bolas se distribuyeron en 5 cajas de igual apariencia; de la sigueitne
manera (siempre hay una vacía):
H1M
6
M5
H6
H5
M4
H4M3
H3
M2
H2
M1
FIJO
CAJA 1 CAJA 2 CAJA 3 CAJA 4 CAJA 5
--- 2 1 1 1
2 --- 1 1 1
5 formas en que 1 1 1 2 ---
se distribuyen 1 1 --- 1 2
1 1 2 --- 1
El número total de manera estará dada por:
5(52)P4=5 5 !2 !3!
4 !
¿5 (5 ) (4 ) 3 !2 !3 !
4 !
¿5 (5 ) ( 4 )2
(4 ) (3 ) (2 )(1)
= 5 (20) (12)
= 1200
Se pueden ubicar de 1200 maneras las 5 bolas diferentes garantizando que 1 caja
quede vacía.
6.- 5 Libros de Matemática (M1, M2, M3, M4, M5), 2 de Estadística deben ser
colocados en un estante, de cuantas maneras pueden colocarse si:
a) Los libros de cada materia deben estar juntos.
Graficando:
Bloque Bloque Matemática Estadística
P4
P4
P4
P4
P4
M1 M2 M3 M4 E1 E2M5
E1 E2
E1 E2
E1 E2
E1 E2
E2E1
E1 E2
El número de maneras en que pueden colocarse es:
P2 P5 P2 = 2! 5! 2! = (2) (120) (2) = 480 maneras
Permutación de libros de estadística
Permutación de libros de matemática
Permutación de bloques
b) Si solo los libros de Estadística deben estar juntos.
Graficando:
1 2 3 4 5 6 7
El número de maneras en que deben colocarse los libros en el estante de
manera que siempre estén juntos los de Estadística es:
6 P2 P5 = 6(2!) (5!) = 6(2) (120) = 1440 maneras
6 CASOS
7.- ¿De cuántas maneras se puede escoger en el tablero de ajedrez una casilla
blanca y una negra que no estén en la misma horizontal ni vertical?
Solución:
Dibujemos el tablero de ajedrez.
Fijamos
1 2 3 4
Hay 32 casilleros negros, entonces el número de maneras en que podemos
escoger una casilla blanca y una negra que no estén en la misma horizontal ni
vertical es:
Nº de maneras = 32 x 24 = 768 maneras
1 2 3
4 5 6 7
8 9 10
11 12 13 14
15 16 17
18 19 20 21
22 23 24
(Anulamos 1 filay 1 columna)
EJERCICIOS PROPUESTOS1.- Se tienen 6 parejas de casados los cuales asistieron a una reunión social. ¿De
cuántas maneras puede formarse una pareja de baile, tal que no sean esposos?
a) 45 b) 30 c) 55 d) 58 e) 60
2.- Para ir del local de Wilson al de San Felipe se tiene 4 líneas de combi, 5 líneas
de coaster y, 5 líneas de microbús ¿De cuántas formas distintas se puede realizar
dicho recorrido en alguna de estas líneas?
a) 13 b) 15 c) 16 d) 17 e) 18
3.- Si Maribel tiene 5 faldas que combinan con 3 blusas y también 9 pantalones
que hacen juego con 6 polos diferentes ¿De cuántas maneras distintas podrá
vestirse?
a) 45 b) 30 c) 55 d) 58 e) 60
4.- Se tienen 3 obras la primera obra consta de 3 tomos, la segunda de 4 tomos y
la tercera de 1 tomo. Se quiere colocarlas en una misma fila de un estante, de tal
manera que los libros de la misma obra se coloquen junto.
a) 144 b) 288 c) 432 d) 720 e) 864
5.- Determinar de cuantas formas se puede permutar las letras de la palabra
MARACANA, de modo que las cuatro A no vayan juntas.
a) 1 020 b) 1 280 c) 1 560 d) 1 640 e) 1 810
6.- Alrededor de una mesa circular se van a sentar 6 personas, si dos de ellas
deben sentarse juntas y otras dos no pueden sentarse juntas ¿de cuántas
maneras pueden sentarse dichas personas?
a) 24 b) 112 c) 120 d) 180 e) 216
7.- De un grupo de 12 estudiantes, se quiere seleccionar a 4 de ellos. ¿De
cuántas formas se puede seleccionarlos si dos de ellos en particular no pueden
escogerse juntos?
a) 380 b) 400 c) 420 d) 450 e) 460
8.- De un grupo de 5 hombres y 4 mujeres; determinar cuántos grupos se pueden
formar, si en estos grupos hay al menos 2 hombres y 2 mujeres.
a) 138 b) 143 c) 286 d) 420 e) 826
9.- Un estudiante debe inscribirse en 2 cursos electivos de un conjunto de 10
posibles. Si dos de dichos cursos se imparten en la misma hora y los demás
tienen horarios que no se cruzan, determinar de cuántas formas pueden realizar
su elección.
a) 10 b) 44 c) 18 d) 20 e) 24
10.- En una empresa se quieren contratar 3 personas para cubrir las vacantes A;
B y C y se observó que 8 personas se presentan para cualquiera de las 3
vacantes, 5 personas solo se presentan para la vacante A y 3 personas solo para
la vacante 8 ¿De cuántas formas diferentes se pueden cubrir las vacantes?
a) 120 b) 280 c) 400 d) 604 e) 904
11.- De 6 varones y 5 chicas se desea seleccionar un comité de 4 personas ¿De
cuántas formas podrá hacerse dicha selección, si deben integrarlo al menos 2
chicas?
a) 80 b) 120 c) 180 d) 210 e) 215
12.- Determinar de cuántas maneras diferentes podrán viajar 7 personas en un
automóvil de5 asientos y una moto, sabiendo que todos saben manejar moto
pero solo 3 de ellos saben manejar automóvil.
a) 720 b) 840 c) 1 400 d) 2 180 e) 3 000
13.- Determinar de cuántas formas se pueden repartir 5 manzanas y 5 naranjas
entre 3 niños, de modo que cada uno reciba por lo menos en naranja y una
manzana.
a) 32 b) 33 c) 34 d) 35 e) 36
14.- Paola va a una discotienda y gana S 18 en acomodar Cds de ****** (a S 6
cada uno) y de technocumbia (a S 3 cada uno). Determinar de cuantas maneras
diferentes puede haber elegido su compra. Si la discotienda tiene 2 Cds de cada
genero y son de diferentes autores.
a) 20 b) 100 c) 125 d) 150 e) 200
15.- En una tienda de mascotas hay 6 perros y 4 gatos ¿Cuántas elecciones
diferentes se obtendrá de tal forma que entre las escogidas haya por lo menos
una de cada especie?
a) 430 b) 465 c) 470 d) 482 e) 496
16.- De 8 hombres y 5 mujeres ¿De cuántas formas distintas se pueden
seleccionar un grupo mixto de 7 personas integrado con por lo menos 3 hombres?
a) 78 b) 94 c) 1024 d) 1680 e) 169
17.- Un producto se arma en tres etapas. En la primera etapa hay 5 líneas de
armado. En la segunda etapa hay 4 líneas de armado y en la tercera etapa hay 6
líneas de armado ¿De cuántas maneras puede moverse el producto en el proceso
de armado?
a) 120 b) 180 c) 240 d) 300 e) 250
18.- Se disponen de 4 fichas, roja, blanca, verde y amarilla ¿De cuántas maneras
pueden ser colocados en el siguiente tablero, de manera que se tenga una sola
ficha por fila y una sola ficha por cada columna?
19.- Una señora tiene 11 amigos de confianza, de cuántas maneras puede invitar
5 de ellos a comer, si dos de ellos no se llevan bien y no asisten juntos.
a) 462 b) 378 c) 400 d) 210 e) 360
20.- Un club tiene 15 miembros: 10 hombres y 5 mujeres, ¿Cuántos comités de 8
miembros se pueden formar si cada uno de ellos deben contener por lo menos 3
mujeres y en cada uno de ellos debe estar el presidente y la secretaria del club?
a) 144b) 288c) 576d) 1152e) 1240
a) 1512 b) 756 c) 336 d) 1128 e) 1092
21.- En un estante hay 15 libros: 9 de aritmética y 6 de algebra, se desea tomar 7
libros de tal manera que 4 sean de aritmética y 3 de algebra ¿De cuántas
maneras se pueden escoger los 7 libros?
a) 2520 b) 2720 c) 3650 d) 1560 e) 1260
22.- Siete personas se sientan al azar en un círculo ¿Cuál es la probabilidad que
3 personas queden contiguas?
a) 30 b) 32 c) 36 d) 42 e) 48
23.- Alrededor de una mesa circular de 7 asientos se ubican 2 niñas y 4 niños.
¿De cuántas formas podrán hacerlo, si el asiento vacio debe quedar entre las
niñas?
a) 8 b) 24 c) 48 d) 12 e) 96
24.- Se tiene 4 libros de aritmética y 3 de álgebra ¿De cuántas formas se podrán
ubicar en une estante donde solo entran 5 libros y deben estar alternados?
a) 144 b) 288 c) 210 d) 216 e) 343
25.- Se quiere formar con los dígitos 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 una placa de 5
dígitos, de cuántas maneras puede hacerse la placa, si los números no deben
repetirse.
a) 18760 b) 51720 c) 39240 d) 13440 e) 28680