calcolo combinatorio - Dipartimento di Matematica

CALCOLO COMBINATORIO
1.1 Necessità del calcolo combinatorio
Accade spesso di dover risolvere problemi dall'apparenza molto semplice, ma che
richiedono calcoli lunghi e noiosi per riuscire a trovare delle conclusioni valide.
Supponiamo, ad esempio, di voler risolvere il seguente problema: in quanti modi
quattro persone possono sedersi l’una accanto all’altra?
Risolvere il problema, nel migliore dei casi, richiede disciplina e la scelta di una
strategia per arrivare a contare effettivamente tutti i modi possibili. Decidiamo, allora, di
procedere sistematicamente per esaurire tutte le possibilità esistenti: fissiamo la prima persona,
senza cambiargli di posto, e contiamo in quanti modi le tre rimanenti possono sederglisi
accanto. Poi fissiamo la seconda e così via fino alla quarta. Se chiamiamo A, B, C e D le
quattro persone, avremo:
ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
DABC
DACB
DBAC
DBCA
DCAB
DCBA
Dallo schema precedente, si vede subito che ci sono 24 modi diversi per far sedere
quattro persone l'una accanto all'altra, in fila.
Il nostro problema é risolto, diremmo. Ma quanta fatica per arrivarci! In effetti, a noi
interessa solo contare il numero dei diversi modi e non elencarli esplicitamente l'uno dopo
l'altro.
Supponiamo ora di voler complicare il problema. Possiamo ritenere che le lettere, che
rappresentano le quattro persone, elencate l'una dopo l'altra, siano le lettere dell’alfabeto di una
certa lingua. Allora, se non ci sono ripetizioni di lettere, ci sono 24 parole diverse che si
possono formare con le quattro lettere dell'alfabeto.
Ma quante parole si possono formare se vogliamo considerare anche le ripetizioni di
ciascuna lettera? Per rispondere potremmo pensare di seguire la strategia precedente. Ma ci
vorrebbe molto tempo e rinunciamo a farlo, dando soltanto il risultato: 256.
Il risultato di sopra l'abbiamo dato non perché, in separata sede ci siamo messi a fare il
lavoro per elencare prima e contare poi le parole che si possono formare. Abbiamo soltanto
2 Cap. 1: Calcolo combinatorio
contato il numero del modi possibili in cui le quattro lettere si possono scrivere l'una accanto
all'altra con tutte le ripetizioni possibili. Vediamo come.
In quanti modi possiamo scegliere la prima lettera? In 4 modi diversi.
In quanti modi possiamo scegliere la seconda lettera? In 4 modi diversi.
In quanti modi possiamo scegliere la terza lettera? In 4 modi diversi.
In quanti modi possiamo scegliere la quarta lettera? In 4 modi diversi.
Allora il numero delle parole possibili (contando le ripetizioni) é: 4x4x4x4=256.
Per il primo problema la situazione è differente in quanto non possiamo avere
ripetizioni; e dunque:
In quanti modi possiamo scegliere la prima lettera? In 4 modi diversi.
In quanti modi possiamo scegliere la seconda lettera? In 3 modi diversi.
In quanti modi possiamo scegliere la terza lettera? In 2 modi diversi.
In quanti modi possiamo scegliere la quarta lettera? In 1 modo.
Allora il numero dei modi in cui possiamo scrivere, senza ripetizioni, parole con le
quattro lettere A, B, C e D é: 4x3x2x1=24.
A quali conclusioni ci portano le considerazioni precedenti?
Innanziturro possiamo fare astrazione dalla natura degli oggetti considerati (persone o
lettere dell'alfabeto). In secondo luogo, la scelta di una buona strategia di calcolo può farci
evitare elenchi lunghi e noiosi che, in casi più complessi, sarebbero addirittura impensabili.
Scopo del calcolo combinatorio é evitare, appunto, elenchi inutili e noiosi ed arrivare al
risultato richiesto con l'ausilio di calcoli molto semplici (le classiche 4 operazioni!) e di fornire
anche, se necessario, gli elenchi di tutti i casi possibili.
Nel resto del capitolo vedremo, in modo sistematico, le tecniche del calcolo
combinatorio da applicare, nei capitoli seguenti, al calcolo delle probabilità.
1.2 Disposizioni semplici e con ripetizione
Un problema molto ricorrente, in diverse situazioni (non necessariamente di tipo
matematico), é quello del calcolo del numero dei modi in cui un certo numero di elementi, presi
da un determinato insieme finito, possono essere disposti, ritenendo che due configurazioni
sono diverse o per la natura degli elementi o per l'ordine in cui gli elementi sono sistemati.
Per rendere le idee più chiare, supponiamo di avere un insieme di cinque lettere: A, B,
C, D ed E. Vogliamo sapere quante parole diverse, ciascuna formata da tre lettere, si possono
formare a partire dalle cinque lettere date. Ogni parola prende il nome di disposizione dei
cinque elementi presi tre alla volta. E' chiaro che la prima lettera può essere scelta, tra le cinque,
in cinque modi diversi; la seconda lettera, tra le quattro rimanenti, in quattro modi diversi;
infine, la terza lettera, tra le tre rimanenti, in tre modi diversi. Quindi otteniamo 5x4x3=60
modi diversi di disporre tre lettere da scegliere in un insieme di cinque lettere.
3
R. SANTORO: Elementi di calcolo delle probabilità
La cosa può essere generalizzata, considerando un insieme di n elementi e volendo
calcolare il numero di modi in cui possiamo scegliere una configurazione di k elementi, tra gli n
disponibili, considerando diverse due configurazioni che hanno elementi diversi o che, pur
avendo gli stessi elementi, questi sono disposti in ordine diverso. Si parla in questo caso di
disposizioni semplici di n elementi presi k alla volta, il cui numero viene indicato
simbolicamente con D(n,k) o con D kn .
Per calcolare questo numero possiamo procedere come nell'esempio precedente:
In quanti modi possiamo scegliere il 1° elemento? In n modi diversi.
In quanti modi possiamo scegliere il 2° elemento? In n - 1 modi diversi.
In quanti modi possiamo scegliere il 3° elemento? In n - 2 modi diversi.
.......................................................
In quanti modi possiamo scegliere il k-esimo elemento? In n - k + 1 modi diversi.
Allora avremo:
Dkn = n  (n - 1)  (n - 2)...(n - k + 1)
(1)
La (1), che ci dà il numero di disposizioni semplici di n elementi presi k alla volta, può
essere letta come il prodotto di k fattori naturali decrescenti a partire da n.
Mediante la (1), non abbiamo più bisogno di elencare tutte le configurazioni possibili e
poi contarle. Tutto si riduce ad un calcolo meccanico per il problema specifico.
Esempio 1
Calcolare in quanti modi 10 palline numerate da 1 a 10 possono essere estratte
da un'urna prendendone 4 alla volta.
Il calcolo é semplice ed abbiamo:
D(10,4) = 10·9·8·7 = 5040.
Notare che abbiamo il prodotto di 4 fattori decrescenti a partire da 10.
Esempio 2
Calcolare il numero dei modi in cui uno studente può scegliere, nell'ordine, 5
domande tra un questionario di 8 domande.
Abbiamo facilmente:
D(8,5) = 8·7·6·5·4 = 6720.
Notare che abbiamo il prodotto di 5 fattori decrescenti a partire da 8.
Ma cosa succede se i k elementi che dobbiamo scegliere tra gli n disponibili possono
essere ripetuti? In questo caso si parla di disposizioni con ripetizione di n elementi presi k alla
volta, il cui numero viene indicato con D'(n,k) o con D' kn .
Il calcolo del numero di queste disposizioni é ancora più semplice che nel caso delle
disposizioni semplici, in quanto, ogni volta, possiamo scegliere tutti gli n elementi dell'insieme
dato. Avremo allora:
In quanti modi possiamo scegliere il 1° elemento? In n modi diversi.
In quanti modi possiamo scegliere il 2° elemento? In n modi diversi.
In quanti modi possiamo scegliere il 3° elemento? In n modi diversi.
.......................................................
4 Cap. 1: Calcolo combinatorio
In quanti modi possiamo scegliere il k-esimo elemento? In n modi diversi.
Dunque:
D' nk = n k
Esempio 3
(2)
Omettendo il loro discutibile significato, quante parole di 3 lettere si possono
formare con 5 lettere?
Abbiamo immediatamente:
3
D'(5,3) = 5 = 125.
Esempio 4
Disponendo di bandiere di 7 colori diversi, quanti messaggi differenti si possono
formare usando 4 bandiere alla volta?
Si tratta evidentemente di disposizioni con ripetizione di 7 elementi presi 4 alla
volta. Quindi avremo:
4
D'(7,4) = 7 = 2401.
Esempio 5
Calcoiamo il numero delle colonne che é mecessario giocare, nel gioco del
Totocalcio, per fare con certezza un tredici.
In questo gioco, molto popolare in Italia, bisogna fare dei pronostici su tredici
partite di calcio dei campionati di serie A, serie B e serie C. Per dare la vittoria
alla squadra che gioca in casa bisogna indicare '1' sulla schedina, per dare un
pareggio 'X' e per dare la sconfitta alla squadra di casa '2'. Allora si tratta di
calcolare il numero delle disposizioni con ripetizione di tre elementi (1, X e 2)
presi 13 alla volta:
13
D'(3,13) = 3 = 1.594.323.
Come si vede il numero delle colonne da giocare per fare certamente un tredici é
molto grande e bisognerebbe investire delle somme considerevoli (con 800 lire a
colonna, ben 1.275.548.400 lire) per riuscire un tredici che nessuno assicura, a
priori, essere miliardario!
1.3 Permutazioni semplici e con ripetizione
Se il numero di elementi da prendere in considerazione é uguale al numero degli
elementi dell'insieme considerato non si parla più di disposizioni di n elementi presi n alla volta
ma piuttosto di permutazioni di n elementi.
Per calcolare il numero di permutazioni semplici di n elementi,P(n), possiamo applicare
la (1) del paragrafo precedente; solo che, in questo caso, dovremo avere il prodotto di n fattori
decrescenti a partire da n fino a 1:
P(n) = P n = n  (n - 1)  (n - 2)...2  1 = n!
(3)
5
R. SANTORO: Elementi di calcolo delle probabilità
dove abbiamo anche una nuova notazione (n!, da leggere n fattoriale), appunto per indicare il
prodotto suddetto. Con la nuova notazione, possiamo riscrivere la (1) in questa nuova forma (la
facile dimostrazione si lascia per esercizio al lettore):
Dkn =
n!
(n - k )!
(1')
A proposito di fattoriale, mentre
risulta immediato che 1!=1, dobbiamo ammettere, per convenzione e per dare un senso alla (1')
quando n = k, che 0!=1.
Esempio 6
Calcoliamo il numero di permutazioni di 6 elementi.
Abbiamo:
P(6) = 6! = 6·5·4·3·2·1 = 720.
Esempio 7
In quanti modi 4 persone possono sedersi in fila? (ricordate l'esempio del
paragrafo 1.1?)
Abbiamo:
P(4) = 4! = 4·3·2·1 = 24.
Il fattoriale di un numero cresce rapidamente al cresce del numero, come si può vedere
dalla tabella della pagina seguente che fornisce il fattoriale di alcuni numeri:
n
0
1
2
3
4
5
6
7
8
9
10
n!
1
1
2
6
24
120
720
5040
40320
362880
3628800
n
11
12
13
14
15
16
17
18
19
...
69
n!
39916800
479001600
6227020800
10
8.7178291·10
12
1.3076744·10
13
2.092279·10
14
3.5568743·10
15
6.4023737·10
17
1.216451·10
...
98
1.7112245·10
I fattoriali della tabella precedente sono stati calcolati con una normale calcolatrice
scientifica, il che comporta due limitazioni:
- a partire da 14!, si perde in precisione; questa limitazione può essere evitata ad esempio
con un programma per computer capace di effettuare calcoli in multiprecisione
- è possibile calcolare, con l'ausilio della funzione predefinita x!, il fattoriale di un
numero x fino ad un valore di x uguale a 69 (la calcolatrice può fornire risultati fino
all'ordine di grandezza 1099); anche questa limitazione può essere evitata sia con un
opportuno programma per computer, sia utilizzando la formula approssimata di
Stirling:
n! = n n  e -n  2 pn
6 Cap. 1: Calcolo combinatorio
che fornisce un valore approssimato del fattoriale di un numero n per valori abbastanza
grandi di n.1
Anche per le permutazioni possiamo considerare la possibilità della ripetizione di tutti
gli elementi; in questi casi la formula (2) é ancora applicabile,sostituendo, al posto di k, n.
Esempio 8:
Disponendo di bandiere di cinque tipi differenti, quanti messaggi si possono
formare con queste bandiere, se possiamo avere anche la ripetizione delle stesse?
Abbiamo:
D'(5,5) = 55 = 3125.
Supponiamo ora di voler calcolare il numero delle permutazioni delle lettere contenute
nella parola LOLLO, parola in cui la lettera L é ripetuta 3 volte e la lettera O due volte. In casi
come questi, si parla di permutazioni con ripetizioni (nel nostro esempio, di 5 elementi di cui
uno presente 3 volte ed uno presente due volte). Per calcolare il numero di queste permutazioni
supponiamo, in un primo momento, che le lettere ripetute non siano uguali ma diverse e le
distingueremo con un indice (provvisorio!). Così, delle seguenti permutazioni:
L1L2L3O1O2
L1L2L3O2O1
L1L3L2O1O2
L1L3L2O2O1
L2L1L3O1O2
L2L1L3O2O1
L2L3L1O1O2
L2L3L1O2O1
L3L1L2O1O2
L3L1L2O2O1
L3L2L1O1O2
L3L2L1O2O1
(12 in tutto: 6x2 = 3!x2!, ottenute dalla permutazione delle tre L e delle due O) dobbiamo
prendere in considerazione solo una, in quanto gli indici sono solo fittizi. Quindi possiamo
calcolare le permutazioni delle lettere della parola LOLLO, calcolando prima le permutazioni
di tutte e cinque le lettere supposte diverse e dividendo il risultato per 12=3!x2!:
P(5,3,2) =
5!
120
=
= 10.
3!2!
12
Possiamo generalizzare il risultato e considerare il caso in cui vogliamo calcolare il numero delle permutazioni con ripetizione di n elementi, fra cui k1, k2, ..., kr sono uguali fra loro
(ma tali che k1  k 2 ... k r  n ) e scrivere che tale numero é uguale a:
1
L'applicazione della formula di Stirling comporta la conoscenza delle funzioni esponenziali e logaritmiche. Gli
studenti che non conoscono ancora queste funzioni possono applicarla successivamente per calcolare, ad esempio,
un valore approssimato di 150! e 2500!.
7
R. SANTORO: Elementi di calcolo delle probabilità
P(n, k1 , k 2 ,..., k r ) =
Esempio 9
n!
k1!k 2!... k r!
(4)
Vogliamo fare una ripartizione di 15 studenti in 3 classi: 5 nella classe A, 4 nella
classe B e 6 nella classe C. In quanti modi possiamo fare questa ripartizione?
Possiamo risolvere il problema proposto supponendo che la ripartizione sia già
fatta e che i 5 studenti della classe A siano paragonabili a cinque A ripetute, i 4
studenti della classe B siano paragonabili a quattro B ripetute ed infine che i 6
studenti della classe C siano paragonabili a 6 C ripetute. Quindi il numero
cercato é:
15!
P(15;5,4,6) 
 630630
5! 4! 6!
1.4 Combinazioni semplici
Supponiamo che una classe di 15 alunni debba mandare una delegazione di tre studenti
ad un certo congresso. In quanti modi diversi é possibile scegliere gli studenti della
delegazione? Il problema somiglia molto ad un problema di disposizioni semplici, solo che, in
questo caso, l'ordine con cui vengono scelti i 3 studenti non ha alcuna importanza. Allora se A,
B e C sono tre studenti scelti, le permutazioni semplici dei tre studenti conducono sempre alla
stessa scelta. Dunque dobbiamo calcolare le disposizioni semplici di 15 elementi presi 3 alla
volta e dividere il risultato per 3!; avremo quindi che il numero richiesto é:
15  14  13
= 455
3!
In casi come questi, in cui due raggruppamenti sono diversi soltanto se hanno almeno
un elemento diverso, si parla di combinazioni semplici di n elementi presi k alla volta: il cui
numero indicheremo con C(n,k) o con Ckn .
Da quanto visto sopra abbiamo facilmente che:
C(n, k ) =
D(n, k )
.
k!
Dunque, combinando la formula precedente con la (1'), avremo:
C ( n, k ) =
n!
k!(n - k )!
(5)
Esempio 10 Gioco del Lotto. Anche questo é un gioco molto popolare in Italia. In un urna ci
sono 90 palline numerate da 1 a 90. Vengono estratte, una dopo l'altra e senza
reimbussolamento, 5 palline. Si vince se si riesce ad indovinare, in una giocata
precedente l'estrazione, una coppia di numeri (ambo), una terna di numeri
8 Cap. 1: Calcolo combinatorio
(terno), una quaterna di numeri (quaterna), i 5 numeri (cinquina). Calcolare il
numero di ambi, terni, quaterne, cinquine possibili.
In tutti i casi si tratta di combinazioni semplici di 90 elementi presi 2, 3, 4 o 5
alla volta, rispettivamente. Quindi possiamo scrivere:
90!
n(ambi ) = C90
=
= 45  89 = 4005.
2
2!88!
n(terni ) = C90
=
3
90!
90  89  88
=
= 117480.
3!87!
6
n(quaterne) = C90
=
4
n(quintine) = C590 =
90!
90  89  88  87
=
= 2555190.
4!86!
24
90!
90  89  88  87  86
=
= 43949268.
5!85!
120
Come si vede dal calcolo precedente, se da una parte é relativamente semplice
realizzare un ambo, diventa sempre più difficile realizzare un terno, una
quaterna, una quintina (quasi 44 milioni di quintine possibili!).
Sarebbe interessante anche esaminare come lo Stato, gestore del gioco,
ricompensa (si fa per dire...) le eventuali vincite.
Esempio 11
Nella figura sottostante é rappresentato un reticolato formato da 36 quadrati;
ciascun vertice dei quadrati viene individuato da una coppia di numeri (che
potrebbero essere le coordinate cartesiane dei vertici stessi), da 0 a 9 in
orizzontale e da 0 a 4 in verticale. In quanti modi diversi si può andare,
seguendo i lati dei quadrati, dal punto (0,0) al punto (9,4)?
(0,4)
(9,4)
(0,0)
(9,0)
Possiamo rappresentare i diversi spostamenti usando il simbolo d per indicare
uno spostamento orizzontale verso destra, il simbolo a per indicare uno
spostamento verticale verso l'alto. Allora uno dei possibili itinerari
(rappresentato in figura) é:
dddaadddaddad.
9
R. SANTORO: Elementi di calcolo delle probabilità
Evidentemente bisogna percorrere, in orizzontale o in verticale, tredici cammini
unitari e possiamo scegliere 9 o 4 di questi cammini come é immediato rendersi
conto. Quindi avremo che il numero dei cammini richiesto é dato da:
13!
13  12  11  10
C9+4
= C13
=
= 2860,
9
9 =
9!3!
6
oppure da:
13!
C9+4
= C13
= 2860.
4
4 =
4!9!
Dall'esempio precedente abbiamo visto che:
13
13
C913  C13
 9  C4 .
Il risultato dell'esempio precedente é del tutto generale e può essere dimostrato in modo
diretto a partire dalla (5). Possiamo allora concludere che:
Ckn  Cnn k
(6)
.
1.5 Coefficienti binomiali e binomio di Newton
Tenendo conto delle convenzioni fatte sul fattoriale di un numero, possiamo facilmente
verificare che, fissato n e facendo variare k da k = 0 fino a k = n, abbiamo la seguente tabella
dei valori di Ckn per i primi 8 valori di n:
n\k
0
1
2
3
4
5
6
7
8
0
1
1
1
1
1
1
1
1
1
1
2
3
Ckn
4
1
2
3
4
5
6
7
8
1
3
6
10
15
21
28
1
4
10
20
35
56
1
5
15
35
70
5
6
7
8
1
6
21
56
1
7
28
1
8
1
La tabella precedente ci suggerisce alcune osservazioni:
a) Per ogni n: C0n  Cnn  1 .
b) Per ogni n: Ckn  Ckn1  Ckn11 ; questa circostanza é stata messa in evidenza nella tabella,
dove si può notare, ad esempio, che:
C(5,1)+C(5,2) = 5 + 10 = 15 = C(5+1,1+1) = C(6,2)
C(7,4)+C(7,5) = 35 + 21 = 56 = C(7+1,4+1) = C(8,5).
10 Cap. 1: Calcolo combinatorio
c) Se guardiamo i numeri di ogni riga, ci viene subito da pensare ai coefficienti numerici
dello sviluppo di (x + y)n (potenza n-esima di un binomio). Per esempio, lo sviluppo:
(x + y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4
ha i coefficienti numerici 1, 4, 6, 4 e 1, corrispondenti ai valori forniti dalla tabella
precedente per n = 4. Per questo motivo i numeri forniti dalla tabella precedente si
chiamano anche coefficienti binomiali e si indicano con
 n
 
 k
da leggere 'n su k' (senza alcuna relazione con la divisione!).
E' evidente che utilizzando il nuovo simbolo per i coefficienti binomiali, risulta:
 n
Ckn    .
 k
Utilizzando il nuovo simbolo, la potenza n-sima di un binomio si può esprimere
mediante la formula:
k =n n
 
(7)
( x + y) n =    x n - k y k
k =0  k 
formula che che usa anche un nuovo simbolo (, sigma maiuscolo, simbolo di sommatoria in
matematica, da leggere sommatoria per k uguale a 0 fino a k uguale a n di ...).
La (7) si chiama anche formula del binomio di Newton e la tabella precedente prende
il nome di triangolo di Tartaglia (i francesi la chiamano triangolo di Pascal).
Esempio 12: Calcoliamo lo sviluppo di  x  2 y  .
Utilizzando i coefficienti forniti dal triangolo di Tartaglia o la formula di
Newton abbiamo:
 x  2 y 6 =
6
 6
 6
 6
 6
=   x 6 • (-2 y) 0 +   x 5 • (-2 y) 1 +   x 4 • (-2 y) 2 +   x 3 • (-2 y) 3 +
 0
 1
 2
 3
 6
 6
 6
+   x 2 • (-2 y) 4 +   x 1 • (-2 y) 5 +   x 0 • (-2 y) 6 =
 4
 5
 6
= x 6  12 x 5 y  60x 4 y 2  160x 3 y 3  230x 2 y 4  192 xy 5  64 y 6 .
1.6 Diagrammi ad albero
A volte diventa difficile classificare un determinato problema combinatorio e quindi
applicare la formula delle disposizioni o quella delle combinazioni, semplici o ripetute. In
alcuni di questi casi (ma anche in altri di facile classificazione) risulta utile schematizzare il
11
R. SANTORO: Elementi di calcolo delle probabilità
problema con un diagramma ad albero (così chiamato a causa della sua struttura ramificata) per
enumerare tutti i possibili esiti di una serie di esperimenti, ciascuno dei quali può avere solo un
numero finito di esiti. Altre volte é anche necessario conoscere, oltre al numero, anche la lista
completa di tutti gli esiti possibili: pure in questi casi, un diagramma ad albero é di grande
aiuto.
Esempio 13
Lanciamo una moneta 3 volte. Quanti risultati diversi (successioni di testa e
croce) possiamo avere?
Osserviamo lo schema seguente, dove possiamo notare che per ognuno dei lanci
sono rappresentati i due risultati possibili: T (testa) e C (croce).
C
T
T
C
T
C
T
C T
C
T
C T
C
TTT
TTC
TCC
CTT
CTC
CCC
TCT
CCT
Dallo schema precedente non solo abbiamo la possibilità di contare tutti i
possibili esiti, 8, del nostro esperimento ripetuto tre volte, ma abbiamo anche
l'elenco completo degli esiti possibili, che sono quelli scritti alla fine di ciascun
ramo.
Esempio 14
Primo dado
Secondo
dado
Conf.razioni:
Lanciamo due dadi per studiare la somma dei risultati delle due facce 'vincenti'.
Vogliamo calcolare il numero delle configurazioni che generano un determinato
risultato della somma, dal 2 al 12.
1
2
3
4
5
6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 1 1 1 1 1
1 2 3 4 5 6
2 2 2 2 2 2
1 2 3 4 5 6
3 3 3 3 3 3
1 2 3 4 5 6
4 4 4 4 4 4
1 2 3 4 5 6
5 5 5 5 5 5
1 2 3 4 5 6
6 6 6 6 6 6
1 2 3 4 5 6
Dallo schema precedente (dove le configurazioni sono da leggere in verticale)
deduciamo facilmente i seguenti risultati per ciascuna somma possibile:
Somma
N. configurazioni
2
1
3
2
4
3
5
4
6
5
7
6
8
5
9 10 11 12
4 3 2 1
12 Cap. 1: Calcolo combinatorio
1.7 Problema risolto e sua generalizzazione
Supponiamo di voler disporre 3 oggetti in tre cassetti diversi. Vogliamo calcolare il
numero dei modi differenti in cui l’operazione puó essere effettuata.
La prima soluzione che viene in mente è quella di shematizzare tutte le possibili configurazioni e quindi contarle, come nello schema seguente (dove gli oggetti sono rappresentati da
piccole clessidre):
1

2

3

4

5

6







Dallo schema il conto è facile: ci sono 10
modi diversi di sistemare i tre oggetti nei tre
cassetti.
Peró la soluzione trovata è molto artigianale
e poco razionale e non siamo soddisfatti. In
pratica siamo nella stessa situazione del
paragrafo 1: supponendo che i numeri siano
molto piú grandi, una soluzione del genere
(mediante elencazione completa di tutti i casi
possibili) sarebbe semplicemente impensabile.
Razionalmente possiamo pensare agli oggetti
7

8


9


10

e alle separazioni dei cassetti () come ad
uniche entità (articoli). Se trascuriamo la
prima e l’ultima barretta verticale (poste
sempre nelle stesse posizioni), ci sono da
sistemare tre oggetti e due barrette verticali
(5 articoli). Ad esempio, per la configurazione 3, abbiamo: .
Dunque, il numero delle possibili configurazioni è uguale a:
 5
  = 10 (numero dei modi di scegliere due barrette fra 5 articoli), oppure
 2
 5
  =10 (numero dei modi di scegliere tre oggetti fra 5 articoli).
 3
Il risultato raggiunto puó essere generalizzato al caso di n oggetti da sistemare in k
cassetti diversi: abbiamo k + 1 barrette verticali per formare k cassetti, ma due di queste sono
sempre alle due estremità; allora in tutto abbiamo k + 1 - 2 = k - 1 barrette verticali e n oggetti.
Dunque il numero delle configurazioni possibili è uguale al numero di combinazioni di n + k - 1
elementi presi k - 1 alla volta, oppure al numero di combinazioni di n + k - 1 elementi presi n
alla volta:
 n  k  1  n  k  1

 
.
n 
 k 1  
R. SANTORO: Elementi di calcolo delle probabilità
13
1.8 Esercizi
1.
In quanti modi 8 persone possono sedersi su una panchina che ha 5 posti?
2.
Una comitiva di 7 uomini e 6 donne devono sedersi in fila in modo che gli uomini abbiano solo posti dispari. Quante sistemazioni diverse esistono?
3.
Quanti numeri di quattro cifre possono essere formati con le 10 cifre 0,1,2,...9 se:
a) si ammettono delle ripetizioni;
b) le ripetizioni non sono ammesse;
c) l'ultima cifra deve essere 2 e non si ammettono ripetizioni?
4.
Attorno ad un tavolo circolare vogliono sedersi 5 uomini e 5 donne. In quanti modi
diversi possono sedersi se:
a) non ci sono preferenze di alcun tipo;
b) se i due sessi devono alternarsi?
c) se, oltre a b), una coppia vuole restare unita?
5.
Si vogliono sistemare 15 libri, 5 rossi, 3 verdi e 7 gialli, su uno scaffale di una libreria. In
quanti modi diversi é possibile sistemarli se:
a) possono stare in un ordine qualunque;
b) i libri di uguale colore devono stare uno accanto all'altro;
c) un determinato libro rosso deve essere al primo posto e gli altri in un ordine
qualunque;
d) un determinato libro rosso deve essere al primo posto e gli altri dello stesso colore
l'uno accanto all'altro.
6.
Dimostrare la formula (1').
7.
Nel gioco del Totocalcio, alcuni giocatori, chiamati sistemisti, selezionano un certo numero di partite a cui dare un risultato fisso e lasciano variare in tutti i modi possibili tutti
gli altri risultati. Quante colonne bisogna giocare (per fare il '13') col sistema nel caso in
cui ci siano:
a) 4 risultati fissi;
b) 5 risultati fissi;
c) 4 risultati fissi e due con '1' oppure 'X'.
8.
9.
 n
 n 
