Calcolo combinatorio

2021/22

Docente:
Prof. Mangiagli Marcantonio
 Calcolo combinatorio
Scopo:
Determinare in quanti modi possono essere associati,
secondo prefissate regole, gli elementi di uno stesso
insieme o di più insiemi
Esempio:
1. In quanti modi diversi si possono scegliere tre libri da una
libreria che ne contiene 12 ?
2. Nel menù di un ristorante si può scegliere tra cinque primi
piatti, sei secondi e sette dessert: quanti tipi di pasti, con
almeno una portata diversa, può somministrare il ristoratore?
3. In quanti modi si possono disporre 4 persone in 4 posti diversi?
 Calcolo combinatorio
Fornisce quegli strumenti di calcolo per determinare il
numero di raggruppamenti che si possono formare
con un numero k di oggetti presi da un insieme
contenente n oggetti
Se i k oggetti formano gruppi ordinati -- disposizioni

Se i k oggetti formano gruppi non ordinati -- combinazioni

Se k = n formano gruppi ordinati -- permutazioni.

Se i k oggetti sono distinti -- Semplici

Se qualche oggetto si ripete -- Con ripetizione
 Il fattoriale di un numero naturale

• Se n è un numero naturale maggiore di 1

si definisce n! e si legge “n fattoriale” il prodotto dei
primi n numeri naturali

• Per n=1 ed n=0 si pone per definizione

0!=1 e 1!=1
• Esempio: 3!=1*2*3=6 5!=1*2*3*4*5=120
 Proprietà del fattoriale

• Infatti
 Regola fondamentale del
calcolo combinatorio
Se un oggetto è costruito con una sequenza di k scelte e vi
sono n1 possibilità per la prima scelta, n2 per la seconda, …,
nk per la k-esima, il numero totale degli oggetti (k-uple
ordinate) così ottenibili è

Esempi:
Se ad un ristorante si può scegliere tra 5 primi piatti, 6 secondi e
4 dessert, il numero totale di pranzi completi di 3 portate (un
primo, un secondo, un dessert) è 5⋅6⋅4 =120.
 Regola fondamentale del
calcolo combinatorio
Calcolare quanti numeri naturali ci sono con quattro
cifre ( decimali ) distinte.

I numeri naturali di 4 cifre (decimali) tutte distinte sono 9⋅9⋅8⋅7= 4536.

Infatti, la prima cifra può essere scelta da 1 a 9 in 9 modi diversi (non

è incluso la cifra 0 perché, i numeri naturali, escluso lo zero, non
hanno zero come prima cifra); per la seconda cifra si hanno ancora 9
scelte in quanto essa deve essere scelta da 0 a 9 ma diversa dalla
prima; analogamente per la terza cifra si hanno 8 scelte possibili, e
per la quarta 7.
 Disposizioni semplici
Si chiamano disposizioni semplici degli n elementi presi a k a k
(o disposizioni della classe k ) un gruppo ordinato formato da k degli n elementi
dell’insieme dato A in modo che valgano le seguenti proprietà:
1. in ciascun raggruppamento figurano k oggetti senza ripetizione;
2. due di tali disposizioni si ritengono diverse quando differiscono per almeno un
elemento oppure per l’ordine con cui gli stessi elementi si presentano nel
raggruppamento.

A={a,b,c}
Sono disposizioni semplici dei tre elementi di A in classe 2
le coppie (a,b) (b,a),(a,c) (c,a), (c,b),(b,c)
Non sono disposizioni semplici: (a,a) (b,b) (c,c)

Le disposizioni semplici sono un sottoinsieme di A2

 Disposizioni semplici
Il numero delle disposizioni semplici di n elementi
distinti, della classe k, si indica con il simbolo Dn, k.

TEOREMA
Il numero delle disposizioni semplici di n elementi distinti della classe k,
è uguale al prodotto di k numeri interi consecutivi decrescenti dei quali il
primo è n.

Calcolare le disposizioni delle lettere A,B,C su due posti e

stabilire il loro numero.
Le disposizioni sono: AB AC BA BC CA CB.

