Calcolo combinatorio - Teoria ed esercizi

Leggi...

Il calcolo combinatorio è la branca della matematica che si occupa dello studio dei modi in cui si possono associare, o ordinare, gli elementi di uno o più insiemi finiti; nella fattispecie il calcolo combinatorio è utile per determinare il numero dei possibili modi in cui questi elementi si possono raggruppare.

Vediamo un esempio su come si contano i raggruppamenti:

Esempio 1. Supponiamo di volerci mangiare una pizza e che la nostra pizzeria abbia a disposizione due tipi diversi di impasto (bianco o integrale) e tre tipi diversi di topping (funghi, salame, verdure); in quanti modi possiamo scegliere la nostra pizza?

$\quad$

Svolgimento. Un primo approccio è quello di costruire l’albero delle scelte e contare le relative foglie:

$\quad$

Calcolo combinatorio

$\quad$

Dall’albero si capisce subito che è possibile comporre un totale di sei pizze:

$\quad$

impasto bianco e funghi

impasto bianco e salame

impasto bianco e verdure

impasto integrale e funghi

impasto integrale e salame

impasto integrale e verdure

Un altro possibile approccio consiste nel considerare i due insiemi:

$\begin{aligned} I&=\left\{impasto\;bianco,\:impasto\;integrale\right\}\\ T&=\left\{funghi,\;salame,\;verdure\right\} \end{aligned}$

Le possibili pizze sono gli elementi del prodotto cartesiano $I\times T$ , ovvero tutte le coppie che posso formare prendendo un elemento dall’insieme I ed un elemento dall’insieme T:

$I\times T=\left\{(i, t)\;|\;i\in I,\;t\in T\right\}$

dato che ho due modi di scegliere un elemento da I e tre modi di scegliere un elemento da T il numero totale di pizze è:

Purtroppo, al contrario di quanto appena visto, spesso non è possibile contare manualmente il numero di elementi che ci viene richiesto, per questo nei prossimi capitoli presenteremo i vari tipi di raggruppamento e le relative metodologie di calcolo.

Introduzione.

Il problema generico, insiemisticamente parlando, è quello di contare le sequenze di $k$ elementi che si possono formare da un insieme di $n$ elementi distinti; se le sequenze differiscono tra loro per qualche elemento o per l’ordine in cui essi sono disposti, si parla di disposizioni.

Nei prossimi due paragrafi distingueremo tra disposizioni semplici (per le quali un singolo elemento non può ripetersi) e disposizioni con ripetizione (per le quali invece la ripetizione è concessa).

Disposizioni semplici.

Come specificato sono disposizioni semplici le sequenze ordinate di $k$ elementi (classe k), estratte da un insieme di $n$ elementi distinti, che non presentano ripetizioni; è immediato dedurre che si ha $k\leq n$ .

Esempi di disposizioni semplici possono essere:

$\triangleright$ le possibili combinazioni del podio in una maratona;

$\triangleright$ i modi in cui disporre una parte dei vostri libri su una mensola;

$\triangleright$ i numeri compresi tra 100 e 999 che posso formare usando soltanto cifre dispari e senza ripetizioni.

Per capire come arrivare alla formula facciamo un esempio pratico in cui vogliamo contare i possibili sottoinsiemi ordinati contenenti 3 palline da un insieme di 9 palline numerate; immaginiamo uno di questi sottoinsiemi come formato da tanti slot quanti sono gli elementi che vogliamo:

$\quad$

Calcolo combinatorio

$\quad$

Riempiamo uno slot alla volta: in quanti modi posso riempire il primo? Ho tutte e 9 le palline a mia disposizione, quindi posso riempirlo in 9 modi diversi.

Supponiamo di inserire la pallina numero 4 nel primo slot:

$\quad$

Calcolo combinatorio

$\quad$

Riempito il primo slot passiamo al secondo: per la seconda posizione ci rimangono 8 palline, quindi abbiamo 8 possibilità.

Scegliamo di inserire la pallina numero 2 nel secondo slot:

$\quad$

Calcolo combinatorio

$\quad$

Come esposto ho 9 possibili scelte per la prima posizione, per ognuna di queste ho 8 possibili scelte per la seconda e per ognuna delle $9\cdot8$ scelte fatte ho 7 possibili scelte per la terza, per un totale di $9\cdot8\cdot7=504$ possibili terne diverse.

