Disposizioni semplici; permutazioni semplici; combinazioni semplicidisposizioni con ripetizione; permutazioni con ripetizionecombinazioni con ripetizione

  

"Quanti sono gli anagrammi della parola matematica?"

"Quante schedine diverse possiamo giocare al superenalotto?"

"Quanti sono i numeri formati da cinque cifre tutte pari?"

"Quante partite si disputano in un torneo a girone unico con dieci squadre partecipanti?"

"Quante sono le diagonali di un poligono convesso di \(n\) lati?"

Per risolvere i quesiti proposti possiamo avvalerci del calcolo combinatorio, ovvero quella branca della matematica che si occupa di contare in quanti modi possiamo selezionare \(k\) oggetti da un insieme che ne contiene \(n\). Per applicare correttamente le formule del calcolo combinatorio è fondamentale stabilire secondo quali regole vengono scelti gli oggetti, come capiremo meglio nei prossimi paragrafi.

Disposizioni semplici

Parliamo di disposizioni semplici quando consideriamo insiemi di oggetti che verificano i seguenti requisiti:

  • un oggetto non può essere scelto più di una volta;
  • l'ordine di scelta degli oggetti è significativo.

Immaginiamo ad esempio che otto persone partecipino ad una competizione e che i primi tre classificati vincano tre premi diversi: in quanti modi possibili si può concludere la gara? Per il primo posto abbiamo \(8\) possibili candidati; per il secondo, una volta stabilito il primo, rimangono \(7\) persone mentre per il terzo posto restano \(6\) possibili scelte. Il numero totale di disposizioni ottenibili è quindi dato da \(8\cdot 7\cdot 6=336\).

Più in generale, dire che il numero di disposizioni semplici di \(n\) oggetti presi a \(k\) a \(k\) è dato dalla formula $$D_{n,k}=n(n-1)(n-2)\ldots(n-k+1).$$Ricordando la funzione fattoriale, definita come $$0!=1, \\ n!=n(n-1)(n-2)\ldots3\cdot2\cdot 1, \forall n\in\mathbb{N}^+$$otteniamo una formula equivalente per le disposizioni semplici: $$D_{n,k}=\frac{n!}{(n-k)!}.$$

Permutazioni semplici

Consideriamo ora una situazione simile a quella del paragrafo precedente, con la differenza che ora tutti e otto i partecipanti alla gara ricevono un premio, seppur di valore diverso. In questo caso, le disposizioni potranno differire tra loro solo per l'ordine con cui sono stati premiati i concorrenti: parleremo in questo caso di permutazioni semplici. Le permutazioni quindi non sono che un caso particolare delle disposizioni, ottenuto quando \(k=n\) e cioè quando tutti gli elementi dell'insieme vengono prima o poi scelti. La formula per il calcolo delle permutazioni deriva automaticamente da quella delle disposizioni: $$P_n=D_{n,n}=\frac{n!}{(n-n)!}=\frac{n!}{0!}=n!.$$Nel caso del nostro esempio le permutazioni degli otto partecipanti sono \(8!=40320\).

Combinazioni semplici

A differenza delle disposizioni, parliamo di combinazioni semplici quando l'ordine di scelta degli oggetti non è significativo; più concretamente, le coppie \(\{a,b\}\) e \(\{b,a\}\) generano due diverse disposizioni ma contano come una singola combinazione. Per rifarci al solito esempio della gara, se supponiamo che i tre vincitori ricevano lo stesso premio, allora l'ordine di premiazione non ha più alcuna importanza e pertanto entreremo nell'ambito delle combinazioni.

Il numero delle disposizioni di \(8\) oggetti presi a \(3\) a \(3\) era \(336\) ma ora dobbiamo eliminare tutte le disposizioni che differiscono solo per l'ordine. Ad esempio, le disposizioni $$\{B,E,G\} \\ \{B,G,E\}\\ \{E,B,G\} \\ \{E,G,B\} \\ \{G,B,E\} \\ \{G,E,B\}$$generano un'unica combinazione, essendo tutte permutazioni della medesima terna. Deduciamo allora che per calcolare il numero delle combinazioni è sufficiente dividere il numero delle disposizioni per il numero delle permutazioni, ottenendo nello specifico $$C_{8,3}=\frac{D_{8,3}}{P_3}=\frac{336}{6}=56.$$Possiamo generalizzare quanto appena detto dicendo che il numero di combinazioni semplici di \(n\) oggetti presi a \(k\) a \(k\) è $$C_{n,k}=\frac{D_{n,k}}{P_k}=\frac{n!}{(n-k)!k!}.$$Data l'importanza delle combinazioni nella matematica (ad esempio nel calcolo delle probabilità) si è deciso di dare un nome particolare al numero \(C_{n,k}\): esso viene detto coefficiente binomiale "\(n\) su \(k\)" e viene indicato col simbolo $$C_{n,k}=\binom{n}{k}.$$

Disposizioni con ripetizione