D3, 2 =3*2= 6
 Disposizioni semplici

Proprietà:

.
Dimostrazione:
 Disposizioni con ripetizione
Consideriamo un insieme costituito n elementi distinti ed un
numero naturale k senza alcuna limitazione superiore.
Le disposizioni con ripetizione di n oggetti su k posti sono costituite da
raggruppamenti di k oggetti scelti dagli n elementi in modo che:

a) in un raggruppamento uno stesso oggetto può figurare ripetuto fino ad un

massimo di k volte;
b) due qualsiasi raggruppamenti sono distinti se uno di essi contiene almeno
un oggetto che non figura nell’altro, oppure gli oggetti sono diversamente
ordinati, oppure gli oggetti che figurano in uno figurano anche nell’altro ma
sono ripetuti un numero diverso di volte.
Esempio: se A={a,b} allora
A3={(a,a,a), (a,a,b), (a,b,a), (a,b,b), (b,a,a), (b,a,b), (b,b,a),
(b,b,b)}
Gli elementi di A3 formano le disposizioni con
ripetizione di 2 elementi di classe 3
 Disposizioni con ripetizione
Il numero delle disposizioni con ripetizione si indica
con il simbolo D'n, k
Teorema
Il numero di disposizioni con ripetizione di n oggetti di
classe k è dato da n elevato a k,
D'n,k = nk.

Determiniamo quanti numeri diversi di tre cifre si possono

formare con le nove cifre decimali ( 0 escluso).

È evidente che si tratta di disposizioni con ripetizione di 9

elementi della classe 3, per cui si ha D'9,3 = 93 = 729.

S
 Permutazioni semplici
Le permutazioni semplici di n oggetti sono raggruppamenti
di n oggetti senza ripetizione in maniera tale che due
raggruppamenti sono distinti se differiscono solo per
l’ordine in cui sono disposti gli elementi.
Siano dati gli la cifre 1,2,3 calcolare le permutazioni delle tre
cifre.
Si tratta di raggruppare i tre oggetti in modo che i raggruppamenti
differiscono solo per l’ordine.
Avremo quindi i seguenti raggruppamenti
123 132 213 231 312 321
in totale 6.
Il numero di permutazioni semplici di n oggetti, indicato con Pn, è
uguale al numero di disposizioni semplici degli n oggetti in classe n
 Permutazioni semplici

Pn = n!
Siano dati gli la cifre 1,2,3 calcolare le permutazioni delle tre cifre.
P3=3!=3*2*1=6
 Permutazioni semplici
Gli anagrammi di una parola costituita da lettere diverse altro non
sono che le permutazioni che si ottengono dalla parola variando
solo il posto delle lettere.

Con la parola ROMA (composta da 4 lettere) Quanti anagrammi

si possono formare?
Si tratta di calcolare le permutazioni di 4 oggetti.
P4 = 4! = 4x3x2x1 = 24 anagrammi.
 Combinazioni semplici
Dato un insieme di n elementi, si dicono combinazioni semplici
degli n elementi presi a k a k (o di classe k) con k n

tutti i gruppi di k elementi, scelti fra gli n dell’insieme dato, in

modo che ciascun gruppo differisca dai restanti almeno per uno
degli elementi in esso contenuti (senza considerare, quindi,
l’ordine degli elementi).
Le combinazioni semplici di tre oggetti A,B,C su due posti
sono:
AB AC BC In totale 3
Le combinazioni di quattro oggetti 1,2,3,4 su due posti
sono
12 13 14 23 24 34 in totale 6.
 Combinazioni semplici
Dato un insieme A di n elementi le combinazioni degli n elementi
in classe k possono essere pensati come sottoinsiemi di A
costituiti da k elementi

A={1,2,3}

{1} {2} {3} Combinazione di 3 oggetti classe 1

{1,2} {2,3} {3,1} Combinazione di 3 oggetti classe 2

{1,2,3} Combinazione di 3 oggetti classe 3

Il numero delle combinazioni semplici di n elementi di classe k,

