Che cos'è il calcolo combinatorio
Si tratta di uno dei primi argomenti che si affrontano in Statistica alle scuole superiori. Per definizione questa branca della Matematica studia i metodi per raggruppare un insieme o più insiemi di elementi.
Porta perciò a elaborare delle combinazioni, da cui deriva il nome dell’argomento, che sono in numero variabile a seconda della numerosità dei gruppi da organizzare.
Pensando al mondo delle scommesse e del gioco d’azzardo troviamo diverse situazioni a cui applicare il calcolo combinatorio. Ma lo stesso vale per quando bisogna per esempio sbloccare una serratura chiusa con un codice di un determinato numero di cifre o lettere.
Le disposizioni semplici e con ripetizione
Gli elementi che dobbiamo raggruppare con il calcolo combinatorio possono formare sia gruppi ordinati che non ordinati. Nel primo caso parliamo di disposizioni, che sono sequenze ordinate di k elementi selezionati da un gruppo di n elementi distinti, con k ≤ n. Ciascuna disposizione prevede k elementi e differisce dalle altre almeno per un elemento o per l’ordine in cui le componenti si dispongono.
Il numero di disposizioni che si possono ottenere si indica con il simbolo Dn,k e per calcolarlo abbiamo a disposizione due formule. Per le disposizioni semplici si ricorre al calcolo Dn,k = n!/(n – k)!. Sia n! che (n – k)! sono fattoriali, ovvero il prodotto fra tutti i numeri interi positivi minori o uguali rispettivamente di n e (n – k).
Il calcolo combinatorio delle disposizioni con ripetizioni (D’n,k ) invece richiede una formula molto più semplice, cioè D’n,k = nk. Proviamo a vedere un esempio calcolando il numero di disposizioni semplici di classe 2 delle lettere della parola vaso. Dato che n = 4 e k = 3 useremo la formula D4,3 = 4!/(4 – 3)! = 6. Invece se dovessimo calcolare le disposizioni con ripetizione di classe 4 delle lettere della parola certo useremo D’5,4 = 54 = 625.
Il calcolo combinatorio delle permutazioni
A differenza delle disposizioni le permutazioni si costruiscono scambiando l’ordine degli elementi di una sequenza. In base alla modalità con cui si decide di ordinarli se ne possono ottenere di tre tipi diversi: semplici, con ripetizione e circolari.
Quando consideriamo un insieme contenente n elementi consideriamo permutazioni tutti i possibili raggruppamenti che li prevedono tutti.
Partiamo dalle permutazioni semplici, il cui numero si indica con il simbolo Pn e che corrispondo al fattoriale del numero di elementi da permutare. Per calcolarle quindi si usa la formula Pn = n!. Considerando un insieme B = {a,b,c,d,e} il numero delle sue permutazioni semplici sarà P5 = 5! = 120.
Ora passiamo al calcolo combinatorio delle permutazioni con ripetizione, che contengono sempre n elementi ma alcuni sono presenti più di una volta. La formula da usare è Pnn1,n2,n3… = n!/n1! · n2! · n3!… dove n1, n2 e n3 sono le tipologie di elementi che si ripetono nella sequenza. Se abbiamo per esempio la successione di cifra 55484 abbiamo n = 5, n1 = 2 (il 5) e n2 = 2 (il 4).
Infine abbiamo le permutazioni circolari, dove in una sequenza si scambiano di posto gli elementi in modo tale che non si può distinguere tra il primo e l’ultimo.
La formula da usare è Pcn = (n – 1)!. Nel fattoriale si considera un elemento in meno proprio perché la disposizione circolare impedisce di capire l’inizio e la fine della sequenza.
La combinazioni semplici e con ripetizione
Quando si ha un insieme di n elementi le combinazioni di classe k sono tutti quei gruppi che contengono k elementi, ma differiscono per almeno un componente. Il calcolo combinatorio però prevede che questa differenza non si estenda all’ordine degli elementi.
Le combinazioni semplici hanno k elementi scelti da un insieme che ne contiene numerosità n, con k ≤ n, tutti diversi fra di loro. Per calcolare quante se ne possano generare utilizziamo la formula Cn,k = n!/k!(n – k)!. Facciamo un esempio prendendo un insieme con 10 elementi e k = 4; nella formula scriveremo C10,4 = 10!/4!(10-4)! = 10!/4! · 6!.
Per quanto riguarda invece le combinazioni con permutazione nel calcolo combinatorio consideriamo sempre sequenze di k elementi in cui alcuni sono presenti più volte. La formula da utilizzare per calcolare tutte quelle possibili è leggermente più complessa della precedente. Indichiamo il loro numero con C’n,k e il calcolo da eseguire è (n + k – 1)!/k!(n – 1)!.
Dunque se dovessimo formare delle combinazioni con ripetizione prendendo classi di 5 elementi da un insieme di 12 lettere il calcolo sarebbe C’n,k = (12 + 5 – 1)!/5!(12 – 1)! = 16!/5! · 11!.
Come affrontare i problemi di calcolo combinatorio
Quando il quesito precisa che l’ordine non è rilevante, per esempio, si può essere sicuri di optare per la formula delle combinazioni.
Se si può usare un simbolo o un elemento più di una volta è facile intuire che sia il caso in cui si verifica la ripetizione.
Se invece il problema rende chiaro che l’ordine in cui gli elementi si dispongono in sequenza ha un certo rilievo siamo di fronte a una permutazione o a una disposizione. Nel primo caso tuttavia k sarà sempre uguale a n, mentre nel secondo il valore di k può essere diverso anche se sempre inferiore.
Un esempio di problema
Proviamo ad affrontare uno di questi esercizi per avere più chiari i ragionamenti al paragrafo precedente. Una classe di 15 ragazzi va a cena insieme, e al momento di andare via ciascuno stringe la mano a tutti gli altri. Quante saranno le strette di mano totali?
La stretta di mano comprende due persone alla volta quindi k = 2, mentre il numero di ragazzi rappresenta n ed è uguale a 15. Dato che nessuno si stringe la mano da solo non può esserci ripetizione, e l’ordine non ha un’importanza particolare. Di conseguenza si tratta di una combinazione semplice.
La formula di calcolo combinatorio da usare quindi è Cn,k = n!/k!(n – k)!. Sostituendo i dati si ottiene 15!/2! · 13! = 105 strette di mano.
