|
1.2 - Il “primo principio” del C.C. |
|||
|
|
|||
|
Quante parole (anche prive di senso: insomma, quante “sequenze”, quante “stringhe”) di 3 lettere possono essere composte 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 tanti altri problemi di questo tipo, immaginiamo di SCRIVERE effettivamente tutte queste stringhe di tre lettere. Scriviamole, poi le conteremo. Evidentemente, per evitare confusione, omissioni o ripetizioni, dovremo seguire un certo ordine, un certo schema nel "mettere giù" tutte queste stringhe. Per esempio, potremmo stilare un "grafo ad albero" come il seguente:
|
|||
|
|
|
||
|
|
“Stringa” significa: “sequenza di caratteri” |
|
|
|
|
|||
|
|
|||
|
|
|||
|
|
|||
|
|
|||
|
|
|||
|
|
|||
|
|
|||
|
|
|||
|
|
|||
|
Nel tracciare il grafo, si deve considerare innanzitutto il ventaglio di opzioni che si apre per la prima lettera. Per la prima lettera si hanno 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
E per ognuna di queste si aprirà un ventaglio di 5 possibilità per la terza lettera, per cui in definitiva avremo
Risposta: le stringhe di 3 lettere costruibili utilizzando solo le vocali sono 125.
|
|||
|
q Problema 2 Quante sono le stringhe di 7 lettere costruibili utilizzando tutte le 21 lettere dell'alfabeto italiano?
|
|||
|
Pensiamo ancora ad un "albero" come il precedente. Ovviamente, non staremo a completarlo! Vogliamo solo fissare bene in mente le modalità con cui il diagramma potrebbe, avendo tempo e pazienza, essere compilato.
[grafo ad albero (non è qui, ma è nella tua mente… )]
Risposta: le stringhe di 7 lettere
che si possono costruire con le 21 lettere dell'alfabeto italiano sono
(se calcoli questo numero con la macchinetta, troverai che supera 1 miliardo e 800 milioni).
|
|||
|
q Problema 3 Quante stringhe di 3 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 problema 1) si modificherà perdendo qualche ramo; immagina di tracciare il nuovo albero, o, meglio, traccialo realmente, sul tuo quaderno!
Risposta:
Ricapitoliamo il ragionamento: abbiamo 5 possibilità per la prima lettera della stringa; a ciascuna di queste 5 possibilità sono abbinate 4 possibilità per la seconda lettera (quindi, per le prime due
lettere abbiamo e per ciascuna di
queste In definitiva, abbiamo
|
|||
|
q Problema 4 Quante sono le stringhe di 7 lettere costruibili utilizzando tutte le 21 lettere dell'alfabeto italiano, ma “senza ripetizione”, cioè col vincolo di non utilizzare una lettera più di una volta nella stessa stringa?
|
|||
|
Risposta:
|
|||
|
q Problema 4' Quante sono le stringhe di 7 lettere costruibili utilizzando tutte le 21 lettere dell'alfabeto italiano, ma “senza consecutività”? (Quindi, “abbcdef” sarebbe vietata, ma andrebbe invece bene “abababa”)
|
|||
|
Risposta:
|
|||
|
La risoluzione "col metodo del diagramma ad albero" dei problemi 1) ... 4') mostra che vale il seguente
|
|||
|
PRIMO PRINCIPIO GENERALE DEL CALCOLO COMBINATORIO
Se una scelta può essere fatta in r modi diversi, per ognuno 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
modi diversi
(traduzione dal testo americano "Introduction to Finite Maths" di Kemeny-Snell-Thompson)
|
|||
