MOLTIPLICAZIONE COMBINATORIA
Con esempi e problemi
1
2
3
a
a1
a2
a3
b
b1
b2
b3
AUTORE
ADRIANA LANZA
Liceo scientifico “Cavour”
Unconcetto molto semplice
ma fondamentale per
comprendere i metodi del
Calcolo combinatorio è
Il concetto di
MOLTIPLICAZIONE
COMBINATORIA
di due insiemi di cardinalità
m ed n , rispettivamente
CARDINALITA’ DI UN INSIEME
• Ricordiamo in proposito
che si chiama cardinalità
di un insieme finito il
numero dei suoi elementi
• L’insieme dei piccoli e
vivaci animali,
rappresentati a lato, ha
cardinalità 4
• L’insieme di queste
altre bestioline”
più tranquille” ha
invece cardinalità 3
Siano A e B due insiemi aventi
rispettivamente n ed m elementi
Il numero delle coppie ordinate che si
possono formare con un elemento di A ed un
elemento di B sono
n*m
ESEMPIO
• Proviamo ad associare un
animale del secondo
gruppo con un
componente del primo.
• Pensiamo per esempio al
gufo che legge
tranquillamente il suo
libro
Quale ,tra i chiassosi amici, verrà a
disturbarlo?
4
3
2
1
Si ottengono pertanto 4 possibili
accoppiamenti
• Il ragionamento si può
ripetere a partire dal
gatto addormentato
O dal silenzioso
pesciolino
Complessivamente i possibili accoppiamenti sono
3*4 =12
Un modello più generale si ottiene mediante
il
DIAGRAMMA AD ALBERO
Gufo
Agnellino
Micino
Gatto
Galletto
Pulcino
Agnellino
Micino
Pesce
Agnellino
Micino
Galletto
Pulcino
Galletto
Pulcino
GENERALIZZANDO
Siano A1 A2 A3 A4 ...................Ak
k insiemi contenenti rispettivamente n1 n2 n3 n4...nk
elementi ,
il numero delle kappuple ordinate che
si possono formare scegliendo un elemento da ciascun insieme
sono n1 n2 n3 n4...nk
Per costruire l’albero dei possibili percorsi basta procedere come
nell’esempio precedente:
si sceglie uno degli n1 elementi di A1e lo si collega con gli n2 elementi di
A2
da ciascuno di essi si fanno si fanno partire altri n3 rami collegati con
gli n3 elementi di A3 ... e così via.
Diagramma ad albero ottenuto a partire dal
primo elemento di A1:
i possibili percorsi sono n2*n3
a1
b2
b1
c1
c2
c3
c1
c2
b3
c3
c1
c2
b4
c3
c1
c2
c3
Poiché si possono costruire n1 alberi, in corrispondenza
di ciascun elemento di A1, si hanno complessivamente
n1*n2*n3 scelte possibili
L’operazione così definita prende il
nome di
Moltiplicazione
combinatoria
Calcolo combinatorio
problemi
• Il metodo della Moltiplicazione combinatoria
permette di risolvere i problemi classici di
Calcolo combinatorio e determinare le formule
delle principali funzioni:
• Disposizioni semplici
• Disposizioni con ripetizione
• Permutazioni semplici
• Permutazioni con elementi ripetuti
• Combinazioni semplici
• Combinazioni con ripetizione
DISPOSIZIONI
• Consideriamo ora un solo insieme di n
elementi e vediamo in quanti modi si può
da esso estrarre un gruppo di k elementi
( kappupla ) disponendoli secondo l’ordine
di estrazione
Chiamiamo Disposizioni di n oggetti a k a k
il numero che determina in quanti modi si possono scegliere k elementi in un insieme
di cardinalità n, considerando distinti due gruppi che differiscano almeno per un
elemento o per l’ordine di scelta
Si parla di disposizioni semplici (D n,k) se ciascun elemento può
essere scelto una sola volta
Si parla di disposizioni con ripetizione (Dr n,k) se ciascun elemento
può essere scelto più di una volta
Si devono disporre ,in ordine, k degli elementi di un insieme
di cardinalità n.
• 1) Si sceglie il primo elemento: la scelta può essere fatta in n modi
diversi
• 2) Si sceglie il secondo elemento: la scelta può essere fatta in n-1 modi
diversi, poiché l’elemento scelto non può essere ripetuto
• 3) Si sceglie il terzo elemento: la scelta può essere fatta in n-2 modi
diversi
• ................................................................................................................
......
• ................................................................................................................
.......
• k) Si sceglie il k-esimo elemento: la scelta può essere fatta in n-(k-1) = nk+1 modi diversi.
Come si può osservare , ogni scelta modifica l’insieme di partenza,
pertanto il problema è analogo a quello della formazione di un
gruppo di k elementi scegliendo un elemento da ciascuno dei k
insiemi a disposizione.
Con il metodo della Moltiplicazione Combinatoria si trova
pertanto che il numero delle disposizioni semplici di n oggetti a k
a k sono
D n,k = n(n-1)(n-2)....(n-k+1)
←Calcolo combinatorio
DISPOSIZIONI CON RIPETIZIONE
Supponiamo di dover formare un gruppo di k elementi scelti in
un insieme di cardinalià n, potendo ripetere più volte lo stesso
elemento. Due gruppi sono diversi se differiscono per qualche
elemento o anche per l’ordine.
Ripetendo un ragionamento analogo a quello fatto per le
disposizioni semplici, si osserva che
il primo elemento può essere scelto in n modi diversi
il secondo elemento può essere scelto ancora in n modi diversi
così tutti gli altri k-2 elementi
Pertanto
D
r
n,k
= n*n*n*n...n
=n
k
←Calcolo combinatorio
Permutazioni
• Come caso particolare di Disposizioni semplici si
consideri il caso k=n:
• In questo caso i gruppi da formare sono costituiti
sempre da tutti gli elementi dell’insieme, posti però
in ordine diverso.
•
Si parla in questo caso di permutazioni di classe n
La formula delle
PERMUTAZIONI SEMPLICI si ottiene
come caso particolare
delle DISPOSIZIONI→Pn=Dn,n
Pn = n(n-1)(n-2)...3*2*1 = n!
←Calcolo combinatorio
PERMUTAZIONI CON ELEMENTI
RIPETUTI
Consideriamo n elementi non tutti distinti, tra cui siano presenti per
esempio h elementi uguali.
Fra le n! permutazioni, quelle che permutano tra di loro gli elementi
uguali, lasciando inalterati gli altri, non sono tra di loro distinguibili
Poiché queste ultime sono in numero di h!, il numero totale va diviso
per h!.
In generale, se sono presenti h1,h2,h3...hi elementi tra di loro uguali, il
numero di permutazioni è
n!
h1 !h2 !h3 !...hk !
←Calcolo combinatorio
COMBINAZIONI SEMPLICI
Si vogliono formare gruppi di k elementi
scelti in n insieme di cardinalità N. I gruppi
sono distinti solo se differiscono per qualche
elemento.
A differenza del caso delle disposizioni, i
gruppi che differiscono solo per l’ordine e in
cui compaiono gli stessi elementi vanno
considerati come un unico gruppo.
Pertanto il numero delle Combinazioni di N
oggetti a k a k è uguale al rapporto tra le
analoghe Disposizioni e le permutazioni di
classe k
Cn,k = Dn,k/ k! =
.
n(n  1)( n  2)...( n  k  1)
k!
n!
k!(n  k )!
come si può facilmente
dimostrare
Le combinazione si indicano anche
n
con il simbolo
 
