Capitolo III : Calcolo combinatorioweb.ticino.com/lucarovelli/appunti/3N_Cap3_Combinatoria.pdf ·...

Liceo Lugano 1, 2011-2012 3N (Luca Rovelli)

Capitolo III : Calcolo combinatorio

1. Introduzione

In matematica, con Combinatoria1 si indica la disciplina che si occupa dello studio degliinsiemi finiti i cui elementi soddisfano proprieta ben definite. Il calcolo combinatorio2,in particolare, studia i modi di ordinare o raggruppare tali insiemi secondo determinateregole (le configurazioni o presentazioni), con particolare riferimento all’enumerazione.Esso si prefigge quindi lo scopo di contare in maniera efficiente, specialmente nei casi incui l’enumerazione diretta risulta impossibile.

Elenchiamo alcuni problemi tipici del calcolo combinatorio:

• In quanti modi posso abbinare 3 camicie e 2 cravatte?

• In quanti modi 10 persone possono disporsi attorno ad un tavolo?

• Quanti sono gli anagrammi di LICEO?

• In quanti modi posso compilare la schedina del lotto?

• Quanti sono i ”quadrati magici” di ordine n?

• Quante sono le funzioni f : {1, 2, 3, 4} → {α, β, γ} ?

• Quanti sottoinsiemi possiede un insieme di 10 elementi?

• In quanti modi posso realizzare il numero 100 come somma di 5 numeri naturali?

La prima menzione scritta di un problema combinatorio risale al 300 a.C. circa: in un testosacro, il Bhagabati Sutra, venivano enumerati i modi in cui e possibile abbinare uno, due otre sapori scelti tra 6 differenti. Considerazioni di carattere combinatorio erano comunquegia presenti nell’I Ching, uno tra i piu antichi testi cinesi. Probabilmente anche Archimededa Siracusa (II sec. a.C.) si occupo di problemi di enumerazione nel trattato Ostomachion(lo studio di un gioco simile al moderno Tangram).

Dopo secoli di predominio orientale, la combinatoria si diffuse in occidente a partire dalXIII secolo, grazie soprattutto agli sforzi di Leonardo Fibonacci e Giordano da Nemi.Nei secoli successivi la disciplina ebbe poi un’evoluzione spettacolare, anche grazie allesue applicazioni al calcolo delle probabilita. Alcuni Grandi della matematica diederocontributi allo sviluppo dell’analisi combinatoria (citiamo solo Pascal, Leibnitz, de Moivreed Eulero), e al giorno d’oggi essa e parte integrante della cosiddetta matematica discreta,un campo di studio fondamentale per le applicazioni in ambito informatico.

1o Combinatorica2chiamato anche analisi combinatoria

Calcolo combinatorio (V1.0) 48 LiLu1, 3N (Luca Rovelli)

2. Un principio fondamentale

Esempio 1: in quanti modi n posso abbinare 3 camicie e 2 cravatte?

Indicando con A, B e C le camicie e con a, b le cravatte potremmo facilmente elencaretutte le possibilita:

(A, a) , (A, b) , (B, a) , (B, b) , (C, a) , (C, b) ,

concludendo che il numero di modi e n = 6. Potremmo anche ragionare in un altro modo,rappresentando con un diagramma ad albero le scelte effettuate:

in questo modo, i rami terminali dell’albero rap-presentano tutte le possibilita; concludiamo imme-diatamente che n = 6.

La realizzazione (generalmente mentale) di un tale schema ad albero si rivela interessantequando il numero delle configurazioni e considerevole.

Esempio 2: A, B, C, D, E sono 5 localita, collegate nel modo indicato da strade. Inquanti modi n posso raggiungere E partendo da A (supponendo di mai tornare indietro)?

Disegnando mentalmente lo schema ad albero,concludiamo che

n = 3 · 2 · 2 · 4 = 48 .

Potremmo intuire il seguente

Principio fondamentale: se, nell’effettuare k scelte, vi sono n1 possibilita per laprima, per ognuna di esse n2 per la seconda, per ogni scelta delle prime due n3 per laterza e cosı via, allora il numero totale di scelte possibili e pari a

