Page 27 - cepe2012.pdf
P. 27
i i
“cepeMathBookFC” — 2012/12/11 — 19:57 — page 17 — #21
i i
3. AN ´ ALISIS COMBINATORIO 17
n objetos k objetos
Urna Muestra
FIGURA 1.8
escogido y lo regresamos a la urna, de esta forma el mismo objeto puede ser extra´ ıdo
varias veces. El total de arreglos que se pueden obtener de esta urna al hacer k ex-
k
tracciones es el n´ umero n , pues en cada extracci´ on tenemos n objetos posibles para
escoger y efectuamos k extracciones. Esta f´ ormula es consecuencia del principio de
multiplicaci´ on enunciado antes. A este n´ umero se le llama ordenaciones con repetici´ on.
Se dice que la muestra es con orden pues es importante el orden en el que se van obte-
niendo los objetos, y es con reemplazo pues cada objeto seleccionado se reincorpora a
la urna.
EJEMPLO 1.20. Suponga que tenemos un conjunto de 60 caracteres diferentes.
Este conjunto contiene todas las letras min´ usculas del alfabeto, las letras may´ usculas,
los diez d´ ıgitos y algunos caracteres especiales. ¿Cu´ antos passwords o palabras clave
de longitud 4 se pueden construir usando este conjunto de 60 caracteres? Este es un
ejemplo de una ordenaci´ on de 60 caracteres en donde se permiten las repeticiones.
Como cada car´ acter de los 60 disponibles puede ser escogido para ser colocado en
cada una de las cuatro posiciones de la palabra clave, entonces se pueden construir
4
60 60 60 60 D 60 D 12; 960; 000 distintos passwords de longitud 4.
Ordenaciones sin repetici´ on: muestras con orden y sin reemplazo
Suponga que se tiene la misma situaci´ on que antes, una urna con n objetos y de los
cuales se deben extraer, uno a uno, k objetos. Suponga esta vez que el muestreo es
sin reemplazo, es decir, una vez seleccionado un objeto ´ este ya no se reincorpora a la
urna. El total de arreglos distintos que se pueden obtener de este modo es el n´ umero:
n.n 1/.n 2/ .n k C 1/. Primeramente debemos observar que hay k factores en
la expresi´ on anterior. El primer factor es n y ello es debido a que tenemos cualesquiera
de los n objetos para ser colocado en primera posici´ on, para la segunda posici´ on
tenemos ahora n 1 objetos, para la tercera n 2 objetos, y as´ ı sucesivamente. Este
razonamiento termina al escoger el k-´ esimo objeto para el cual tenemos ´ unicamente
n k C 1 posibilidades. Nuevamente por el principio de multiplicaci´ on, la respuesta
i i
i i