si indica Cn, k
 Combinazioni semplici
Considero una combinazione di classe k e permuto tutti i suoi elementi.
Eseguo questa operazione per tutte le combinazioni. Quello che otterrò
saranno tutte le disposizioni
Allora il numero delle disposizione di n oggetti classe k saranno uguali
al numero di combinazione di n oggetti di classe k moltiplicato il numero
delle permutazioni dei k elementi

=
 Combinazioni semplici

Il numero delle combinazioni di n oggetti di classe k è dato

dal rapporto tra il prodotto di k fattori interi, consecutivi,
decrescenti a partire da n ed il prodotto di k fattori interi,
consecutivi, crescenti a partire da 1.

Il numero di combinazioni semplici di tre oggetti A,B,C su due posti

è C3,2 =

Il numero di combinazioni di quattro oggetti 1,2,3,4

su due posti è C4,2 =

 Combinazioni semplici
Quante rette passano per 5 punti a tre a tre non allineati?
Se indichiamo con P1,P2,P3,P4,P5 i 5 punti una retta è individuata
da due punti dove l’ordine dei due punti non è importante.
Quindi si tratta di combinazione di 5 oggetti di classe 2

Quante diagonali ha un pentagono convesso?

E un poligono convesso di n lati?
 Combinazioni semplici
Cn,k si può scrivere anche
come
 Coefficienti binomiali
Il numero delle combinazioni semplici, Cn,k è spesso indicato con
Il simbolo seguente:

che si legge « n su k » e viene detto coefficiente binomiale.

Viene chiamato cosi perché è il coefficiente della parte

letterale akbn-k nello sviluppo di (a+b)n

Con

S
 Proprietà dei
coefficienti binomiali
 Il triangolo di Tartaglia
La quarta proprietà , che si può anche scrivere

insieme alla prima proprietà

permettono di calcolare i coefficienti binomiali per ricorrenza.

Il triangolo di Tartaglia
 Il triangolo di Tartaglia
k
n 0 1 2 3 4 5 6 7 8
1
0
1 1
1
1 2 1
2
1 3 3 1
3
1 4 6 4 1
4
1 5 10 10 5 1
5
1 6 15 20 15 6 1
6
1 7 21 35 35 21 7 1
7
1 8 28 56 70 56 28 8 1
8
 Il triangolo di Tartaglia
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
 Permutazioni con ripetizione
Supponiamo ora che degli n elementi di una permutazione
ve ne sia uno che si ripete k volte( k< n).

Ci proponiamo allora di trovare il numero delle loro

permutazioni che indicheremo con

Supponiamo di voler determinare gli anagrammi della parola ORO

Notare come una lettera si ripete due volte.
Gli Anagrammi( permutazioni) sono ORO ROO OOR
E sono 3
 Permutazioni con ripetizione
Distinguendo le due O indicandole O1 e O2 avrò le
permutazioni
O1 R O 2 O 2 R O1
R O 1 O2 R O 2 O1
O1 O2 R O 2 O1 R
Ma se le due O sono indistinuibili la prima e la seconda permutazione sono
uguali, cosi come la terza e la quarta e la quinta e la sesta.
Per cui le permutazioni distinte sono la metà.
Ma perché sono proprio la metà? Perché due sono i modi di permutare
le 2 O nei loro posti rendendo la permutazione indistinguibile.
Permutazioni con ripetizione
Il numero delle permutazioni di n oggetti
di cui uno si ripete k volte è

Generalizzando

Il numero delle permutazioni di n oggetti

di cui uno si ripete k1 volte, un altro k2volte, un altro ancora
k3 volte e cosi via è indicato Pn(k1,k2,k3,..)
Permutazioni con ripetizione
Ad esempio, se prendiamo in considerazione la parola
MATEMATICA osserviamo che nelle 10 lettere in essa
contenute, la lettera M si ripete 2 volte (k1= 2), la lettera A
si ripete 3 volte (k2 = 3) e la lettera T si ripete 2 volte k3 =
2). Il numero di anagrammi distinti che si possono
costruire con essa è dato da:
 Permutazioni con ripetizione