n = n1 · n2 · n3 · . . . · nk .

Esempio 3: in quanti modi posso compilare una colonna del totocalcio?

Per ognuna delle 13 partite in schedina vi sono tre possibilita (1, X oppure 2); i modipossibili sono quindi

n = 3 · 3 · . . . · 3︸︷︷︸13 fattori

= 313 = 1 594 323 .


3. Permutazioni semplici

Esempio 1: quanti anagrammi possiede la parola LICEO?

Chiaramente, il metodo meno conveniente consiste nell’elencare tali anagrammi. Pos-siamo invece procedere secondo il principio appena introdotto: per la prima lettera di unanagramma ci sono 5 scelte possibili, per la seconda 4, per la terza 3, per la quarta 2 eper la quinta una sola. Il numero degli anagrammi e quindi pari a

5 · 4 · 3 · 2 · 1 = 5!︸︷︷︸notazione

= 120 .

Definizione 1: sia n intero e positivo. Allora il fattoriale di n, indicato con n!, edefinito come segue:

0! = 1 e n! = n · (n− 1) · (n− 2) · . . . · 3 · 2 · 1 .

Per n 6= 0, si tratta quindi del prodotto di tutti i numeri naturali minori o uguali a n.Esso puo anche essere definito ricorsivamente dalla regola{

0! = 1

n! = n · (n− 1)! , n ≥ 1.

Ad esempio, quindi

1! = 1 ; 2! = 2 · 1! = 2 ; 3! = 3 · 2! = 6 ; 4! = 4 · 3! = 24 ; 5! = 5 · 4! = 120 ; . . .

Esempio 2: in quanti modi posso allineare 4 diverse piante ornamentali?

Ragionando come sopra, concludiamo immediatamente che il numero n cercato e

4! = 4 · 3 · 2 · 1 = 24 .

Definizione 2: una presentazione ordinata di un insieme di n elementi dove le ripe-tizioni non sono ammesse e detta permutazione semplice.

Ragionando come sopra, concludiamo immediatamente quanto segue:

Lemma 1: sia Pn il numero di permutazioni semplici di un insieme di n elementi.Allora vale

Pn = n! .

Osservazione: nel calcolo combinatorio, e spesso conveniente disporre di un campionariodi esempi ”standard” a cui fare riferimento. Per quanto riguarda le permutazioni l’esempiopiu adatto e forse quello degli anagrammi.


Esempio 3: in quanti modi una classe di 23 allievi puo prendere posto in un’aula con 12banchi?

Considerando il posto vuoto come una sorta di ”fantasma”, osserviamo che il problemasi riduce all’enumerazione delle permutazioni di un insieme di 24 elementi. La risposta equindi

P24 = 24! ∼= 6, 204 · 1023 .

Il problema delle permutazioni si complica leggermente se gli oggetti presentati non sonotutti diversi (ad esempio nel caso di anagrammi con lettere ripetute o di un’aula con piudi un posto vuoto).

4. Permutazioni con ripetizioni

Esempio 1: quanti anagrammi possiede la parola BABBO?

• Immaginiamo innanzitutto che le ”B” siano distinguibili: gli anagrammi della ”parola”B1AB2B3O sono 5! = 120;

• dal momento che le tre ”B” sono invece indistinguibili, dobbiamo identificare gliallineamenti in cui solo esse sono permutate, ad esempio B1AB2B3O, B2AB3B1O eB3AB2B1O. Occorre quindi dividere 5! per il numero di permutazioni di B1B2B3,cioe 3! : la risposta e quindi

P5

P3

=5!

3!= 5 · 4 = 20 .

Definizione 3: una presentazione ordinata di un insieme di n elementi dove le ripe-tizioni sono ammesse e detta permutazione con ripetizioni.

Supponiamo quindi che degli n elementi k1 siano uguali tra loro, k2 siano uguali tra loro(ma diversi dai primi) e cosı via. Ragionando come sopra, osserviamo che per contare ilnumero di permutazioni occorre dividere n! per k1!, k2! e cosı via al fine di identificare gliallineamenti indistinguibili.

Lemma 2: sia Pn

k1,k2,...,kmil numero di permutazioni con ripetizioni di n elementi di

cui k1, k2, . . . , km sono uguali tra loro. Allora vale

Pn

k1,k2,...,km=

n!

k1! · k2! · . . . · km!.

Esempio 2: quanti sono gli anagrammi di ANAGRAMMA?

Dal momento che la parola e composta di 9 lettere, con 4 ”A” e 2 ”M”, basta calcolare

P9

4,2 =9!

4! 2!= 7 560 .


Esempio 3: in quanti modi puo distribuirsi una classe di 23 allievi in un’aula con 15banchi?

Vi sono 7 posti vuoti, e quindi indistinguibili. Si tratta quindi di una permutazione conripetizioni. Il numero cercato e

P30

7 =30!

7!∼= 5, 26 · 1028 .

Esempio 4: in quanti modi posso compilare uno schema del lotto (6 su 45)?

Uno schema puo essere ”codificato” da una sequenza ordinata composta usando 2 caratteri(ad esempio O e X) dove ”O” indica la casella vuota e ”X” indica la casella crociata. Adesempio, la scelta dei numeri 1, 11, 12, 22, 35, 45 e indicata da

XOOOOOOOOOXXOOOOOOOOOXOOOOOOOOOOOOXOOOOOOOOOX .

Di conseguenza, contare gli schemi possibili equivale a contare gli anagrammi di unaparola di 45 lettere composta da 6 ”X” e 39 ”O”: il numero cercato e quindi

P45

6,39 =45!

6! 39!= 8 145 060 .

Osservazione: se k ≤ n, il numero Pn

k,n−k = n!k!(n−k)!

e detto coefficiente binomiale, e

viene anche indicato con(nk

). Ce ne occuperemo piu tardi nei dettagli.

5. Disposizioni semplici

Esempio 1: in quanti modi (ordinati) posso estrarre 10 ”tombolini” da un sacchetto chene contiene 90 (senza reimmissione)?

Ho 90 possibilita per la prima estrazione, 89 per la seconda, 88 per la terza e cosı via: intotale

90 · 89 · . . . · 82 · 81 =90!

80!∼= 2, 08 · 1019 modi.

Definizione 4: sia k ≤ n; una presentazione ordinata di k elementi scelti tra n dovele ripetizioni non sono ammesse e detta disposizione semplice di n elementi presi kalla volta.

Ragioniamo come sopra: per la scelta del primo elemento ho n possibilita, per la sceltadel secondo n − 1, ... e per la scelta del k-esimo ho (n − k + 1) possibilita. Vale quindiquanto segue:

Lemma 3: sia Dnk il numero di disposizioni di k elementi scelti da un insieme di n

elementi (n ≥ k). Allora vale

Dnk = n · (n− 1) · (n− 2) · . . . · (n− k + 2) · (n− k + 1) =

n!

(n− k)!.

Si tratta cioe del prodotto dei numeri naturali compresi tra (n− k + 1) e n.


Osservazione: se n = k vale

Dnn =

n!

(n− n)!=n!

0!=n!

1= n! = Pn ;

infatti una permutazione di n elementi distinti puo essere vista come una disposizione conn = k (tutti gli elementi dell’insieme vengono scelti).

Esempio 3: da una commissione comprendente 15 membri devo scegliere un presidente,un vicepresidente ed un cassiere. Quante possibilita ho?

Una terna (presidente,vice,cassiere) possiede un ordine. Si tratta quindi di disposizionisemplici, e il loro numero e pari a

D153 =

15!

12!= 13 · 14 · 15 = 2730 .

6. Disposizioni con ripetizioni

Esempio 1: in quanti modi (ordinati) posso estrarre 10 ”tombolini” da un sacchetto chene contiene 90, se ad ogni estrazione il tombolino viene reimmesso?

Ho 90 possibilita per ognuna delle 10 estrazioni: in totale

90 · 90 · . . . · 90︸︷︷︸10 volte

= 9010 ∼= 3, 49 · 1019 modi.

Definizione 5: una presentazione ordinata di k elementi scelti tra n dove le ripetizionisono ammesse e detta disposizione con ripetizioni di n elementi presi k alla volta.

Nota che, dal momento che un elemento puo ripetersi, non e piu necessario supporre chevalga k ≤ n.

Ragionando come sopra, concludiamo immediatamente quanto segue:

Lemma 4: sia Dn

k il numero di disposizioni con ripetizioni di di n elementi presi k allavolta. Allora vale

Dn

k = nk .

Esempio 2: il totocalcio.

Come abbiamo gia visto (pag. 49), le possibilita per compilare una colonna sono pari a

D3

13 = 313 = 1 594 323 .

Esempio 3: quante parole di 4 lettere, anche prive di senso, posso formare con un alfabetodi 26 lettere?

Si tratta evidentemente di disposizioni con ripetizioni: la risposta e

D21

4 = 214 = 194 481 .


7. Combinazioni semplici

Esempio 1: ho 20 bevande diverse; quanti cocktails composti da quattro di esse possorealizzare?

• Se contasse l’ordine in cui le bevande vengono aggiunte, il problema sarebbe ricon-ducibile ad una disposizione: le sequenze possibili sarebbero

D204 =

20!

16!= 17 · 18 · 19 · 20 = 116 280 ;

• ma l’ordine non conta: occorre quindi dividere tale risultato per il numero di modiin cui le 4 bevande possono essere ordinate: il risultato e

D204

P4

=116 280

4!=

20!

16! 4!= 4 845 .

Definizione 6: una presentazione di k elementi scelti tra n dove l’ordine non haimportanza e le ripetizioni non sono ammesse e detta combinazione semplice di nelementi presi k alla volta.

Per ricavare il numero di tali combinazioni possiamo procedere come sopra: Dnk e il nu-

mero di disposizioni di k elementi presi fra n; se l’ordine non ha importanza, occorreidentificare le k! permutazioni dei k elementi. Vale quindi :

Lemma 5: sia Cnk il numero di combinazioni semplici di n elementi presi k alla volta.

Allora vale

Cnk =

Dnk

k!=

n!

k!(n− k)!.

Definizione 7: siano n, k ∈ N con n ≥ k. Il numero (naturale)(n

k

)=

n!

k!(n− k)!=n · (n− 1) · . . . · (n− k + 2) · (n− k + 1)

k · (k − 1) · . . . · 3 · 2 · 1

e detto coefficiente binomiale.

Per le combinazioni di n oggetti presi k alla volta vale quindi Cnk =

(nk

).

Esempio 2: quanti sono i sottoinsiemi contenenti k elementi di un insieme di n ele-menti?

Dal momento che nella presentazione di un insieme l’ordine non ha importanza, con-cludiamo che si tratta proprio delle combinazioni

(nk

).

Questa caratterizzazione puo essere usata come alternativa per la definizione di com-binazione semplice.


Esempio 3: e dato un insieme I di 50 punti del piano. Quanti triangoli aventi i verticinell’insieme I posso disegnare?

Si tratta di contare tutte le terne {A,B,C} ⊂ I di punti (diversi), cioe i sottoinsiemi diI aventi 3 elementi. Il loro numero e (al massimo) pari a

C503 =

(50

3

)=

50!

3!47!=

50 · 49 · 48

3 · 2= 50 · 49 · 8 = 400 · 49 = 19 600 .

Esempio 4: quante ”parole” di 10 lettere posso formare utilizzando 4 volte la lettera”A” e 6 volte la lettera ”B” ?

Si tratta di scegliere, tra 10 posizioni possibili, le 4 posizioni da occupare con la lettera”A” (le posizioni rimanenti sono automaticamente occupate da ”B”). Dal momento chel’ordine di scelta non ha importanza, si tratta di combinazioni. Il loro numero e quindi

C106 =

(10

6

)=

10!

6!4!=

10 · 9 · 8 · 74 · 3 · 2

= 5 · 3 · 2 · 7 = 210 .

Osservazioni:

1) Avremmo anche potuto trattare l’es. 4 facendo uso delle permutazioni con ripe-tizioni (vedi III.4): si tratta degli anagrammi di ”AAAABBBBBB”!

