Problemi di Calcolo Combinatorio

I problemi di Calcolo Combinatorio sono gli esercizi che si riconducono al calcolo del numero di modi con cui si può raggruppare un numero finito di elementi, seguendo determinate regole che possono essere dedotte dal testo del problema oppure essere note a priori.

Dalle precedenti lezioni sappiamo che esistono tre fondamentali tipologie di raggruppamenti: permutazioni, disposizioni e combinazioni, ciascuna delle quali presenta a sua volta due varianti: semplici o con ripetizione. Vi è inoltre un caso particolare di permutazioni semplici, le cosiddette permutazioni circolari.

Quando si deve risolvere un problema di Calcolo Combinatorio l'unica difficoltà è capire quale tipo di raggruppamento bisogna considerare, scegliendo tra permutazioni semplici, permutazioni con ripetizione, permutazioni circolari, disposizioni semplici, disposizioni con ripetizione, combinazioni semplici oppure combinazioni con ripetizione. Dopo averlo stabilito la risoluzione dell'esercizio si limita all'applicazione di semplici formule.

Lo scopo di questa lezione è fornire una guida chiara e semplice su come risolvere i problemi di Calcolo Combinatorio. Richiameremo brevemente le definizioni e le formule per il calcolo del numero di permutazioni, disposizioni e combinazioni; spiegheremo quindi come scegliere il giusto tipo di raggruppamento, con l'aiuto di uno schema risolutivo, e concluderemo con qualche problema svolto.

Definizioni e formule di Calcolo Combinatorio

Partiamo da un breve ripasso delle definizioni dei vari tipi di raggruppamenti e delle formule di Calcolo Combinatorio, così da averle tutte a portata di mano. Per ogni genere di approfondimento vi rimandiamo alle relative lezioni, che linkeremo di volta in volta.

Permutazioni semplici: possibili modi di ordinare totalmente elementi distinti.

Il numero di permutazioni semplici si indica con ed è uguale al fattoriale di

Permutazioni circolari: caso particolare di permutazioni semplici, in cui gli elementi da ordinare sono disposti in modo circolare e non è possibile distinguere la prima dall'ultima posizione.

Il numero di permutazioni circolari di elementi distinti si denota con ed è pari al fattoriale di

Permutazioni con ripetizione: possibili modi di ordinare totalmente elementi, di cui alcuni sono ripetuti due o più volte.

Immaginiamo di avere elementi di cui sono di un tipo, di un altro tipo, e così via fino a , con .

Il numero di permutazioni con ripetizione di elementi si denota con ed è uguale al rapporto tra il fattoriale di e il prodotto dei fattoriali di

Disposizioni semplici (o disposizioni senza ripetizione): raggruppamenti ordinati di elementi distinti estratti tra elementi distinti, con .

Il numero di disposizioni semplici di classe di elementi distinti si indica con ed è uguale al rapporto tra il fattoriale di e il fattoriale di

Disposizioni con ripetizione: raggruppamenti ordinati di elementi estratti tra elementi distinti, con la possibilità che un elemento possa presentarsi fino a volte nello stesso raggruppamento.

Il numero di disposizioni con ripetizione di classe di elementi distinti si denota con ed è pari alla potenza -esima di

Combinazioni semplici (o combinazioni senza ripetizione): raggruppamenti di elementi distinti estratti tra elementi distinti, con , e senza tenere conto dell'ordine con cui gli elementi si presentano in ogni raggruppamento.

Il numero di combinazioni semplici di classe di elementi distinti si rappresenta con ed è uguale al coefficiente binomiale su

Combinazioni con ripetizione: raggruppamenti di elementi estratti tra elementi distinti, nei quali uno stesso elemento può ripetersi fino a volte e in cui l'ordine di estrazione non viene preso in considerazione.

Il numero di combinazioni con ripetizione di classe di elementi distinti si indica con ed è uguale al coefficiente binomiale su

Schema risolutivo dei problemi di Calcolo Combinatorio

Per risolvere un problema di Calcolo Combinatorio la prima cosa da fare è leggere attentamente il testo del problema e individuare i valori di e di , dove è il numero totale di elementi e è il numero degli elementi con i quali si devono formare i raggruppamenti.

Fatto ciò bisogna concentrarsi su due aspetti: l'ordine degli elementi e le possibili ripetizioni di un elemento all'interno del medesimo gruppo.

1) Se l'ordine è irrilevante opteremo per le combinazioni, e sceglieremo:

- le combinazioni semplici se non sono ammesse ripetizioni;

- le combinazioni con ripetizione se un elemento può ripetersi nello stesso raggruppamento.

2) Se l'ordine è rilevante, useremo le permutazioni se oppure le disposizioni se .

• Se la scelta ricade sulle permutazioni, dobbiamo usare:

- permutazioni semplici se i elementi sono distinti tra loro;

- permutazioni con ripetizione se almeno un elemento è ripetuto più di una volta.

• Se la scelta ricade sulle disposizioni, usiamo:

- le disposizioni semplici se non possono esserci ripetizioni di uno stesso elemento;