Quanto appena fatto è analogo a quanto visto con l’albero del primo capitolo, chiaramente difficile da implementare con così tante aperture; generalizzando il ragionamento otteniamo il seguente risultato:

Proposizione 1 (disposizioni semplici). Il numero di disposizioni semplici di $n$ elementi distinti di classe $k$ ( $k\leq n)$ è dato dalla seguente formula:

(1) $\begin{equation*} D(n,k)=n\cdot(n-1)\cdot...\cdot(n-k+1)=\frac{n!}{(n-k)!} \end{equation*}$

dove il simbolo $n!$ si chiama fattoriale del numero naturale $n$ ed è definito come $n!=1\cdot 2 \cdot 3 \cdots (n-1) \cdot n$ .

Disposizioni semplici: esercizi.

Esercizio 1. In quanti modi possiamo affidare 3 mansioni avendo a disposizione 5 dipendenti?

$\quad$

Svolgimento. Dobbiamo estrarre 3 dipendenti dai 5 disponibili ed assegnarli ognuno ad una mansione differente; dato che plausibilmente non possiamo assegnare un dipendente a due diverse mansioni dobbiamo contare le disposizioni di 5 elementi di classe 3 senza ripetizione, quindi per (1) si ha

$D(5,3)=5\cdot4\cdot3=60$

ovvero i dipendenti possono essere scelti in 60 modi diversi.

$\quad$

Esercizio 2. In numeri di 5 cifre differenti possiamo formare con le 10 cifre decimali?

$\quad$

Svolgimento. L’esercizio presenta un trabocchetto, infatti dobbiamo considerare che i numeri non possono iniziare per 0!

Fatta questa premessa, emulando il ragionamento fatto per arrivare alla formula delle disposizioni semplici, vediamo il numero come composto da 5 slot differenti, quanti modi ho di riempire ogni slot?

S1: Al primo slot posso assegnare tutte le crifre tranne lo 0, quindi ho 9 scelte;

S2: al secondo slot posso assegnare qualsiasi cifra tra quelle rimaste, anche per questo slot ho 9 scelte;

S3: al terzo slot posso assegnare una tra le 8 cifre rimaste;

S4: al quarto slot posso assegnare una tra le 7 cifre rimaste;

S5: all’ultimo slot posso assegnare una delle 6 cifre rimaste.

In totale avremo $9\cdot9\cdot8\cdot7\cdot6=27.216$ possibili numeri.

Possiamo arrivare allo stesso risultato anche utilizzando la formula (1), come? Per prima cosa eliminiamo il problema della prima cifra fissando in tale posizione una delle 9 cifre disponibili e ammissibili (tutte tranne lo 0), fatto questo contare i modi in cui scegliere le ultime quattro cifre equivale a contare tutti i numeri di quattro cifre diverse che possono essere formati utilizzando 9 (delle 10) cifre, ovvero equivale a contare le disposizioni di 9 elementi di classe 4:

$\sharp_{numeri}=9\cdot D(9,4)=9\cdot(9\cdot8\cdot7\cdot6)=9\cdot3024=27,216$

$\quad$

Esercizio 3. Ad un torneo di basket partecipano 12 squadre. Quante partite, tra andata e ritorno, si dovranno giocare sapendo che tutte le squadre si dovranno incontrare?

$\quad$

Svolgimento. Possiamo rappresentare ogni partita come una coppia in cui il primo elemento è la squadra che gioca in casa ed il secondo elemento è l’avversario; così facendo due coppie con ordine diverso rappresentano due partite diverse e ogni coppia deve contenere due squadre distinte, questo ci porta a contare le disposizioni semplici di 12 elementi di classe 2:

$D(12,2)=12\cdot11=132$

Nel torneo si giocheranno 132 partite.

Disposizioni con ripetizione.

Se le sequenze ordinate possono presentare elementi ripetuti si parla di disposizioni con ripetizione, in questo caso non ci sono limiti a $k$ .

Esempi di disposizioni con ripetizione possono essere:

$\triangleright$ i possibili numeri di telefono;

$\triangleright$ i possibili pin dei bancomat emessi da una banca;

$\triangleright$ le possibili combinazioni di un lucchetto con codice numerico.

Il ragionamento che ci porta alla formula per contare le disposizioni con ripetizione di classe $k$ è analogo a quello fatto in precedenza per le disposizioni semplici con la differenza che, per ogni slot, ho sempre $n$ possibilità di scelta. Si arriva così alla:

$\quad$

Proposizione 2. Il numero di disposizioni con ripetizione di $n$ elementi distinti di classe $k$ è dato dalla seguente formula:

(2) $\begin{equation*} D'(n,k)=\underbrace{n\cdot n\cdot...\cdot n}_{k\;volte}=n^k \end{equation*}$

Disposizioni con ripetizione: esercizi.

Esercizio 4. Quanti numeri di 5 cifre si possono formare con le 10 cifre decimali?

$\quad$

Svolgimento. Questo esercizio è molto simile ad un esercizio visto in precedenza con la differenza che qui non è richiesto che le cifre che compongono il numero siano differenti.

Fatta questa considerazione possiamo ripetere il ragionamento fatto con un paio di modifiche:

$\quad$

Nonostante si fissi la prima cifra (sempre con 9 scelte possibili per evitare lo 0) rimangono 10 cifre disponibili per gli altri slot;

Per contare i modi di scegliere le cifre per gli ultimi quattro slot non usiamo disposizioni semplici bensì con ripetizione.

Il numero di combinazioni sarà dato quindi da

$\sharp_{numeri}=9\cdot D'(10,4)=9\cdot10^4=90,000$

$\quad$

Esercizio 5. Una piccola azienda di 10 dipendenti elegge regolarmente il dipendente del mese appendendo una targhetta su una bacheca. Quante sono le possibili combinazioni di targhette che potremmo trovare relativamente all’anno 2021?

$\quad$

Svolgimento. Ogni dipendente può essere chiaramente scelto più di una volta come dipendente del mese, quindi abbiamo a che fare con disposizioni con ripetizione di 10 elementi di classe 12 (i mesi del 2021), quindi il numero di combinazioni sarà dato da:

$D'(10,12)=10^{12}$

Introduzione.

Data una sequenza di $n$ elementi chiamiamo permutazione una qualsiasi sequenza ottenuta da quella iniziale semplicemente cambiandone l’ordine degli elementi.

Distinguiamo tra permutazioni semplici (se gli elementi della sequenza iniziale sono tutti distinti) e permutazioni con ripetizione (se nella sequenza iniziale sono presenti elementi ripetuti).

Permutazioni semplici.

Da quello che abbiamo detto le permutazioni semplici non sono altro che sequenze di $n$ elementi ottenute dagli $n$ elementi della sequenza originale in cui l’ordine discrimina, possiamo dunque affermare che le permutazioni semplici altro non sono che disposizioni semplici di $n$ elementi di classe $n$ , quindi la formula per determinarne il numero deriva direttamente da quella per le disposizioni semplici, ovvero:

$P_n=D(n,n)=\dfrac{n!}{(n-n)!}=\dfrac{n!}{0!}=\dfrac{n!}{1}=n!$

Possiamo dunque enunciare il seguente risultato:

$\quad$

Proposizione 3 (permutazioni semplici). Il numero di permutazioni semplici di $n$ elementi distinti è dato dalla seguente formula:

(3) $\begin{equation*} P_n=n! \end{equation*}$

Permutazioni semplici: esercizi.

Esercizio 6. Quanti sono gli anagrammi della parola cane?

$\quad$

Svolgimento. Gli anagrammi sono l’esempio più comune per rappresentare le permutazioni; in questo caso, dato che non ci sono ripetizioni nelle lettere, si tratta di permutazioni semplici, quindi il numero di anagrammi in questione, utilizzando la (3), sarà

$P_4=4!=4\cdot3\cdot2\cdot1=24$

$\quad$

Esercizio 7. In quanti modi cinque amici possono sedersi su cinque poltrone al cinema?

$\quad$

Svolgimento. Supponiamo che gli amici abbiano scelto un determinato modo per sedersi, per ottenere gli altri basterà scambiare tra loro uno o più amici; questo procedimento è lo stesso che si segue quando si vuole creare un anagramma di una parola e quindi anche qua si parla di permutazioni (semplici in quanto i cinque amici sono tutte persone diverse).

Anche qui dunque possiamo utilizzare la (3) e ottenere

$P_5=5!=5\cdot4!=5\cdot24=120$

Ci sono dunque 120 modi di disporre i 5 amici.

L’esercizio può essere approcciato anche in modo diverso, ovvero come disposizione: è chiaro che l’ordinamento discrimini le posizioni degli amici (altrimenti non avrebbe senso contare) e dato che $n=k=5$ si ottiene, dalla (1)

$D(5,5)=\dfrac{5!}{(5-5)!}=5!=120$

Permutazioni con ripetizione.

