Calcolo combinatorio




E’ una branca della matematica che si occupa
di contare gli oggetti di un insieme finito.
Tipica domanda: Quanti sono…?
Per rispondere a domanda di questo tipo,
utilizziamo vari modelli.
Una volta scelto il modello giusto, i metodi di
base sono basati su due principi: il principio
additivo e il principio moltiplicativo.
Principi fondamentali

Principio additivo: se A e B sono due insiemi
finiti disgiunti, allora la cardinalità della loro
unione è la somma delle loro cardinalità: in
altri termini:
Card ( A  B)  Card ( A)  Card ( B).
Principio additivo - Seconda
versione



Se però A e B non sono disgiunti, il principio
non vale più nella stessa forma, in quanto nel
computo di Card(A)+Card(B) gli elementi
dell’intersezione sono contati due volte.
Il principio diviene allora il seguente:
Se A e B sono insieme finiti, allora:
)B  A ( draC  )B ( draC  )A ( draC  )B  A ( draC
Principio additivo, seconda
versione: un esempio
In figura, A (rettangolo in basso a sinistra) ha 10
elementi, B (rettangolo in alto a destra) ne ha 9.
A e B hanno 4 elementi in comune (rettangolo verde),
per cui l’unione di A e di B ha 10+9-4=15 elementi
Principio additivo: un esempio
In una classe di 30 studenti vengono fatti due test per
l’ammissione all’anno successivo.
• E’ ammesso chi supera almeno un test.
• Il primo test è superato da 16 studenti
• Il secondo test è superato da 14 studenti.
• Solo 8 superano entrambi i test.
• Quanti studenti sono ammessi all’anno successivo?
Risposta: 16+14-8=22.
•
Il Principio moltiplicativo




Principio moltiplicativo. Il numero delle sequenze
a1,…,an dove:
a1 varia in un insieme di k1 elementi;
a2 varia in un insieme di k2 elementi,…,
an varia in un insieme di kn elementi è
k1 . k2 …. . kn
.
Principio moltiplicativo:
illustrazione grafica
a2
a1
b1
c1
b3
b2
c2 c1
c2
c1 c2
b1
c1
b2
c 2 c1 c2
b3
c
1
c2
Il primo elemento varia in due modi (a1 e a2),
il secondo in tre modi (b1, b2 e b3).
Il terzo in due modi (c1 e c2).
Le sequenze che si leggono scendendo lungo i rami
sono 2.3.2=12
Il principio moltiplicativo: esempi
•
Quante targhe si possono fare con 2 lettere
dell’alfabeto inglese seguite da 3 cifre e poi
ancora 2 lettere dell’alfabeto inglese?
•
R. 26 . 26 . 10 . 10 . 26 . 26=45697600
E se si usassero invece 7 lettere dell’alfabeto
italiano il numero di targhe aumenterebbe?
Risposta. Si, si otterrebbero 217 =1801088541
targhe.
•
•
Problemi

Quante sono le terne di lettere (anche prive di senso)
che precedono la parola LIO nell’ordine lessicografico?
Risposta: Le possibilità sono: la prima lettera precede
L (9 casi) e le altre sono arbitrarie (21 .21 casi)
oppure la prima è L (1 caso), la seconda precede I (8
casi) e la terza è arbitraria (21 casi)
o infine le prime due sono LI e la terza precede O (12
casi).
Totale: 9 .21 .21+8 .21+12=4149 possibilità.
Problemi

Viene lanciato per tre volte un dado. Quanti sono gli esiti dei
tre lanci che hanno come somma 13?
Risposta: ripartiamo gli esiti a seconda dell’esito del primo
dado.
Se il primo uscito è 1, vi è una sola possibilità per gli altri 2,
cioè 6 e 6.
Se il primo è 2 vi sono 2 possibilità per gli atri 2, cioè 5 e 6
oppure 6 e 5.
Se il primo è 3 le possibilità sono 3, ossia: 6 e 4, 4 e 6 o 5 e 5.
Etc. etc.
In totale le possibilità sono 1+2+3+4+5+6=21.
Problemi





Da un’urna contenente i numeri da 1 a 90 si
estraggono 3 numeri senza reimbussolamento. Quante
sono le estrazioni in cui i primi due estratti sono numeri
pari?
Risposta: il primo varia in 45 modi (tutti i pari).
Il secondo varia in 44 modi (i pari meno il primo).
Il terzo in 88 modi (tutti salvo i primi due).
Totale: 45.44.88=174240.
Le 4 figure fondamentali della
combinatoria
Disposizioni semplici:
Combinazioni semplici:
Ordine SI Ripetizioni NO
(L’ordine conta; non sono
ammesse ripetizioni)
Ordine NO Ripetizioni NO
(L’ordine non conta e non sono
ammesse ripetizioni)
Disposizioni con ripetizioni: Combinazioni con
ripetizioni:
Ordine SI Ripetizioni SI
(L’ordine conta e sono
ammesse ripetizioni)
Ordine NO Ripetizioni SI
(L’ordine non conta e sono
ammesse ripetizioni)
Disposizioni semplici
•
•
•
•
•
Sono raggruppamenti di k oggetti presi da un insieme
di n oggetti senza ripetizioni ma tenendo conto
dell’ordine.
Il numero delle disposizioni di k oggetti di un insieme di
n oggetti si indica con D(n,k).
Per il Principio Moltiplicativo ha:
D(n,k)=n(n-1)…(n-k+1).
Posto n!=1.2.3.…. (n-1).n, si ha anche:
D(n,k)=n! : (n-k)!
Esempi




Ad una gara partecipano 10 atleti. Quante
sono le possibili salite sul podio (primo,
secondo e terzo?)
Risposta: D(10,3)=10 . 9 . 8=720
Quanti sono i possibili allineamenti alla
partenza delle 10 contrade su 17 che
parteciperanno al Palio del 2020?
Risposta: D(17,10)=70572902400.
Problema




Quante sono le funzioni iniettive da un insieme A di m
elementi ad un insieme B di n elementi, con mn?
Risposta: D(n,m). Siano a1,…,am gli elementi di A. Per
scegliere una funzione iniettiva f da A a B devo determinare
f(a1),…,f(am).
f(a1) lo posso scegliere in n modi diversi (tanti quanti gli
elementi di B). f(a2) deve essere diverso da f(a1), quindi lo
posso scegliere in n-1 modi. f(a3) lo posso scegliere in n-2
modi,…,f(am) lo posso scegliere in n-m+1 modi.
Per il principio moltiplicativo, ho
D(n,m)=n . (n-1) . … . (n-m+1) scelte possibili.
Permutazioni




Sono disposizioni di n oggetti a n a n.
Dato che la scelta degli elementi da ordinare è
obbligata (devo sceglierli tutti), le permutazioni
di n oggetti sono i loro possibili ordinamenti.
Il numero delle permutazioni di n oggetti è
quindi
D(n,n)=n! : 1!=n!
Esempi





Quanti sono gli anagrammi della parola ASTRO?
Risposta: 5!=120.
Il 30 maggio sono noti i nomi delle 10 contrade che
parteciperanno al Palio del 2 Luglio. Quanti sono i
possibili allineamenti alla partenza? E quanti gli
ordini di arrivo?
Risposta in entrambi i casi: 10!=362880.
Quante sono le biiezioni da un insieme A di n
elementi ad un insieme B di n elementi? Risposta:
n!
Altri problemi




Ad una gara partecipano 10 atleti, di cui 5 italiani e 5
svizzeri. Quanti sono gli ordini di partenza in cui gli
italiani precedono gli svizzeri?
Risposta: basta fissare l’ordine degli italiani (5!
possibilità) e quello degli svizzeri (5! possibilità).
Mettendo gli italiani davanti agli svizzeri otteniamo
l’ordine d’arrivo completo.
Gli ordini degli italiani e degli svizzeri possono essere
scelti indipendentemente. Totale: 5!.5!=14400.
Altri problemi


Ad una tavola rotonda (in senso letterale) si
devono sedere 8 commensali fra cui il Signor
Pedro Gonzales. Se consideriamo le loro posizioni
a meno di rotazioni, in quanti modi si possono
disporre?
Risposta: poiché l’ordine è a meno di rotazioni, si
può assumere che il primo sia Gonzales. Gli altri 7
commensali possono essere disposti in 7! modi.
Quindi le possibilità sono 7!.
Altri problemi



Ad un’altra gara partecipano 8 atleti, fra cui
Gennaro Esposito (GE) e Ambrogio Brambilla (AB).
Quanti sono gli ordini d’arrivo in cui GE precede
AB?
Risposta: il numero degli ordini d’arrivo con GE
davanti a AB è uguale al numero di ordini d’arrivo
con AB davanti a BE (si passa da uno all’altro
scambiando i due).
Il numero richiesto è la metà degli 8! possibili
ordini di arrivo, ossia 8! : 2=20160.
Combinazioni semplici



Le combinazioni semplici di k oggetti presi da
un insieme di n oggetti sono i sottoinsiemi di k
elementi dell’insieme dato.
Quando parliamo di insiemi o di sottoinsiemi
intendiamo che sono escluse ripetizioni e che
si prescinde dall’ordine.
Il numero delle combinazioni di k oggetti presi
da un insieme di n oggetti si indica con C(n,k).
Calcolo di C(n,k)





Una combinazione semplice genera una disposizione
semplice per ogni ordinamento della combinazione
stessa.
Gli ordinamenti di un insieme di k elementi sono k!
Quindi D(n,k)=C(n,k).k!
Ne segue che C(n,k)=D(n,k)/k!=n!/((n-k)! . k!)
Notazione: nei testi, invece di C(n,k) si usa di solito la
notazione
 n

k

 
Esempi




C(5,3)=(5 . 4 . 3):(3 . 2)=10
C(7,4)=(7 . 6 . 5 . 4) : (4 . 3 . 2)=35
C(20,2)=(20 . 19) : 2=190
C(9,3)=(9 . 8 . 7):(3 . 2)=84
Esempi



Nel gioco del Poker vengono distribuite a
ciascun giocatore 5 carte su 32. Quante sono
le possibilità per ciascun giocatore?
Risposta: l’ordine in cui il giocatore riceve le
carte non importa, e non sono possibili
ripetizioni.
Quindi le possibilità sono date dalle
combinazioni di 5 oggetti presi da un insieme
di 32, ossia C(32,5)=201356.
Esempi






Quante sono le cinquine nel gioco del lotto?
Risposta: Sono gli insiemi di cinque numeri presi
dall’insieme dei primi 90 numeri. Quindi le cinquine
sono C(90,5)=43949268.
Quante partite si giocano in tutto in un torneo a 18
squadre?
Risposta: le partite di andata sono tante quanti gli
insiemi di 2 squadre prese dalle 18 partecipanti.
Quindi nell’andata si giocano C(18,2)=146 partite.
In totale le partite sono 292.
Esempi





In occasione di un Palio straordinario, a Siena
vengono sorteggiate 10 contrade partecipanti su
17. Quante sono le possibili scelte?
Risposta: C(17,10)=19448.
Quante sono le sequenze crescenti di 3 numeri
presi da 1 a 20?
Risposta: basta prendere i sottoinsiemi di 3 numeri
da 1 a 20 e ordinarli in ordine crescente.
Quindi il numero richiesto è C(20,3)=1140.
Un altro esempio



Ad una corsa partecipano 8 concorrenti fra cui
Ambrogio Brambilla, (AB), Gennaro Esposito (GE) e
Duccio Peccianti (DP). Quanti sono gli ordini di arrivo
in cui DP precede GE e GE precede AB?
Soluzione. Una volta fissati i 3 posti in cui si piazzano
DP, GE e AB, vi è un solo ordine possibile dei 3
concorrenti.
Quindi l’ordine d’arrivo è determinato dall’ordine degli
altri 5 concorrenti.
Altro esempio


La scelta dei 3 posti in cui si piazzano GE, AB
e DP varia in C(8,3) modi, mentre la scelta
degli ordini dei rimanenti 5 concorrenti varia in
5! modi.
Per il principio moltiplicativo (le due scelte sono
indipendenti), abbiamo C(8,3).5!=6720 possibili
ordini d’arrivo.
Proprietà dei coefficienti binomiali




I numeri C(n,k) si chiamano coefficienti binomiali. Si
ha:
C(n,k)=0 se k>n. Infatti non ci sono sottoinsiemi con
più elementi dell’insieme.
C(n,0)=C(n,n)=1. Infatti l’unico sottoinsieme privo di
elementi è l’insieme vuoto, e l’unico sottoinsieme con
lo stesso numero di elementi è l’insieme stesso.
C(n,1)=n. I sottoinsiemi di un elemento sono tanti
quanti gli elementi stessi.
Proprietà dei coefficienti binomiali
•
•
•
•
C(n,k)=C(n,n-k). Infatti i sottoinsiemi con k elementi
sono tanti quanti i loro complementi, cioè i sottoinsiemi
di n-k elementi.
C(n+1,k+1)=C(n,k+1)+C(n,k). Infatti sia A un insieme di
n+1 elementi, e sia b un suo elemento.
I sottoinsiemi di A di k+1 elementi (C(n+1,k+1) in totale)
sono i C(n+1,k) insiemi che contengono b più i C(n,k)
sottoinsiemi che non contengono b.
Quindi C(n+1,k+1)=C(n,k+1)+C(n,k).
Esercizio




Calcolare C(100,98).
Invece di calcolare D(100,98)/98!, una frazione
in cui sia il numeratore che il denominatore
sono numeri grandissimi, osserviamo che
C(100,98)=C(100,100-98)=C(100,2)
Quindi C(100,98)=C(100,2)=100.99/2=4950.
Il binomio di Newton




Le formule di elevamento al quadrato e al cubo
di un binomio sono ben note:
(a+b)2 =a2+2ab+b2.
(a+b)3=a3+3a2b+3ab2+bn.
Vogliamo generalizzare la formula trovando
un’espressione per (a+b)n.
Binomio di Newton


Per calcolare (a+b)2=(a+b)(a+b) dobbiamo
sommare tutti i prodotti di due lettere in cui
ogni fattore è una a o una b. tali fattori sono 4:
aa, ab, ba, bb.
Più in generale, per calcolare
(a+b)n=(a+b)(a+b) .…. (a+b)(a+b) dobbiamo
sommare tutti i 2n prodotti di n lettere di cui
alcune sono a e le altre sono b.
Binomio di Newton




Per k=0,1,…,n, raccogliamo tutti gli addendi del tipo
akbn-k.
Tali addendi sono tanti quanti i prodotti con k fattori
uguali ad a e quindi con n-k fattori uguali a b.
Di tali fattori ve ne è uno per ogni scelta dei k posti (fra
gli n posti totali) in cui si trova la a.
Tali scelte sono tante quanti i sottoinsiemi di k elementi
di un insieme di n elementi, ossia C(n,k), o
n
equivalentemente  
k
Binomio di Newton






Pertanto (a+b)n è la somma di:
C(n,0) volte a 0b n più
C(n,1) volte a 1bn-1 più
C(n,2) volte a2bn-2 più …
…più C(n,n) volte an b0.
n
In formula:
 n  k nk
n
(a  b)    a b
k 0  k 
Esempi


(a+b)4=C(4,0)a4+C(4,1)a3b+C(4,2)a2b2
+C(4,3)ab3 +C(4,4)b 4= a4+4a3b+6a2b2 +6ab3
+b4.
(a+b)5=C(5,0)a5+C(5,1)a4b+C(5,2)a3b2
+C(5,3)a2b3 +C(5,4)ab4+C(5,5)b5
=a5+5a4b+10a3b2 +10a2b3 +5ab4 +b5.
Disposizioni con ripetizione



Le disposizioni con ripetizione sono
raggruppamenti di oggetti in cui sono possibili
ripetizioni e in cui si tiene conto dell’ordine.
Le disposizioni con ripetizione si chiamano
anche sequenze o stringhe.
Il numero delle disposizioni con ripetizione di
k oggetti presi da un insieme di n oggetti si
indica con D’(n,k).
Calcolo di D’(n,k)

Ciascuno dei k oggetti può essere scelto
indipendentemente in n modi. Quindi per il
principio moltiplicativo:
D’(n,k)=n . n . …. n (k volte). Quindi:
D’(n,k)=nk.
Esempi




Quante stringhe di lunghezza 100 si possono
formare con le lettere A, C, G, T?
Risposta:
4100=160693804425899027554196209234116
2602522202993782792835301376
Quante sono le possibili colonne nel
totocalcio?
Risposta: 313=1594323
Disposizioni con ripetizioni:
applicazioni





Quante sono le funzioni da un insieme A di n elementi
ad un insieme B di m elementi?
Siano a1,…,an gli elementi di A. Per ottenere una
funzione f da A a B basta scegliere fra gli m elementi di
B gli n valori f(a1),…,f(an).
Ciascun f(ai) può essere scelto in m modi.
Per il principio moltiplicativo, una funzione f da A a B
può essere scelta in m . … . m = mn modi.
Quindi le funzioni da A a B sono mn =D’(m,n).
Combinazioni con ripetizioni



Con il simbolo C’(n,k) indichiamo il numero di modi di
formare raggruppamenti di k elementi presi da un
insieme di n elementi, prescindendo dall’ordine e con
la possibilità di ripetere più volte lo stesso oggetto.
Siano a1,…,an gli oggetti. Una combinazione è ottenuta
dicendo quante volte ciascun oggetto è ripetuto.
Se a1,…,an sono ripetuti rispettivamente k1,…,kn volte,
la combinazione è rappresentabile con la seguente
tabella:
Rappresentazione di una
combinazione con ripetizioni
tramite una tabella
a1
a2
… … an-1 an
k1
k2
… … kn-1 kn
Combinazioni con ripetizioni


Se a1 è ripetuto k1 volte, a2 è ripetuto k2
volte,…, an è ripetuto kn volte, essendo il
numero totale di oggetti uguale a k, sarà:
k1+k2+…+kn=k.
Quindi per calcolare C’(n,k) basta contare il
numero di sequenze k1, k2,…,kn di numeri
naturali tali che
k1+k2+…+kn=k
Esempi
Un padre decide di ripartire 50 monete d’oro fra i suoi
3 figli. In quanti modi può farlo?
 Risposta: devo calcolare il numero di terne di numeri
naturali la cui somma sia 50. Tale numero è C’(3,50).
 Ad una votazione partecipano 200 persone, che
possono scegliere fra 3 candidati o votare scheda
bianca. Quanti sono gli esisti possibili?
 Risposta: C’(4,200).
Vedremo poi come calcolare C’(n,k).

Il modello dei contenitori






Le combinazioni con ripetizioni C’(n,k) possono essere
modellate come segue:
Consideriamo n contenitori distinguibili, numerati da 1
a n e k biglie indistinguibili.
La combinazione data dalla stringa di numeri naturali
k1, k2,…,kn con k1+k2+…+kn=k può essere
rappresentata come l’atto di inserire
k1, biglie nel contenitore 1,
k2 biglie nel contenitore 2,…,
kn biglie nel contenitore n.
Il modello dei contenitori: un
esempio



Consideriamo l’esempio della votazione a cui
partecipano 200 persone che possono scegliere fra 3
candidati o votare scheda bianca.
Dopo lo scrutinio delle schede, mettiamo nell’urna 1 le
schede a favore del candidato 1, nell’urna 2 quelle a
favore di 2, nell’urna 3 quelle a favore di 3 e nell’urna 4
le schede bianche.
In totale le schede sono 200, e si tratta di distribuirle fra
4 contenitori distinguibili.
Calcolo di C’(n,k)






Si tratta di contare i modi di distribuire k biglie
indistinguibili fra n contenitori distinguibili. Ad ogni
distribuzione associamo una stringa di k uni e di n-1
zeri come segue:
Iniziamo dal contenitore 1.
Un 1 nella stringa significa: aggiungi una biglia.
Uno 0 nella stringa significa: passa al contenitore
successivo.
Dopo n-1 zeri arrivo all’ultimo contenitore.
Dopo k uni ho finito di distribuire le biglie.
Esempio






Supponiamo che i contenitori siano 3 e che le biglie
siano 5. La stringa 1100111 si interpreta così:
I primi due uni significano: metti due biglie nel
contenitore 1.
Lo zero successivo significa: passa al contenitore 2.
Lo zero successivo significa: passa al contenitore 3 (il
contenitore 2 resta vuoto).
I 3 uni finali significano: metti 3 biglie nel contenitore 3.
Alla fine nel primo contenitore vengono messe 2 biglie,
nel secondo 0 e nel terzo 3.
Calcolo di C’(n,k)



Una sequenza di k uni e di n-1 zeri è
determinata dalla scelta degli n-1 posti fra gli
n+k-1 possibili in cui la sequenza vale 0
(ovviamente negli altri posti la sequenza vale
automaticamente 1).
Tali scelte sono tante quanti i sottoinsiemi di
n-1 elementi di un insieme di n-k-1 elementi,
ossia:
C’(n,k)=C(n+k-1,n-1).
Esempi




Ad una votazione partecipano 200 persone,
che possono scegliere fra 3 candidati o votare
scheda bianca. Quanti sono gli esisti possibili?
Risposta: C’(4,200)=C(203,3)=1373701.
Un padre decide di ripartire 50 monete d’oro
fra i suoi 3 figli. In quanti modi può farlo?
Risposta: C’(3,50)=C(52,2)=1326.
Permutazioni con ripetizioni




Abbiamo visto che ci sono 5! anagrammi (anche privi
di significato) della parola ASTRO.
Quanti sono gli anagrammi della parola CARTA?
Attenzione: permutando fra loro le due A ottengo la
stessa parola. Quindi 5! rappresenta gli anagrammi
della parola CARTA contati due volte.
Pertanto il numero di anagrammi della parola CARTA è
5!:2=60.
Permutazioni con ripetizioni





Consideriamo ora gli anagrammi della parola MAMMA.
Stavolta otteniamo lo stesso anagramma in
corrispondenza di ognuna delle 3! permutazioni delle 3
M e per ognuna delle 2!=2 permutazioni delle 2 A.
Tali scelte sono indipendenti, e per il Principio
Moltiplicativo sono 3!.2!=12.
Quindi 5! è il numero degli anagrammi di MAMMA,
ciascuno ripetuto 3!2!=12 volte.
Il numero degli anagrammi della parola MAMMA è
quindi 5!:(3!2!)=120:12=10.
Esempio



Quante sono le permutazioni della parola
MISSISSIPPI?
Risposta: MISSISSIPPI ha 11 lettere, fra cui la
M compare una sola volta, la I compare 4
volte, la S compare 4 volte, e la P compare 2
volte.
Per calcolare il numero degli anagrammi,
dobbiamo dividere 11! per 4! . 4! . 2!, ottenendo
34650.
Permutazioni con ripetizioni


In generale: supponiamo di avere una
sequenza lunga k di oggetti a1,…,ar, in cui a1 è
ripetuto k1 volte, a2 ripetuto k2 volte,…, ar
ripetuto kr volte (quindi k1+k2+…+kr=k).
Il numero delle permutazioni della sequenza è
dato da k! : (k1! . k2! . …. kr!).
Esempi



Una stringa è formata da 40 caratteri, di cui 10 sono A,
10 sono C, 10 sono G e 10 sono T. In quanti modi può
essere composta la stringa?
Risposta. 40! : (10! 4)= 4705360871073570227520
Anche se il numero è grandissimo, esso è molto più
piccolo di 440=1208925819614629174706176, il
numero di possibilità che avremmo in assenza di
informazioni sulla distribuzione delle lettere.
Esempi




Quante stringhe di 8 lettere possiamo ottenere
usando per 3 volte la A, due volte la T, due
volte la O e una volta la S?
Risposta: 8! : (3! . 2! . 2!) =1680
Quante sono le stringhe binarie di lunghezza
20 con lo stesso numero di zeri e di uni?
Risposta: 20! : (10! . 10!) =184756.
Generalizzazioni del binomio di
Newton



Vogliamo trovare una formula simile a quella
del binomio di Newton per la potenza di un
trinomio (a+b+c)n.
Il ragionamento che seguiamo è simile a quello
adottato per il binomio di Newton, vale a dire:
Applicando la proprietà distributiva, (a+b+c)n
risulta uguale alla somma di tutti i prodotti di n
lettere di cui alcune sono a, altre sono b e le
rimanenti sono c.
Potenza di un trinomio


Fissiamo 3 numeri h,k,m la cui somma è n. Ci
chiediamo quante sono le sequenze di lettere a,b,c con
h volte la a, k volte la b e m volte la c, cioè quanti sono
gli addendi del tipo ahbkcm.
Le sequenze di questo tipo sono tante quante le
permutazioni con ripetizioni di una qualunque
sequenza di n lettere con h volte la a, k volte la b e m
volte la c vale a dire n!/(h!.k! .m!). Pertanto:
n!
h
k
m
( a  b  c) 

a

b

c

h ,k ,m:h k  mn h!k!m!
n
Esempio



Sviluppare (a+b+c)3.
Soluzione. Elenchiamo tutte le terne (h,k,m)
con h+k+m=3. A fianco di ciascuna terna
scriviamo il corrispondente termine, ossia
(3!/(h! . k! . m!)) . ah . bk . cm.
Fatto questo, basterà sommare tutti i termini
così ottenuti.
Esempio








(0,0,3)
(0,1,2)
(0,2,1)
(0,3,0)
(1,0,2)
(1,1,1)
(1,2,0)
(2,0,1)
(3!/(0!.0!.3!) c3= c3.
(3!/(0!.1!.2!) b c2= 3bc2.
(3!/(0!.2!.1!)) b2c= 3b2c
(3!/(0!.3!.0!) b3= b3.
(3!/(1!.0!.2!) .ac2= 3ac2.
(3!/(1!.1!.1!) abc= 6abc.
(3!/(1!.2!.0!)ab2= 3ab2.
(3!/(2!.0!.1!) .a2c=3a2c.
Potenza di un trinomio




(2,1,0) (3!/(2!.1!.0!)a2b= 3a2b.
(3,0,0) (3!/(3!.0!.0!)a3=a3.
Pertanto si ha:
(a+b+c)3= c3 +3bc2+ 3b2c+ b3+ 3ac2+ 6abc+
3a2c+ 3a2b+ a3.
Esercizi di riepilogo





Una classe di 28 studenti, di cui 13 maschi e 15
femmine deve eleggere 3 rappresentanti.
Quante sono le scelte possibili?
Risposta: C(28,3)= 3276.
Quante sono le scelte che prevedono almeno un
maschio e almeno una femmina?
Risposta: ci sono C(13,3)= 286 scelte che prevedono
solo maschi e C(15,3)=455 che prevedono solo
femmine. Il numero richiesto è quindi C(28,3)-C(13,3)C(15,3)=3276-455-286= 2535.
Esercizi di riepilogo


Un’auto con la targa italiana (2 lettere fra le 26
dell’alfabeto inglese, 3 cifre e poi ancora 2 lettere)
viene usata per una rapina. Un testimone ricorda che
la prima lettera era una T, che la prima cifra era 3, che
non vi erano zeri, e che le altre lettere erano una A,
una F e una K. Quante sono le targhe possibili?
Risposta: le tre lettere rimanenti (A, F e K) possono
variare in 3!=6 modi

Le due cifre variano in 9 . 9 = 81 modi.

In totale, 6 . 81 = 486 modi.
Esercizi di riepilogo



Un’urna contiene 40 palline numerate, e quindi
distinguibili. Fra queste, 18 sono colorate di rosso e 22
di nero. Quante sono le cinquine prese fra le 40 palline
che contengono 2 palline rosse e 3 nere?
Risposta: dobbiamo calcolare il numero di terne di
palline prese fra le 22 nere (ossia C(22,3)), e il numero
delle coppie di palline prese fra le 18 rosse, (ossia
C(18,2)).
Le scelte delle 3 palline nere e delle 2 rosse sono
indipendenti. Il numero richiesto è
C(22,3).C(18,2)=235620.
Esercizi di riepilogo



Quanti sono i sottoinsiemi di un insieme di n
elementi?
Risposta: vi sono C(n,0)=1 sottoinsiemi di 0
elementi, C(n,1) sottoinsiemi di 1 elemento,
C(n,2) di 2 elementi,…,C(n,n)=1 di n elementi.
In totale, il numero dei sottoinsiemi è
n
 n
 n  i ni
C (n, i )        1 1  (1  1) n  2n.

i 0
i 0  i 
i 0  i 
n
n
Esercizi di riepilogo
 20 
 

i 0  i 
10
Calcolare
Poniamo
x 
Pertanto
ed infine
 20 


 i 
 
i 0
 20   20 

   
20

i

  i 
Essendo
Si deduce
10
2
20
 (1  1)
 20  10  20  20  20   20 
              
i 0  i 
i 0  i 
i 10  i 
 10 
20
20
 20 
 20 
220  x  x  
 10 
  2x  
 10 





 20 
 
10
20
x  2     956198.
2
Esercizi di riepilogo


Ho smarrito il numero segreto della mia
tessera Bancomat. Mi ricordo che due cifre
erano 0, che la prima cifra era 5 e le altre due
erano un 3 e un 9. Qual è il massimo numero
di tentativi che devo fare per ricostruire il
numero segreto?
Risposta: devo determinare le altre 4 cifre.
Queste sono permutazioni della stringa 0039.
Tali permutazioni sono 4! : 2! = 12.
Esercizi di riepilogo



In pizzeria, quattro amici fanno le ordinazioni,
scegliendo fra 12 tipi di pizza. Quante sono le possibili
ordinazioni per il pizzaiolo se ciascuno ordina una
pizza ed una sola? E se ciascuno ne ordina 2?
Risposta: al pizzaiolo non importa l’ordine delle pizze
ma solo quante pizze deve fare per ciascun tipo.
Nel primo caso il numero richiesto è C’(12,4), nel
secondo C’(12,8).