Quanti anagrammi ha parola MAMMA ?
Il numero di elementi è 5 con
M che si ripete 3 volte e
A che si ripete 2 volte.

Infatti gli anagrammi sono

MMMAA MMAMA MAMMA AMMMA MMAAM
MAMAM AMMAM MAAMM AMAMM AAMMM
 Permutazione con ripetizione
Calcoliamo il numero di permutazioni di n oggetti di cui uno
si ripete k volte e un altro n-k volte.
Esempio: le permutazioni di AAAAAAABBB dove A si ripete
7 volte e B 3 volte

Coincide con il numero di combinazioni di n oggetti su k posti

PERCHE?
 Permutazione con
ripetizione

Proprietà

Segue da
Potenza intera di un binomio
Sia dato il binomio (a+b) si voglia calcolare la sua
potenza n-esima (a+b)n
Calcoliamo il quadrato del binomio

Nello sviluppo del quadrato notare come il monomio

a2 figuri tante volte quante P2(2,0)=1
ab figuri tante volte quante P2(1,1)=2
b2 figuri tante volte quante P2(0,2)=1
Potenza intera di un binomio
Calcoliamo il cubo del binomio

Notare come il monomio

a3 figuri tante volte quante P3(3,0)=1
a2b figuri tante volte quante P3(2,1)=3
ab2 figuri tante volte quante P3(1,2)=3
b3 figuri tante volte quante P3(0,3)=1
 Potenza intera di un binomio
Sviluppando

Il termine che ha per parte letterale akb(n-k) sarò ripetuto

Pn(k,n-k)
e quindi il coefficiente sarà proprio lui cioè

QUINDI
 Applicazioni

Poniamo nella formula trovata a=1 e b=1

Cosa rappresenta la somma a secondo membro?

 Applicazioni
Consideriamo un insieme A costituito da n elementi.
Quanti sono i sottoinsiemi che contengono k elementi ?
I sottoinsiemi costituiscono le combinazioni di n oggetti su k posti
Quindi il loro numero sarà
 Applicazioni

Il secondo membro è la somma del numero di sottoinsiemi con

1 elemento, 2 elementi, con 3 elementi,…..,n elementi
Cioè da il numero dei sottoinsiemi di A
Dall’uguaglianza sopra data possiamo dire che:

Il numero di sottoinsiemi di un insieme di n elementi è 2 n

 Combinazioni con ripetizione
Consideriamo un insieme formato da n elementi e fissiamo
un numero k (senza alcuna limitazione superiore).
Ci proponiamo di costruire i possibili raggruppamenti distinti
prendendo k elementi dell’insieme dato in modo che:

1) in ciascun raggruppamento figurino k elementi

dell’insieme dato potendovi uno stesso elemento figurare
più volte fino ad un massimo di k volte;

2) due raggruppamenti sono distinti se uno di essi contiene

almeno un elemento che non figura nell’altro, oppure gli
elementi che figurano in uno figurano anche nell’altro ma
sono ripetuti un numero diverso di volte.
 Combinazioni con ripetizione
A = { a, b, c }
Le combinazioni di classe 2, con ripetizione, sono:
aa ab ac bb bccc
In totale sono 6

Le combinazioni di classe 3, con ripetizione, sono:

aaa aab aac abb abc
acc bbb bbc bcc ccc
In totale sono 10.
Le combinazioni di classe 4, con ripetizione , sono:
aaaa aaab aaac aabb aabc aacc a
bbb abbc accc abccbbbc bbbb bccc
cccc bbcc
In totale sono 15.
 Combinazioni con ripetizione
Numero di combinazioni con ripetizione di n oggetti di classe k
Consideriamo una combinazione con ripetizione di 4 oggetti
(a,b,c,d) di classe 6
( a, b, b, d, d, d )
Adesso codifico la combinazione ponendo un 1 al posto
dell’elemento e aggiungendo un posto in corrispondenza di
ogni cambio dell’elemento e ponendo uno 0.
( 1, 0, 1, 1, 0, 0, 1, 1, 1 )

