Arranjos com repetição

Os arranjos com repetição são parecidos com os arranjos clássicos, só que permitimos que os elementos do conjunto base M se repitam.

Definição e fórmula

Vamos começar com um exemplo clássico: quantas palavras diferentes conseguimos formar com as letras do alfabeto (abc … xyz, são 26), se a palavra deve ter comprimento 6? Seis letras não é muito, mas mesmo assim haverá muitas palavras. Não nos interessamos pelo significado das palavras, então até “weqrww” vale como palavra válida de comprimento seis.

Para calcular, só precisamos conhecer o princípio multiplicativo. Temos 26 letras diferentes que podemos usar. Na primeira posição podemos colocar uma das 26 letras. Na segunda posição também podemos colocar uma das 26 letras, porque não impusemos a condição de que as letras não podem se repetir. Assim, em cada posição escolhemos entre 26 letras, e o número total de arranjos é, pelo princípio multiplicativo, 26⁶ = 308.915.776. É bastante coisa para termos usado só 26 letras.

Dizemos que um arranjo com repetição de k elementos de um conjunto M com n elementos é toda k-upla ordenada cujos elementos pertencem ao conjunto M e em que cada elemento pode aparecer na k-upla até k vezes. Se temos o conjunto M = {1, 2, 3}, então todos estes são arranjos com repetição válidos de 4 elementos: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3). O número desses arranjos com repetição, que denotamos por (AR)_n,k, é igual a

$$(AR{)}_{n,k}=n^k.$$

Exercícios resolvidos

1. Quantos números de seis algarismos podem ser formados com os algarismos {2, 4, 6, 8}, se os algarismos podem se repetir? Basta substituir na fórmula: o conjunto tem 4 elementos e escolhemos sêxtuplas:

   $$(AR{)}_{4,6}=4^6=4096.$$

2. Nos computadores, normalmente se usa o sistema de numeração binário, isto é, um sistema que usa apenas os algarismos 0 e 1. Nele são introduzidas novas unidades; por exemplo, um bit representa uma espécie de célula em que se guarda exatamente o zero ou o um. Maior é o byte, que contém 8 bits. Assim, 1 é um bit, enquanto 01110001 é um byte. De quantas maneiras diferentes é possível preencher um byte com 8 bits?

   Escolhemos do conjunto {0, 1}, isto é, de dois elementos. Escolhemos uma k-upla com k = 8, então o número de todas as possibilidades é igual a

   $$(AR{)}_{2,8}=2^8=256.$$

3. Do exercício anterior sabemos que um byte consegue distinguir até 256 valores diferentes. De quantas maneiras é possível preencher 4 bytes?

   Quatro bytes contêm 4 · 8 = 32 bits, e continuamos escolhendo de um conjunto com 2 elementos. Então o resultado é:

   $$(AR{)}_{2,32}=2^{32}=4.294.967.296.$$

   Vemos que apenas quatro bytes conseguem distinguir mais de quatro bilhões de valores. Para você ter uma ideia: os computadores de hoje têm discos com centenas de gigabytes ou até terabytes. Um terabyte contém 1.000.000.000.000 bytes e, portanto, 8.000.000.000.000 bits. Em um disco de um terabyte conseguimos, então, guardar até 2^{8.000.000.000.000} valores diferentes.

   Observação: atualmente há certa confusão com o termo quilobyte (megabyte etc.). Por razões tecnológicas, um quilobyte não continha 1.000 bytes, como é costume nas outras unidades (um quilograma é igual a mil gramas), mas era igual a 2¹⁰ bytes, ou seja, 1024 bytes. Um megabyte era, então, 2²⁰ bytes ou também 2¹⁰ quilobytes.

   Hoje em dia distinguimos duas notações: 1 kB (lê-se quilobyte) são 1.000 bytes e 1 KiB (lê-se kibibyte) são 2¹⁰ = 1024 bytes.

4. Outro exemplo está em um artigo separado, sobre a segurança de senhas.