A) = #(A) / #(S) para A 
S.Laboratorios Virtuales > Combinatorias > [1] 2 3 4 5
Si una variable aleatoria X para un experimento está uniformemente distribuida sobre un subconjunto finito S, entonces la distribución de probabilidad de X es proporcional a calcular la medida de:
P(X A) = #(A) / #(S) para A S.
Tales variables aleatorias surgen frecuentemente de muchos experimentos diferentes, particularmente de aquellos que pueden ser interpretados como muestra de un conjunto finito. El conjunto S es típicamente muy grande, por lo tanto, son esenciales los métodos eficientes para contar. El primer problema combinacional es atribuido al matemático griego Xenocrates.
En muchos casos, un conjunto de objetos puede ser contado estableciendo una correspondencia uno a uno entre el conjunto dado y algún otro conjunto. Naturalmente, los dos conjuntos tienen el mismo número de elementos, pero por alguna razón, el segundo conjunto puede ser mas fácil de contar.
La regla de suma de combinatorias simplemente es el axioma de sumabilidad de medir contando. Si A1, A2, ..., An son subconjuntos separados de un conjunto finito S entonces
#(A1 
A2 ··· An) = #(A1)
+ #(A2) + ··· + #(An)
Recordar también que las reglas de probabilidad básicas tienen análogos por medir contando. La más importante de éstas están dadas en los ejercicios siguientes:
1. Demostrar
que #(Ac) = #(S) - #(A)
2. Demostrar
que #(B 
Ac)
= #(B) - #(A B).
3. Demostrar
que si A B
entonces #(B
Ac) = #(B) - #(A).
4. Demostrar
que #(A B) = #(A) + #(B) - #(A B).
5. Demostrar
que
#(A B C) = #(A) + #(B) + #(C) - #(A
B) - #(A
C) - #(B
C) + #(A
B C).
Los Ejercicios 11 y 12 pueden ser generalizados a una unión de n eventos Ai, i = 1, 2, ...n; la generalización es conocida como la fórmula inclusión -exclusión. Para simplificar la formulación, permita a N denotar el conjunto índice: I = {1, 2, ..., n} y definir
nJ = # [
j
en J Aj] para J N,
mk = 
{J: #(J) = k}
nJ para k N.
6. Demostrar
que # [
i = 1, ..., n Ai] = k =
1, ..., n (-1)k - 1 mk.
n1 n2 ··· nk.
La clave para una aplicación exitosa de la regla de multiplicación a un problema de cuenta es la formulación clara de un algoritmo que genera los objetos siendo contados, para que cada objeto se genere solo una vez. Es decir, no debemos contar por encima ni por debajo.
Los dos primeros ejercicios de abajo dan formulaciones equivalentes del principio de multiplicación.
7. Suponga
que S es un conjunto de secuencias de longitud k, y que indicamos
los elementos de S por
(x1, x2, ..., xk)
Suponga que por cada j, xj tiene nj valores diferentes, sin tener en cuenta los valores de las coordenadas anteriores. Demostrar que la cardinalidad de A es
n1 n2 ··· nk.
8. Suponga
que T es un árbol ordenado con profundidad k y que cada vértice al
nivel i - 1 tiene ni chicos para i = 1, 2,
..., k. Demostrar que el número de vértices al nivel k es
n1 n2 ··· nk.
9. Un número de licencia consiste de dos letras (mayúsculas)
seguidas de cinco dígitos.
10. Suponga que un Número de Identificación Personal (NIP)
es una palabra código de cuatro símbolos en que cada entrada es una letra (mayúscula) o
un dígito.
11. En el juego de mesa Clue,
Mr. Boddy ha sido asesinado. Hay 6 sospechosos, 6 posibles armas, y 9 posibles cuartos
para el asesinato.
12. Suponga
que Si es un conjunto con ni elementos para i
= 1, 2, ..., k. Demuestre que
#(S1 × S2 × ··· × Sn ) = n1 n2 ··· nk.
En particular, si Si es el espacio muestral del experimento Ei, entonces este producto da el número de resultados en el experimento compuesto que cosiste de realizar E1, ..., Ek en secuencia.
13. Un experimento consiste de arrojar un dado no cargado,
elegir una carta de un mazo estándar, y arrojar una moneda no cargada.
14.
Demostrar que si S es un conjunto con m elementos, entonces Sn
tiene mn elementos.
En particular, si un experimento básico tiene m respuestas, entonces el experimento compuesto que consiste de n replicas del experimento básico tiene mn respuestas.
15. Un dado no cargado es arrojado 5 veces y la secuencia
escores es grabadas.
16.
Demostrar que el número de muestras ordenadas de tamaño n que pueden ser
elegidas con reemplazos desde una población de m objetos es mn.
17. Suponga que 10 personas son elegidas al azar y sus
cumpleaños registrados.
18.
Demostrar que el número de funciones de un conjunto A de n
elementos en un conjunto B de m elementos es mn.
Los elementos de {0,1}n son algunas veces llamados secuencias de bits de longitud n. El resultado del experimento que consiste de n ensayos de Bernoulli es una secuencia de bits de longitud n.
19.
Demostrar que el número de secuencias de bits de longitud n es 2n.
20. Una moneda no cargada es arrojada 10 veces.
21. Una secuencia de luces tiene 20 bombillas, cada una de las
cuales puede ser buena o defectuosa.¿Cuantas configuraciones hay?
22. El experimento del dado-moneda consiste de arrojar un dado
y entonces tirar una moneda el número de veces que muestra el dado. La secuencia de los
resultados de la moneda es registrada.
23. Ejecute el experimento del
dado-moneda 1000 veces, actualizando cada 10 ejecuciones. Compare la probabilidad
empírica que todas tiradas de la moneda son caras con la verdadera probabilidad del
ejercicio anterior.
La Tabla de Galton, nombrada por Francis Galton, es un arreglo triangular de marcas (Galton llamó el dispositivo un quincunx). Las filas se numeran, desde la superior hacia abajo, por 0,1,... La fila k tiene k + 1 marcas que son etiquetadas, desde izquierda a derecha por0, 1, ..., i. Así, una marca puede ser identificada únicamente por un par ordenado (i, j) donde i es el número de fila y j es el número de marca en esa fila.
Una bola se deja caer sobre la marca superior (0, 0) de la tabla de Galton. En general, cuando la bola choca la marca (i, j), salta a la izquierda de la marca (i + 1, j) o a la derecha a la marca (i + 1, j + 1). La secuencia de marcas que la bola choca es un camino en la tabla de Galton.
24.
Demostrar que hay una correspondencia uno a uno entre cada par de las siguientes tres
colecciones:
Así, del ejercicio anterior, cada una de estas colecciones tiene 2n elementos. En particular, un experimento con n resultados tiene 2n eventos.
25. En el juego de la tabla
de Galton, mueva la bola de (0, 0) a (10, 6) a lo largo de un camino de su elección.
Note la secuencia de bits y el subconjunto correspondientes.
26. En el juego de la tabla
de Galton, genere la secuencia de bits 011100101. Note el subconjunto y camino
correspondientes.
27. En el juego de la tabla
de Galton, genere el subconjunto {2, 4, 5, 9, 12}. Note la secuencia de bits y el
camino correspondientes.
28. En el juego de la tabla
de Galton, genere todos los caminos desde (0, 0) a (4, 2). ¿Cuantos caminos hay?
29. Suponga
que A1, A2, ..., Ak son
eventos de un experimento aleatorio. Demostrar que hay 2^(2k)
diferentes eventos (en general) que pueden ser construidos desde los k eventos
dados, usando las operaciones de unión, intersección, y complemento. Los siguientes
pasos muestran como:
B2 ··· Bk donde Bi es Ai
o Aic para cada i. 30. En la aplicación del diagrama
de Venn, observe el diagrama de cada uno de los 16 eventos que pueden ser construidos
de A y B.
31. Suponga que S es un conjunto con n
elementos y que A es un subconjunto de S con k elementos.
Si un subconjunto aleatorio de S se elige, encuentre la probabilidad que
contenga A.
Las aplicaciones más básicas del principio de multiplicación son para permutaciones y combinaciones. Es también interesante notar que el principio de multiplicación es el análogo de la medida que cuenta de la regla de multiplicación para la probabilidad condicional. Los métodos combinacionales juegan un rol fundamental en el capítulo sobre Modelos de Muestreo Finito.