Combinatorias

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:

  1. Muestreo ordenado con reemplazo
  2. Muestreo ordenado sin reemplazo
  3. Muestreo no ordenado sin reemplazo
  4. 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 (x1x2x3… xk) con elementos xi de un grupo de ni elementos diferentes es:

número de k-tuplas en orden distinto = n1n2n3… nk

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 = 52 = 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 n1=n elementos diferentes, la segunda n2=n-1, la tercera n3=n-2, … en la última nk=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 Ckn 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