Il Calcolo combinatorio è una branca della matematica orientata allo sviluppo di formule che permettono di ottenere il numero di casi distinti che si possono presentare in un esperimento, od il numero di elementi che compongono un insieme, senza ricorrere alla loro enumerazione esplicita.

   Qualcuno ha definito la combinatoria come "l'arte di contare ... senza contare" mettendo in evidenza la maggiore importanza che in combinatoria ha la conoscenza del numero di combinazioni, rispetto alla conoscenza delle combinazioni stesse.

Serve conoscere prima i seguenti dati:

• il numero di oggetti disponibili

• il numero di quelli che costituiscono una sola combinazione

• le regole per procedere alla costituzione delle combinazioni: si possono utilizzare tutti gli oggetti disponibili oppure solo una parte; lo stesso oggetto può essere utilizzato una sola volta o più volte in una stessa combinazione, regole che stabiliscono se conta oppure no l'ordine in cui sono disposti gli oggetti nelle varie combinazioni.

PRINCIPIO FONDAMENTALE DEL CALCOLO COMBINATORIO:

Se una scelta può essere fatta in r modi diversi, per ciascuno dei quali una seconda scelta può essere effettuata in s modi diversi, e, per ciascuno dei modi in cui si sono compiute le prime due scelte una terza scelta può essere effettuata in t modi diversi ecc., allora la successione di tutte le scelte può essere compiuta in r·s·t... modi diversi.

Sotto è rappresentato un schema dicotomico che può essere un valido aiuto per trovare la giusta combinazione. Per utilizzare lo schema, occorre preliminarmente fissare i valori n = numero di elementi disponibili e k = numero di elementi contenuti in una combinazione. Poi si può procedere lungo il grafo, scegliendo il percorso in base alla risposta data ai vari quesiti; al termine si otterrà una risposta fra le sette possibili elencate a destra.   

 Schema dicotomico per trovare la giusta combinazione:

 1) PERMUTAZIONI SEMPLICI DI n OGGETTI sono le combinazioni di n elementi in cui conta l'ordine in cui gli elementi sono disposti e non si possono ripetere gli stessi elementi all'interno di ogni permutazione.

Si chiama FATTORIALE  di un numero naturale n il prodotto di tutti i numeri naturali compresi fra 1 e n: n fattori interi decrescenti da n ad 1.  Il fattoriale di un numero naturale n si indica col simbolo: n! e indica il numero di permutazioni semplici o ordinamenti di n oggetti:

n! = n⋅ (n-1)⋅(n-2)⋅...⋅2⋅1

Esempi:    4! = 4 ⋅3 ⋅2 ⋅1 = 24.          Il fattoriale di 4 è 24.

                  3! = 3 ⋅2 ⋅1 = 6.                Il fattoriale di 3 è 6.

                  5! = 5 ⋅4 ⋅3 ⋅2 ⋅1 = 120.   Il fattoriale di 5 è 120.

Proprietà:            n! = n⋅(n-1)!          Per convenzione:   0! =1.    

    I primi 10 valori del fattoriale di n sono:

Il numero complessivo di permutazioni di n oggetti è: 

Esempio:

A teatro vogliamo contare in quanti modi possiamo far sedere tre persone su tre sedie. La prima persona sarà indicata con A , la seconda con B e la terza con C.

Le 6 possibili combinazioni sono : ABC, ACB, BAC, BCA, CAB, CBA. (3!=3⋅2⋅1=6)

2) PERMUTAZIONI CON RIPETIZIONE

    Una permutazione di n oggetti di cui h uguali tra loro e distinti dai precedenti, k uguali tra loro e distinti dai precedenti, ..., p uguali tra loro e distinti dai precedenti con h+k+...+p=n è:

Esempio 1:

Quanti sono i numeri che è possibile formare con le cifre date dall'insieme A= {1,2,2,3} ?

Ci sono quattro elementi di cui due ripetuti, ragion per cui la formula iniziale non è applicabile venendo a mancare una condizione necessaria. Dobbiamo sfruttare quanto appena appreso: permutazioni con ripetizione!  Il risultato è:

Esempio 2:

In un ufficio si devono stabilire le ferie per 10 impiegati e si hanno 3 turni: nel primo vanno in ferie 3 impiegati, nel secondo 4 impiegati e nel terzo 3 impiegati. Quante sono le assegnazioni possibili dei 10 impiegati ai 3 turni? Notiamo prima di tutto che i turni sono ordinati ma all'interno di ogni turno l'ordine degli impiegati non conta. Il numero di scelte è:

3) DISPOSIZIONI SEMPLICI DI n OGGETTI DI CLASSE k

    Si dice "disposizione semplice di n oggetti a k a k" o anche "di classe k" 

(con k ≤ n) ogni allineamento con oggetti tutti distinti, di n oggetti a gruppi di k.

Il numero totale di  n  oggetti a gruppi di k  è dato da:

   (ci sono k fattori)

Possiamo infatti scegliere in n modi diversi l'oggetto da mettere al primo posto, in n-1 modi quello da mettere al secondo posto (vanno bene tutti, tranne quello messo al primo posto), in n-2 modi quello da mettere al terzo posto e così via fino all'ultimo posto; poiché i posti sono k, all'ultimo posto potremo scegliere tra n-(k-1) oggetti (tutti meno i (k-1) già utilizzati). 