- le disposizioni con ripetizione in caso contrario.

Per maggiore chiarezza ecco uno schema risolutivo dei problemi di Calcolo Combinatorio sotto forma di diagramma di flusso:

Schema per risolvere i problemi di Calcolo Combinatorio.

Problemi svolti di Calcolo Combinatorio

Passiamo finalmente dalla teoria alla pratica e vediamo come applicare il metodo per risolvere qualche problema di Calcolo Combinatorio.

Problema 1

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?

Svolgimento: ogni stretta di mano può essere pensata come un raggruppamento di elementi, dove gli elementi sono le due persone che si stringono la mano per salutarsi.

Evidentemente il numero totale di elementi corrisponde al numero di amici, che sono 24, dunque .

Abbiamo così individuato i valori di e .

Seguiamo lo schema risolutivo dei problemi di Calcolo Combinatorio e chiediamoci se nel formare i raggruppamenti l'ordine ha importanza. La risposta è no, infatti ognuno può stringere la mano a chi vuole e in che ordine vuole. Ci orientiamo quindi verso le combinazioni.

Per capire se dobbiamo usare combinazioni semplici o con ripetizione, domandiamoci se uno stesso elemento può essere ripetuto all'interno del medesimo raggruppamento. Ancora una volta la risposta è negativa, infatti sarebbe assurdo che ogni amico salutasse se stesso stringendosi la mano da solo. ;)

Ci siamo! Con questo ragionamento deduciamo che ogni stretta di mano è una combinazione semplice di classe 2 di 24 elementi, dunque il numero totale di strette di mano è:

Scriviamo 24! come prodotto in cui compare 22! come fattore e semplifichiamo:

Problema 2

8 amici si incontrano settimanalmente per un banchetto, cambiando ogni volta la loro sistemazione a tavola. Supponendo che i posti siano numerati, dopo quanti anni avranno esaurito tutte le possibili disposizioni?

Svolgimento: non lasciamoci ingannare dalla parola disposizioni presente nella traccia del problema e seguiamo lo schema risolutivo.

L'insieme di partenza è formato da elementi e ogni sistemazione a tavola è un raggruppamento di elementi.

L'ordine degli elementi è fondamentale, infatti ogni sistemazione a tavola varia dalle altre proprio per l'ordine con cui gli amici occupano i posti.

Poiché e dal momento che gli elementi sono distinti tra loro (ogni persona è diversa dalle altre), ogni sistemazione a tavola è una permutazione semplice di 8 elementi.

Vi sono dunque 40320 modi possibili modi di occupare i posti a tavola.

Per calcolare dopo quanti anni si saranno esaurite tutte le possibili disposizioni basta dividere il numero di sistemazioni a tavola per il numero di settimane in un anno, che sono circa 52.

dunque impiegheranno più di 775 anni.

Problema 3

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 tra le 26 dell'alfabeto anglosassone, si calcoli quante targhe differenti si possono ottenere.

Svolgimento: una targa automobilistica ha la seguente struttura:

lettera lettera - cifra cifra cifra - lettera lettera

Abbiamo quindi due tipi di raggruppamenti:

lettera lettera

cifra cifra cifra

Ogni raggruppamento "lettera lettera" è formato da elementi estrapolati tra elementi distinti (le lettere dell'alfabeto anglosassone).

L'ordine con cui gli elementi sono disposti ha importanza, in quanto due lettere scambiate di posto generano targhe distinte. Essendo inoltre , abbiamo a che fare con disposizioni. Semplici o con ripetizione?

In un raggruppamento la stessa lettera può ripetersi fino a due volte, dunque ogni gruppo "lettera lettera" è una disposizione con ripetizione di classe 2 di 26 elementi.

Per calcolare quante sono usiamo la formula delle disposizioni con ripetizione

e sostituiamo e

Per quanto riguarda i gruppi di cifre, essi sono raggruppamenti di elementi scelti da un insieme che ne contiene (i numeri interi da 0 a 9).

Anche in questo caso l'ordine è rilevante e una stessa cifra può essere ripetuta fino a 3 volte. Utilizziamo ancora una volta la formula delle disposizioni con ripetizione e otteniamo che il numero di raggruppamenti del tipo "cifra cifra cifra" è

Per calcolare il numero totale di targhe osserviamo che a ciascuno dei 676 gruppi "lettera lettera" si possono associare 1000 gruppi "cifra cifra cifra", per un totale di 676×1000 abbinamenti. A ciascuno di questi 676000 abbinamenti si possono accostare altri 676 gruppi "lettera lettera", dunque il numero totale di targhe automobilistiche è

Le lezioni di Calcolo Combinatorio terminano qui. Vi aspettiamo nel corso sul Calcolo delle Probabilità, in cui faremo un uso massiccio delle formule del Calcolo Combinatorio nello svolgimento degli esercizi... Non prima però che abbiate provato a risolvere gli esercizi di riepilogo di Calcolo Combinatorio. ;)

Buon proseguimento su YouMath,

Giuseppe Carichino (Galois)

.....

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

Ultima modifica: 09/05/2023