Problemi di Calcolo Combinatorio

Eccoci alla lezione conclusiva di Calcolo Combinatorio, per molti aspetti la più importante: vediamo come fare per risolvere un qualsiasi problema di Calcolo Combinatorio e soprattutto come si fa a capire se usare permutazioni, disposizioni o combinazioni, semplici o con ripetizione.

 

La maggior parte degli studenti trova difficoltà proprio a capire quale sia la formula corretta da utilizzare. Se è così anche per te, vai sereno e continua a leggere: tra poco sarà tutto chiaro!

 

 

Tutte le possibili formule da usare nei problemi di Calcolo Combinatorio

 

Iniziamo innanzitutto col richiamare le formule che ricorreranno nei problemi di Calcolo Combinatorio.

 

Permutazioni semplici di n oggetti distinti:

 

P_n=n!

 

Permutazioni con ripetizione di n oggetti di cui \alpha sono uguali:

 

P_n^{(\alpha)}=\frac{n!}{\alpha !}

 

Disposizioni semplici di n oggetti distinti di classe k:

 

D_{n,k}=\frac{n!}{(n-k)!}

 

Disposizioni con ripetizione di n oggetti distinti di classe k:

 

D'_{n,k}=n^k

 

Combinazioni semplici di n oggetti distinti di classe k:

 

C_{n,k}=\frac{n!}{k!(n-k)!}

 

Combinazioni con ripetizione di n oggetti distinti di classe k:

 

C'_{n,k}=\frac{(n+k-1)!}{k!(n-1)!}

 

Se non l'avete già fatto vi consiglio vivamente di leggere almeno una volta le singole lezioni correlate, che spiegano nel dettaglio le caratteristiche di ogni metodo del Calcolo Combinatorio e che presentano svariati esempi.

 

Come riconoscere la formula da usare

 

Veniamo ora al vivo della lezione. Come capire quale formula usare? Con il seguente schemino arriverete in un batter d'occhio alla soluzione:

 

1) Innanzitutto leggiamo con attenzione il testo del problema ed individuiamo

 

- n (numero totale degli elementi) e

 

- k (numero degli elementi coi quali dobbiamo formare i raggruppamenti)

 

Schema per risolvere problemi di Calcolo Combinatorio

 

Esempi svolti sulla scelta delle formule: permutazioni, combinazioni, disposizioni

 

1) Le targhe automobilistiche sono costituite da 2 lettere, seguite da 3 cifre, seguite a loro volta da 2 lettere. Sapendo che le 2 lettere possono essere scelte fra le 26 dell'alfabeto anglosassone, si calcoli quante automobili si possono immatricolare in questo modo.

 

Svolgimento: come già spiegato dal testo del problema una targa automobilistica ha questa struttura:

 

\mbox{lettera lettera   numero numero numero    lettera lettera}

 

Abbiamo cioè tre tipi di raggruppamenti diversi.

 

Nel primo "\mbox{lettera lettera}" abbiamo k=2 elementi che si possono scegliere tra n=26 elementi distinti (le lettere dell'alfabeto anglosassone)

 

L'ordine ha importanza? , in quanto, due lettere scambiate di posto generano due targhe distinte. Abbiamo a che fare quindi con disposizioni (in quanto k \neq n). 

 

Uno stesso elemento, all'interno di un raggruppamento, può essere ripetuto? , vi sono infatti targhe che iniziano con due lettere uguali

 

Siamo quindi di fronte a disposizioni con ripetizione di classe k. Ne segue che le lettere possono essere raggruppate in:

 

D'_{26,2}=26^2=676

 

modi diversi.


Per quanto riguarda le cifre, esse sono raggruppamenti di k=3 elementi, scelti da un insieme che ne contiene n=10Anche in questo caso l'ordine ha importanza e una stessa cifra può essere ripetuta fino a tre volte. Utilizzeremo quindi le disposizioni con ripetizione da cui:


D'_{10,3}=10^3=1000

 

Avendo tre raggruppamenti (lettere - cifre - lettere) il numero totale delle targhe automobilistiche che si possono formare è dato da:

 

D'_{26,2} \cdot D'_{10,3} \cdot D'_{26,2} = 676 \cdot 1000 \cdot 676 = 456976000

 

 

2) 24 amici, ex compagni di liceo, si rivedono dopo qualche anno e organizzano una cena. A fine serata si salutano e ognuno stringe la mano a tutti gli altri. Quante strette di mano ci saranno?

 

Soluzione: come di consueto iniziamo con l'individuare n (numero totale elementi) e k (numero di elementi con cui si forma un raggruppamento).

 

Ovviamente n=24 e k=2 in quanto una stretta di mano avviene fra due persone. L'ordine ha importanza? NO, ognuno può stringere la mano a chi vuole e in che ordine vuole. Ci orientiamo quindi verso le combinazioni

 

Uno stesso elemento, all'interno di un raggruppamento può essere ripetuto? NO, sarebbe assurdo infatti che ciascun tipo salutasse se stesso stringendosi da solo la mano.. non dite? Tongue out

 

Per contare il numero delle strette di mano ricorreremo quindi alle combinazioni semplici, da cui:

 

C_{24,2}=\frac{24!}{2!(24-2)!}=\frac{24!}{2 \cdot 22!}=\frac{23 \cdot 24}{2}=276

 

 

3) 8 amici si incontrano settimanalmente per un banchetto, cambiando ogni volta la loro posizione lungo una tavolata. Dopo quanti anni avranno esaurito tutte le possibili disposizioni?

 

Soluzione: l'ordine ha importanza? Certo che. Ogni disposizione a tavola varierà dalle altre proprio per l'ordine in cui gli amici occuperanno i posti.

 

Quanto valgono k \ \mbox{ed} \ n? In questo caso k=n=8. Gli elementi son tutti distinti? Certo che . Utilizzeremo quindi le permutazioni semplici, da cui troveremo:

 

P_8=8!=40320

 

possibili modi di occupare i posti a tavola.

 

Considerando che si vedono una volta la settimana ed in un anno vi sono circa 52 settimane, ci impiegheranno la bellezza di circa 40320 : 52 \simeq 775 anni per esaurire tutte le possibili disposizioni a tavola.

 

Domanda bonus: se il tavolo fosse stato circolare ed i posti non numerati, sarebbe cambiata qualcosa?

 

La risposta è sì! Per risolvere correttamente il problema avremmo dovuto far ricorso alle permutazioni circolari - click!

 

 


 

Può bastare! Speriamo davvero di avervi fatto capire quale sia il modo corretto di procedere per affrontare e risolvere questo genere di problemi. Ancora dubbi? Utilizzate l'apposita barra di ricerca o fate la vostra domanda sul Forum!

 

Buona Probabilità a tutti!

Giuseppe Carichino

 

Lezione precedente..........Lezione successiva


Tags: metodo per risolvere gli esercizi di Calcolo Combinatorio - come distinguere se usare permutazioni, disposizioni o combinazioni nei problemi di Calcolo Combinatorio.