In effetti, e immediatamente evidente che vale

Cnk =

(n

k

)=

n!

k!(n− k)!= P

n

k,n−k .

(cfr. con l’osservazione a pag. 52).

2) Sempre nell’es. 4, avremmo potuto scegliere dapprima le 6 posizioni per la lettera”B”. Cio mostra che C10

4 = C106 . Si tratta di un caso particolare di una proprieta

del coefficiente binomiale che approfondiremo in seguito.

8. Combinazioni con ripetizioni

Iniziamo con un esempio apparentemente fuori contesto.

Esempio 1: in quanti modi posso riporre 4 oggetti (indistinguibili) in tre cassetti?

Rappresentiamo la situazione, e in seguito ”codifichiamo” con X gli oggetti e con I iseparatori tra i cassetti, ad esempio

1 nel 1o cassetto, 1 nel 2o, 2 nel 3o XIXIXX

0 nel 1o cassetto, 3 nel 2o, 1 nel 3o IXXXIX

4 nel 1o cassetto, 0 nel 2o, 0 nel 3o XXXXII

Risulta immediatamente chiaro che il numero di modi cercati e pari al numero di ana-grammi di XXXXII, vale a dire

(64

)= 15.


Esempio 2: Un’urna contiene palline verdi, rosse e blu (in numero sufficiente, almenoquattro per tipo). Effettuo quattro estrazioni (senza reimmissione). Quanti sono gli esitipossibili, se l’ordine in cui le palline vengono estratte non ha importanza (cioe se annotosoltanto il numero di palline rosse, verdi risp. blu estratte)?

