TEMA 3: TÉCNICAS DE RECUENTO.
COMBINATORIA
1. INTRODUCCIÓN
2.1 INTRODUCCIÓN HISTÓRICA
Análisis combinatorio: Diferentes maneras de ordenar o agrupar elementos dados siguiendo instrucciones
establecidas sin necesidad de enumerarlas.
Europa: Edad media. Interés a través de la cábala.
S. XVII-XVIII: Pascal estudia triángulo tartaglia. Trabajos de Ramón Llul. Liebniz (influido por Llul).
2.2 EL FACTORIAL DE UN NÚMERO
▪ Para 𝒏 ≠ 𝟎, 𝒏! = 𝒏 ∙ (𝒏 − 𝟏) ∙ (𝒏 − 𝟐) ∙ … ∙ 𝟑 ∙ 𝟐 ∙ 𝟏 = 𝒏 ∙ (𝒏 − 𝟏)!
▪ Para 𝒏 = 𝟎, 𝟎! = 𝟏
𝑛[`𝑘] ∙(𝑛−𝑘)! 𝑛!
Factorial generalizado (𝑘 ≤ 𝑛): 𝑛[`𝑘] = 𝒏 ∙ (𝒏 − 𝟏) ∙ (𝒏 − 𝟐) ∙ … ∙ (𝒏 − 𝒌 + 𝟏) = (𝑛−𝑘)!
= (𝑛−𝑘)!
Propiedades:
▪ 𝑛[`𝑛] = 𝑛! ▪ 𝑛[`𝑘] = (𝑛 − 𝑘) = 𝑛[`𝑘+1]
▪ 𝑛[`𝑛−𝑘] ∙ 𝑘! = 𝑛! ▪ 𝑛[`𝑘] = (𝑛 + 1) = (𝑛 + 1)[`𝑘+1]
▪ 𝑛[`𝑘] = (𝑛 − 𝑘)! = 𝑛! ▪ 𝑛[`0] = 𝑛[`1] = 𝑛 (𝑃𝑜𝑟 𝑐𝑜𝑛𝑣𝑒𝑛𝑖𝑜)
2.3 EL NÚMERO COMBINATORIO
Número combinatorio 𝑛 sobre 𝑘 con (𝑘 ≤ 𝑛):
𝑛 𝑛[𝑘] 𝑛[𝑘] ∙ (𝑛 − 𝑘)! 𝑛!
( )= = =
𝑘 𝑘! 𝑘! ∙ (𝑛 − 𝑘)! 𝑘! ∙ (𝑛 − 𝑘)!
Números combinatorios sencillos:
𝑛! 𝑛! 𝑛! 𝑛! 𝑛!
(𝑛0) = 0!∙(𝑛−0)!=𝑛! = 1 (𝑛1) = 1∙(𝑛−1)! = 𝑛 (𝑛𝑛) = 𝑛!∙(𝑛−𝑛)!=𝑛!∙1 = 1
2. PRINCIPIOS FUNDAMENTALES DEL CONTEO
Contar: Hallar el número de elementos de un conjunto. Por enumeración o por principios de conteo.
3.1 PRINCIPIO DE LA ADICIÓN O DE LA SUMA
Para dos opciones mutuamente excluyentes:
|𝑨𝟏 ∪ 𝑨𝟐 | = |𝑨𝟏 | + |𝑨𝟐 |
𝒏 𝒏
|⋃ 𝑨𝒊 | = |𝑨𝟏 ∪ 𝑨𝟐 ∪ 𝑨𝟑 ∪ … ∪ 𝑨𝒏 | = |𝑨𝟏 | + |𝑨𝟐 | + |𝑨𝟑 |+ . . . +|𝑨𝒏 | = ∑|𝑨𝒏 |
𝒊=𝟏 𝒊=𝟏
3.2 PRINCIPIO DEL PRODUCTO
Una opción se puede tomar de 𝑛 maneras diferentes y una segunda de 𝑚 maneras, etc…
|𝑨𝟏 × 𝑨𝟐 | = |𝑨𝟏 | ∙ |𝑨𝟐 |
𝒏 𝒏
|∏ 𝑨𝒊 | = |𝑨𝟏 ∙ 𝑨𝟐 ∙ 𝑨𝟑 ∙ … ∙ 𝑨𝒏 | = |𝑨𝟏 | ∙ |𝑨𝟐 | ∙ |𝑨𝟑 | ∙ . . .∙ |𝑨𝒏 | = ∏|𝑨𝒏 |
𝒊=𝟏 𝒊=𝟏
3.3 DIAGRAMA DE ÁRBOL
No es una técnica de recuento. Para esquematizar las diferentes posibilidades que se presentan en un
problema. Según las circunstancias sirve para aplicar el principio de la suma o el del producto.
3. TÉCNICAS DE RECUENTO. COMBINATORIA.
Técnicas de cálculo para el recuento de casos o elementos en conjunto base (orden: número de elementos
que contienen los subconjuntos ordenados a partir de conjunto base).
Técnicas diferentes según: Importa el orden → se repiten los elementos → se usan todos los elementos
3.1 VARIACIONES.
SÍ IMPORTA EL ORDEN → NO SE UTILIZAN TODOS LOS ELEMENTOS
3.1.1 VARIACIONES SIMPLES O SIN REPEICIÓN: De 𝑛 elementos tomados de 𝑘 en 𝑘 (𝑘 < 𝑛)
No se repiten elementos. Dos grupos son distintos si se diferencian en algún elemento o
en el orden en que están colocados. Demostración para:(𝑘 = 1), (𝑘 = 2), (𝑘 = 𝑛 − 1)
𝒏!
𝑽𝒌𝒏 = 𝑽𝒏,𝒌 = 𝒏 ∙ (𝒏 − 𝟏) ∙ (𝒏 − 𝟐) ∙ … ∙ (𝒏 − 𝒌 + 𝟏) = 𝒏[𝒌] =
(𝒏 − 𝒌)!
3.1.2 VARIACIONES CON REPEICIÓN: De 𝑛 elementos tomados de 𝑘 en 𝑘 ( 𝑘 puede ser > 𝑛)
Los elementos se pueden repetir hasta 𝑘 vedes. Dos grupos son distintos si se diferencian
en algún elemento o en el orden en que están colocados.
(𝒌)
𝑽𝑹𝒌𝒏 = 𝑽𝑹𝒏,𝒌 = 𝒏 ∙ 𝒏 ∙ …
⏞ ∙ 𝒏 = 𝒏𝒌
3.2 PERMUTACIONES.
Caso particular de variaciones (𝑛 = 𝑘): SÍ IMPORTA EL ORDEN → SE UTILIZAN TODOS LOS ELEMENTOS
3.2.1 PERMUTACIONES SIMPLES O SIN REPETICIÓN: De 𝑛 elementos (tomados de 𝑛 en 𝑛):
Intervienen todos los elementos sin repetirse. Dos grupos son distintos si el orden en que
están colocados es distinto. Demostración a partir de 𝑃𝑛 = 𝑉𝑛,𝑛 :
𝒏! 𝒏!
𝑷𝒏 = 𝑽𝒏,𝒏 = = = 𝒏!
(𝒏 − 𝒏)! 𝟎!
3.2.2 PERMUTACIONES CON REPETICIÓN: De 𝑛 elementos (tomados de 𝑛 en 𝑛) con 𝑘
agrupaciones de elementos repetidos iguales en el grupo base: (𝑛1 + 𝑛2 +. . . +𝑛𝑘 ) = 𝑛
Intervienen todos los elementos (hay repetición). Dos grupos son distintos si el orden en
que están colocados es distinto (se excluye el orden de colocación dentro de elementos
iguales). Demostración sustituyendo un grupo de elementos iguales 𝑛1 y permutando sin
cambiar el orden de los demás:
𝑛 ,𝑛2 ,…,,𝑛𝑘
𝑛1 ! ∙ 𝑛2 ! ∙ 𝑛3 ! ∙ … ∙ 𝑛𝑘 ! ∙ 𝑃𝑅𝑛 1 = 𝑃𝑛 = 𝑛!
𝒏 ,𝒏𝟐 ,…,,𝒏𝒌 𝒏!
𝑷𝑹𝒏𝟏 =
𝒏𝟏 ! ∙ 𝒏𝟐 ! ∙ 𝒏𝟑 ! ∙ … ∙ 𝒏𝒌 !
3.3 COMBINACIONES
No importa el orden, y lógicamente no se toman todos los elementos.
3.3.1 COMB. SIMPLES O SIN REPETICIÓN: De 𝑛 elementos tomados de 𝑘 en 𝑘 (𝑘 ≤ 𝑛):
Intervienen 𝑘elementos sin repetirse. Dos grupos son distintos si se diferencian en un
elemento. Se corresponde con el número combinatorio:
𝒏[𝒌] 𝒏[𝒌] ∙ (𝒏 − 𝒌)! 𝒏! 𝒏
𝑪𝒌𝒏 = 𝑪𝒏,𝒌 = = = =( )
𝒌! 𝒌! ∙ (𝒏 − 𝒌)! 𝒌! ∙ (𝒏 − 𝒌)! 𝒌
3.2.2 COMB. CON REPETICIÓN: De 𝑛 elementos tomados de 𝑘 en 𝑘 (𝑘 < 𝑛) con 𝑘 agrupaciones
de elementos repetidos iguales en el grupo base: (𝑛1 + 𝑛2 +. . . +𝑛𝑘 ) = 𝑛
Intervienen 𝑘 elementos que pueden estar o no repetidos. Dos grupos son distintos si se
diferencian en un elemento. Se corresponde con el número combinatorio:
(𝒏 + 𝒌 − 𝟏)! 𝒏+𝒌−𝟏
𝑪𝑹𝒌𝒏 = 𝑪𝑹𝒏,𝒌 = 𝑪𝒏+𝒌−𝟏
𝒏 = =( )
𝒌! ∙ (𝒏 − 𝟏)! 𝒌
3.2.3 APLICACIONES DE LAS COMBINACIONES: El Triángulo de Tartaglia: Tomamos conjuntos
de un número creciente de elementos (desde ∅) y colocando por filas sus posibles
subconjuntos y se hallan los números combinatorios del cardinal de cada conjunto y los
cardinales de los diferentes subconjuntos.
𝟎
( )
𝟎
𝟏 𝟏
( ) ( )
𝟎 𝟏
𝟐 𝟐 𝟐
( ) ( ) ( )
𝟎 𝟏 𝟐
𝟑 𝟑 𝟑 𝟑
( ) ( ) ( ) ( )
𝟎 𝟏 𝟐 𝟑
𝟒 𝟒 𝟒 𝟒 𝟒
( ) ( ) ( ) ( ) ( )
𝟎 𝟏 𝟐 𝟑 𝟐
El triángulo con los números combinatorios calculados. En las posiciones centrales cada
número es la suma de los anteriores (las diagonales son unos):
𝟏
𝟏 𝟏
𝟏 𝟐 𝟏
𝟏 𝟑 𝟑 𝟏
𝟏 𝟒 𝟔 𝟒 𝟏
