Elementi di Analisi Combinatoriaold€¦ · Elementi di Analisi Combinatoria Angelica Malaspina...

Elementi di Analisi Combinatoria

Angelica Malaspina

Dipartimento di Matematica, Informatica ed EconomiaUniversita degli Studi della Basilicata, Italy

[email protected]

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.


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.


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.


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


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.


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)


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)


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


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


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.


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.


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


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


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)


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 .


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


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)


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

)


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


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!


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


Identita

(n0

)=

(nn

)= 1

(n1

)=

(n

n − 1

)= n

(n

n − k

)=

(nk

)(

n − 1k − 1

)+

(n − 1

k

)=

(nk

)(

127

)=

(125

)= 792


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


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


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)


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.


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)


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.


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).


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}


Sushruta Samhita

Combinazioni di 6 gusti

(66

)= 1 (tutto l’insieme G)

Combinazioni di 5 gusti:

(65

)Combinazioni di 4 gusti:

(64


(63


(62


(61

)= 6

Combinazioni di 0 gusti:

(60

)= 1 (insieme vuoto)


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.


Elementi di Analisi Combinatoriaold€¦ · Elementi di Analisi Combinatoria Angelica Malaspina...

Documents

Transcript of Elementi di Analisi Combinatoriaold€¦ · Elementi di Analisi Combinatoria Angelica Malaspina...