Se nella sequenza iniziale sono presenti alcuni elementi ripetuti parliamo di permutazioni con ripetizione, come possiamo contarle?

Facciamo un esempio: cerchiamo il numero di anagrammi (anche senza significato) della parola “MACININI”; chiaramente un anagramma è una permutazione, quindi partiamo contando le permutazioni semplici della parola in questione:

$P_8=8!=40.320$

Contando le permutazioni semplici andiamo incontro all’errore di double counting, infatti stiamo contando anche gli anagrammi che si ottengono scambiando due lettere uguali e che quindi abbiamo già contato.

Dobbiamo quindi epurare gli anagrammi ripetuti dal totale delle permutazioni, come fare? Il conteggio extra di un anagramma si ottiene quando si scambiano due lettere uguali quindi per ogni lettera che si ripete più di una volta abbiamo un numero di conteggi extra pari alle permutazioni semplici di questa parola.

Nel nostro caso specifico ci sono due lettere che si ripetono:

I: sono presenti tre I, le permutazioni semplici di queste lettere sono quindi $P_3=3!=6$ ;

N: sono presenti due N, le permutazioni semplici di queste lettere sono quindi $P_2=2!=2$ ;

Quindi il numero di conteggi extra che facciamo è pari a $3!\cdot 2!$ .

Per eliminare queste ripetizioni dal conteggio totale dividiamo il numero iniziale per il numero di anagrammi ripetuti, ottenendo così il conteggio giusto:

$P'(8,3,2)=\dfrac{8!}{3!\cdot 2!}=3,360$

Possiamo generalizzare il ragionamento per ottenere il seguente risultato:

$\quad$

Proposizione 4 (permutazioni con ripetizione). Data una sequenza di $n$ elementi in cui $h$ elementi si ripetono ognuno con frequenza $k_j$ (con $j=1,...,h$ ), il numero di permutazioni (con ripetizione) è dato dalla seguente formula:

(4) $\begin{equation*} P'(n,k_1,k_2,..,k_h)=\dfrac{n!}{k_1!\cdot k_2!\cdot...\cdot k_h!} \end{equation*}$

Permutazioni con ripetizione: esercizi.

Esercizio 8. Quanti sono gli anagrammi della parola gatto? E quelli della parola gattina?

$\quad$

Svolgimento. Dato che ci vengono chiesti degli anagrammi dobbiamo pensare subito alle permutazioni e dato che in entrambe le parole sono presenti delle lettere ripetute dobbiamo pensare a quelle con ripetizione.

Per la parola gatto abbiamo 5 lettere di cui una che si ripete due volte, quindi utilizzando la (4) otteniamo

$P'(5,2)=\dfrac{5!}{2!}=\dfrac{5\cdot4\cdot3\cdot2\cdot1}{2\cdot1}=5\cdot4\cdot3=60$

Per la parola gattina, invece, abbiamo 7 lettere di cui se ne ripetono due, entrambe due volte; possiamo ottenere il numero di anagrammi utilizzando ancora la (4):

$P'(7,2,2)=\dfrac{7!}{2!\cdot2!}=\dfrac{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{2\cdot1\cdot2\cdot1}=7\cdot6\cdot5\cdot3\cdot2=1,260$

$\quad$

Esercizio 9. Dopo un trasloco dobbiamo rimettere tutti i nostri libri sulla mensola;se si hanno tre libri di poesie, due libri di saggistica e cinque libri di narrativa, in quanti modi questi potranno essere disposti sul ripiano?

$\quad$

Svolgimento. In questo esercizio bisogna innanzitutto capire le condizioni sottostanti alla richiesta: ci interessa il titolo di ogni libro oppure soltanto il suo genere? Nel primo caso i libri sono tutti diversi tra loro e quindi avremo a che fare con permutazioni semplici, ottenendo dalla (3) un numero di modi pari a

$P_10=10!=3,628,800$

Se invece non ci interessa la posizione per titolo ma solo per genere, dobbiamo utilizzare le permutazioni con ripetizione, osservando che dei 10 libri a disposizione ci sono 3 generi che si ripetono rispettivamente 3, 2 e 5 volte; utilizzando la (4) otteniamo

$P(10,3,2,5)=\dfrac{10!}{3!\cdot2!\cdot5!}= \dfrac{10\cdot9\cdot8\cdot7\cdot6\cdot5!}{3!\cdot2!\cdot5!}=10\cdot9\cdot4\cdot7=2,520$

