Combinatorias – Procesos Estocásticos

Referencia: León-García p.42, Gubner p.35, Ross p.10

Combinatorias es el estudio de metodos sistemáticos de conteo, las cuatro clases de problemas principales son:

Muestreo ordenado con reemplazo
Muestreo ordenado sin reemplazo
Muestreo no ordenado sin reemplazo
Muestreo no ordenado con reemplazo

Muestreo ordenado con reemplazo

Se llaman variaciones con repetición de m elementos tomados de n en n, a los diferentes grupos que pueden formarse con los m elementos dados, tomados de n en n.
Dos grupos pueden ser distintos entre si, si tienen diferentes elementos en diferente orden.

El número de posibles k-tuplas en distinto orden (x₁x₂x₃… x_k) con elementos x_i de un grupo de n_i elementos diferentes es:

número de k-tuplas en orden distinto = n₁n₂n₃… n_k

Ejemplo : Posibles rutas para un paquete de internet

León-García E2.15 p.42.
Una urna tiene cinco pelotas numeradas de 1 al 5. Suponga que se sacan dos pelotas de la urna con reemplazo.

– ¿Cuántos pares diferentes de se pueden obtener?

pares diferentes = 5 * 5 = 5² = 25 pares diferentes

– ¿Cuál es la probabilidad que en se repitan las pelotas?

las formas de repetir son (1,1),(2,2),(3,3),(4,4) y (5,5), en total 5 de un total de 25 pares diferentes, por lo que la probabilidad será 5/25 = 1/5 = 0.20

Muestreo ordenado sin reemplazo

Se seleccionan k elementos en sucesi{on sin reemplazo de una población A de n elementos diferentes. Con k≤n, la primera vez se pueden escoger n₁=n elementos diferentes, la segunda n₂=n-1, la tercera n₃=n-2, … en la última n_k=n-(k-1)

número de k-tuplas en orden distinto = n(n-1)(n-2)…(n-k+1)

n(n-1)(n-2)...(n-k+1) = \frac{n!}{(n-k)!}

Ejemplo :

León-García E2.17 p.43.
Una urna tiene cinco pelotas numeradas de 1 al 5. Suponga que se sacan tres pelotas sin reemplazo .

– ¿Cuántos tripletas diferentes de se pueden obtener?

tripletas diferentes = 5 * 4 * 3 = 60 formas diferentes

(5!)/(5-3)! = 5!/2! = 5*4*3*(2!)/2! =5*4*3 = 60 formas diferentes

import scipy.special as sts

sts.perm(5,3)

60.0

Muestreo no ordenado sin reemplazo

Se sacan k elementos de un grupo A de n objetos diferentes sin reemplazo, y que se escriben los resultados sin importar e orden. Sería como colocarlos en otro conjunto B, el orden deja de importar.

En el nuevo conjunto B, existen k! formas ordenadas de seleccionar los objetos, y C_kⁿ será el valor buscado de las combinaciones de tamaño k del conjunto A de n elementos.

C_k^n k! = n(n-1)(n-2)...(n-k+1) =

= \frac{n!}{(n-k)!}

que simplificando se convierte el «coeficiente binomial» y se lee «de n toma k elementos»:

C_k^n = \frac{1}{n!} \frac{k!}{(n-k)!} = \left( \begin{array}{c} n \\ k \end{array} \right)

da lo mismo escoger k elementos del conjunto A, que dejar n-k elementos en el conjunto, por lo que:

\left( \begin{array}{c} n \\ k \end{array} \right) =\left( \begin{array}{c} n \\ n-k \end{array} \right)

Ejemplo :

Gubner E 1.38 p.38.

Se requiere conformar un jurado de 12 personas seleccionados de un total de 20 jueces. ¿Cuántas formas posibles existen para conformar el jurado?. No importa el orden.

\left( \begin{array}{c} 20 \\ 12 \end{array} \right) = \frac{20!}{12!8!} = 125970

import scipy.special as sts

sts.comb(20,12,repetition=False)

125970.0

Muestreo no ordenado con reemplazo

Se toman k objetos de un grupo de n objetos diferentes con reemplazo, se escribe el resultado sin importar el orden.

\left( \begin{array}{c} n-1+k \\ k \end{array} \right) = \left( \begin{array}{c} n-1+k \\ n-1 \end{array} \right)

Ejemplo : Dispensadora de frutas

(Gubner Ej 1.38 )

En una maquina dispensadora automática se entregan manzanas, bananas y peras. Por un precio fijo, se puden obtener cinco frutas seleccionadas por el cliente.

El proceso se maneja electrónicamente con una secuencia de 7 bits que los ceros (0) representan las manzanas, bananas y peras en orden y se separan por un bit uno (1) como en el ejemplo:

0100100 son un manzana, dos bananas y dos peras.

El primer grupo de 0’s es manzanas, el segundo grupo de 0’s son bananas y el grupo final de 0’s son peras.
¿Cuántas opciones tienen los clientes?

Solución: Equivale a preguntar cuántas secuencias de 7 bits hay con cinco ceros y dos unos.

\left( \begin{array}{c} 7 \\ 5,2 \end{array} \right) = \left( \begin{array}{c} 7 \\ 5 \end{array} \right) =\left( \begin{array}{c} 7 \\ 2 \end{array} \right)

import scipy.special as sts

c1 = sts.comb(7,2)
c2 = sts.comb(7,5)

print(c1)
print(c2)

21.0
21.0