Dimostrare, in modo diretto, la formula:   = 

 k
n - k
 n
 n 
 n + 1
Dimostrare la formula (detta di Stiefel):   + 
 = 
 (questa formula è
 k
 k + 1
 k + 1
alla base della formazione del triangolo di Tartaglia).
10.
Dimostrare la formula del calcolo di Ckn a partire dalla formula (4) del paragrafo 1.3.
11.
Gioco della tombola. Questo gioco, molto diffuso in Italia, consiste nell'estrazione di 90
palline numerate. Si partecipa al gioco con delle cartelle, sulle quali sono segnati 15 dei
14 Cap. 1: Calcolo combinatorio
90 numeri. Due cartelle si distinguono per almeno un numero diverso. Quante cartelle
diverse é possibile costruire?
12.
Con la formula del binomio di Newton, calcolare lo sviluppo delle seguenti potenze:
8
a)  x  y ;
b)  x  2 y ;
6
5
y

c)  3x -  .

2
13.
Senza effettuare lo sviluppo completo di  x  3 y , calcolare il coefficiente numerico del
15
termine x 8 y 7 dello sviluppo.
14.
Teorema del polinomio. Lo sviluppo di  x1  x2 ... xr  si ottiene sommando tutti i
termini del tipo:
n!
• x n1 x n2 ... x nr ,
n1!n2! ... nr!
n
con n1  n2 ... nr  n .
Dimostrare il teorema.
15.
Con l'ausilio del teorema del polinomio calcalare gli sviluppi di:
4
a)  x  y  z ;
b) 2 x  y  z ;
5
c)  x  y  z  t  .
5
16.
Calcolare il coefficiente numerico del termine x 4 y 5 z 7 , appartenente allo sviluppo di
 x  y  z16 , senza effettuarne lo sviluppo completo.