dove nel penultimo passaggio abbiamo semplificato i due $5!$ , il 6 con il $3!$ e l’8 con il $2!$ .

Introduzione.

Come introdotto nel capitolo relativo alle disposizioni, il problema è sempre quello di contare le sequenze di $k$ elementi che si possono formare da un insieme di $n$ elementi; se l’ordine non discrimina le sequenze, quindi se due sequenze con gli stessi elementi, anche se in ordine diverso, rappresentano la stessa sequenza, si parla di combinazioni.

Nei prossimi due paragrafi distingueremo tra combinazioni semplici (per le quali, in una sequenza, non sono ammesse ripetizioni) e combinazioni con ripetizione (per le quali, invece, è concesso che alcuni elementi si ripetano).

Combinazioni semplici.

Le combinazioni semplici sono sottoinsiemi di $k$ elementi (classe k) estratti da un insieme di $n$ elementi distinti e che non presentano ripetizioni e in cui l’ordine degli elementi non ha importanza. come per le disposizioni semplici si ha $k\leq n$ .

Esempi di combinazioni semplici possono essere:

$\triangleright$ Le possibili combinazioni di carte che si possono avere in una mano di Poker;

$\triangleright$ Le possibili estrazioni del superenalotto;

$\triangleright$ Le possibili liste con gli ammessi al test d’ingresso di medicina.

Contare le combinazioni semplici di classe $k$ da un insieme di $n$ elementi consiste essenzialmente nel contare i possibili sottoinsiemi di $k$ elementi che possiamo formare; con questa interpretazione andiamo a ricavarci la formula.

Per arrivare alla formula vediamo un esempio pratico: abbiamo un sacchetto contenente 9 palline numerate e vogliamo contare i modi in cui si possono estrarre 3 palline (senza ordinamento); partendo dalla prima estrazione, ad esempio quella che vede estratte le palline numerate con $1,2$ e $3$ , la situazione si può rappresentare nel seguente modo:

$\quad$

Possiamo immaginare che questa estrazione sia stata generata da una permutazione dei 9 elementi, in cui i 6 elementi rimasti siano i primi 6 della permutazione, mentre i 3 estratti siano gli ultimi 3 elementi della lista.

Occorre anche tenere conto che, permutando tra loro gli elementi che sono stati estratti (in totale $6!$ permutazioni) o gli elementi rimasti nell’insieme (in totale $3!$ permutazioni), la combinazione estratta non cambia.

$\quad$

Da queste considerazioni segue il numero di combinazioni semplici di $3$ elementi su $9$ è pari al numero delle permutazioni dei $9$ elementi, cioè $9!$ , diviso per il numero di permutazioni dei $6$ elementi rimasti dentro, cioè $6!$ , e il numero di permutazioni dei $3$ elementi estratti, cioè $3!$ , che non cambiano i sottoinsiemi creati. In formule:

$\frac{9!}{3! \cdot 6!}.$

Da qui generalizziamo: se invece che 9 palline ne avessimo avute $n$ e invece di sequenze di 3 elementi gli avessimo voluti di $k$ , avremmo avuto $k$ palline fuori dal sacco e $n-k$ dentro il sacco, applicando la (4) otterremmo:

$\dfrac{n!}{k!\cdot (n-k)!}$

Da cui:

$\quad$

Proposizione 5 (combinazioni semplici). Il numero di combinazioni semplici di $n$ elementi distinti di classe $k$ ( $k\leq n$ ) è dato dalla seguente formula:

(5) $\begin{equation*} C(n,k)=\binom{n}{k}=\dfrac{n!}{k!\cdot(n-k)!}, \end{equation*}$

dove il simbolo $\binom{n}{k}$ è detto coefficiente binomiale $n$ su $k$ .

$\quad$

Un’altra possibile spiegazione della formula è la seguente: ogni combinazione di $n$ elementi distinti di classe $k$ genera $k!$ disposizioni semplici degli stessi elementi, ottenute permutando i $k$ elementi estratti. Dunque

$D(n,k)=k! \cdot C(n,k) \implies C(n,k) = \frac{D(n,k)}{k!} = \frac{n!}{(n-k)! \cdot k!}.$

Combinazioni semplici: esercizi.

Esercizio 10. Quante sono le possibili estrazioni del lotto sulla ruota di Cagliari?

$\quad$

Svolgimento. E’ chiaro che qualunque sia l’ordine delle estrazioni al fine della vincita conta solo quali numeri sono usciti, dato quindi che l’ordinamento non discrimina stiamo contando delle combinazioni.