Supponiamo di riporre le palline estratte in cassetti diversi a seconda del colore, ad es.

Rosse Verdi Blu

1 rossa, 1 verde, 2 blu XIXIXX

0 rosse, 3 verdi, 1 blu IXXXIX

4 rosse, 0 verdi, 0 blu XXXXII

Ci rendiamo immediatamente conto che la situazione e equivalente a quella descritta nelprimo esempio. Gli esiti possibili sono quindi nuovamente

(64

)= 15.

Definizione 8: una presentazione di k elementi scelti tra n dove l’ordine non haimportanza e le ripetizioni sono ammesse e detta combinazione con ripetizioni din elementi presi k alla volta.

Per contare tali combinazioni ragioniamo come sopra: il loro numero e pari al numero dimodi in cui k oggetti possono essere riposti in n cassetti (con n− 1 separatori), e quindial numero di anagrammi di

X X . . . X︸︷︷︸k

I I . . . I︸︷︷︸n−1

.

Lemma 6: sia Cn

k il numero di combinazioni con ripetizioni di di n elementi presi kalla volta. Allora vale

Cn

k =

(k + n− 1

k

).

Esempio 3: In quanti modi possono presentarsi i gruppi sanguigni di 10 persone?

I tipi possibili sono 4 (0, A, B e AB); si tratta quindi di combinazioni di 10 persone sceltetra 4 tipi; il loro numero e pari a

