Disposizioni con ripetizione

Le disposizioni con ripetizione somigliano alle disposizioni semplici, solo che permettiamo che gli elementi dell’insieme di partenza M si ripetano.

Definizione e formula

Cominciamo da un esempio classico: quante parole diverse possiamo formare con le lettere dell’alfabeto inglese (abc … xyz, sono 26), se la parola deve essere lunga 6 lettere? Sei lettere non sono molte, eppure le parole saranno parecchie. Non ci interessa il significato delle parole, quindi anche «weqrww» la consideriamo una parola valida di lunghezza sei.

Per il calcolo ci basta conoscere il principio del prodotto. Abbiamo in tutto 26 lettere diverse da usare. Al primo posto possiamo mettere una delle 26 lettere. Anche al secondo posto possiamo mettere una delle 26 lettere, perché non abbiamo posto la condizione che le lettere non si possano ripetere. Così arriviamo a dire che in ogni posizione scegliamo tra 26 lettere e il numero totale di disposizioni è, per il principio del prodotto, 26⁶ = 308.915.776. È parecchio, considerando che abbiamo usato solo 26 lettere.

Diciamo che una disposizione con ripetizione di classe k di un insieme M di n elementi è ogni k-upla ordinata i cui elementi appartengono all’insieme M e in cui ogni elemento può comparire fino a k volte. Se quindi abbiamo l’insieme M = {1, 2, 3}, queste sono tutte disposizioni con ripetizione di classe 4 valide: (1; 1; 1; 1), (1; 2; 3; 1), (2; 2; 3; 3). Il numero di tali disposizioni con ripetizione, che indichiamo con D'_n,k, è allora uguale a

$$D_{n,k}^{\prime }=n^k.$$

Esercizi svolti

1. Quanti numeri di sei cifre si possono formare con le cifre {2, 4, 6, 8}, se le cifre possono ripetersi? Basta sostituire nella formula: l’insieme ha 4 elementi e scegliamo sestuple:

   $$D_{4,6}^{\prime }=4^6=4096.$$

2. Nei computer si usa normalmente il sistema di numerazione binario, cioè un sistema che usa solo le cifre 0 e 1. Vi si introducono nuove unità: ad esempio un bit è una specie di cella in cui si memorizza esattamente uno zero oppure un uno. Più grande è il byte, che contiene 8 bit. Quindi 1 è un bit, mentre 01110001 è un byte. In quanti modi diversi si può riempire un byte con 8 bit?

   Scegliamo dall’insieme {0, 1}, cioè da due elementi. Scegliamo una k-upla con k = 8, quindi il numero di tutte le possibilità è uguale a

   $$D_{2,8}^{\prime }=2^8=256.$$

3. Dall’esercizio precedente sappiamo che un byte può distinguere fino a 256 valori diversi. In quanti modi si possono riempire 4 byte?

   Quattro byte contengono 4 · 8 = 32 bit e scegliamo sempre da un insieme di 2 elementi. Il risultato è quindi:

   $$D_{2,32}^{\prime }=2^{32}=4.294.967.296.$$

   Vediamo che appena quattro byte riescono a distinguere più di quattro miliardi di valori. Per farti un’idea: i computer di oggi hanno dischi da centinaia di gigabyte o addirittura da terabyte. Un terabyte contiene 1.000.000.000.000 byte e quindi 8.000.000.000.000 bit. Su un disco da un terabyte possiamo quindi memorizzare fino a 2^{8.000.000.000.000} valori diversi.

   Nota: oggi c’è una certa confusione sul significato di kilobyte (megabyte ecc.). Per ragioni tecnologiche un kilobyte non conteneva 1000 byte, come è consuetudine nelle altre unità (un chilogrammo è uguale a mille grammi), ma un kilobyte era uguale a 2¹⁰ byte, cioè 1024 byte. Un megabyte era poi 2²⁰ byte, ovvero 2¹⁰ kilobyte.

   Oggi distinguiamo quindi due tipi di notazione: 1 kB (si legge kilobyte) sono 1000 byte e 1 KiB (si legge kibibyte) sono 2¹⁰ = 1024 byte.

4. Un altro esempio si trova nell’articolo a parte dedicato alla sicurezza della password.