Variaciones con repetición

Las variaciones con repetición se parecen a las variaciones clásicas; solo permitimos que los elementos del conjunto de partida M puedan repetirse.

Definición y fórmula

Empecemos con un ejemplo clásico: ¿cuántas palabras distintas podemos formar con las letras del alfabeto inglés (abc … xyz, son 26) si la palabra ha de tener longitud 6? Seis letras no son muchas, pero aun así habrá bastantes palabras. No nos interesa el significado de las palabras, así que también «weqrww» la consideramos una palabra válida de longitud seis.

Para el cálculo solo necesitamos conocer el principio de multiplicación. Tenemos en total 26 letras distintas que podemos usar. En el primer lugar podemos poner, por tanto, una de las 26 letras. En el segundo lugar también podemos poner una de las 26 letras, porque no hemos impuesto la condición de que las letras no se repitan. De ahí llegamos a que en cada posición elegimos entre 26 letras y el número total de variaciones es, según el principio de multiplicación, 26⁶ = 308.915.776. Es bastante, teniendo en cuenta que solo hemos usado 26 letras.

Diremos que una variación con repetición de k elementos de un conjunto M de tamaño n es toda k-upla ordenada cuyos elementos pertenecen al conjunto M y en la que cada elemento puede aparecer hasta k veces. Si tenemos, pues, el conjunto M = {1, 2, 3}, todas estas son variaciones con repetición válidas de 4 elementos: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3). El número de estas variaciones con repetición, que se denota VR_n,k, es igual a

$$V{R}_{n,k}=n^k.$$

Ejercicios resueltos

1. ¿Cuántos números de seis cifras se pueden formar con las cifras {2, 4, 6, 8} si las cifras pueden repetirse? Basta sustituir en la fórmula: el conjunto tiene tamaño 4 y elegimos séxtuplas:

   $$V{R}_{4,6}=4^6=4096.$$

2. En los ordenadores se usa habitualmente el sistema de numeración binario, es decir, un sistema que utiliza solo las cifras 0 y 1. Se introducen allí nuevas unidades; por ejemplo, un bit representa una especie de celda en la que se guarda exactamente un cero o un uno. Más grande es el byte, que contiene 8 bits. Así, 1 es un bit, mientras que 01110001 es un byte. ¿De cuántas formas distintas se puede llenar un byte con 8 bits?

   Elegimos del conjunto {0, 1}, es decir, de dos elementos. Elegimos una k-upla de tamaño k = 8, así que el número de todas las posibilidades es igual a

   $$V{R}_{2,8}=2^8=256.$$

3. Del ejemplo anterior sabemos que un byte puede distinguir hasta 256 valores distintos. ¿De cuántas formas se pueden llenar 4 bytes?

   Cuatro bytes contienen 4 · 8 = 32 bits y seguimos eligiendo de un conjunto de tamaño 2. Por tanto, el resultado es:

   $$V{R}_{2,32}=2^{32}=4.294.967.296.$$

   Vemos que solo cuatro bytes pueden distinguir más de cuatro mil millones de valores. Para hacernos una idea: los ordenadores de hoy tienen discos de cientos de gigabytes o directamente de terabytes. Un terabyte contiene 1.000.000.000.000 bytes y, por tanto, 8.000.000.000.000 bits. En un disco de un terabyte podemos, pues, guardar hasta 2^{8.000.000.000.000} valores distintos.

   Nota: actualmente hay cierta confusión con el término kilobyte (megabyte, etc.). Por razones tecnológicas, un kilobyte no contenía 1000 bytes, como es habitual en las demás unidades (un kilogramo equivale a mil gramos), sino que un kilobyte era igual a 2¹⁰ bytes, es decir, 1024 bytes. Un megabyte era entonces 2²⁰ bytes o también 2¹⁰ kilobytes.

   Hoy distinguimos, por tanto, dos tipos de notación: 1 kB (se lee kilobyte) son 1000 bytes y 1 KiB (se lee kibibyte) son 2¹⁰ = 1024 bytes.

4. Otro ejemplo se encuentra en un artículo aparte dedicado a la seguridad de las contraseñas.