k 
←Calcolo combinatorio
COMBINAZIONI CON RIPETIZIONE
• Ci limitiamo a dare la formula delle
• C r n,k verificandone la validità con un
esempio.
C r n,k = C n+k-1,k
←Calcolo combinatorio
Il metodo della moltiplicazione
combinatoria
Può essere applicato anche nel caso in
cui il gruppo debba essere formato
scegliendo più elementi da ciascun
insieme
Se , per esempio, si devono scegliere n
elementi dall’insieme A e k elementi
dall’insieme B
Basta sostituire ad A l’insieme delle n-ple che si possono formare nel
suo interno
e a B l’insieme delle rispettive
k-ple!
ESEMPI
Gruppo formato con elementi di due insiemi
Con scelta multipla all’interno di ciascun insieme
Disposizioni
Permutazioni
•semplici
•Con ripetizione
•semplici
•Con elementi ripetuti
• Combinazioni semplici
• Combinazioni con ripetizione
ESEMPIO N.1
Se , tornando all’esempio iniziale, supponiamo che
uno degli animali <<tranquilli>> sia disturbato da
due amici per volta
si deve associare un elemento del primo insieme con una
coppia di elementi del secondo insieme
Si ottengono C3,1*C4,2=3*6 =18
situazioni possibili
<=esempi
ESEMPIO N 2
ESEMPIO N 3
Disposizioni
• In un Circolo di 100 soci devono
essere eletti un Presidente ed un
Segretario.
• Le due cariche sono incompatibili
• Se tutti i soci sono candidati,
quante sono le possibili scelte?
• Risposta
D 100,2 = 100*99
• ( l'ordine in cui vengono estratti i
due nominativi è significativo)
•
• Con riferimento all’esempio
precedente, supponiamo che le
cariche siano compatibili.
• In questo caso lo stesso
individuo può essere scelto due
volte
• Risposta : Dr 100, 2=1002
<=esempi
ESEMPIO N. 3
Anagramma
( parole con lettere distinte)
Quanti sono i possibili anagrammi
della parola Roma?
Risposta 4! = 4.3.2.1 = 24
ESEMPIO N.4
• Anagramma
• (parole con lettere ripetute)
• Quanti sono i possibili anagrammi
della parola <<mamma>> ?
• Risposta 10
•
5!
3!2!
<=esempi
ESEMPIO N 5- Combinazioni semplici
In quanti modi si possono
eleggere i 2
rappresentanti di classe in
una classe di 15 alunni?
Risposta : C 15, 2= 15*14/2
l'ordine in cui vengono
estratti i due nominativi
non è significativo
<=esempi
ESEMPIO N 6- Combinazioni con ripetizione
Consideriamo un insieme di 4 oggetti
[ A ,B , C , D] e costruiamo tutti i possibili gruppi di tre elementi, non necessariamente
distinti
•C r
4,3
= C 6,3 = 20
SPIEGAZIONE
3 elementi uguali => C 4,1 = 4
[A,A,A] [B,B,B] [C,C,C] [D,D,D]
2 elementi uguali => C 4,1*C 3,1 =12
[A,A,B] [B,B,A] [C,C,A] [D,D,A]
[A,A,C] [B,B,C] [C,C,B] [D,D,B]
[A,A,D] [B,B,D] [C,C,D] [D,D,C]
3 elementi distinti => C 4,3
[A,B,C] [ B,C,D] [A,C,D] [A,B,D]
In tutto 4+ 12+ 4 = 20 casi
<=esempi
PROBLEMI
Da risolvere solo col metodo
Della
MOLTIPLICAZIONE COMBINATORIA
ELENCO-PROBLEMI
1. Numeri
2. Menù semplice
3. Menù complesso
4. Concerto
5. Percorsi
6. Regali
7. Schedina
8. Ballerini
9. Urna
10.Poker
PROBLEMA N1
NUMERI
QUANTI SONO I NUMERI DI 4 CIFRE
CHE TERMINANO CON LA CIFRA 2?
SOLUZIONE
SOLUZIONE (Numeri)
• La prima cifra va scelta in un insieme di 9 elementi
• La seconda cifra va scelta in un insieme di 10
elementi
• La seconda cifra va scelta in un insieme di 10
elementi
• La seconda cifra va scelta in un insieme di 1 solo
elemento
Risultato : 9*10*10*1=900
PROBLEMI
PROBLEMA N.2
Menù semplice
Quanti tipi di pranzo(1 antipasto, 1 primo, 1 secondo, 1
contorno,1 dessert) si possono organizzare con 3 antipasti, 2
primi, 4 secondi, 4 dessert?
Risposta 3*2*4*4 = 96
PROBLEMI
PROBLEMA N.3
Menù complesso
In quanti modi si può scegliere un pranzo formato da un
antipasto, due primi, tre secondi, 2 dessert
scegliendo da un Menù
Comprendente
•
•
•
•
3 antipasti
5 primi
8 secondi
4 dessert
SOLUZIONE
SOLUZIONE-Menù complesso
•
•
•
•
•
L’antipasto si può scegliere in un solo modo
i primi in C5,2 modi
i secondi in C8,3 modi
i dessert in C4,2 modi
Con il metodo della Moltiplicazione Combinatoria si
trova in totale
• C 5,2 * C8,3 * C4,2 = 10* 56*6 = 3360
•
PROBLEMI
PROBLEMA N.4
CONCERTO
Fra 10 violinisti, 5 suonatori
di viola e 5 di violoncello
si deve formare un sestetto
composto da
2 violini, 3 viole e 1 violoncello.
In quanti modi ciò è
possibile?
SOLUZIONE:
C 10,2 *C 5,3*C 5,1
PROBLEMI
PROBLEMA N.5
PERCORSI
• La figura seguente rappresenta la mappa dei
collegamenti di 4 città
A
B
D
C
a. In quanti modi si può andare da A a D passando per B e C?
b. Quanti percorsi ABCDCBA sono possibili?
c. Una persona compie il circuito ABCDCBA:
in quanti modi può farlo non ripassando mai sulle strade imboccate nell’andare da
A a D?
SOLUZIONE
SOLUZIONE-Percorsi
a. 2*3*4 = 24
b. (2*3*4) 2 =576
c. 2*3*4*3*2*1 = 144
indietro
PROBLEMI
PROBLEMA N.6
REGALI
In quanti modi si possono assegnare 2 regali a 3 bambini, se ciascun
bambino può avere più di un oggetto?
Soluzione
Il primo regalo può essere assegnato in 3 modi diversi
Il secondo regalo può essere assegnato in 3 modi diversi
•
Risposta
3*3=9
PROBLEMI
PROBLEMA N.7
Schedina
• Quante sono le possibili colonne della
schedina del totocalcio?
• risposta 3*3*3*3……….*3 13 volte = 3 13
indietro
PROBLEMI
PROBLEMA N.8
Ballerini
• In una piccola scuola di ballo
sono presenti 10 ballerini e 10
ballerine
•
A)In quanti modi si possono
costituire le coppie danzanti
( con ballerini di sesso diverso)?
B)In quanti modi si può scegliere
una coppia per rappresentare
la scuola in una gara di
<<liscio>>?
SOLUZIONE
SOLUZIONE-Ballerini
A) 10!
Si immaginino le 10 ballerine ferme
e i 10 ballerini-cavalieri dirigersi verso di loro per scegliere
la dama
Il primo sceglie tra 10, il secondo tra 9 etc. etc.
L’ultimo avrà la <<scelta obbligata>> dell’ultima dama
rimasta
In effetti le varie configurazioni corrispondono ad un
scambio di posto ( ballerina) dei 10 ballerini
→Permutazioni
B) 10*10 = 100
PROBLEMI
PROBLEMA N.9
URNA
Un’urna contiene 10 palline di cui 5 bianche
e 5 nere.
Si estraggono in blocco (senza reimmissione) 4
palline
Quante sono le possibili quaterne che
contengono esattamente 3 palline bianche e
una nera?
SOLUZIONE
SOLUZIONE-urna
La pallina nera può essere scelta in 5 modi
diversi
Le 3 palline bianche possono essere scelte in
C5,3 modi diversi
Risposta 3* C5,3=30
PROBLEMI
PROBLEMA N.10
POKER
Si gioca a Poker con un mazzo di 32 carte, assegnando 5 carte a ciascun giocatore.
In quanti modi si può avere un Poker <<servito>>?
SOLUZIONE
Le 4 carte uguali possono essere scelte in 8 modi diversi
La carta diversa può essere scelta in 28 modi diversi
Risposta: 8*28=224
PROBLEMI