Le combinazioni sono semplici in quanto un numero non può uscire due volte, inoltre abbiamo $n=90$ (90 numeri tra cui scegliere) e $k=5$ (5 numeri estratti), dalla (5) si ottiene

$\begin{aligned} C(90,5)=\binom{90}{5}=\dfrac{90!}{5!\cdot85!}&=\dfrac{90\cdot89\cdot88\cdot87\cdot86\cdot85!}{5!\cdot85!}\\&= \dfrac{90\cdot89\cdot88\cdot87\cdot86}{5!}\\&=43,949,268 \end{aligned}$

$\quad$

Esercizio 11. L’azienda per cui lavori ha ricevuto un nuovo progetto a cui dovranno lavorare 5 dei tuoi 12 sottoposti; quanti modi ci sono per creare un team del genere?

$\quad$

Svolgimento. Anche in questo caso l’ordine non conta in quanto conta soltanto quali sono le persone presenti nel team scelto. Dato che le persone non possono ripetersi stiamo parlando di combinazioni semplici in cui $n=12$ (il numero di elementi da cui dobbiamo fare l’estrazione) e $k=5$ (il numero di elementi da estrarre); utilizzando la (5) otteniamo

$C(12,5)=\binom{12}{5}=\dfrac{12!}{5!\cdot7!}=792.$

Combinazioni con ripetizione.

Se le sequenze possono presentare elementi ripetuti e non conta l’ordine si parla di combinazioni con ripetizione, in questo caso non ci sono limiti a $k$ . Esempi di combinazioni con ripetizione possono essere:

$\triangleright$ i modi di distribuire alcune penne in due astucci;

$\triangleright$ i modi di scegliere i due gusti di un cono gelato (con la possibilità di scegliere più volte lo stesso);

$\triangleright$ In quanti modi posso colorare le pareti di casa avendo a disposizione un set di colori.

Per arrivare alla formula che ci permette di contare le combinazioni con ripetizione possiamo tornare all’esempio del sacchetto con le 9 palline, anche stavolta ne vogliamo estrarre 3 (senza ordinamento) ma con la possibilità di estrarre più volte la stessa, ad esempio segnando il risultato dell’estrazione e reinserendo la pallina nel sacchetto.

Supponiamo di estrarre la prima pallina e che questa corrisponda alla numero 5, segniamo 5 su un foglio e prima di rimettere la pallina nel sacchetto facciamo un segno di riconoscimento sulla stessa; facciamo la seconda estrazione, questa potrà essere ancora la pallina numero 5 o un’altra pallina, nel primo caso però non è più la stessa pallina in quanto adesso ha anche un segno, annotiamo che è uscito di nuovo il 5, facciamo un secondo segno sulla pallina e reinseriamo; in questo modo guardando solo il numero sulla pallina stiamo tenendo conto della ripetizione, ma guardando anche i segni fatti dopo l’estrazione è come se non reinserissimo la pallina ma una pallina diversa. Dopo aver pescato l’ultima terminiamo l’estrazione senza reinserirla, quante palline abbiamo aggiunto marcandole con la penna dopo l’estrazione? Tutte tranne l’ultima ovvero $2$ , quindi guardando numero e segno è come se stessimo contando le combinazioni semplici di classe $3$ estratte da un insieme di 9 palline originali più 2 palline segnate, quindi 11.

Generalizzando l’esempio con $n$ palline nel sacchetto da cui ne estraggo $k$ senza ordinamento, reinserendone $k-1$ segnate (tutte tranne l’ultima) è come contare le combinazioni senza ripetizione da un insieme di $n$ palline con l’aggiunta di $k-1$ palline, quindi applicando la (5) si ha:

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

quindi:

$\quad$

Proposizione 6 (combinazioni con ripetizione). Il numero di combinazioni con ripetizione di $n$ elementi distinti di classe $k$ è dato dalla seguente formula:

(6) $\begin{equation*} C'(n,k)=\binom{n+k-1}{k}=\dfrac{(n+k-1)!}{k!\cdot(n-1)!} \end{equation*}$

Combinazioni con ripetizione: esercizi.

$\quad$

Esercizio 12. La gelateria di fronte all’ufficio ha diversi gusti ma noi scegliamo sempre i soliti quattro: crema, pistacchio, cioccolato e caramello; dato che nel pomeriggio dobbiamo tornare a lavoro decidiamo di acquistare un cono piccolo su cui possiamo mettere solo due gusti.