C4

10 =

(10 + 4− 1

10

)=

(13

10

)= 286 .

Nota che, come mostra il terzo esempio, non si suppone piu che valga k ≤ n.


9. Proprieta del coefficiente binomiale

Lemma 7

Sia n ≥ k.

(i)

(n

0

)=

(n

n

)= 1 ;

(ii)

(n

k

)=

(n

n− k

);

(iii)

(n

k

)+

(n

k + 1

)=

(n+ 1

k + 1

).

La relazione (iii) e nota come formula di Stifel3.

Dimostrazione:

(i)

(n

0

)=

n!

0!(n− 0)!=n!

n!= 1 e

(n

n

)=

n!

n!(n− 0)!=n!

n!= 1 ;

(ii)

(n

n− k

)=

n!

(n− k)!(n− (n− k))!=

n!

k!(n− k)!=

(n

k

);

(iii)

(n

k

)+

(n

k + 1

)=

n!

k!(n− k)!+

n!

(k + 1)!(n− k − 1)!;

scegliendo (k + 1)!(n− k)! quale denominatore comune si ricava

n!

k!(n− k)!+

n!

(k + 1)!(n− k − 1)!=

(k + 1)n! + (n− k)n!

(k + 1)!(n− k)!=

(�k + 1 + n��−k)n!

