PDF de programación - Métodos combinatorios TECNICAS BASICAS

Métodos combinatorios

TECNICAS BASICAS

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) }
| A U B U C | = | 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)

TEOREMA DEL BINOMIO

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

Ultima actualización: 3 de septiembre de 1997