Post on 18-Oct-2020
Elementi di Analisi Combinatoria
Angelica Malaspina
Dipartimento di Matematica, Informatica ed EconomiaUniversita degli Studi della Basilicata, Italy
angelica.malaspina@unibas.it
A. Malaspina Elementi di Analisi Combinatoria
Lo studio dei vari raggruppamenti che si possono fare con unnumero finito di oggetti e il modo di calcolare tale numero sichiama calcolo combinatorio.
Risulta un problema assai interessante calcolare quanti sono idiversi modi di raggruppare gli oggetti di un insieme.
Ad es. quante sigle diverse si possono fare con tre letteredell’alfabeto, in quanti modi diversi si possono abbinare duesquadre di un torneo.
A. Malaspina Elementi di Analisi Combinatoria
Disposizioni
Sia A un insieme costituito da un numero finito di elementi pari adn, si chiama disposizione (semplice) di n oggetti di classe k(k ≤ n) un sottoinsieme di A di k oggetti ordinati presi in modotale che ogni elemento compaia al massimo una volta.
Il modo di scrivere gli oggetti nelle disposizioni emolto importante.
A. Malaspina Elementi di Analisi Combinatoria
Esempi
Le seguenti sono disposizioni di classe 3 dell’alfabeto
a c m
m c a
c a m
Esse sono disposizioni diverse tra loro, perche le letterecompaiono in ordine diverso.
Le seguentib q
b k
sono disposizioni di classe 2 dell’alfabeto diverse tra loro perche hanno un elemento diverso.
A. Malaspina Elementi di Analisi Combinatoria
Numero di disposizioni semplici
Contiamo il numero di disposizioni di 2 lettere su 3 date.Sia A = {a, b, c}.Preso un elemento di A, ad esempio a, possiamo abbinare ad a glialtri due rimanenti di A, cioe b e c , ottenendo a b e a c . Questoragionamento si fa pure per gli altri due elemnti di A. Quindi intotale il numero di disposizioni di classe 2 di A e pari a
3 · 2 = 6.
Le possibili disposizioni semplici di 2 lettere rispetto ad A sono
a b a c b a b c c a c b
A. Malaspina Elementi di Analisi Combinatoria
Numero di disposizioni semplici
Il numero delle disposizioni semplici Dn,k di n oggetti presi k allavolta e uguale al prodotto dei primi k numeri naturali decrescenti apartire da n:
Dn,k = n(n − 1)(n − 2) · · · (n − k + 1), k ≤ n. (1)
Possiamo scegliere il primo elemento tra gli n dati.Il secondo elemento, possiamo sceglierlo tra gli (n − 1) rimanentiSe k = 2, allora Dn,2 = n(n − 1)
Se k = 3, allora Dn,3 = n(n − 1)(n − 2)
Il k-mo elemento si puo sciegliere in (n − k + 1) modi.
A. Malaspina Elementi di Analisi Combinatoria
Un caso particolare di disposizioni semplici: le permutazioni
Se k = n, le disposizioni semplici di classe n su n oggetti sichiamano permutazioni.
Il numero di permutazioni di n oggetti Pn si ottiene da (1)ponendo k = n (Dn,n = Pn), esso e pari al prodotto dei primi nnumeri naturali:
Pn = n(n − 1)(n − 2) · · · 2 · 1 (2)
A. Malaspina Elementi di Analisi Combinatoria
Il fattoriale
Si chiama fattoriale di n ∈ N e si indica con
n!
il prodotto dei numeri naturali da 1 a n
n! = 1 · 2 · . . . · (n − 1) · n.
0! = 1 1! = 1
(n + 1)! = n!(n + 1)
Con la notazione introdotta, la (2) si scrive:
Pn = n! (3)
A. Malaspina Elementi di Analisi Combinatoria
Esempio di permutazione
Quanti modi possibili possiamo mettere in sequenza le cartenapoletane?
40!=815.915.283.247.897.734.345.611.269.596.115.894.272.000.000.000
Il numero 40! e formato da 48 cifre
A. Malaspina Elementi di Analisi Combinatoria
Un altro modo di scrivere, Dn,k
Tenendo presente la definizione di fattoriale, Dn,k si puo scriverenel seguente modo:
Dn,k =n!
(n − k)!, k ≤ n (4)
Infatti
n!
(n − k)!=
1 · 2 · · · (n − k) · (n − k + 1) · · · (n − 1)n
1 · 2 · · · · (n − k)=
1 · 2 · · · (n − k)
1 · 2 · · · (n − k)· (n − k + 1) · · · (n − 1)n =
(n − k + 1) · · · · (n − 1)n = Dn,k
A. Malaspina Elementi di Analisi Combinatoria
Disposizioni con ripetizioni
Una parola dell’alfabeto puo essere pensata come disposizione dellelettere dell’alfabeto. Ad esempio
L I B R O
e una disposizione di 5 oggetti dell’alfabeto.Spesso, pero le lettere che compongono una parola sono ripetute.Ad esempio, nella parola
M A T E M A T I C A
le lettere M, A, T sono ripetute.
La parola M A T E M A T I C A rappresenta una disposizione conripetizione.
A. Malaspina Elementi di Analisi Combinatoria
Disposizioni con ripetizioni
Quante parole, anche prive di senso, si possono scriverecombinando 4 lettere (non necessariamente diverse) scelte dalle 21dell’alfabeto latino?
Si tratta di contare quante sono le sequenze ordinate, lunghek = 4, di elementi non necessariamente diversi, presi da un insiemeche ne contiene n = 21.La risposta e 214 = 194.481.
Si chiama disposizione con ripetizione di classe k ogniraggruppamento ordinato di k oggetti fra n dati con laconvenzione che ogni oggetto puo essere ripetuto. Il loro numero epari alla potenza k-ma di n:
D ′n,k = nk , k ≤ n.
A. Malaspina Elementi di Analisi Combinatoria
Esercizio sulle disposizioni ordinate con ripetizioni
Determinare quanti numeri diversi di tre cifre si possono formarecon le cifre {1, 2, 3}.
111, 112, 113, ....
Si tratta di scrivere le disposizioni con ripetizioi di tre elementi diclasse tre, per cui
D ′3,3 = 33 = 27
A. Malaspina Elementi di Analisi Combinatoria
Esempio di disposizione con ripetizioni:il lancio di due dadi
Supponiamo di lanciare due dadi distinti, uno rosso e uno blu.Indichiamo con D = {1, 2, 3, 4, 5, 6} l’insieme che rappresenta tuttii possibili risultati del lancio di un dado. Indichiamo con D2
l’insieme che rappresenta i possibili risultati del lancio simultaneodei due dadi. Gli elementi di D2 sono
D2 =
(1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (1, 6)(2, 1) (2, 2) (2, 3) (2, 4) (2, 5) (2, 6)(3, 1) (3, 2) (3, 3) (3, 4) (3, 5) (3, 6)(4, 1) (4, 2) (4, 3) (4, 4) (4, 5) (4, 6)(5, 1) (5, 2) (5, 3) (5, 4) (5, 5) (5, 6)(6, 1) (6, 2) (6, 3) (6, 4) (6, 5) (6, 6)
Si noti che la coppia (2, 3) e distinta dalla coppia (3, 2), infatti nelprimo caso il 2 esce nel lancio del dado rosso, nel secondo esce nellancio del dado blu.
D ′6,2 = 62 = 36
A. Malaspina Elementi di Analisi Combinatoria
Permutazioni con ripetizioni
La parola ORO contiene due lettere uguali. Il numero dianagrammi con tre lettere e pari a P3 = 3! = 6.Nel caso della parola ORO i possibili anagrammi distinti sonosoltanto: ORO, ROO, OOR, cioe sono 3 = P3/2 e non P3 = 6.
In generale, volendo calcolare le permutazioni di n oggetti in cui vene siano r identici fra loro, si ottiene un numero di permutazionidato da
P ′n =Pn
r !=
n!
r !. (5)
A. Malaspina Elementi di Analisi Combinatoria
Disposizioni senza ordine: combinazioni semplici
Si chiama combinazione semplice ogni scelta, indipendentedall’ordine, di k elementi in un insieme di n elementi.
Il numero di combinazioni di n oggetti in gruppi di k si indica conCn,k .
A. Malaspina Elementi di Analisi Combinatoria
Esempio di disposizioni senza ordine (combinazioni)
Dobbiamo selezionare 3 candidati su 8. Tutti risultano validi mapossiamo sceglierne solo 3. Quante possibili scelte abbiamosapendo che non e importante l’ordine con cui scegliamo, ma solochi scegliamo?
Se scegliessimo le k = 3 persone dando importanza all’ordine,avremmo costruito una disposizione semplice, ovvero avremmo
8!(8−3)! = 336 possibili scelte.Visto che non siamo interessati all’ordine, per ogni terna di personece ne saranno altre 5 ad essa equivalenti (perche 6 = 3! sono lepermutazioni possibili di 3 elementi). Allora il numero dicombinazioni possibili e dato da e visto che 6 = 3! sono lepermutazioni possibili di 3, il numero delle combinazioni possibili edato da
336
6= 56
A. Malaspina Elementi di Analisi Combinatoria
Cn,k
Dobbiamo scegliere k oggetti da un insieme di n.Ad ogni combinazione corrispondono k! disposizioni semplicidiverse, perche per costruire una disposizione semplice dobbiamoordinare i k elementi scelti, e questo possiamo farlo in k! modi.Dunque il numero di combinazioni e uguale al numero didisposizioni semplici diviso per k!.
Il numero di combinazioni di n oggetti in gruppi di k e
Cn,k =Dn,k
Pk=
n(n − 1) . . . (n − k + 1)
k!(6)
Tendendo presente la (4), (6) si scrive
Cn,k =n!
k!(n − k)!(7)
A. Malaspina Elementi di Analisi Combinatoria
Il coefficiente binomiale
Il numero (nk
)=
n!
k!(n − k)!(8)
si chiama coefficiente binomiale e si legge ”n su k”.
Quindi il numero di combinazioni semplici di n oggetti in gruppi dik e pari al coefficiente binomiale n su k :
Cn,k =
(nk
)
A. Malaspina Elementi di Analisi Combinatoria
Esempio
In una fase di un torneo sportivo, 4 squadre si devono incontrare,l’una contro l’altra. Quante partite verranno giocate?
(42
)=
4!
2!2!= 6
A. Malaspina Elementi di Analisi Combinatoria
Calcolo del coefficiente binomiale
Ne il calcolo del fattoriale ne quello del coefficiente binomiale sonoin genere presenti nelle calcolatrici. Uno dei motivi e che ilfattoriale (anche di numeri piccoli) e un numero molto grande.Vediamo come si puo procedere con carta e penna a calcolarealcuni coefficienti binomiali. Per calcolare il coefficiente binomialee piu agevole utilizzare la seguente espressione che si ricavaimmediamtamente dalla (8)(
nk
)=
n · (n − 1) · . . . · (n − k + 1)
k!
A. Malaspina Elementi di Analisi Combinatoria
Calcolo di coefficienti binomiali
(42
)=
4 · 32!
= 6
(53
)=
5 · 4 · 33!
=5 · 4 · 3
3·= 5 · 2 = 10
(127
)=
12 · 11 · 10 · 9 · 8 · 7 · 67!
=12 · 11 · 10 · 9 · 8 · 7 · 6
7 · 6 · 5 · 4 · 3 · 2
= 11 · 9 · 8 = 792
A. Malaspina Elementi di Analisi Combinatoria
Identita
(n0
)=
(nn
)= 1
(n1
)=
(n
n − 1
)= n
(n
n − k
)=
(nk
)(
n − 1k − 1
)+
(n − 1
k
)=
(nk
)(
127
)=
(125
)= 792
A. Malaspina Elementi di Analisi Combinatoria
Coefficienti binomiali e binomio di Newton
La potenza n-ma del binomio
(x + y)n = (x + y)(x + y) · · · (x + y)
si ottiene moltiplicando ogni fattore del binomio per tutti gli altri(compreso se stesso) in tutti i modi possibili.
n = 3
(x + y)3 = (x + y)(x + y)(x + y) =xxx + xxy + xyx + xyy+yxx + yxy + yyx + yyy =
x3 + 3x2y + 3xy 2 + y 3
A. Malaspina Elementi di Analisi Combinatoria
Coefficienti binomiali e binomio di Newton
n qualsiasi
xn compare una sola volta
xn−1y compare n volte: dobbiamo scegliere y in uno degli n fattorie x in tutti gli altri
xn−2y 2 compare volte
(n2
)volte perche dobbiamo contare in
quanti modi possiamo scegliere 2 volte y tra gli n fattori
In generale, xn−kyk compare volte
(nk
)volte perche scegliamo
k volte y e n − k volte x
A. Malaspina Elementi di Analisi Combinatoria
Binomio di Newton
Osservando che
(n0
)= 1 e
(n1
)= n
(x + y)n =(n0
)xn+
(n1
)xn−1y+
(n2
)xn−2y 2+. . .+
(n
n − 1
)xyn−1+
(nn
)yn
=n∑
k=0
(nk
)xn−kyk . (9)
A. Malaspina Elementi di Analisi Combinatoria
Triangolo di Tartaglia
11 1
1 2 11 3 3 1
1 4 6 4 11 5 10 10 5 1
1 6 15 20 15 6 1. . . . . . . . . . . .
Permette di determinare i coeffcienti binomiali, ovvero i coefficientidello sviluppo del binomio (x + y)n. Ogni numero (tranne l’1 alvertice) e la somma dei due sovrastanti.
A. Malaspina Elementi di Analisi Combinatoria
Triangolo di Tartaglia: somma delle righe
La somma della n-ma riga e 2n
1 = 11 + 1 = 2
1 + 2 + 1 = 41 + 3 + 3 + 1 = 8
1 + 4 + 6 + 4 + 1 = 161 + 5 + 10 + 10 + 5 + 1 = 32
Per x = 1 = y , dalla (9) si ottiene un’importante identita
2n =n∑
k=0
(nk
). (10)
A. Malaspina Elementi di Analisi Combinatoria
Triangolo di Tartaglia: somma delle righe
La somma della n-ma riga e 2n
1 = 11 + 1 = 2
1 + 2 + 1 = 41 + 3 + 3 + 1 = 8
1 + 4 + 6 + 4 + 1 = 161 + 5 + 10 + 10 + 5 + 1 = 32
Per x = 1 = y , dalla (9) si ottiene un’importante identita
2n =n∑
k=0
(nk
). (10)
A. Malaspina Elementi di Analisi Combinatoria
Triangolo di Tartaglia: differenza nelle righe
La somma dei numeri in posto dispari meno la somma dei numeriin posto pari e 0.
11 - 1 = 0
1 - 2 + 1 = 01 - 3 + 3 - 1 = 0
1 - 4 + 6 - 4 + 1 = 01 - 5 + 10 - 10 + 5 - 1 = 0
Prendendo x = 1 e y = −1 nella (9) si ottiene la somma pari azero.
A. Malaspina Elementi di Analisi Combinatoria
Triangolo di Tartaglia: differenza nelle righe
La somma dei numeri in posto dispari meno la somma dei numeriin posto pari e 0.
11 - 1 = 0
1 - 2 + 1 = 01 - 3 + 3 - 1 = 0
1 - 4 + 6 - 4 + 1 = 01 - 5 + 10 - 10 + 5 - 1 = 0
Prendendo x = 1 e y = −1 nella (9) si ottiene la somma pari azero.
A. Malaspina Elementi di Analisi Combinatoria
Triangolo di Tartaglia: potenze di 11
Le cifre che compongono le potenze di 11 si possono leggereimmediatamente
1 1 = 110
1 1 11 = 111
1 2 1 121 = 112
1 3 3 1 1331 = 113
1 4 6 4 1 14641 = 114
1 5 10 10 5 1 15101051 = 115
Basta prendere x = 10 e y = 1 nella (9).
A. Malaspina Elementi di Analisi Combinatoria
Triangolo di Tartaglia: potenze di 11
Le cifre che compongono le potenze di 11 si possono leggereimmediatamente
1 1 = 110
1 1 11 = 111
1 2 1 121 = 112
1 3 3 1 1331 = 113
1 4 6 4 1 14641 = 114
1 5 10 10 5 1 15101051 = 115
Basta prendere x = 10 e y = 1 nella (9).
A. Malaspina Elementi di Analisi Combinatoria
Sushruta Samhita
Che conto e stato fatto nel Sushruta Samhita (trattato medicoindiano, VI sec. a.C.) per dire che con i 6 gusti fondamentali sipossono ottenere 63 sensazioni differenti?
L’insieme dei 6 gusti fondamentaliG = {amaro, aspro, salato, dolce, piccante, astringente}
A. Malaspina Elementi di Analisi Combinatoria
Sushruta Samhita
Combinazioni di 6 gusti
(66
)= 1 (tutto l’insieme G)
Combinazioni di 5 gusti:
(65
)Combinazioni di 4 gusti:
(64
)Combinazioni di 3 gusti:
(63
)Combinazioni di 2 gusti:
(62
)Combinazioni di 1 gusti:
(61
)= 6
Combinazioni di 0 gusti:
(60
)= 1 (insieme vuoto)
A. Malaspina Elementi di Analisi Combinatoria
Sushruta Samhita
Sommando tutti i contributi si ottiene la formula (10) nel cason = 6(
66
)+
(65
)+
(64
)+
(63
)+
(62
)+
(61
)+
(60
)=
=6∑
k=0
(6k
)= 26 = 64
La risposta nel Sushruta Samhita e 63 perche la sensazione nullanon e stata presa in considerazione dagli antichi indiani.
In termini insiemistici abbiamo contato tutti i possibili sottoinsiemidell’insieme G. Tale calcolo si generalizza al caso di n elementi.
Il numero dei sottoinsiemi di un insieme di n elementi e 2n.
A. Malaspina Elementi di Analisi Combinatoria