Calcolo combinatorio

Cenni di calcolo combinatorio
1 Introduzione
Calcolare quanti sono i diversi modi di ordinare un insieme di oggetti è un problema interessante.
Quante sigle diverse si possono fare con le tre lettere RST ? In quanti modi diversi ci si può
vestire con tre gonne, due camicette, e quattro maglioni ? In quanti modi diversi si possono
accoppiare le squadre in un torneo?
Per rispondere a queste domande dobbiamo scoprire come si trova il numero dei possibili
ordinamenti di insiemi di oggetti.
Lo studio dei vari raggruppamenti che si possono fare con un numero finito di elementi e il
modo di calcolarne il numero si dice calcolo combinatorio.
2 Definizioni
Dati n oggetti distinti, si dice allineamento un qualunque ordinamento degli oggetti n in modo
che siano collocati in n posti numerati da 1 a n. (es le lettere dell’alfabeto).
Si dice disposizione semplice di n oggetti di classe k (k 6 n), ogni allineamenti di k
oggetti scelti tra gli n. Per esempio alcune disposizioni semplici, diverse fra loro, di classe 4 delle
lettere dell’alfabeto sono le seguenti:
a, c, f , h
a, f , h, c
(gli oggetti sono gli stessi e cambia l’allineamento)
c, a, f , h
a, m, d, t
m, a, r, t
(cambia almeno un’oggetto)
p, r, d, t
Si dice combinazione semplice di n oggetti di classe k (con k 6 n), ogni raggruppamento
di k oggetti scelti fra gli n, indipendentemente dall’ordine in cui vengono presi.
Nota 1. Nelle combinazioni non importa quindi l’ordine con cui vengono presi gli elementi (non
è necessario un preciso allineamento). È allora evidente che due combinazioni per essere diverse
devono avere almeno un oggetto diverso!
Per esempio ecco alcune combinazioni semplici di classe 5 delle lettere dell’alfabeto
r, m, g, h, u
e, a, t, h, u
r, m, h, p, u
(ciascun raggruppamento differisce dall’altro per almeno un oggetto)
Quando scriviamo una parola, ad esempio ALBERO, abbiamo in sostanza costruito una
disposizione delle 21 lettere dell’alfabeto di classe 6 (le sei lettere che compongono la parola);
qualsiasi parola può essere quindi pensata come una disposizione delle lettere dell’alfabeto. Ma
spesso le lettere che compongono una parola sono ripetute!
MATEMATICA è una disposizione delle lettere M, A, T, E, I, C, delle quali M, A, T sono
ripetute.
In questo caso k (i posti) possono essere anche maggiori di n (le lettere). Infatti per costruire
la nostra parola usiamo 6 lettere (n = 6) e riempiamo dieci posti (k = 10).
Si dice disposizione con ripetizione di classe k ogni allineamento di k oggetti scelti fra
gli n dati, con la convenzione che ogni oggetto possa essere ripetuto più volte.
1
2
Sezione 3
Analogamente si dice combinazione con ripetizione di classe k ogni raggruppamento di
k oggetti scelti fra gli n dati, con la convenzione che ogni oggetto può essere ripetuto.
3 Le disposizioni
3.1 Le disposizioni semplici
Esempio 1. Un concessionario di automobili vuole esporre nella vetrina del suo salone quattro
vetture tutte dello stesso tipo ma con 4 colori diversi (blu, grigio, rosso e nero). La vetrina però
dispone di soli due posti: uno fisso e l’altro fornito di una piattaforma rotante. Il concessionario
desidera sapere in quanti modi diversi è possibile disporre le auto.
Usiamo un diagramma ad albero per rappresentare la situazione:
Si hanno le seguenti possibilità
BG, BR, BN, GB, GR, GN, RB, RG, RN, NB, NG, NR
Il numero di disposizioni di 4 oggetti di classe 2, che indichiamo cn il simbolo D4,2 = 4 · 3 = 12
Supponiamo che il concessionario abia anche un terzo spazio d’esposizione, quante possibilità
ci sarebbero?
Usiamo di nuovo il diagramma ad albero:
3
Le disposizioni
Si nota che complessivamente le possibili disposizioni di vetture è D4,3 = 4 · 3 · 2 = 24
In generale per calcolare il numero di disposizioni semplici, cioè il numero di allineamenti
diversi con oggetti tutti diversi, di n oggetti a gruppi di k, dobbiamo tener presente che da
ognuno dei nodi iniziali si dipartono n − 1 nodi laterali e che da ognuno di essi poi si dipartono
n − 2 rami e così via, per cui
Dn,k = n · (n − 1) · (n − 2) (n − k + 1) = (n − k)!
n!
(k fattori)
3.2 Il caso particolare delle permutazioni e il simbolo fattoriale
Le permutazioni sono il caso particolare in cui k = n.
Esempio 2. Vogliamo contare in quanti modi possiamo far sedere tre persone su tre sedie. La
prima persona sarà indicata con A, la seconda con B e la terza con C.
Usiamo un diagramma ad albero:
Le 6 possibili combinazioni sono:
ABC
ACB
BAC
BCA
CAB
CBA
Quando il numero degli oggetti n corrisponde al numero dei posti k si parla di permutazioni.
Le permutazioni di n elementi sono tutti i possibili allineamenti che si ottengono scambiando semplicemente di posto gli n oggetti. Esse coincidono con le disposizioni semplici di n
elementi di classe n.
Pn = Dn,n = n · (n − 1) · (n − 2) 3 · 2 · 1
Nota 2. Osserviamo che tale prodotto ha per fattori tutti i numeri naturali a partire da n fino
a 1. Esso viene anche indicato col simbolo n! e si chiama fattoriale di n (si legge anche “n fattoriale”). Per ogni numero naturale n > 1 si pone cioè:
n! = n · (n − 1) · (n − 2) · 2 · 1
E per completare la definizione si pone poi:
4
Sezione 3
0! = 1 e 1! = 1
Dunque la permutazione di n elementi si calcola:
Pn = n!
Si noti infine che:
(n + 1)! = (n + 1) · n!
3.3 Permutazioni con elementi identici
Consideriamo l’insieme di sei elementi a, a, b, b, b, c
nel quali i primi due sono identici e i secondi tre sono uguali tra loro. Quando scambiamo di
posto due elementi dell’allineamento, non è detto che si ottenga una nuova disposizione perché
gli oggetti uguali non si distinguono. Il numero delle permutazioni nonè più dunque 6!, ma sarà
un numero inferiore. Per calcolare tale numero ragioniamo in questo modo. Mettiamo un indice
agli oggetti uguali in modo che diventino distinguibili tra loro
a1, a2, b1, b2, b3, c
Scriviamo poi una qualsiasi delle possibili permutazioni, per esempio
b1, a1, b3, c, a2, b2
Se togliamo gli indici alla lettera a otteniamo:
b1, a, b3, c, a, b2
Tutte le permutazioni che si ottengono da questa scambiano fra loro le lettere a danno la
stessa permutazioneed il numero di queste permutazioni è due (cioè 2 = 2!)
b1, a1, b3, c, a2, b2
b1, a2, b3, c, a1, b2
Ripetendo lo stesso ragionamento con la lettera b
b1, a1, b3, c, a2, b2
diventa
b, a1, b, c, a2, b
E nella fattispecie ci sono sei (cioè 6 = 3!) permutazioni che collassano a quest’ultima
b1, a1, b3, c, a2, b2
b1, a1, b2, c, a2, b3
b2, a1, b3, c, a2, b1
b2, a1, b1, c, a2, b3
b3, a1, b1, c, a2, b2
b3, a1, b2, c, a2, b1
Quindi le permutazioni saranno:
6!
3! · 2!
= 60
Generalizzando si ha per una permutazione di n elementi di cui l uguali tra loro, m uguali
tra loro, ecc, p uguali tra loro
n!
∗
Pn,l,m,
,p = l! · m! · · p!
5
Le disposizioni
Ecco uno schema ad albero con le 60 possibilità
3.4 Le disposizioni con ripetizioni
Consideriamo l’insieme A = {1, 3, 5, 8}: voglaimo determinare quanti numeri a due cifre si possono scrivere con gli elementi di A, considerando che sono ammesse le ripetizioni.
Usiamo un diagramma ad albero:
Le possibili combinazioni sono 16:
11
13
15
18
31
33
35
38
51
53
55
58
81
83
85
88
6
Sezione 4
r
Se indichiamo con D4,2
= 16 = 42
Se si considerasse di costruire numeri di tre cifre, con un diagramma ad albero ci si renderebbe conto che le possibilità salgono a 64, per cui la regola generale è:
r
Dn,k
= nk
4 Le combinazioni
4.1 Le combinazioni semplici
Dati gli oggetti a, b, c vogliamo calcolare il numero di combinazioni semplici di classe 2, che
indichiamo con C3,2
Abbiamo detto che in una combinazione si diversifica da una disposizione perché nella prima
non ha importanza l’ordine con cui si presentano gli elementi. Le disposizioni D3,2 sono 6 e sono
le seguenti:
ab
ac
bc
ba
ca
cb
Se non importa più l’ordine, lecoppie a b e b a, a c e c a, b c e c b possono essere considerate
uguali; allora le combinazioni sono ridotte a sole tre
ab
ac
bc
Il loro numero è quindi, pari al rapporto fra il numero delle disposizioni di 3 elementi presi a
2 a 2 ed il numero 2; ma quest’ultimo è il numero delle permutazioni di due elementi, quindi è 2!
, possiamo dunque scrivere che:
C3,2 =
D3,2
2!
o più in generale
Cn,k =
Dn,k
k!
=
n · (n − 1) · (n − 2) · · (n − k + 1)
k!
Il numero delle combinazioni Cn,k, si indica anche con il simbolo
n
k
che si legge “n su k”
e prende il nome, per motivi storici, di coefficiente binomiale. Cioè:
n
n!
n · (n − 1) · (n − 2) · · (n − k + 1)
= Cn,k = (n − k)! · k!
=
k!
k
Corollario 1. Nella mia libreria ci sono trenta libri diversi; anche se tutti gli abitanti della
Terra, uomini, donne e bambini, lavorassero giorno e notte per oltre un milione di anni, non
riuscirebbero a ordinare i libri della mia libreria in tutti i modi possibili. Provate a dimostrare
che questa affermazione è vera!
4.2 Combinazioni fra raggruppamenti indipendenti
Talvolta si forma una combinazione con elementi di raggruppamenti diversi. Allora si combinano le combinazioni di ciascun raggruppamento.
Esempio 3. L’allenatore di una squadra di pallacanestro deve scegliere due attaccanti e due
guardie. Se nella squadra ci sono 5 attaccanti e 4 guardie, quante formazioni diverse si possono
scegliere?
Le combinazioni
possibili per gli attaccanti sono:
5
5.4
C5,2 =
= 1.2 = 10
2
7
Esercizi
Le combinazioni
possibili per le guardie sono:
4
4.3
C4,2 =
= 1.2 = 6
2
Per ciascuna delle dieci possibili combinazioni di attaccanti vi sono sei possibili combinazioni
di guardie. Dunque il numero totale delle diverse formazioni è 10 · 6 = 60
5 Esercizi
Esercizio 1.
a) Quanti anagrammi,anche privi di significato,si possono formare con tutte le lettere della parola VERBASCO ?
[40320]
b) Quanti di questi hanno tutte le vocali l’una di seguito all’altra ?
[4320]
c) Quanti di questi iniziano e terminano con una consonante ?
[14400]
d) Quanti di questi iniziano con una consonante e terminano con una vocale?
[10800]
e) Quanti di questi iniziano con una vocale e terminano con la lettera E ?
[1440]
Esercizio 2.
a) In quanti modi 3 ragazzi e 2 ragazze possono mettersi in fila ?
[120]
b) In quanti modi possono mettersi in fila se i ragazzi vogliono stare l’uno di seguito all’altro e cos ì pure
le ragazze ?
[24]
c) In quanti modi possono mettersi in fila se devono alternarsi ? [12]
Esercizio 3.
In quanti modi Alberto, Bruno, Cecilia e Donatella si possono sedere su una panca di 4 posti se:
a) Alberto vuole sedersi all’estremità destra
b) Donatella non vuole sedersi ad una delle estremità
c) Bruno non vuole sedersi vicino ad una ragazza
[6]
[12]
[4]
d) Alberto non vuole sedersi vicino a Donatella
[12]
e) Le 4 persone non devono sedersi in ordine alfabetico
[23]
Esercizio 4. Un coro è composto da 8 cantanti.Se questi cantano tre volte al giorno, ed ogni volta qualcuno
cambia il proprio posto con un altro,quanto tempo occorrerebbe per eseguire tutti gli spostamenti possibili
prima di tornare alla posizione di partenza ? [36a 10m]
Esercizio 5.
a) Quanti anagrammi si possono formare con tutte le lettere della parola VEDERE
[120]
b) Quanti di questi anagrammi:
1. Terminano sempre con la lettera E ?
[60]
2. Iniziano e terminano sempre con una lettera uguale ?
[24]
3. Iniziano e terminano mai con una lettera uguale ?
[96]
4. Iniziano sempre con una consonante ?
[60]
5. Iniziano con una vocale e terminano con una consonante ?
[36]
Esercizio 6.
mare?
Con i colori dell’arcobaleno quante bandierine tricolori a strisce trasversali posso for[210]
8
Sezione 5
Esercizio 7. Quante colonnine tutte diverse si possono riempire giocando al totocalcio?
[1594323]
Esercizio 8. Quanti numeri di tre cifre, non importa se ripetute, si possono formare con le cifre 2,3,4,5,6,7
[216]
Esercizio 9. Con quattro persone esaminatrici, quante commissioni d’esame diverse di tre persone si possono formare?
[4]
Esercizio 10. un’associazione ha 30 membri. Se tra essi deve essere formato un comitato di 4 persone,
quanti comitati diversi sono possibili ?
[27405]
Esercizio 11.
a) Trova il numero di parole di 4 lettere che si possono formare con le lettere della parola
STRINGA
[840]
b) Quante di queste sono formate da sole consonanti?
[120]
c) Quante di queste iniziano e terminano con una consonante?
[400]
d) Quante di queste iniziano con una vocale?
[240]
e) Quante contengono la lettera R?
[480]
f) Quante iniziano con la T e terminano con una vocale?
[40]
g) Quante iniziano con la T e contengono anche la S?
[60]
h) Quante contengono entrambe le vocali?
[240]
Esercizio 12. Prendiamo nel piano 10 punti A, B , ..., K , in modo che non ce ne siano 3 sulla stessa retta.
a) quante rette vengono determinate dai punti?
[45]
b) quante di queste non passano per A o per B?
[17]
c) quante di queste non passano per A e per B?
d) quanti triangoli vengono determinati dai punti?
[44]
[120]
e) quanti di questi triangoli contengono il punto A?
[36]
f) quanti di questi triangoli contengono il lato AB?
[8]
Esercizio 13. Quanti distinti segnali ,ognuno formato da 6 bandiere allineate verticalmente,si possono ottenere da 4 identiche bandiere rosse e da 2 identiche bandiere gialle?
[15]
Esercizio 14. In quanti modi si può formare una commissione di 3 uomini e 2 donne scelti fra 7 uomini e 5
donne?
[350]
Esercizio 15. Una classe è formata da 9 ragazzi e 3 ragazze.
a) In quanti modi un insegnante può scegliere una commissione di 4 studenti?
[495]
b) Quante commissioni conteranno esattamente una ragazza?
[252]
c) Quante commissioni conteranno al minimo una ragazza?
[369]
Esercizio 16. Una donna ha 11 amici.
a) In quanti modi può invitarne 5 a pranzo?
[462]
b) In quanti modi se due amici sono sposati e non partecipano separatamente?
[210]
c) In quanti modi se due di essi non sono in buoni rapporti e non partecipano assieme?
[378]
Esercizi
9
Esercizio 17. Un quartiere è stato diviso in zone nord e sud. La zona nord comprende 16 caseggiati e la
zona sud ne comprende 10. Un rappresentante deve visitare 4 caseggiati della zona nord e 3 della zona sud.
In quanti modi diversi può farlo ?
[218’400]
Esercizio 18. Cinque persone devono apparire nello stesso gruppo fotografico. Se due di loro rifiutano di
apparire vicini nella foto, in quanti modi diversi può essere fotografato il gruppo ?
[72]
Esercizio 19. Una scuola offre corsi di specializzazione in italiano, inglese, diritto, elettronica, informatica e
robotica. Se uno studente vuol seguire solo 3 corsi, in quanti modi diversi può scegliere il suo curricolo ?
[20]
Esercizio 20. Un gruppo di 7 lavoratori decide di mandare una delegazione di 2 persone a esporre le loro
lamentele al capo del personale.
a) quante delegazioni diverse sono possibili ?
[21]
b) si decide che un lavoratore particolare deve essere nella delegazione; quante delegazioni sono possibili?
[6]
Esercizio 21. Una cassetta contiene 25 mele e 5 di esse sono marce.
a) quanti campioni diversi di 3 mele possono essere presi dalla cassetta ?
b) quanti campioni diversi di 3 mele possono ottenersi, in cui tutte e tre le mele siano marce ?
c) quanti campioni diversi di 3 mele si possono avere, in cui 2 mele siano sane e 1 marcia ?
[2’300]
[10]
[950]
Esercizio 22. In una società vi sono 24 soci fra i quali devono essere scelti un presidente, un vicepresidente
ed un segretario. In quanti modi si può fare la scelta ?
[12’1446]
Esercizio 23. 5 persone viaggiano su un’automobile, 2 davanti e 3 dietro. In quanti modi diversi possono
sedersi se:
a) tutte le persone hanno la patente di guida?
[120]
b) solo due persone hanno la patente di guida?
[48]
c) 2 persone hanno la patente di guida e una terza persona è allievo conducente?
[60]
Esercizio 24. In una certa indagine su un omicidio l’investigatore Smith, per risolvere il caso, ha solo
bisogno di determinare un certo numero di telefono. Dei testimoni hanno sentito il numero, ma non sono
d’accordo su di esso. Sono tutti però concordi su quanto segue:
a) il numero è composto di cinque cifre e termina con la cifra 0
b) la prima cifra è dispari
c) tutte le cifre sono diverse
d) la cifra più grande è 5
Quanti numeri telefonici deve controllare l’investigatore Smith ?
[72]