(k + 1)!(n− k)!=

(n + 1)!

(k + 1)!(n− k)!.

D’altro canto,(n+ 1

k + 1

)=

(n+ 1)!

(k + 1)!(n��+1− k��−1)!=

(n+ 1)!

(k + 1)!(n− k)!�

Ricordando che(nk

)rappresenta il numero di sottoinsiemi di k elementi contenuti in un

insieme di n elementi, il lemma appena dimostrato possiede anche un’interessante inter-pretazione combinatoria:

(i) sia I un insieme di n elementi; I contiene un solo sottoinsieme di 0 elementi(l’insieme vuoto) e un solo sottoinsieme di n elementi (I stesso);

3Michael Stifel, 1487-1567 fu dapprima monaco agostiniano e in seguito seguace di Martin Lutero; oltreche per i suoi risultati matematici (fra cui spicca l’invenzione delle tavole logaritmiche indipendentementeda Burgi e Napier) egli e noto per aver profetizzato l’Apocalisse per il 3 ottobre 1533 e per aver identificatol’Anticristo con la figura di Papa Leone X


(ii) sia nuovamente I un insieme di n elementi; per ogni sottoinsieme S di k elementi,esiste esattamente un sottoinsieme di I con (n− k) elementi (il complemento S =I \S); quindi, I contiene tanti sottoinsiemi di k elementi quanti di (n−k) elementi;

(iii) sia ora I un insieme di n+ 1 elementi, e sia x ∈ I; allora I contiene

•(nk

)sottoinsiemi di (k+1) elementi comprendenti x (ognuno di essi e una scelta

di k elementi tra n, dal momento che un ”posto” e gia ”occupato” da x),

•(

nk+1

)sottoinsiemi di (k + 1) elementi non comprendenti x (l’elemento x e

escluso a priori, quindi le scelte disponibili sono soltanto n).

Assommando i sottoinsiemi privi dell’elemento x con quelli contenenti x otteniamotutti i sottoinsiemi di I contenenti k + 1 elementi. Quindi

(nk

)+(

nk+1

)=(n+1k+1

).

La formula di Stifel permette di calcolare in maniera ricorsiva i valori di tutti i coefficientibinomiali

(nk

)a partire dal fatto che

(00

)=(10

)=(20

)= . . . = 1 e

(00

)=(11

)=(22

)= . . . = 1.

Disponiamo i coefficienti binomiali in una struttura triangolare in modo tale che l’n-esimariga (partendo da n = 0) sia formata dai coefficienti binomiali

(n0

),(n1

),(n2

), . . . ,

(nn

):(

0

0

)(

1

0

) (1

1

)(

2

0

) (2

1

) (2

2

)(

3

0

) (3

1

) (3

2

) (3

3

)(

4

0

) (4

1

) (4

2

) (4

3

) (4

4

)(

5

0

) (5

1

) (5

2

) (5

3

) (5

4

) (5

5

)e cosı via.

La formula di Stifel(n+1k+1

)=(nk

)+(

nk+1

)implica che ogni coefficiente binomiale ”all’interno”

del triangolo e somma dei coefficienti binomiali a sinistra e a destra di esso nella rigasovrastante: ad esempio(

2

1

)=

(1

0

)+

(1

1

),

(3

1

)=

(2

0

)+

(2

1

),

(3

2

)=

(2

1

)+

(2

2

),

(4

1

)=

(3

0

)+

(3

1

),

(4

2

)=

(3

1

)+

(3

2

). . .

Dal momento che i numeri ”all’esterno” del triangolo sono tutti pari ad 1, e facile calcolarericorsivamente i coefficienti binomiali:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1


e cosı via. Vale quindi, ad esempio,(5

0

)= 1 ,

(5

1

)= 5 ,

(5

2

)= 10 ,

(5

3

)= 10 ,

(5

4

)= 5 ,