17.
18.
In quanti modi distinti si possono distribuire 8 mele tra quattro bambini? Ed in quanti se
ad ogni bambino deve toccare almeno una mela?
 n
 n
 n
Dimostrare che:   +   + ...   = 2 n - 1 .
 1
 2
 n
19.
Dimostrare che il cardinale dell'insieme delle parti di un insieme finito A (insieme di tutti
gli insiemi, compresi l'insieme vuoto e l'insieme A) é 2n, dove n é il cardinale di A.
20.
In quanti modi diversi un gruppo di 12 persone può essere suddiviso in:
a) due gruppi di 9 e 3 persone;
b) tre gruppi di 4, 5 e 3 persone;
c) quattro gruppi di 3, 2, 2 e 5 persone?
R. SANTORO: Elementi di calcolo delle probabilità
15
21.
Abbiamo n palline e k scatolette, con n > k. Dimostrare che il numero dei modi distinti in
cui si possono distribuire le palline nelle scatolette é uguale a Ckn11 se ogni scatoletta deve
avere almeno una pallina.
22.
Per il calcolo dei cofficienti binomiali é molto utile la relazione:
 n
n - k + 1  n 
•
  =

k
 k
 k - 1
che é una relazione ricorrente da dimostrare.
23.
 2n
2n • (2n - 1) • (2n - 3) • ... • 3 • 1
Dimostrare la relazione:   =
n!
 n