Supponendo di poter scegliere anche due volte lo stesso gusto (il lunedi abbiamo bisogno di doppia dose di cioccolato) in quanti modi possiamo comporre il nostro cono?

$\quad$

Svolgimento. L’ordine in cui ordiniamo i gusti non cambia il risultato, quindi stiamo parlando di combinazioni e dato che potremmo scegliere anche lo stesso gusto più volte è presente la ripetizione.

Dato che il pool di gusti ha 4 elementi e che noi ne dobbiamo scegliere 2, otteniamo dalla (6)

$C'(4,2)=\binom{4+2-1}{2}=\binom{5}{2}=\dfrac{5!}{2!\cdot3!}=10$

I dieci possibili gelati sono:

$\quad$

crema – crema

crema – pistacchio

crema – cioccolato

crema – caramello

pistacchio – pistacchio

pistacchio – cioccolato

pistacchio – caramello

cioccolato – cioccolato

cioccolato – caramello

caramello – caramello

$\quad$

Esercizio 13. In quanti modi possiamo disporre 15 penne in 3 astucci?

$\quad$

Svolgimento. Per risolvere questo tipo di esercizi dobbiamo ragionare a partire dagli astucci. Per capire il metodo immaginiamo di disporre le penne in fila sul tavolo e di associare ad ogni penna uno dei tre astucci; dato che le penne sono identiche (non viene specificato diversamente) possiamo intuire che l’ordine di disposizione delle penne sul tavolo non influisce sul risultato e che quindi stiamo parlando di combinazioni, dato inoltre che posso associare lo stesso astuccio a più penne possiamo dire che sono con ripetizione.

Utilizzando la (6) con $n=15$ e $k=3$ otteniamo:

$C'(15,3)=\binom{15+3-1}{3}=\binom{17}{3}=\dfrac{17!}{3!\cdot14!}=680$

Introduzione.

Gli esercizi presentati finora sono giusto a titolo esemplificativo per mostrare come applicare le formule, tipicamente gli esercizi sono più complessi e richiedono capacità di schematizzare il problema per poterlo suddividere in sottoproblemi da risolvere con le formule esposte; nei prossimi paragrafi vedremo qualche linea guida.

Linee guida per la risoluzione.

La prima cosa da fare quando si affronta un esercizio relativo al calcolo combinatorio è schematizzare il problema in modo da individuare una possibile suddivisione dello stesso in sottoproblemi risolvibili tramite l’applicazione diretta delle formule viste nei capitoli precedenti.

Prima di entrare nel merito torniamo all’esempio della pizza visto nell’introduzione dove ci viene richiesto quante pizze è possibile comporre sapendo di avere a disposizione due tipi diversi di impasto e tre tipi diversi di topping; abbiamo visto che un modo semplice per risolvere il problema è quello di suddividerlo in due parti: contare in quanti modi posso scegliere l’impasto e contare in quanti modi posso scegliere il topping, dopodiché abbiamo moltiplicato i risultati per ottenere il numero finale.

L’approccio è generalizzabile e si articola nei punti seguenti:

$\quad$

suddividere il problema in sottoproblemi risolubili con le formule;

risolvere ogni sottoproblema;

aggregare i risultati ottenuti per ottenere il risultato finale.

Il problema può essere spacchettato in sottoproblemi indipendenti o meno, cerchiamo di capire cosa vuol dire e cosa cambia in termini di metodo:

indipendenti: se i sottoproblemi ottenuti sono relativi a elementi diversi allora si parla di indipendenza; per aggregare risultati indipendenti dobbiamo moltiplicarli tra loro.

non indipendenti: se i sottoproblemi ottenuti sono relativi agli stessi elementi, ad esempio se stiamo valutando diverse casistiche sullo stesso insieme, non c’è indipendenza; per aggregare risultati non indipendenti dobbiamo sommarli tra di loro.

Detto questo vediamo come applicare il ragionamento all’esempio della pizza: dobbiamo contare le possibili pizze ottenibili usando due impasti e tre topping ovvero dobbiamo contare le combinazioni di questi due elementi, l’idea più diretta è quella di contare separatamente tutti i modi di scegliere l’impasto (combinazioni semplici con $n=2$ e $k=1$ ) che sono $\binom{2}{1}=2$ e tutti i modi che ho di scegliere i topping (combinazioni semplici con $n=3$ e $k=1$ ) che sono $\binom{3}{1}$ ; topping e impasti sono elementi diversi, quindi abbiamo effettuato uno spacchettamento indipendente e quindi il risultato finale lo otteniamo moltiplicando i due risultati:

$\sharp pizze=\binom{2}{1}\cdot\binom{3}{1}=2\cdot3=6$

Se invece avessi avuto l’idea di contare tutte le pizze ottenibili usando il primo impasto e tutte quelle ottenibili usando il secondo avrei avuto una suddivisione non indipendente e dato che in entrambi i casi le possibili pizze sono tre (una per ogni scelta di topping) per ottenere il risultato finale avrei dovuto sommare:

$\sharp pizze=3+3=6$

Concludiamo con un focus sul punto 2 del metodo, ovvero la scelta della formula da utilizzare per il sottoproblema; possiamo riassumere il procedimento di scelta con questo diagramma:

$\quad$

Rendered by QuickLaTeX.com

$\quad$

Fonte: Problemi risolti matematica e fisica

Leggi...

Strutture algebriche.

Algebra lineare.

Geometria analitica.

Geometria differenziale.

Leggi...

Math Stack Exchange – Parte della rete Stack Exchange, questo sito è un forum di domande e risposte specificamente dedicato alla matematica. È una delle piattaforme più popolari per discutere e risolvere problemi matematici di vario livello, dall’elementare all’avanzato.
Art of Problem Solving (AoPS) – Questo sito è molto noto tra gli studenti di matematica di livello avanzato e i partecipanti a competizioni matematiche. Offre forum, corsi online, e risorse educative su una vasta gamma di argomenti.
MathOverflow – Questo sito è destinato a matematici professionisti e ricercatori. È una piattaforma per domande di ricerca avanzata in matematica. È strettamente legato a Math Stack Exchange ma è orientato a un pubblico con una formazione più avanzata.
PlanetMath – Una comunità collaborativa di matematici che crea e cura articoli enciclopedici e altre risorse di matematica. È simile a Wikipedia, ma focalizzata esclusivamente sulla matematica.
Wolfram MathWorld – Una delle risorse online più complete per la matematica. Contiene migliaia di articoli su argomenti di matematica, creati e curati da esperti. Sebbene non sia un forum, è una risorsa eccellente per la teoria matematica.
The Math Forum – Un sito storico che offre un’ampia gamma di risorse, inclusi forum di discussione, articoli e risorse educative. Sebbene alcune parti del sito siano state integrate con altri servizi, come NCTM, rimane una risorsa preziosa per la comunità educativa.
Stack Overflow (sezione matematica) – Sebbene Stack Overflow sia principalmente noto per la programmazione, ci sono anche discussioni rilevanti di matematica applicata, specialmente nel contesto della scienza dei dati, statistica, e algoritmi.
Reddit (r/Math) – Un subreddit popolare dove si possono trovare discussioni su una vasta gamma di argomenti matematici. È meno formale rispetto ai siti di domande e risposte come Math Stack Exchange, ma ha una comunità attiva e molte discussioni interessanti.
Brilliant.org – Offre corsi interattivi e problemi di matematica e scienza. È particolarmente utile per chi vuole allenare le proprie capacità di problem solving in matematica.
Khan Academy – Una risorsa educativa globale con lezioni video, esercizi interattivi e articoli su una vasta gamma di argomenti di matematica, dalla scuola elementare all’università.

Calcolo combinatorio – Teoria ed esercizi

Autori e revisori

Leggi...

Introduzione

Leggi...

Disposizioni

Introduzione.

Disposizioni semplici.

Disposizioni semplici: esercizi.

Disposizioni con ripetizione.

Disposizioni con ripetizione: esercizi.

Permutazioni

Introduzione.

Permutazioni semplici.

Permutazioni semplici: esercizi.

Permutazioni con ripetizione.

Permutazioni con ripetizione: esercizi.

Combinazioni

Introduzione.

Combinazioni semplici.

Combinazioni semplici: esercizi.

Combinazioni con ripetizione.

Combinazioni con ripetizione: esercizi.

Esercizi di riepilogo

Introduzione.

Linee guida per la risoluzione.

Tutta la teoria di analisi matematica

Leggi...

Tutte le cartelle di Analisi Matematica

Leggi...

Tutti gli esercizi di geometria

Strutture algebriche.

Algebra lineare.

Geometria analitica.

Geometria differenziale.

Risorse didattiche aggiuntive per approfondire la matematica

Leggi...