(5

5

)= 1 .

Lo schema numerico ottenuto e noto come triangolo di Pascal, dalnome del celebre matematico e filosofo Blaise Pascal (1623-1662)che ne mise in evidenza le proprieta combinatorie nel Traite ditriangle arithmetique. Nel ’600, comunque, esso era gia noto dasecoli. In particolare era gia stato descritto da Niccolo Fontana(detto il Tartaglia, 1500-1577), da Yang Hui (1238-1298, v. disegnoa destra) e da Omar Khayyam (1048-1131).

10. La formula binomiale

In questo paragrafo finale ci proponiamo innanzitutto di giustificare il metodo per losviluppo delle potenze

(a+ b)n (n ≥ 0)

di un binomio, gia incontrato nel programma di I Liceo.Iniziamo con una semplice considerazione: dato che

(a+ b)n = (a+ b) · (a+ b) · . . . · (a+ b)︸︷︷︸n volte

,

ogni termine dello sviluppo risultera dal prodotto di n fattori scelti tra a e b, cioe dimonomi la cui parte letterale e pari a

an−kbk con k ≤ n .

Indichiamo (provvisoriamente) con Xk (k = n, . . . , 0) il coefficiente di an−kbk :

(a+ b)n = X0 ·an +X1 ·an−1b+X2 ·an−2b2 + . . .+Xn−2 ·a2bn−2 +Xn−1 ·abn−1 +Xn · bn .

Qual e il significato di Xk? Notiamo immediatamente che si tratta del numero di modi incui k fattori ”a” e (n− k) fattori ”b” possono essere moltiplicati senza tener conto dellacommutativita, cioe degli anagrammi della ”parola”

a a . . . a︸︷︷︸(n−k)

b b . . . b︸︷︷︸k

.

Si tratta quindi di combinazioni semplici di n elementi presi k alla volta (vedi III.7)4. Inparticolare, vale quindi

Xk = Cnk =

(n

k

).

4oppure anche di permutazioni con ripetizioni (vedi III.4)


Ad esempio,

(a+ b)3 = (a+ b)(a+ b)(a+ b) = a(a+ b)(a+ b) + b(a+ b)(a+ b)

= aa(a+ b) + ab(a+ b) + ba(a+ b) + bb(a+ b)

= aaa+ aab+ aba+ abb+ baa+ bab+ bba+ bbb

= aaa︸︷︷︸1·a3

+ aab+ aba+ baa︸︷︷︸3·a2b

+ abb+ bab+ bba︸︷︷︸3·ab2

+ bbb︸︷︷︸1·b3

= a3 + 3a2b+ 3ab2 + b3

=

(3

0

)a3 +

(3

1

)a2b+

(3

2

)ab2 +

(3

3

)ab3 .

In questo modo si dimostra il

Teorema 8 (Formula binomiale)

Sia n ∈ N ∪ {0}. Allora

(a+b)n =

(n

0

)an+

(n

1

)an−1b+

(n

2

)an−2b2+. . .+

(n

n− 2

)a2bn−2+

(n

n− 1

)abn−1+

(n

n

)bn .

Nota che vale(n0

)=(nn

)= 1, e quindi che i coefficienti di an e bn sono pari a 1, e inoltre

che da(n1

)=(

nn−1

)= n segue che i coefficienti di an−1b e abn−1 sono pari a n.

La formula binomiale (cosı come il triangolo che ne descrive i coefficienti) viene general-mente attribuita a Blaise Pascal (1623-1662), ma in realta era gia nota in precedenza:Euclide (IV sec. a.C.) e il matematico indiano Pingala (II sec. a. C.) ne conoscevanoalcuni casi particolari, e i gia menzionati Omar Khayyam (1048-1131) e Yang Hui (1238-1298) l’avevano derivata nel caso generale. A volte il risultato viene anche attribuito aIsaac Newton (1643-1727), il quale ne aveva ricavata una generalizzazazione al caso diesponenti qualsiasi (quindi non per forza interi) nel contesto delle serie infinite5.

Esempio: calcoliamo lo sviluppo di (a+ b)6;

(a+ b)6 = a6 +