I raggruppamenti che abbiamo considerato nei paragrafi precedenti erano tutti accomunati dall'essere costituiti da elementi distinti. Esamineremo ora invece cosa succede quando ciascun elemento di un insieme può essere scelto anche più di una volta. Parleremo di disposizioni con ripetizione quando la scelta degli oggetti rispetta le seguenti regole:

  • un oggetto può essere scelto quante volte si vuole;
  • l'ordine di scelta degli oggetti è significativo.

Per determinare il numero delle disposizioni con ripetizioni analizziamo il seguente esempio: un test consiste in dieci domande, ciascuna delle quali ammette tre possibili risposte A, B o C. Per ogni casella abbiamo tre possibili risposte visto che nessuno ci vieta di usare la stessa risposta più volte, inoltre l'ordine è significativo visto che invertire due risposte comporta risultati diversi.

Ragionando in modo simile a quanto fatto per le disposizioni semplici, deduciamo che il numero di disposizioni con ripetizione si ottiene moltiplicando tra loro i numeri di scelte ad ogni passo, e pertanto avremo $$D_{3,10}^r=3\cdot3\cdot3\cdot3\cdot3\cdot3\cdot3\cdot3\cdot3\cdot3=3^10.$$A questo punto è immediato estendere il ragionamento al caso in cui abbiamo \(n\) oggetti da prendersi a gruppi di \(k\): $$D_{n,k}^r=n^k.$$

Permutazioni con ripetizione

Mentre le permutazioni semplici erano un caso particolare delle disposizioni semplici, lo stesso non si può dire delle permutazioni con ripetizione nei confronti delle disposizioni con ripetizione: in queste ultime infatti il numero di ripetizioni era variabile, mentre nel caso delle permutazioni il numero di ripetizioni è fissato a priori. Prendiamo ad esempio le lettere della parola "asso": se consideriamo le disposizioni con ripetizione, potremmo prendere le lettere "a", "s" e "o" quante volte vogliamo, mentre se parliamo di permutazioni siamo vincolati a usare una volta ciascuna le lettere "a" e "o" e due volte la lettera "s". Le permutazioni semplici sarebbero \(n!\), ma questo numero ora è troppo grande in quanto considera le parole "asso" e "asso" come due permutazioni distinte (i colori servono solo a indicare che abbiamo permutato tra loro le "s"). Il totale delle permutazioni semplici va quindi diviso per le permutazioni delle lettere ripetute, permettendoci di concludere che $$P_{4,2}^r=\frac{4!}{2!}=12.$$Nell'introduzione di questa lezione si chiedeva quanti fossero gli anagrammi della parola matematica: in questo caso abbiamo la lettera "a" ripetuta \(3\) volte e le lettere "m" e "t" ripetute \(2\) volte ciascuna. Il numero di permutazioni sarà allora $$P_{10,3,2,2}^r=\frac{10!}{3!2!2!}=151200.$$In generale diremo che dati \(n\) oggetti ripetuti rispettivamente \(k_1 k_2\ldots k_n\) volte, il numero delle loro permutazioni è $$P_{n,k_1,k_2\ldots k_n}^r=\frac{n!}{k_1!,k_2!\ldots k_n!}.$$

Combinazioni con ripetizione 

L'ultimo caso che presentiamo è quello delle combinazioni con ripetizione, ovvero raggruppamenti di oggetti dove l'ordine di scelta non è significativo e un oggetto può essere pescato più volte. Immaginiamo questo scenario: Aldo e Basilio si sfidano tre volte a una gara per stabilire chi sia il migliore: gli esiti possibili sono \(4\): Aldo vince \(3\) a \(0\); Aldo vince \(2\) a \(1\); Basilio vince \(3\) a \(0\); Basilio vince \(2\) a \(1\). Finché abbiamo a che fare con numeri piccoli possiamo calcolare le combinazioni con ripetizione elencandole esplicitamente ma ciò diventa improponibile in presenza di numeri grandi. Senza scendere nei dettagli, l'idea per calcolare il numero di combinazioni con ripetizione è quello di immaginare che oltre agli \(n\) oggetti iniziali ci siano a disposizione anche \(k-1\) oggetti "fittizi" che rappresentano le possibili ripetizioni. A questo punto applichiamo la formula delle combinazioni semplici partendo dal nuovo insieme di \(n+k-1\) oggetti: $$C_{n,k}^r=C_{n+k-1,k}=\binom{n+k-1}{k}.$$Con riferimento all'esempio citato a inizio paragrafo, il numero massimo di ripetizioni è \(2\), e pertanto introduciamo due oggetti fittizi C e D. Le combinazioni semplici a tre a tre di {A,B,C,D} coincidono con le combinazioni con ripetizione di {A,B}, infatti 

{A,B,C}\(\leftrightarrow\){A,B,A}

{A,B,D}\(\leftrightarrow\){A,B,B}

{A,C,D}\(\leftrightarrow\){A,A,A}

{B,C,D}\(\leftrightarrow\){B,B,B}

Notiamo infine che la formula delle combinazioni con ripetizione è soddisfatta, infatti $$C_{2,3}^r=\binom{2+3-1}{3}=\frac{4!}{3!1!}=4.$$