Download al c

ANÁLISIS COMBINATORIO
Métodos combinatorios
Técnicas básicas
Sea S un conjunto finito no vacío. Se designar por | S | al cardinal de S, es decir, el
número de elementos de S. En particular | CV | = 0 (CV es el conjunto vacío).
Principio de Adición
Sean A1, A2, ... , An conjuntos finitos tales que Ai INT Aj = CV (INT es la intersección)
para cada i # j, donde i, j pertenecen a {1, 2, ... , n}, entonces:
| A1 U A2 U ... U An | = | A1 | + | A2 | + ... + | An |
En el lanzamiento de dos dados
¿De cuántas formas se pueden obtener un siete o un ocho?
•
•
•
Obtener un siete = A = { (1, 6) , (2, 5) , (3, 4) , (4, 3) , (5, 2) , (6, 1) }
Obtener un ocho = B = { (2, 6) , (3, 5) , (4, 4) , (5, 3) , (6, 2) }
| A U B | = | A | + | B | = 6 + 5 = 11
El experimento de lanzar una moneda al aire tres veces
¿De cuántas formas se puede obtener una, dos o tres caras?
•
•
•
•
Una cara = A = { (C, +, +) , (+, C, +) , (+, +, C) }
Dos caras = B = { (+, C, C) , (C, +, C) , (C, C, +) }
Tres caras = C = { (C, C, C) }
|AUBUC|=|A|+|B|+|C|=3+3+1=7
Principio de Multiplicación
Sea A1, A2, ... , An una colección de conjuntos finitos no vacíos, entonces:
| A1 x A2 x ... x An | = | A1 | · | A2 | · ... · | An |
Formación de placas de matrícula
¿Cuántas placas de matrícula pueden formarse con cuatro letras (en un alfabeto de 26
letras) seguidas de tres números?
•
•
•
Cuatro letras = A = B = C = D = 26
Tres dígitos = E = F = G = 10
| A x B x C x D x E x F x G | = | A |·| B |·| C |·| D |·| E |·| F |·| G | =
26·26·26·26·10·10·10 = 456976000
Se dispone de una baraja de 40 cartas
Se extraen 4 cartas por dos procedimientos:
a) sin devolución de la carta extraída
b) con devolución en cada extracción.
•
•
•
1ª carta = A , 2ª carta = B , 3ª carta = C , 4ª carta = D
a) | A x B x C x D | = | A |·| B |·| C |·| D | = 40 · 39 · 38 · 37 = 2193360
b) | A x B x C x D | = | A |·| B |·| C |·| D | = 40 · 40 · 40 · 40 = 2560000
Formación de números
¿Cuántos números naturales distintos existen entre 5000 y 10000 y tienen todas sus
cifras diferentes?
•
•
1º dígito (5...9) = A , 2º dígito (0...9) = B , 3º dígito (0...9) = C , 4º dígito (0...9) = D
| A x B x C x D | = | A |·| B |·| C |·| D | = 5 · 9 · 8 · 7 = 2520
Principio de Distribución
Sean m, n y p números naturales. Si se distribuyen np + m objetos en n cajas
entonces alguna caja deberá contener al menos p + 1 objetos.
ELEMENTOS COMBINATORIOS
Permutaciones
Cualquier arreglo de un conjunto de n objetos en un orden dado se llama permutación
de los objetos (tomados todos al mismo tiempo). Se designa por:
P( n ) = n! = n · (n - 1) · (n - 2) · ... · 2 · 1
Formaciones con personas
¿De cuántas maneras puede organizarse un grupo de 7 personas:
a) en una fila de 7 asientos?
b) alrededor de una mesa redonda?
•
•
a) P( 7 ) = 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 = 5040
b) P( 7 - 1 ) = 6! = 6 · 5 · 4 · 3 · 2 · 1 = 720
Permutaciones con repetición
Con frecuencia deseamos encontrar el número de permutaciones de objetos, algunos
de los cuales son iguales. La fórmula general es (r es el número de elementos
repetidos):
PR( n ) = n! / n1! · n2! · ... · nr!
Permutaciones con letras
¿Cuántas permutaciones pueden formarse con las letras de la palabra "radar"?
•
•
Repeticiones: r = 2 , a = 2
PR( 5 ) = 5! / 2! · 2! = 5 · 4 · 3 · 2 · 1 / 2 · 1 · 2 · 1 = 120 / 4 = 30
Permutaciones con banderas
¿Cuántas señales de 6 banderas pueden formarse con 4 banderas rojas y 2 azules?
Repeticiones: rojas = 4 , azules = 2
PR( 6 ) = 6! / 4! · 2! = 6·5·4·3·2·1 / 4·3·2·1·2·1 = 720 / 48 = 15
Variaciones
Sea un conjunto finito con n elementos (n > 0) y r un número natural (r <= n). Una
variación de orden r es una lista ordenada de n elementos distintos tomados de r en r.
Su fórmula es:
V( n, r ) = n! / (n - r)!
Variaciones con bolas
Una urna contiene 8 bolas. Encontrar el número de muestras ordenadas de magnitud
3.
V( 8, 3 ) = 8! / (8 - 3)! = 8! / 5! = 8·7·6·5·4·3·2·1 / 5·4·3·2·1 = 40320 / 120 = 496
Variaciones con números
¿Cuántos números de 3 dígitos pueden formarse con las cifras 2, 3, 5, 6, 7 y 9?
V( 6, 3 ) = 6! / (6 - 3)! = 6! / 3! = 6·5·4·3·2·1 / 3·2·1 = 720 / 6 = 120
Variaciones con repetición
Sea un conjunto finito con n elementos (n > 0) y r un número natural (r <= n). Una
variación con repeticiones de orden r es una lista ordenada de n elementos tomados
de r en r. Su fórmula es:
VR( n, r ) = n^r
Los catorce en las quinielas
En el juego de las quinielas, ¿cuál es el número mínimo de columnas que han de
rellenarse para acertar con seguridad los catorce signos?
VR( 3, 14 ) = 3^14 = 4728969
Formaciones de palabras
En un alfabeto formado por las letras (a, b, c, d), ¿cuántas palabras distintas de diez
letras pueden formarse?
VR( 4, 10) = 4^10 = 1048576
Combinaciones
Sea un conjunto finito con n elementos (n > 0) y r un número natural (r <= n). Una
combinación de orden r es una lista de elementos distintos, donde el orden no se tiene
en cuenta. Se formula:
C( n, r ) = n! / r! . (n - r)!
El juego del póker
¿Cuántas manos de póker distintas (5 cartas) pueden formarse con una baraja de 52
cartas?
C( 52, 5 ) = 52! / 5!·47! = 52·51·50·49·48 / 5·4·3·2·1 = 311875200 / 120 = 2598960
Comité de personas
¿De cuántas maneras puede formarse un comité que consta de 3 hombres y 2
mujeres, a partir de 7 hombres y 5 mujeres?
•
•
•
A = Hombres = C( 7, 3 ) = 7! / 4! · 3! = 210 / 6 = 35
B = Mujeres = C( 5, 2 ) = 5! / 3! · 2! = 20 / 2 = 10
| A x B | = | A | ú | B | = 35 · 10 = 350
Combinaciones con repetición
Sea un conjunto finito con n elementos (n > 0) y r un número natural. Una combinación
con repetición de orden r es una lista ordenada de n elementos en donde los
elementos pueden ser iguales. Su fórmula es:
CR( n, r ) = C( n + r - 1, r )
Distribución de objetos
¿De cuántas formas se pueden distribuir 10 canicas azules en 5 bolsas distintas?
CR( 5, 10 ) = C( 5 + 10 - 1, 10 ) = C( 14, 10 ) = 87178291000 / 87091200 = 1001
Suma de dígitos
¿Cuántos números hay en el conjunto {1, 2, ..., 1000 } que tengan la propiedad de que
la suma de sus dígitos sea 5?
CR( 3, 5 ) = C( 3 + 5 - 1, 5 ) = C( 7, 5 ) = 5040 / 240 = 21
Resumen del empleo de elementos combinatorios
Se eligen r
objetos de un
Número de selecciones
Número de selecciones
conjunto de n
ordenadas
no ordenadas
=========================================================
No están permitidas
las repeticiones
V(n,r) = n!/(n-r)!
C(n,r) = n!/(n-r)!·r!
Están permitidas
las repeticiones
VR(n,r) = n^r
CR(n,r) = C(n+r-1,r)
Se considera la expresión (x + y)^n . Su desarrollo puede obtenerse mediante la
fórmula:
(x + y)^n = Sumatorio de r ( 0 ... n ) en C( n, r ) · x^n-r · y^r
Desarrollo de un binomio
Calcúlese el coeficiente de x^6 en el desarrollo de (x - 3)^11.
C( 11, 6 ) · x^6 · (-3)^5 = 462 · x^6 · (-243) = -112266x^6
Fórmula de Pascal
Si n y r son enteros tales que 1 <= r <= n - 1, entonces:
C( n, r ) = C( n - 1, r ) + C( n - 1, r - 1 )
La fórmula de Pascal da un método para el cálculo de los coeficientes binómicos, dado
el valor inicial C( n, 0 ) = C( n, n ) = 1, para todo n >= 0. Los coeficientes de sucesivas
potencias (x + y)^n se pueden distribuir en una figura que se conoce como triángulo de
Pascal, en el cual se tiene:
•
•
El primer y el último elemento de cada fila es 1.
Cualquier otro número del tri ngulo se puede obtener sumando los dos números
que aparecen encima de él.
Fórmula de Leibnitz
Se aplica a los coeficientes del tipo multinómicos:
(x1 + x2 + ... + xk)^n = n! / n1! · n2! · ... · nk!
Cálculo de un coeficiente
Calcúlese el coeficiente del término a^3b^2c^4 del desarrollo de (a + b + c + d)^9.
9! / 3!·2!·4!·0! = 9·8·7·6·5 / 3·2·1·2·1·1 = 15120 / 12 = 1260