(6

1

)a5b+

(6

2

)a4b2 +

(6

3

)a3b3 +

(6

4

)a2b4 +

(6

5

)ab5 + b6 ;

possiamo leggere i valori dei coefficienti binomiali nella settima riga del triangolo di Pascal(1,6,15,20,15,6,1), ricavando

(a+ b)6 = a6 + 6a5b+ 15a4b2 + 20a3b3 + 15a2b4 + 6ab5 + b6 .

5nel mondo della finzione, inoltre, il professor Moriarty (la nemesi di Sherlock Holmes) viene indicatocome l’autore di un Trattato sul teorema binomiale


In alternativa, notando che per k > 0 vale(n

k

)=

n!

k!(n− k)!=n · (n− 1) · (n− 2) · . . . · (n− k + 2) · (n− k + 1)

1 · 2 · . . . · (k − 1) · k

avremmo potuto calcolare i coefficienti facendo a meno del triangolo di Pascal:

(a+ b)6 = a6 +6

1a5b+

6 · 51 · 2

a4b2 +6 · 5 · 41 · 2 · 3

a3b3 +6 · 5 · �4 · �31 · 2 · �3 · �4

a2b4 +6 · 5 · �4 · �3 · �21 · �2 · �3 · �4 · 5

ab5 + b6

= a6 + 6a5b+ 15a4b2 + 20a3b3 + 15a2b4 + 6ab5 + b6

(il calcolo puo essere semplificando ulteriormente sfruttando la simmetria dei coefficienti!).

Applicazione: ponendo a = b = 1 nella formula binomiale, si ricava

(1+1)n =

(n

0

)1n+

(n

1

)1n−1·1+

(n

2

)1n−2·12+. . .+

(n

n− 2

)12·1n−2+

(n

n− 1

)1·1n−1+

(n

n

)1n ,

cioe

2n =

(n

0

)+

(n

1

)+

(n

2

)+ . . .+

(n

n− 2

)+

(n

n− 1

)+

(n

n

).

La somma di tutti i coefficienti binomiali da(n0

)a(nn

)e quindi pari a 2n. Ricordando

che(nk

)e il numero di sottoinsiemi contenenti k elementi di un insieme che ne contiene n

(vedi pag. 54), osserviamo che in questo modo abbiamo contato tutti i sottoinsiemi di uninsieme di n elementi:

Corollario 9

Un insieme di n elementi contiene 2n sottoinsiemi.

Questo risultato possiede anche un’interessante dimostrazione combinatoria che fauso soltanto del concetto di disposizione con ripetizioni:

sia M un insieme di n elementi; scelto un ordine al suo interno, i suoi sottoinsiemi possonoessere rappresentati per mezzo di sequenze che utilizzano soltanto le cifre 0 e 1 (cioe come”sequenze binarie”)6; ad esempio, con

M = {a, b, c, d, e, f}

indicheremo con 000000 l’insieme vuoto, con 100000 l’insieme {a} (”c’e solo il primo ele-mento”), con 010011 l’insieme {b, e, f} (”ci sono il secondo, il quinto e il sesto elemento”),con 101010 l’insieme {a, c, e}, con 111111 l’intero insieme M e cosı via. Grazie a questarappresentazione, invece di dover contare i sottoinsiemi di M , possiamo semplicementecontare le sequenze di 0 e 1 di lunghezza n; il loro numero e proprio pari a 2n (vedi III.6).Cio conclude la dimostrazione alternativa7 �

6in maniera analoga a quanto visto per ”contare” le combinazioni del lotto, vedi pag. 527nota inoltre che in codice binario (cioe nella notazione in base 2) le sequenze da 000 . . . 0︸︷︷︸

n

a 111 . . . 1︸︷︷︸nrappresentano i numeri da 0 a 2n − 1


Capitolo III : Calcolo combinatorioweb.ticino.com/lucarovelli/appunti/3N_Cap3_Combinatoria.pdf ·...

Documents

Transcript of Capitolo III : Calcolo combinatorioweb.ticino.com/lucarovelli/appunti/3N_Cap3_Combinatoria.pdf ·...