K-uplets avec répétition

Les k-uplets avec répétition ressemblent aux arrangements, à une différence près : les éléments de l’ensemble de base M peuvent se répéter.

Définition et formule

Commençons par un exemple classique : combien de mots différents peut-on former avec les lettres de l’alphabet (abc … xyz, il y en a 26), si un mot doit avoir une longueur de 6 ? Six lettres, ce n’est pas beaucoup, et pourtant il y aura beaucoup de mots. On ne s’intéresse pas au sens des mots, donc « weqrww » est aussi un mot valide de six lettres.

Pour le calcul, il suffit du principe multiplicatif. On dispose de 26 lettres différentes. En première position, on peut donc mettre l’une des 26 lettres. En deuxième position, on peut aussi mettre l’une des 26 lettres, car on ne s’est pas imposé que les lettres ne se répètent pas. Ainsi, à chaque position, on choisit parmi 26 lettres, et le nombre total de possibilités est, par le principe multiplicatif, 26⁶ = 308 915 776. C’est beaucoup, pour seulement 26 lettres.

On appelle k-uplet avec répétition de l’ensemble M de taille n tout k-uplet ordonné dont les éléments sont pris dans M, chaque élément pouvant apparaître plusieurs fois, jusqu’à k fois. Si l’on prend l’ensemble M = {1 ; 2 ; 3}, alors les suivants sont tous des 4-uplets avec répétition valides : (1 ; 1 ; 1 ; 1), (1 ; 2 ; 3 ; 1), (2 ; 2 ; 3 ; 3). Le nombre de tels k-uplets d’un ensemble à n éléments est alors

$$n^k.$$

Exercices corrigés

1. Combien de nombres à six chiffres peut-on former avec les chiffres {2 ; 4 ; 6 ; 8}, si les chiffres peuvent se répéter ?

   Il suffit d’appliquer la formule : l’ensemble a 4 éléments et l’on choisit des 6-uplets.

   $$4^6=4096.$$

2. En informatique, on utilise couramment le système binaire, c’est-à-dire le système qui n’emploie que les chiffres 0 et 1. On y introduit de nouvelles unités : par exemple, un bit est une cellule dans laquelle on range soit 0, soit 1. Plus grand, l’octet (en anglais byte) contient 8 bits. Ainsi, 1 est un bit, tandis que 01110001 est un octet. Combien de façons existe-t-il de remplir un octet avec 8 bits ?

   On choisit dans l’ensemble {0 ; 1}, c’est-à-dire parmi deux éléments, et l’on choisit un 8-uplet, soit k = 8. Le nombre total de possibilités est donc

   $$2^8=256.$$

3. Nous savons d’après l’exemple précédent qu’un octet peut distinguer jusqu’à 256 valeurs différentes. De combien de façons peut-on remplir 4 octets ?

   Quatre octets contiennent 4 · 8 = 32 bits, et l’on choisit toujours dans un ensemble de taille 2. Le résultat est donc :

   $$2^{32}=4294967296.$$

   On voit que quatre octets seulement permettent de distinguer plus de quatre milliards de valeurs. Pour se faire une idée : les ordinateurs d’aujourd’hui ont des disques de plusieurs centaines de gigaoctets, voire de téraoctets. Un téraoctet contient 1 000 000 000 000 octets, soit 8 000 000 000 000 bits. On peut donc stocker sur un disque d’un téraoctet jusqu’à 2^{8 000 000 000 000} valeurs différentes.

   Remarque : il règne actuellement une certaine confusion autour du kilooctet et des multiples suivants. Pour des raisons technologiques, on admettait autrefois qu’un kilooctet ne contient pas 1000 octets, comme c’est l’usage pour les autres unités (un kilogramme vaut mille grammes), mais 2¹⁰ = 1024 octets. Un mégaoctet valait alors 2²⁰ octets, soit 2¹⁰ kilooctets. Aujourd’hui, on distingue donc deux notations : 1 ko (kilooctet) vaut 1000 octets, et 1 Kio (kibioctet) vaut 2¹⁰ = 1024 octets.

4. Un autre exemple se trouve dans un article séparé consacré à la sécurité des mots de passe.