Gli 0 sono (4 -1)=3 e gli 1 sono 6, inoltre i due 0 consecutivi

indicano che manca l’elemento corrispondente.
Cambiando raggruppamenti di 1 e 0 otteniamo un’altra combinazione
con ripetizione. Infatti la combinazione (1,0,1,1,0,1,1,0,1)
corrisponderà a (a,b,b,c,c,d).
 Combinazioni con ripetizione
Quindi ad ogni combinazione con ripetizione di 4 oggetti classe 6
corrisponde una disposizione (4-1) 0 e 6 1 e viceversa
una disposizione di (4-1) 0 e 6 1 individua una combinazione di
4 oggetti classe 6 con ripetizione
Il numero di disposizioni di (4-1) 0 e 6 1 non sono altro che le
permutazioni con ripetizione di 9 (4-1+6) oggetti di cui uno si ripete
(4-1) volte e l’altro 6 volte

Il numero di permutazioni trovate coincide con il numero di

combinazioni con ripetizione di 4 oggetti su 6 posti
 Combinazioni con ripetizione
Generalizzando Il numero di combinazioni con ripetizione
di n oggetti classe k è uguale
al numero di permutazioni con ripetizione di n-1+k oggetti di cui
uno si ripete n-1 volte e l’altro k volte

Ma

Quindi
Combinazioni con ripetizione
 Combinazioni con ripetizione
Applicazione
Trovare le combinazioni con ripetizione di 3 elementi di classe 5.
Siano A, B e C i tre elementi.
Considero tre di queste combinazioni. E costruisco una tabella in
cui per ogni combinazione e per ogni elemento riporto il numero
di volte che si ripete quel elemento.
Elemento
combinazione A B C Somma

AAAAB 4 1 0 5
AABBC 2 2 1 5
BBBBC 0 4 1 5

Per ogni combinazione con ripetizione si genera

una terna di numeri naturali ( uno per ogni elemento
dell’insieme ) la cui somma da 5 ( la classe)
 Applicazione
Quindi le terne sono soluzioni di numeri naturali
dell’equazione

Quante sono queste terne?

Il numero di queste terne è proprio
C’3,5
Ma sono tutte le soluzioni?
Cioè esistono terne di numeri la cui somma dà 5 che non sia
prodotta da alcuna combinazione?
Ovviamente no. Infatti fissata una terna (x1,x2,x3) di somma 5, il
raggruppamento corrispondente sarà formato dal primo elemento
che si ripete x1 volte, dal secondo elemento che si ripete x2 volte e
dal il terzo elemento che si ripete x3 volte, che è proprio una
combinazione con ripetizione di tre elementi di classe 5.
 Applicazione
Allora le soluzioni di numeri naturale dell’equazione

Sono date dalle combinazione con ripetizione di 3 oggetti classe 5

 Applicazione
Trovare il numero di soluzioni naturali dell’equazione

Il numero di soluzioni è

7 soluzioni.
Infatti trovando le soluzioni
(6,0) (5,1) (4,2) (3,3) (2,4) (1,5) (0,6)
 Applicazioni
GENERALIZZANDO
Il numero di soluzioni naturali dell’equazione
x1+x2+x3+ …..+xn=k
è dato da C’n,k
Trovare i diversi modi di porre n biglie identiche in k urne
ordinate o numerate.
Il problema è equivalente al problema precedente.
Infatti se con (x1,x2,x3,…xn) indichiamo, rispettivamente, il
numero di biglie nella prima, seconda, terza, …n-enima urna si
dovrà avere che x1+x2+x3+ …..+xn=k, e quindi si tratterà di trovare
il numero di soluzioni naturali dell’equazione x1+x2+x3+ …..+xn=k
Il numero dei modi sarà uguale alle combinazioni con ripetizione
di n oggetti classe k
 Applicazioni
Torniamo al problema posto all’inizio della lezione
In quanti modi si possono disporre 7 biglie identiche in 4 urne
ordinate?

Il numero di modi è
FINE