Laboratorios Virtuales > Combinatorias > 1 2 [3] 4 5

3. Combinaciones

Combinaciones

Considere un conjunto D con n elementos. Una combinación de tamaño k de D es un subconjunto (desordenado)

{x₁, x₂, ..., x_k}

de D con k elementos (distintos), (por supuesto, k no puede ser mayor que n). Una combinación de tamaño k de D es formada cuando k elementos son elegidos de D sin reemplazo (y sin tener en cuenta el orden). Note que por cada combinación de tamaño k de D, hay k! ordenes distintos de los elementos de esa combinación . Cada una de estas es una permutación de longitud k de D.

Los dos primeros ejercicios de abajo deducirán el número de combinaciones de tamaño k de un conjunto de n-elementos; este número se indica por C(n, k).

1. Demostrar que el siguiente procedimiento genera todas las permutaciones de tamaño k de D:

1. Seleccione una combinación de tamaño k de D.
2. Seleccione un orden de los elementos del conjunto en el paso (a).

2. Demostrar que (n)_k = C(n, k)k!. Indicación: Use el Ejercicio 1 y el principio de la multiplicación.

3. Demostrar que C(n, k) = n! / [k!(n - k)!].

Definiremos C(n, k) = 0 si k < 0 o si k > n. Esta convención algunas veces simplifica las fórmulas.

4. Una  mano de póker consiste de 5 cartas repartidas sin reemplazos y sin tener en cuenta el orden de un mazo de 52 cartas.

1. Demostrar que el número de manos de póker es 2,598,960.
2. Encuentre la probabilidad que una mano de póker aleatoria sea un full (3 cartas de un tipo y 2 de otro).
3. Encontrar la probabilidad que en una mano de póker aleatoria tenga 4 de un palo.

El juego de póker es estudiado en detalle en el capítulo sobre Juegos de Azar.

5. Una mano de bridge consiste de 13 cartas repartidas sin reemplazo y sin tener en cuenta el orden de un mazo de 52 cartas.

1. Demostrar que el número de manos de bridge es 635,013,559,600.
2. Encontrar la probabilidad que una mano de bridge aleatoria tenga 4 picas.
3. Encontrar la probabilidad que una mano de bridge aleatoria tenga 4 picas y 3 corazones.
4. Encontrar la probabilidad que una mano de bridge aleatoria tenga 4 picas, 3 corazones y 2 diamantes.

6. Suponga que en un grupo de n personas, cada persona reparte las manos, con todas las otras personas. Demostrar que hay C(n, 2) manos repartidas diferentes.

7. Un club tiene 20 miembros; 12 son mujeres y 8 son hombres. Un comité de 6 miembros será elegido. ¿ Cuantos comités diferentes son posibles si:

1. No hay otras restricciones.
2. El comité debe tener 4 mujeres y 2 hombres.
3. El comité debe tener al menos 2 mujeres y 2 hombres.

Se dice que una mano de cartas que no tiene cartas con un juego en particular está anulada en ese juego.

8. Encontrar el número de manos de póker que son anuladas en al menos un juego. Sugerencia: Use la fórmula de inclusión-exclusión.

9. En la N, lotería n, n números son elegidos al azar, sin reemplazo de la población de enteros de 1 a N (donde n < N, por supuesto). El orden no tiene importancia. El jugador que compra un ticket de lotería está esencialmente tratando de adivinar el resultado.

1. Demostrar que la probabilidad de ganar (jugando a todos los números n) con un solo ticket es 1 / C(N, n).
2. Calcular la probabilidad de ganar una lotería 6 / 44 con un solo ticket (este es un formato común).

Para más sobre este tema, vea la sección de Loterías en el capítulo de Juegos de Azar.

Secuencias de Bits y la Tabla de Galton

10. Demostrar que hay una correspondencia de uno a uno entre cada par de las siguientes colecciones.

1. Subconjuntos de tamaño k de un conjunto de n elementos.
2. Secuencias de bits de longitud n con exactamente k 1's.
3. Trayectoria en la tabla de Galton desde (0, 0) a (n, k).

Ya que el número de objetos en cada una de estas colecciones es C(n, k).

11. En el juego de la tabla de Galton, mover la pelota desde (0, 0) a (12, 7) a lo largo de la trayectoria de su elección. Note la correspondiente secuencia de bits y el subconjunto.

12. En el juego de la tabla de Galton, generar la secuencia de bits 0011101001101. Note el correspondiente subconjunto y trayectoria.

13. En el juego de la tabla de Galton, generar el subconjunto {1, 4, 5, 10, 12, 15}. Note la correspondiente secuencia de bits y trayectoria.

14. En el juego de la tabla de Galton, generar todas las trayectorias desde (0, 0) a (5, 3). ¿Cuantas trayectorias hay?

15. Una moneda regular es arrojada 10 veces.

1. Encontrar la probabilidad de que hayan exactamente 4 caras.
2. Encontrar la probabilidad de que hayan al menos 8 caras.

16. Un embarque contiene 12 artículos buenos y 8 defectuosos. Una muestra de 5 artículos son elegidos al azar. Encontrar la probabilidad que la muestra contenga exactamente 3 artículos buenos.

17. Suponga que 8 peones son colocados aleatoriamente en un tablero de ajedrez.

1. Demostrar que la probabilidad que ningún peón pueda capturar a otro es 8! / C(52, 8).
2. Compare la respuesta y el método con los del Problema 11 en la última sección sobre permutaciones.

Propiedades Básicas