24.
E' data la parola LOLLOBRIGIDA.
a) Calcolare il numero di permutazioni distinte che si possono avere con le lettere della
parola data.
b) Calcolare il numero di permutazioni distinte che cominciano con la lettera D.
c) Calcolare il numero delle permutazioni distinte che terminano con una vocale.
d) Calcolare il numero delle permutazioni distinte che si ottengono permutando ai primi 5
posti le lettere L e O.
25.
Costruire il diagramma ad albero per le permutazioni semplici degli elementi dell’insieme
{1,2,3,4,5}.
26
Per una lotteria vengono venduti 10000 biglietti. Di questi 100 vincono un premio, gli
altri biglietti non vincono niente. Una persona compra 10 biglietti.
In quanti modi diversi questa persona puó vincere esattamente un premio?
16 Cap. 1: Calcolo combinatorio
Tavola riassuntiva sul calcolo combinatorio
Disposizioni semplici di
n elementi presi k alla
volta:
Dkn
Disposizioni con
ripetizioni di n elementi
Definizione
Calcolo
Raggruppamenti diversi di k elementi fra
gli n disponibili. Due raggruppamenti
sono diversi:

per la natura degli elementi

per l’ordine degli elementi
Dkn  n  (n  1)K (n  k  1) D35  5 4  3  60
Come sopra, solo che gli elementi
possono essere ripeturi da 2 a k volte.
D' nk  n k
D' 26  62  36
Disposizioni semplici di n elementi presi
Pn  n  (n  1)K 2  1  n!
P4  4! 
Dkn 
Esempi
n!
(n  k )!
n
presi k alla volta : D' k
Permutazioni semplici
di n elementi:
Pn
Permutazioni con
ripetizioni di n elementi
n alla volta:
Pn  Dnn
Permutazioni con ripetizioni di n
elementi di cui k1 sono uguali fra di loro,
k2 sono uguali fra di loro, ..., kr sono
uguali fra di loro (k1 + k2 + ... + kr = n)
 4  3 2 1 
n


n!
P

 k1 , k 2 ,K k r  k1 ! k 2 !K k r !
 24
0! = 1
 7 
P

 2,2,3
7!
 210
2 ! 2 ! 3!
5!
 n 5
Dn
n!
 10
Ckn  k 
   C3 
3! 2!
k ! k !(n  k )!  k 
C0n  Cnn  1
 n  n 
  

 k n  k

Combinazioni semplici
di n elementi presi k alla
volta:
Ckn
Raggruppamenti diversi di k elementi fra
gli n disponibili. Due raggruppamenti
sono diversi:

per la natura degli elementi
 n  1  n  n 

    

 k  1  k   k  1