305-Introduzione-CALCOLO-COMBINATORIO

Calcolo combinatorio
E’ detto calcolo combinatorio il complesso delle procedure che permettono il conteggio dei vari
tipi di raggruppamenti che possono essere formati scegliendo k elementi tra gli n elementi di un
insieme assegnato
Fattoriali
Dato il numero naturale n > 0, si dice fattoriale di n e lo si indica con n! il numero naturale ottenuto
moltiplicando tra di loro tutti i numeri naturali da 1 a n incluso.
n !  n  (n  1)  (n  2)..3  2 1
risulta ovvio che
1!  1
per n > 1 vale la seguente identità
n !  n  (n  1)!
volendo che la precedente relazione valga anche per n = 1, dalla (1.2) si ha
0! 1
se k < n,
n !  n  (n  1)  (n  2)...(n  k  1)  k !
da cui :
n!
 n  (n  1)  (n  2)...(n  k  1)
k!
la funzione fattoriale può essere generalizzata all'insieme dei numeri reali con la funzione gamma , Γ , di Eulero


(z)  t
0
z 1  t
e
dt
1
1  3  5    (2n  1) 1
(n  ) 
( )
2
2n
2
1
( )  
2
nella risoluzione dei problemi combinatori e’ fondamentale sapere :
- se l'ordinamento è importante, ossia se due configurazioni sono le stesse a meno di un riordinamento
ad es. {a,b,c} è uguale a {c,a,b}
- se si possono avere più ripetizioni di uno stesso oggetto, ossia se uno stesso oggetto dell'insieme può o meno essere
riusato più volte all'interno di una stessa configurazione
- se gli oggetti sono tutti distinguibili
Permutazioni
una permutazione di un insieme di oggetti è una “presentazione ordinata", cioè una sequenza, dei suoi elementi nella quale ogni oggetto
viene presentato una ed una sola volta per contare quante siano le permutazioni di un insieme con n oggetti basta osservare che il primo
elemento della configurazione può essere scelto in n modi diversi, il secondo in (n-1), il terzo in (n-2) e così via sino all'ultimo oggetto
in conclusione: dato un insieme di n elementi distinti, si dicono permutazioni Pn tutti i possibili diversi ordinamenti di tali elementi
il numero delle possibili permutazioni e’
Pn  n !
P1  1!  1 e per induzione: da ogni permutazione di n elementi si formano n+1 permutazioni di n+1 elementi.
quindi la
Pn  n ! vale per ogni n ≥ 1
in totale le permutazioni di n+1 elementi risultano Pn 1  n !(n  1)  (n  1)!
è evidente che
ad esempio : le permutazioni degli elementi dell'insieme {a,b,c} sono 3! = 6: abc, bac ,bca, cab, cba, acb.
Disposizioni semplici
Una disposizione semplice di lunghezza k di elementi di un insieme di n oggetti, con k ≤ n, è una presentazione ordinata di k
elementi nella quale non si possono avere ripetizioni di uno stesso oggetto
per avere il numero di queste configurazioni si considera che il primo componente di una tale sequenza può essere scelto in n modi
diversi, il secondo in (n-1) e così via, sino al k-esimo che può essere scelto in (n – k + 1) modi diversi
in conclusione:
dato un insieme di n elementi distinti si dicono disposizioni semplici di classe k, Dn,k con (k ≤ n) tutti i diversi
ordinamenti di k elementi scelti tra gli n oggetti dati
accodando ad ogni singola disposizione di classe k le permutazioni degli n-k elementi rimanenti si ottengono tutte le permutazioni
Pn  Dn ,k Pn  k in conclusione il numero delle disposizioni e’
degli n elementi, si ha quindi
Dn ,k 
Pn
n!

Pn  k (n  k )!
le permutazioni sono casi particolari delle disposizioni semplici: le permutazioni di un insieme di n oggetti sono le disposizioni semplici di
tali oggetti di lunghezza n. In effetti il loro numero e’
Dn ,n 
n!
 n !  Pn