Para algunas de las identidades en los ejercicios de abajo, se le pide dar dos demostraciones. Una demostración algebraica, por supuesto, debería estar basada en la fórmula del ejercicio 3. Una demostración de combinatoria es construida demostrando que los lados izquierdos y derechos de la identidad son dos formas diferentes de contar la misma colección.

18. Demostrar que C(n, 0) = C(n, n) = 1

19. Dar una demostración algebraica y combinacional de la identidad

C(n, k) = C(n, n - k).

20. Dar una demostración algebraica y combinacional de la identidad: si n y k son enteros no negativos y k n entonces 

C(n, k) = C(n - 1, k - 1) + C(n - 1, k).

Sugerencia:para el argumento combinacional, fijar un elemento del conjunto.Contar el número de subconjuntos de tamaño k que contienen el elemento designado y el número de subconjuntos de tamaño k que no contienen el elemento designado.

Si cada marca en la tabla de Galton es reemplazada por el coeficiente binomial correspondiente, la tabla resultante de números es conocida como el triángulo de Pascal, nombrado por Blaise Pascal. En el ejercicio 16 cada número interior del triángulo de Pascal es la suma de dos números por encima del mismo.

21. Generar un triángulo de Pascal superior a n = 10.

22. Dar una demostración algebraica y combinacional del teorema binomial: si a y b son números reales y n es un entero positivo, entonces

(a + b)ⁿ = _{k = 0, ..., n} C(n, k) a^k bⁿ - k.

Porque del teorema binomial, los números C(n, j) son llamados coeficientes binomiales.

23. Encontrar el coeficiente de x⁵ en (2 + 3x)⁸.

24. Encontrar el coeficiente de x³y⁴ en (2x - 4y)⁷.

25. Demostrar que jC(n, j) = nC(n - 1, j - 1) para n, j = 1, 2, ...

26. Dar las demostraciones algebraicas y combinacionales de la siguiente identidad: si m, n, y k son enteros positivos, entonces

_{j = 0, ..., k} C(m, j) C(n, k - j) = C(n + m, k).

Sugerencia: Para el argumento combinacional,  suponga que un comité de tamaño k es elegido de un grupo de n + m personas, constituido por n mujeres y m hombres. Contar el número de comités con j hombres y k - j mujeres y calcular j.

27. Dar las demostraciones algebraicas y combinacionales de la siguiente identidad: si n y N son enteros no negativos y n N entonces 

_{j = n, n + 1, ..., N} C(j, n) = C(N + 1, n + 1).

Sugerencia: Para el argumento combinacional, suponga que escogemos un subconjunto de tamaño n + 1 del conjunto {1, 2, ..., N + 1}. Para j = n, n + 1, ..., N, contar el número de subconjuntos en los cuales el mayor elemento es j + 1 y calcular j.

Para una versión aún más general de la identidad en el Ejercicio 27, vea la sección  Estadística de Orden en el capítulo Modelos de Muestreo Finito. 

28. Establecer los siguientes casos especiales de la identidad en el ejercicio previo.

1. La identidad básica en el Ejercicio 20.
2. 1 + 2 + ··· + N = (N + 1)N / 2.

29. En la canción The Twelve Days of Christmas, encontrar el número de regalos dados al cantante por su verdadero amor. Sugerencia: Use la identidad en el Ejercicio 27 dos veces.

Muestras Desordenadas Con Reemplazos

30. Demostrar que hay una correspondencia uno a uno entre cada par de las siguientes colecciones:

1. Muestras desordenadas de tamaño k elegidas con reemplazo de una población D de n elementos.
2. Secuencias distinguibles de longitud n + k - 1 de un alfabeto de dos letras (decir {*, /}) donde * ocurre k veces y / ocurre n - 1 veces.
3. Soluciones enteras no negativas de x₁ + x₂ + ··· + x_n = k.

31. Demostrar que cada una de las colecciones en el Ejercicio 19 tiene C(n + k - 1, k) elementos.

32 Suponga que 20 caramelos iguales se reparten a 4 niños. ¿Cuántas distribuciones hay si 

1. No hay restricciones.
2. Cada niño debe obtener al menos un caramelo.

33. Suponga que son arrojados 5 dados idénticos. ¿Cuántos resultados hay?

34. ¿Cuántas soluciones enteras de x₁ + x₂ + x₃ = 10 hay si

1. x_i  > = 0 para cada i.
2. x_i > 0 para cada i.

Resumen de Fórmulas de Muestreo

La siguiente tabla resume las fórmulas para el número de muestras de tamaño k elegidas de una población de n elementos, basada en el criterio de orden y reemplazo.

35. Calcular explícitamente cada fórmula en la tabla de arriba cuando n = 10 y k = 4.

El Coeficiente Binomial Generalizado

La fórmula C(n, k) = (n)_k / k! tiene sentido para cualquier número real n y entero no negativo k, ya que esto es verdadero por la fórmula de permutación generalizada (n)_k. Con esta extensión, C(n, k) es llamado el coeficiente binomial generalizado.

36. Calcule cada uno de los siguientes

1. C(1 / 2, 3)
2. C(-5, 4)
3. C(-1 / 3, 5)

37. Demostrar que si n y k son enteros no negativos entonces

C(-n, k) = (-1)^k C(n + k - 1, k).

En particular, note que C(-1, k) = (-1)^k.

Laboratorios Virtuales > Combinatorias > 1 2 [3] 4 5
Contenidos | Aplicaciones | Conjuntos de Datos | Biografías | Recursos | Palabras Claves | ©