Upload
others
View
5
Download
1
Embed Size (px)
Citation preview
Tema 3. Técnicas de Recuento. Combinatoria
Tema elaborado por José Luis Lorente (www.joseluislorente.es )
Tema III:
Técnicas de recuento.
Combinatoria.
2
Índice sistemático:
1. Introducción.
2. Técnicas de recuento.
2.1. Principio de paridad.
2.2. Principio de correspondencia uno a uno.
2.3. Principio fundamental del conteo o principio del producto.
2.4. Principio de adición o regla de la suma.
2.5. Principio de las cajas (del palomar o de Dirichlet).
3. Variaciones.
3.1. Variaciones simples u ordinarias.
3.2. Variaciones con repetición.
4. Permutaciones.
4.1. Permutaciones simples u ordinarias.
4.2. Permutaciones con repetición.
4.3. Permutaciones circulares.
5. Combinaciones.
5.1. Combinaciones simples u ordinarias.
5.2. Los números combinatorios.
5.3. Combinaciones con repetición.
3
6. Pautas para la resolución de problemas.
7. Bibliografía.
1. Introducción.
El análisis combinatorio o combinatoria estudia las diferentes formas en que podemos
ordenar o agrupar unos elementos dados siguiendo unas determinadas reglas establecidas. Nos
proporciona algoritmos para averiguar la cantidad de agrupaciones que, bajo determinadas
condiciones, se pueden formar con los elementos de un conjunto.
Existen diversos métodos para obtener el numero de ordenaciones, pero para
determinados problemas tendremos algoritmos que nos permiten de forma sistemática obtener
el número de diferentes agrupaciones, que bajo determinadas condiciones se pueden formar
con los elementos de un conjunto.
La ciencia que estudia las reglas de recuento o conteo se denomina combinatoria. Según
las características de los grupos y la naturaleza de los elementos, nos podemos encontrar con
variaciones, combinaciones y permutaciones.
El surgir de los conceptos principales y el desarrollo del análisis combinatorio
transcurrían paralelamente al desarrollo de otras partes de las matemáticas, tales como el
álgebra, la teoría de números y la teoría de las probabilidades con las que el análisis
combinatorio está estrechamente relacionado.
Los matemáticos del antiguo oriente conocían la fórmula que expresa el número de
combinaciones por medio de coeficientes binomiales, así como la fórmula del binomio de
Newton con índice natural n.
El origen del análisis combinatorio como parte de las matemáticas se debe a B. Pascal y
P. Fermat con obras dedicadas a la teoría de los juegos de azar. Al desarrollo sistemático de
los métodos combinatorios contribuyó considerablemente G. Leibniz en su “Discurso sobre el
arte combinatorio” y J. Bernoulli con su “El arte de pronosticar”. El método de las funciones
generadoras lo dio L. Euler con sus obras dedicadas a las particiones y composiciones de los
números naturales en sumandos.
4
Actualmente, el área de Combinatoria ha sido dividida en tres grandes sub-áreas:
• Combinatoria Enumerativa (problemas y técnicas de conteo).
• Teoría de grafos e hipergrafos.
• Teoría de Diseños / Geometría finita.
• (Análisis discreto y análisis finito). (A gusto del opositor)
• (Investigación de operaciones).
Algunas preguntas típicas del análisis combinatorio serán:
• Existencia: ¿Existen soluciones factibles? Si es así, ¿Es posible exhibir una?
• Enumeración: ¿Cuántas soluciones factibles diferentes existen?
• Isomorfismo: dadas dos soluciones factibles, ¿Es una de ellas simplemente una re-
escritura de la otra?
• Optimización: si a cada solución factible le asociamos un costo (o una medida de
“calidad”), cual es el costo mínimo (o la calidad máxima) que puede ser obtenido entre las
soluciones factibles?
Los algoritmos para encontrar las fórmulas generales se pueden crear por recursión,
mediante diagramas de árbol, gráficos, etc.
2. Técnicas de recuento.
Las técnicas de recuento tratan del estudio de las ordenaciones de los elementos de un
conjunto. Nos encontraremos con dos tipos de problemas, los de existencia (analizarán la
posibilidad de existencia de la ordenación pedida) y los de enumeración (permitirán decir el
número de clasificaciones posibles).
Las técnicas de recuento más utilizadas son:
2.1. Principio de paridad:
5
Un conjunto puede tener un número par o impar de elementos. Si probamos que tiene
un número impar, estamos en condiciones de afirmar que al menos hay uno. Quedaría así
demostrada la existencia. (Para problemas de existencia).
2.2. Principio de correspondencia uno a uno:
Se trata de conseguir establecer una aplicación biyectiva entre el conjunto de estudio y
una sección S(n) de N. En caso de que podamos establecerla, diremos que el cardinal del
conjunto es n. (Para problemas de enumeración).
2.3 Principio fundamental del conteo o principio del producto:
Si una operación se puede hacer de n maneras diferentes y si en cada caso, una
segunda operación se puede hacer de m maneras diferentes, entonces hay m. n maneras de
realizar las dos operaciones.
Generalizando, si un evento puede realizarse de n1 maneras distintas, y si, continuando
el procedimiento, un segundo evento puede realizarse de n2 maneras distintas, y si depués
de efectuados, un tercer evento puede realizarse de n3 maneras distintas, y así
sucesivamente, entonces el número de maneras en que los eventos pueden realizarse en el
orden indicado es el producto n1. n2
. ...
. nk .
2.4 Principio de adición o regla de la suma:
Si dos operaciones son mutuamente excluyentes (es decir, si sólo una de ellas puede
ocurrir) y si la primera se puede hacer de n maneras diferentes y la segunda operación se
puede hacer de m maneras diferentes, entonces hay n + m maneras de realizar la primera o
la segunda operación. (En los problemas de conteo, la palabra “o” se traduce en suma).
2.5 Principio de las cajas (del palomar o de Dirichlet):
Si tenemos m objetos que se distribuyen en n cajas, m>n, entonces una de las cajas
recibe al menos dos objetos. (Principio restringido).
6
Si se distribuyen m objetos en n cajas, entonces hay una caja que recibe al menos
[m/n] objetos; y hay una caja que recibe, a lo más [m/n] objetos. (Principio generalizado).
([x] significa la parte entera de x).
Precisando más, si se quieren distribuir n objetos en k casilleros ( n > k), habrá algún
casillero con al menos [ (n-1) / k ] + 1 objetos.
Definición de factorial:
Para un entero n ≥ 0, n factorial, expresado n!, se define por:
n! = (n)·(n–1)·(n–2)·...·3·2·1, para n ≥1
0! = 1
2. Variaciones.
La característica fundamental de cada agrupación es que sí importa el orden, y no se
utilizan todos los elementos en cada agrupación.
2.1 Variaciones simples u ordinarias. (Muestra ordenada sin repetición)
Definición:
Se llama variación simple de n elementos tomados de k en k (k ≤ n) a los distintos
subconjuntos o grupos formados por k elementos de forma que:
• Los k elementos que forman el grupo son distintos (no se repiten).
• Dos grupos son distintos si se diferencian en algún elemento o en el orden en que están
colocados (influye el orden).
(Aquí no se utilizan todos los elementos)
Problema tipo:
7
Extraemos sucesivamente sin reposición k bolas de una urna que contiene n bolas
distintas, k, n ∈ Ν, k ≤ n. Contaremos el número de k-tuplas ordenadas distintas:
(n1, n2,...,nk) donde nj ∈ {1, 2, ...,n} j = 1, 2, ..., n ni ≠ nj si i ≠ j.
Solución:
El número de resultados posibles es:
Vkn = Vn,k = n·(n-1)·(n-2)·...·(n-k+1) =
k)!(n
n!
−
Vkn = Vn,k = #{Variaciones de n elementos cogidos de k en k}
Demostración: (por recursión ó árbol).
Sea P(n,k) el número de maneras de enumerar k objetos elegidos de entre n.
P(n,k) = n.P(n-1,k-1) = … = n
.(n-1)
.…
.(n-k+2)
.P(n-k+1,1) =
k)!(n
n!
−
P(n,1) = n
Si elegimos un primer elemento, lo que podemos hacer de n formas. Quitamos el
elemento elegido y escogemos otro de entre los n-1 que quedan. Esto podrá hacerse de n-1
formas. Quitamos también este elemento y nos quedamos con n-2, de entre los que
elegimos el tercero. Esto lo podremos hacer de n-2 formas. Según la regla del producto, las
maneras de escoger k elementos de entre un total de n según un determinado orden, será
igual al producto de n·(n-1)·(n-2)·...·(n-k+1).
Para llegar a una versión simplificada se opera así:
8
n.(n–1)
.(n–2)
....
.(n–k+1)· knV
k)!(n
n!
k
kkn,
(3)(2)(1) ... )1-k-)(n-(n
(3)(2)(1) ... )1--)(n-(=
−=
1º 2º 3º k-ésimo (posición)
*Árbol:
n n-1 n-2 n-(k-1) (posibilidades de coger el i-ésimo elemento)
(*Se iría dibujando las ramas de un árbol con todas las posibilidades)
Ejemplo:
¿Cuántas banderas diferentes, de tres franjas horizontales de igual ancho y de colores
distintos, pueden confeccionarse a partir de siete colores diferentes?
Como importa el orden y no pueden repetirse los colores, la solución es: V7,3 = 2104!
7!=
Observación:
Vn,k coincide con el cardinal del conjunto de aplicaciones inyectivas:
f: Ik → In
(1,2,...,k) f(1,2,...,k)=(1,2,...,n)
3.2 Variaciones con repetición. (Muestra ordenada con repetición)
Definición:
9
Se llaman variaciones con repetición de n elementos cogidos de k en k a las diferentes
agrupacionesde esos k elementos de forma que:
• Los elementos que forman los grupos pueden estar repetidos.
• Dos grupos son distintos si se diferencian en algún elemento o en el orden en que están
colocados (influye el orden).
Problema tipo:
Sacamos sucesivamente k bolas y las devolvemos a la urna después de cada
extracción. Se trata de contar el número de k-tuplas ordenadas distintas:
(n1, n2,...,nk) donde nj ∈ {1, 2, ...,n} j = 1, 2, ..., n
Solución:
El número de resultados posibles es: VRn
k = VRn,k = nk = n·n·n·...·n
VRn
k = VRn,k = # {Variaciones con repetición de n elementos cogidos de k en k}
Demostración: (por árbol)
1º 2º 3º k-ésimo (posición)
Árbol:
n n n n (posibilidades de coger el i-ésimo elemento)
Por tanto, k
kn nVR =, .
Observación:
Vn,k coincide con el cardinal del conjunto de aplicaciones f: Ik → In que
indican que elemento de Ik se sitúa en el lugar 1,2, ..., n.
Ejemplo:
10
¿Cuántos números de tres cifras pueden formarse a partir de los dígitos 1 y 2? Como
importa el orden, y pueden repetirse las cifras, la solución es VR2,3 = 2 3 = 8
4. Permutaciones.
Es un caso particular de las variaciones, es decir, importa el orden, pero sí en cada
agrupación cogemos todos los elementos del conjunto.
4.1 Permutaciones simples u ordinarias. (Muestra ordenada sin repetición)
Definición:
Se llaman permutaciones de n elementos a las diferentes agrupaciones de esos n
elementos de forma que:
• En cada grupo intervienen los n elementos sin repetirse ninguno (intervienen todos los
elementos.
• Dos grupos son diferentes si el orden de colocación de alguno de esos n elementos es
distinto (influye el orden).
Problema tipo:
Extraemos sucesivamente sin reposición las n bolas distintas que contiene una urna, (n
∈ Ν). Contaremos el número de n-tuplas ordenadas distintas:
(n1, n2,...,nn) donde nj ∈ {1, 2, ...,n} j = 1, 2, ..., n ni ≠ nj si i ≠ j.
Solución:
Pn = Vn,n = n!, ya que tenemos: !
!0
!n
n
n)!(n
n!P n ==
−=
Pn = # {permutaciones de n elementos}.
Observación:
11
P(1) = 1
P(n) = n P(n-1)
Observación:
Pn corresponde al número de aplicaciones biyectivas:
f: : In → In
(1,2,...,n) f(1,2,...,n)=(1,2,...,n)
Ejemplo:
Una madre tiene 3 hijos ¿de cuántas maneras distintas, nombrándolos uno por uno,
puede llamarlos a cenar?
Como importa el orden, y nombramos a todos una sola vez, la solución es: P 3 = 3! = 6
Más sobre permutaciones:
En general, una permutación de n elementos no es más que una forma de escribir los
mismos elementos en un orden distinto.
Una forma útil de ver esto es pensar que lo que hacemos es llevar los números 1,...,n a
números distintos que estén entre 1 y n. El conjunto de todas las permutaciones de los
números {1,...,n} se suele denotar por Pn o por Sn.
El conjunto Pn de permutaciones de orden n es un grupo no commutativo para la
composición de aplicaciones y cuyo elemento neutro es la aplicación identidad:
σ(i) = i ∀ i = 1, 2, ..., n.
Se suelen representar mediante n-uplas (n1, n2, ..., nk), es decir, σ(1) = n1, σ(2) = 2, ...,
σ(k) = nk.
12
Llamaremos trasposición a una permutación en la que se permutan dos índices
quedando los n-2 índices restantes invariantes: τij(i) = j, τij (j) = i, τij (k) = k ∀k ≠ i, j.
Supongamos fijada una permutación σp, llamada permutación principal. Diremos que
dos elementos en una permutación están invertidos si están en diferente orden que en la
permutación principal.
Llamaremos índice de una permutación al número de inversiones que presenta:
Ind(σ) = min τk°τk-1° … °τ1°σ = σpk
K
Definición:
Diremos que la permutación es par (impar) si su índice es un número par (impar).
Proposición:
# permutaciones pares = # permutaciones impares = n! / 2.
Ejemplo:
Calcular y explicar las maneras posibles de colocar las letras a, b, c.
Hay P3 = 3! = 6 maneras posibles de colocar las tres letras, estas son: abc, acb, bac, bca,
cab, cba
4.2 Permutaciones con repetición. (Muestra ordenada con repetición)
Definición:
Se llaman permutaciones con repetición de n elementos entre los que hay n1 iguales
entre sí, n2 iguales entre sí, ..., nk iguales entre sí de manera que n2 + ... + nk = n, a las
diferentes agrupaciones de n elementos de forma que:
• En cada agrupación se coge cada elemento i ni veces (i = 1, 2, ..., k).
13
• Dos grupos son diferentes si el orden de colocación de alguno de esos n elementos es
distinto (influye el orden).
Problema tipo:
Sea A un conjunto compuesto de n elementos, y sean n1, n2, ...,nk enteros tales que
n1 + n2 + ... + nk = n queremos contar el número particiones ordenadas que hay distintas de
A de la forma (A1, A2, ..., Ak) donde Ai consta de ni elementos i=1,2, ..., k.
Solución:
Existen PRnn1,n2,...,nk
=
!!!
!
21 knnn
n
⋅⋅⋅ ⋅⋅⋅
particiones ordenadas
PRnn1,n2,...,nk
= #{permutaciones con repetición de n elementos entre los que hay n1 iguales
entre sí, n2 iguales entre sí, ..., nk iguales entre sí de manera que n2 + ... + nk = n}
Demostración:
Contamos los subconjuntos de n de n1 elementos = !)!(
!
11 nnn
n
⋅−, contamos los
subconjuntos de n - n1 de n2 elementos =!)!(
)!(
221
1
nnnn
nn
⋅−−
−, y así sucesivamente, lo que
implica:
PRnn1,n2,...,nk =
!)!(
!
11 nnn
n
⋅− .
!)!(
)!(
221
1
nnnn
nn
⋅−−
−. … .
!)!...(
)!...(
21
121
kk
k
nnnnn
nnnn
⋅−−−−
−−−− − (Es decir,
número de permutaciones posibles de n objetos de los cuales n1 son iguales, n2 son iguales,
…, nk son iguales).
Definición:
A la expresión: !!!
!
21 knnn
n
⋅⋅⋅ ⋅⋅⋅
se le llama coeficiente multinomial.
Fórmula de Liebniz:
14
(x1 + x2 + ... + xn)n = m
m
k
m
k
nkk m
xxkk
n...
!!...
!1
1
1
... 1
∑=++
(Generalización de la fórmula de Newton, que se demostrará más adelante).
Ejemplo:
Tenemos 3 libros de química, 4 de física y 5 de matemáticas. ¿De cuantas maneras se
pueden ordenar los libros por materias en una estantería?
Tenemos 3 materias, y 3, 4 y 5 libros de cada materia, por tanto existen PR12
3,4,5 =
!5!4!3
!12
⋅⋅
= = !51234123
!56789101112
⋅⋅⋅⋅⋅⋅⋅
⋅⋅⋅⋅⋅⋅⋅ = 28020 formas diferentes de ordenarlos por materias.
4.3 Permutaciones circulares. (Muestra ordenada sin repetición)
Definición:
Dado un conjunto de n elementos, se llama permutación circular, a las diferentes
agrupaciones de esos n elementos de forma que:
• En cada grupo intervienen los n elementos sin repetirse ninguno (intervienen todos los
elementos.
• Dos grupos son diferentes si varía la posición relativa de sus elementos.
Problema tipo:
Iremos colocando sobre una circunferencia las n bolas que extraemos sucesivamente
sin reposición que contiene una urna, (n ∈ Ν). Contaremos el número de n-tuplas distintas
que hay sobre la circunferencia: (n1, n2,...,nn) donde nj ∈ {1, 2, ...,n} j = 1, 2, ..., n ni ≠ nj si
i ≠ j.
Solución:
Pn’ = (n-1)!
15
Pn’ = # {permutaciones circulares distintas}
Demostración:
Dos colocaciones son la misma cuando una se obtiene de la otra girando todas las
personas en el mismo sentido alrededor de la circunferencia.
n. (permutaciones circulares) = Pn
5. Combinaciones.
La característica fundamental de cada agrupación es que no importa el orden.
5.1 Combinaciones simples u ordinarias. (Muestra sin orden y sin repetición).
Definición:
Se llama combinaciones de n elementos tomados de k en k (n ≥ k) a todas las clases
posibles que pueden hacerse con los n elementos de forma que:
• Cada agrupación está formada por n elementos distintos entre sí.
• Dos agrupaciones distintas se diferencian al menos en un elemento, sin tener en cuenta
el orden.
Problema tipo:
Extraemos k bolas sucesivamente sin reposición de una urna que contiene n bolas
distintas (n, k ∈ Ν, n ≥ k). No nos importa en que orden aparecen (formas de hacer una
extracción única de k bolas).
Solución:
El número de subconjuntos de n con cardinal k es
16
Cn,k = )!(!
!
knk
n
k
n
−=
Cn,k = # {combinaciones de n elementos tomados de k en k}
Demostración:
Consideramos cualquier selección de k objetos. Dicha selección puede ordenarse de Pk
= k! Maneras diferentes, de forma que cada selección no ordenada da lugar a k! selecciones
ordenadas, es decir, k! Cn,k = Vn,k,, ie, , Cn,k = Vn,k,/ k!, por tanto,
Cn,k = )!(!
!
knk
n
k
n
−=
Observación:
La estadística de Fermi-Dirac propone el modelo de muestra no ordenado sin
repeticiones que atribuye a cada una de las
k
n distribuciones la misma probabilidad. Este
modelo se aplica a los electrones, neutrones y protones.
Ejemplo:
¿Cuantas combinaciones de 6 aciertos existen en la lotería primitiva?
C6,49 = 13983816)!649(!6
!49
6
49=
−=
5.2 Los números combinatorios:
Definición:
)!(!
!
knk
n
k
n
−=
se llama número combinatorio, y se lee, n sobre k.
17
Observación:
En general, calcular
k
n por la fórmula anterior implica calcular varios factoriales, lo
que hace que no sea muy útil en la práctica. Un método alternativo de cálculo viene dado
por las siguientes propiedades:
1) 10
=
=
n
nn
2)
−=
kn
n
k
n n ≥ k ≥ 0
Demostración:
Elegir k objetos de entre n es equivalente a elegir los n-k objetos que no van a ser
elegidos. O bien, =−−−
=−
=
)!())!((
!
)!(!
!
knknn
n
knk
n
k
n
− kn
n.
3) Sea n un entero positivo. Entonces al desarrollar (1 + x)n como suma de potencias de x,
el coeficiente de xk es
k
n. Es decir,
∑=
⋅
=⋅
++⋅
+⋅
+
=+
n
i
knn xk
nx
n
nx
nx
nnx
0
2 ...210
)1(
Demostración:
Consideramos (1 + x) . (1 + x)
. ..
n.
. (1 + x) , el término x
k se obtiene eligiendo k de
los paréntesis y tomando el término x de cada uno de ellos, y el término 1 de los
restantes n-k paréntesis. Por lo tanto, xk se obtiene tantas veces como maneras hay de
elegir k de los n paréntesis ie Cn,k.
18
4)
−+
−
−=
k
n
k
n
k
n 1
1
1
Demostración:
Si nos basamos en el principio de adición:
k
n es el número de maneras de
seleccionar k objetos de entre n. Cada selección puede incluir el n-ésimo objeto o no. Si
la selección incluye el n-ésimo objeto, el problema es el de elegir k-1 objetos de entre
los n-1 restantes, y esto puede hacerse de
−
−
1
1
k
nmaneras. Si la selección no incluye el
n-ésimo objeto, entonces deben seleccionarse k objetos de entre los n-1 restantes y esto
puede hacerse de
−
k
n 1maneras.
Alternativamente, si operamos los números combinatorios, tenemos:
−+
−
−
k
n
k
n 1
1
1=
)!(!
!)!(
)!(!
)!1(
)!1(!
)!1(
)!()!1(
)!1(
knk
nknk
knk
n
knk
n
knk
n
−=−+
−−
=−−
−+
−−−
5)
−+
=
+
+
k
n
k
n
k
n 1
1
1+ ... +
k
k ∀ n ≥ k
6)
−
−+
=
+
1
11
k
n
k
n
k
n+ ... +
−
0
kn ∀ n ≥ k
Observación:
Esta última propiedad permite calcular números de la forma
k
n una vez conocidos
los números de la forma
−
i
n 1. Para usar este método se hace una tabla de doble
entrada, en las filas se pone el valor de n y en las columnas el valor de k, poniendo en la
casilla correspondiente el valor del número combinatorio que queremos calcular.
19
Veamos cómo se hace esto con una tabla de números combinatorios para n entre 0
y 5. Construimos la tabla donde hemos puesto un * en las casillas a rellenar:
0 1 2 3 4 5
0 *
1 * *
2 * * *
3 * * * *
4 * * * * *
5 * * * * * *
Por la propiedad 1), las casillas situadas en la columna 0 así como aquellas en las
que el número de fila sea igual al número de columnas deben valer todas 1.
0 1 2 3 4 5
0 1
1 1 1
2 1 * 1
3 1 * * 1
4 1 * * * 1
20
5 1 * * * * 1
Vamos a rellenar la tabla usando la propiedad 2). Esta viene a decir que cada casilla
es igual a la suma de la que tiene inmediatamente encima con la que queda encima y a
la izquierda. Así, la casilla (2,1) será igual a la suma de las casillas (1,1) más (1,0), por
tanto, vale, 1 + 1 = 2.
0 1 2 3 4 5
0 1
1 1 1
2 1 2 1
3 1 * * 1
4 1 * * * 1
5 1 * * * * 1
Una vez rellena la fila 2, pasamos a rellenar la fila 3. Para ello, observemos que la
casilla (3,1) será la suma de la (2,1) con la (2,0), por lo que vale 3. Así mismo, la (3,2)
vale 1 + 2 = 3. Tenemos ahora:
0 1 2 3 4 5
0 1
1 1 1
2 1 2 1
3 1 3 3 1
21
4 1 * * * 1
5 1 * * * * 1
Rellenamos por el mismo procedimiento la fila 4, que queda:
0 1 2 3 4 5
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 * * * * 1
Finalmente, rellenamos la última fila:
0 1 2 3 4 5
0 1
1 1 1
22
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
Triángulo de Tartaglia:
1
1 1
1 2 1
1 3 3 1
...
Es simétrico con los exteriores 1, cada uno de los interiores es suma de los dos
anteriores y la suma de los elementos de la n-ésima línea vale 2n. El elemento de la fila n y
la columna k, (n,k), vale
k
n.
Fórmula del binomio de Newton:
(Se lo envió Newton a Leibniz en 1677, se apoyó en la obra del matemático Wallis
sobre interpolación y extrapolación de términos). Si x e y son variables y n es un entero
positivo, entonces,
knn
i
knnnnn yxk
nyx
n
nyx
nyx
nyx
nyx −
=
−− ⋅⋅
=⋅⋅
++⋅⋅
+⋅⋅
+⋅⋅
=+ ∑
0
02210 ...210
)(
Demostración:
23
Basándonos en la tercera propiedad: (x + y)n = x
n (1+
x
y)n,
, o bien, al desarrollar el
producto (x+y) (x+y) (x+y) ... (x+y) obtendremos una serie de sumandos de forma que
cada uno de ellos será un producto de un cierto número de x’s por otro cierto número de
y’s. Si contamos en cada sumando el número de x’s más el número de y’s, tendremos que
ese número siempre es igual al número de paréntesis que multiplicamos, que es n. Estos
posibles sumandos variarán desde tener 0 x’s y n y’s, después 1 x’s con n-1 y’s, y así
sucesivamente. Cualquiera de ellos lo podemos escribir de la forma xky
n-k, con 0 ≤ k ≤ n, al
sumar, el coeficiente de xky
n-k, 0 ≤ k ≤ n, es el número de veces que aparece ese sumando
al desarrollar el producto, esto es, formas distintas en que se pueden seleccionar las k x’s
(y en consecuencia las (n–k) y’s) de las n x’s disponibles en los n factores (por ejemplo,
una forma es elegir x de los primeros k factores e y de los últimos n–k factores). El nº total
de las selecciones de tamaño k de una colección de tamaño n es n
k
de donde resulta el
teorema.
(Debido a este resultado, n
k
suele denominarse coeficiente binomial.)
Corolario:
n n n n
n
n
0 1 22
+
+
+ +
=...
n n n n
n
n
0 1 21 0
−
+
+ + −
= ... ( )
Observación:
(1 + x)n es la función generatriz de los coeficientes binomiales.
Aplicación:
exp(x)exp(y) = exp (x+y) donde exp(x) = 1 +x + ... + !n
x n + ...
24
En su momento sirvió para hacer cálculos mucho más precisos ya que las máquinas de
cálculo que existían no hacían más que cuatro operaciones y muy lentamente:
(Ejemplo: ...28
12
2
11)21(5 422
1
2 +++=+= )
5.3 Combinaciones con repetición. (Muestra sin orden y con reposición).
Definición:
Se llama combinaciones con repetición de n elementos tomados de k en k, a los
distintos grupos formados por k elementos de manera que:
• Los elementos que forman cada grupo pueden estar repetidos.
• Dos agrupaciones distintas se diferencian al menos en un elemento, sin tener en cuenta
el orden.
Problema tipo:
Cogemos sucesivamente k bolas de una urna que contiene n bolas diferentes. Después
de cada extracción devolvemos la bola (puede haber repeticiones en el resultado).
Queremos encontrar el número de conjuntos no ordenados {i1, i2, i3, ..., ik} donde ij ∈ {1, 2,
..., n} para j = 1, 2, ..., k (no necesariamente diferentes).
También se puede mirar como el número de soluciones (i1, i2, i3, ..., in) de enteros no
negativos de la ecuación x1 + x2 + ... + xn = k donde xj número de veces que ha salido la
bola j en las k extracciones j = 1, ..., n.
Solución:
n
kCR =
−+
k
kn 1=
−
−+
1
1
n
kn
n
kCR = # {Combinación con repetición de n elementos cogidos de k en k}
Demostración:
25
Por recurrencia:
Buscamos soluciones enteras no negativas de x1 + x2 + ... + xn = k. Sean estas f(n,k),
f(1,k) = 1 ∀k ≥ 1 x1 = k una única solución
f(n,1) = n ∀n ≥ 1 x1 + x2 + ... + xn = 1 n soluciones xi = 1, xj = 0 i≠j i, j = 1 , 2, ..., n
f(n,k) = f(n-1,k) + f(n,k-1)
Por función generatriz (método de Euler):
La función (1 – x)-n
es generatriz de los números f(n,k) ya que:
(1 – x)-n
= f(n,0) + f(n,1)x + ... + f(n,k) xk
(1 + x + x2 + ... ) (1 + x + x
2 + ... )
. ..
n.
.(1 + x + x
2 + ... )
f(n,k) coeficiente de xk en (1 + x + x
2 + ... )
n
1 + x + x2 + ... =
x−1
1 = (1 – x)
-1
f(n,k) = k
knnn
⋅⋅⋅−++
...21
)1)...(1( =
!)!1(
)!1(
kn
kn
−−+
Por secuencias xxoooxoxox:
f(n,k) es el número de secuencias de círculos y cruces que contienen exactamente k cruces
y n-1 círculos. Cada secuencia consta de n+k-1 símbolos en total y queda unívocamente
determinada por la posición de los círculos.
f(n,k): número de maneras de escoger n-1 lugares de entre n + k – 1.
Observación:
26
CRn,k equivale al número de biyecciones que hay entre los conjuntos no ordenados de
k elementos escogidos entre n, con repeticiones, y conjuntos no ordenados de k elementos
sin repetición, escogidos entre n + k – 1.
Ejemplo:
La estadística de Bose – Einstein que dice que hay Ak,n =
−+
k
kn 1 maneras
diferentes de disponer las partículas y cada disposición es equiprobable. Los fotones siguen
este modelo de ocupación.
6. Pautas para la resolución de problemas.
¿Importa el orden?
No, ¿Se puede repetir?
No, Combinaciones.
Sí, Combinaciones con Repetición.
Sí, ¿Se utilizan todos los elementos?
No, ¿Se puede repetir?
No, Variaciones.
Sí, Variaciones con Repetición.
Sí, ¿Se puede repetir?
No, Permutaciones.
Sí, Permutaciones con Repetición.
27
7. Bibliografía.
Matemáticas Volumen I
Cuerpo de profesores de enseñanza secundaria
Tema 3: Técnicas de recuento. Combinatoria
Jorge Navarro Camacho
Editorial MAD
Probabilidad
Seymour Lipschutz
Editorial McGraw-Hill 1995
ISBN: 968-422-920-8
Introducción a la combinatoria
Ian Anderson
28
Ediciones Vicens Vives S.A. 1993
ISBN: 84-316-3280-1
Lliçons de càlcul de probabilitats
Marta Sanz i Solé
Textos docents: 9 1994 Publicacions de la Universitat de Barcelona
ISBN: 84-475-0693-2
Paràmetre Matemàtiques 1er BUP
Teresa Riera. Jesús Salillas. Conxa Sanchís
Editorial Barcanova S.A. 1985
ISBN: 84-7533-267-6
Análisis combinatorio
Dr. K. Ribikov
Editorial Mir Moscú 1988
ISBN: 5-03-000610-9
Análisis combinatorio. Problemas y ejercicios
Dr. K. Ribikov
Editorial Mir Moscú 1989
ISBN: 5-03-000693-1
29
Introducción a la combinatoria y sus aplicaciones
Kaufmann
CECSA 1971
www. eltemario.com
Tema 3