0!
ad esempio: le disposizioni semplici di lunghezza 2 degli elementi dell'insieme {1,2,3,4,5} sono 5!/(5-2)! = 5!/3! = 120/6 = 20:
12, 13, 14, 15, 21, 23, 24, 25, 31, 32, 34, 35, 41, 42, 43, 45, 51, 52, 53, 54.
da notare come l’ordine conti: 12 e’ considerato distinto da 21 etc.
Disposizioni con ripetizione
Una presentazione ordinata di elementi di un insieme nella quale si possono avere ripetizioni di uno stesso elemento si dice
disposizione con ripetizione.
in conclusione:
dato un insieme di n elementi distinti si dicono disposizioni con ripetizione di classe k, D’n,k , i raggruppamenti
formati con k elementi scelti anche più volte tra gli n dati. k può quindi risultare anche maggiore di n
cerchiamo il numero delle possibili sequenze di k oggetti estratti dagli elementi di un insieme di n oggetti, ognuno dei quali può essere
preso più volte: si hanno n possibilità per scegliere il primo componente, n per il secondo, altrettante per il terzo e così via, sino al
k-esimo che completa la configurazione.
il numero cercato è
ad esempio :le disposizioni con ripetizione di lunghezza 2 degli elementi di {1,2,3,4,5} sono 52 = 25:
11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55.
Combinazioni semplici
Si chiama combinazione semplice una presentazione di elementi di un insieme nella quale non ha importanza l'ordine dei componenti
e non si può ripetere lo stesso elemento più volte.
La collezione delle combinazioni di k elementi estratti da un insieme di n oggetti distinti si può considerare ottenuta dalla collezione delle
disposizioni semplici di lunghezza k degli elementi dell’insieme ripartendo tali sequenze nelle classi delle sequenze che presentano lo
stesso sottoinsieme e scegliendo una sola sequenza da ciascuna di queste classi.
Ciascuna delle suddette classi di sequenza di lunghezza k contiene k! sequenze, in quanto accanto a una determinata sequenza si hanno
tutte e sole quelle ottenibili permutando i componenti della sequenza.
ad esempio: le disposizioni semplici di lunghezza 2 degli elementi dell'insieme {1,2,3,4,5} sono 20 in totale:
12, 13, 14, 15, 21, 23, 24, 25, 31, 32, 34, 35, 41, 42, 43, 45, 51, 52, 53, 54
12, 13, 14, 15,
23, 24, 25,
34, 35,
45
mentre le combinazioni semplici saranno 10 in totale
dato che l’ordine non conta gli elementi tipo 12 e 21 etc. corrispondono alla stessa combinazione
il numero delle combinazioni semplici di n elementi di lunghezza k si ottiene dividendo per k! il numero delle disposizioni semplici di n
elementi di lunghezza k:
quindi
Cn,k
Dn,k
n!


Pk
k !(n  k )!
i Cn,k coincidono con i numeri del triangolo di Pascal (o di Tartaglia), e sono percio’ denominati coefficienti binomiali.
in questo contesto sono denotati come
n
n!

 
 k  k !(n  k )!
Combinazioni con ripetizione
dato un insieme di n elementi distinti si dicono combinazioni con ripetizione di classe k, C'n,k , gli insiemi
formati con k elementi scelti anche più volte tra gli n dati k può quindi risultare anche maggiore di n.
il numero delle combinazioni con ripetizione di n elementi di classe k è uguale al numero delle combinazioni
semplici di classe k che si otterrebbero aggiungendo agli n elementi dati altri k-1 elementi distinti.
ad esempio, dati tre elementi a, b, c, calcolando le combinazioni con ripetizione di classe 5, si ottiene, tra le
altre, la combinazione aaaaa, impossibile se a non potesse essere ripetuta, possibile se si considerano come
elementi distinti tra di loro le quattro , ossia le (k – 1) a finali
quindi
C 'n,k
 n  k  1


k


 2  4  1

  5 modi di distribuire a 2 persone diverse 4 oggetti indistinguibili, contando anche i casi
 4 
in cui una delle persone non riceve nessun oggetto: 0-4, 1-3, 2-2, 3-1, 4-0
ad esempio, vi sono
n
k 
in effetti   
 n  k  1
n!
(n  k  1)!
(n  k  1)!

quindi 


k !(n  k )!
k !(n  1)!
 k  k !(n  k  1  k )!
in questo caso n = 2 e k = 4 percio’
5!
5  4  3  2 1
(2  4  1)!
 2  4  1


5



4!
1!
4

3

2

1
4!
(2

1)!
4

