CALCOLO COMBINATORIO
Il problema di trasmettere messaggi segreti è molto antico: è sempre stato importante soprattutto in ambito militare per permettere ai diversi eserciti di comunicare senza essere intercettati.
Durante la Seconda Guerra Mondiale la Germania utilizzò un nuovo codice per poter comunicare ai propri soldati i messaggi. Ciò fu possibile grazie alla macchina Enigma che mise da subito alla prova le capacità di decifraggio degli Alleati.
A Bletchley Park, i Britannici raggrupparono l'eccellenza delle menti per risolvere il complicato cifrario utilizzato. Questi si trovarono davanti ad una missione davvero complessa. Studiando lo strumento utilizzato dai tedeschi si potè calcolare la quantità di collegamenti possibili di lettere.
Per calcolare ciò si utilizzò il calcolo combinatorio.
​
Si intende "CALCOLO COMBINATORIO" quella branca della Matematica che studia i modi di raggruppare ed ordinare oggetti presi da un insieme assegnato, con l'obbiettivo finale di contare il numero dei possibili raggruppamenti od ordinamenti.
​
Esempio: quante parole di tre lettere possono essere scritte utilizzando solo le cinque vocali? (es. aoe, iii, uaa...)
Per rispondere a questa domanda, e soprattutto per acquisire un metodo di ragionamento che ci servirà in molti altri problemi di questo tipo, pensiamo di scrivere EFFETTIVAMENTE tutte queste parole di tre lettere.
Evidentemente, per evitare confusione, omissioni o ripetizioni, dovremo seguire un certo ordine, un certo schema nel "mettere giù" tutte queste parole.
Per esempio, si può stilare un "grafo ad albero":
Evidentemente, per la prima lettera abbiamo 5 possibilità che sono quelle elencate in prima colonna (a, e, i, o, u).
Poi, ad ognuna di queste 5 possibilità si possono abbinare 5 possibilità per la seconda lettera della parola.
In totale, per le prime due lettere, abbiamo 5 * 5= 25 possibilità (aa, ae, ai, ao, au, ea, ...).
E ad ognuna di queste 5 * 5 possibilità per le prime due lettere. potremo abbinare 5 possibilità per la terza lettera. In definitiva avremo 5 * 5 * 5 = 125 possibilità (aaa, aae, aai, ...).
Risposta: le parole di tre lettere costruibili utilizzando solo le vocali sono 125.
Si parla di "DISPOSIZIONI CON RIPETIZIONE" quando uno stesso oggetto, nella k-upla ordinata,
può essere ripetuto più di una volta. In questo caso, non dev'essere necessariamente k≤n.
​
II numero delle disposizioni con ripetizione di n oggetti, presi a k a k, si indica col simbolo ed è facile dimostrare, col Primo Principio Generale, che si ha
PRIMO PRINCIPIO GENERALE: Se una scelta può essere fatta in r modi diversi, per ciascuno dei quali
una seconda scelta può essere effettuata in s modi diversi, e, per ciascuno dei modi in cui si sono
compiute le prime due scelte, una terza scelta può essere effettuata in t modi diversi ecc.,
allora la successione di tutte le scelte può essere compiuta in r*s*t modi diversi.
​
Esempio: quante parole di tre lettere possono essere scritte utilizzando solo le cinque vocali, ma senza ripetizione? (es. aoe, uao, aei, MA NON iii, uaa, eie, )
E‘ chiaro che l'albero relativo al primo esempio si modificherà perdendo qualche ramo.
​
​
​
​
​
​
​
​
Risposta: 5 * 4 * 3 = 60
​
Utilizzando il calcolo Combinatorio i ricercatori calcolarono oltre 158 milioni di milioni di milioni di possibili combinazioni per trovare la chiave di lettura della macchina Enigma. Dato impensabile da coprire con il lavoro di soli uomini che avrebbero impiegato anni per risolvere un codice che ogni ventiquattro ore veniva cambiato.