Osservazione: Le permutazioni di n elementi sono tutti i possibili allineamenti che si ottengono scambiando semplicemente di posto gli n oggetti. Esse coincidono con le disposizioni semplici di n elementi di classe n.

Esempio:  Un concessionario di automobili vuole esporre nella vetrina del suo salone quattro vetture tutte dello stesso tipo ma con 4 colori diversi (blu, grigio, rosso e nero). La vetrina però dispone di soli due posti: uno fisso e l’altro fornito di una piattaforma rotante. Il concessionario desidera sapere in quanti modi diversi è possibile disporre le auto. Usiamo un diagramma ad albero per rappresentare la situazione:

Si hanno le seguenti possibilità: NB,  NG, NR, BG, BR, BN, RN, RG, RB, GN, GR, GB.

Il numero di disposizioni di 4 oggetti di classe 2:    

4) DISPOSIZIONI CON RIPETIZIONE

    Una disposizione con ripetizione di n oggetti distinti presi k alla volta è un possibile modo di scegliere k oggetti eventualmente ripetuti dagli n e ordinarli.

Esempio: Consideriamo l'insieme: A = {1,3,5,8}; vogliamo determinare quanti numeri a due cifre si possono scrivere con gli elementi di A, considerando che sono ammesse le ripetizioni.

Le possibili combinazioni sono 16: 

11,13,15,18,31,33,35,38,51,53,55,58,81,83,85,88 

e si indicano con: 

Se si considerasse di costruire numeri di tre cifre, le possibilità  salgono a 64.

5) COMBINAZIONI SEMPLICI

Le combinazioni di n oggetti presi a k a k, sono il numero dei campioni non ordinati di numerosità k. Non conta l'ordine, quindi (a,b) sarà lo stesso campione di (b,a). 

Il simbolo usato per le combinazioni semplici è:  si legge "n su k" e prende il nome, per motivi storici, di coefficiente binomiale. Esprime il numero di sottoinsiemi distinti di cardinalità k che si possono formare con gli elementi di un insieme di cardinalità n, praticamente si risponde alla domanda:"dati n oggetti, in quanti modi ne posso scegliere k?"
(abbiamo sempre k ≤ n)

Proprietà:                 

I coeficienti binomiali  si possono calcolare tramite il triangolo di Tartaglia (o di Pascal):

Esempio :   dove 5 rappresenta la riga e 3 rappresenta il posto nella rispettiva riga. Il triangolo di Tartaglia può essere rappresentato anche così:

I coefficienti binomiali sono i coefficienti dello sviluppo delle potenze di un binomio (binomio di Newton) :

Esempio 1:

Quanti terni si possono formare con i 90 numeri del gioco del Lotto ?

Poiché l’ordine di estrazione dei numeri non ha alcuna importanza, si tratta di combinazioni semplici:

Esempio 2:

Calcola il numero di strette di mano che si possono effettuare fra 6 persone.

Esempio 3:

Qual è la probabilità che in trenta lanci di un dado, esca venti volte un numero maggiore di 4?

L'evento A= "uscita di un numero maggiore di 4" ha la probabilità : . La probabilità dell'evento contrario : "uscita di un numero non maggiore di 4" è : .

Risulta così:

6) COMBINAZIONI CON RIPETIZIONE

    Una combinazione con ripetizione è una combinazione che può avere anche ripetizioni di uno stesso elemento.  Il numero di combinazioni con ripetizione di n oggetti di classe k sono tutti i possibili raggruppamenti che si possono formare con n oggetti, presi k alla volta, considerando differenti due raggruppamenti che differiscano: 

–  per qualche elemento

–  per il numero di volte in cui un dato oggetto viene ripetuto

In tal caso, come si capisce facilmente, l’ordine in cui compaiono gli elementi non è più significativo e ovviamente in questo caso k può essere maggiore, minore o uguale ad n.

C'è un modo tradizionale di enunciare questo problema noto come "problema della pasticceria": nel banco della pasticceria ci sono n tipi diversi di paste e io voglio riempire un vassoio con k paste (con eventuali ripetizioni, cioè posso prendere due o più o, al limite, tutte le k paste dello stesso tipo). In quanti modi diversi posso riempire il vassoio? La risposta è: 

Esempio 1:

Sia A= {1,2,3,4,5}. Quanti gruppi si possono formare con cinque elementi assegnati tale che ciascun gruppo ne contenga due ?

 

infatti, abbiamo: (1,2) (1,3) (1,4) (1,5) (2,3) (2,4) (2,5) (3,4) (3,5) (4,5) (1,1) (2,2) (3,3) (4,4) (5,5).

Esempio 2:
Quanti sono i monomi di 4° grado che si possono formare con le variabili a,b,c ?

Sono tutte le quaterne non ordinate contenenti i simboli a,b,c che possono essere ripetuti più volte. Ad esempio i monomi:

Si devono considerare pertanto le combinazioni (perché non conta l'ordine) con ripetizioni dei tre elementi a,b,c presi a 4 a 4. Quindi i possibili monomi sono :

Per il numero di possibili estrazioni di k oggetti da una scatola contenente n oggetti, tenendo conto del fatto che gli oggetti vengono oppure non vengono sostituiti (rimpiazzati, rimessi) possiamo tener conto della seguente tabella:
 

Nella successiva scheda si presenteranno esempi di come si applicano le nozioni apprese di calcolo combinatorio al problema del calcolo delle probabilità.