Calcolo Combinatorio

Disposizioni e permutazioni

Sia A= { a,b,c,d}.

Tutte le sigle di due elementi che si possono formare con gli elementi di A sono:

aa ab ac ad

ba bb bc bd

ca cb cc cd

da db dc dd

4X4=16 sigle di due elementi (disposizioni di classe 2 di 4 elementi)

Tutte le sigle di 3 elementi che si possono formare con gli elementi di A sono

aaa aab aac aad

aba abb abc abd

aca acb acc acd

ada adb adc add

baa bab bac bad

………………….

dda ddb ddc ddd

4X4X4=64 sigle di tre elementi (disposizioni di classe 3 di 4 elementi)

Sia B={1,2,3}Tutte le sigle di 3 elementi che si possono formare con gli elementi di B sono

111 112 113

121 122 123

131 132 133

211 212 213

221 222 223

231 232 233

311 312 313

321 322 323

331 332 333

3x3x3=27 sigle (disposizioni di classe 3 di 3 elementi)

Definizione generale di disposizione di classe r di n elementi

Sia S un insieme finito di n elementi, cioè

S={a1, a2,…, an} .

Si dice disposizione di classe r (o a r a r) estratta da S (di n elementi), una qualunque r-pla ordinata del tipo

(ak1, ak2,…, akr), k1,k2,…,kr{1,2,…,n}

di elementi non necessariamente distinti di S.

Due qualunque di tali r-ple sono diverse non solo quando c’è almeno un elemento che è presente in una e non nell’altra, ma anche se, essendo le due r-ple costituite dai medesimi elementi, è però diverso l’ordine secondo cui essi sono disposti.

Il numero delle disposizioni di classe r di un insieme di n elementi è uguale a

D(n,r)=nr.Dim: Per formare una di queste disposizioni, ciascuno degli

r elementi si possono scegliere in n modi diversi.Ogni scelta si può associare con una qualsiasi delle

rimanenti r-1 scelte, e così via. Perciò si hanno in tutto n.n. … .n= nr

modi diversi per costruire tali disposizioni.

Esempio Calcolare:

a) in quanti modi si possono presentare le facce di due dadi e quante sono le coppie formate da due numeri dispari,

b) in quanti modi si possono presentare le facce di tre dadi e quante sono le terne formate da tre numeri dispari.

Sol:

a) A={1,2,3,4,5,6} D(6,2)=62=36

B= {1,3,5} D(3,2)= 32=9

b) A={1,2,3,4,5,6} D(6,3)=63=216

B= {1,3,5} D(3,3)= 33=27

EsempioUna colonna della schedina del Totocalcio è una disposizione di classe 13 estratta da S={1,x,2}.Quindi D(3,13)=313.

Esempio

Si devono disporre r palline in n scatole distinte in tutti i modi possibili.

Per ognuna delle r palline può essere scelta una qualunque delle n scatole disponibili, e quindi il numero di tutte le possibili distribuzioni delle palline nelle scatole coincide con il numero delle disposizioni di classe r di n elementi, cioè è uguale a nr.

Consideriamo ora una particolare disposizione di classe r di n elementi, con la condizione che i suoi elementi siano tutti distinti.In questo caso si parla di disposizione semplice di classe r di n elementi e si deve richiedere che rn.

Ad esempio, (a,b,c) è una disposizione semplice di classe 3 estratta da S={a,b,c,d,e,f} (di 6 elementi), mentre (a,a,b) non è una disposizione semplice.

Il numero delle disposizioni semplici di classe r di n elementi (con rn) è uguale a

D’(n,r)=n(n-1)(n-2) … (n-r+1).

Dim: Nel formare una di queste disposizioni si può scegliere in n modi diversi il primo degli r elementi che la

compongono.Per la scelta del secondo elemento, non è più possibile

scegliere quello posto al primo posto, e quindi si hanno solo n-1 possibilità.

Così proseguendo, per la scelta dell’r-esimo elemento si hanno ancora n-(r-1) possibilità, e perciò si hanno

complessivamente

n(n-1)(n-2) … (n-r+1)

disposizioni semplici di classe r di n elementi.

Esempio Quanti numeri di 5 cifre, non ripetute, si possono formare con le 10 cifre del sistema di numerazione decimale?

Sol:

A={0,1,2,3,4,5,6,7,8,9}

9XD’(9,4)=9.(9.8.7.6)=27.216

Esempio Nel consiglio di amministrazione di una società formata da 10 membri si deve procedere alla elezione di 1 presidente, di 1 vicepresidente e di 1 segretario. In quanti modi è possibile la scelta?

Sol.:

D’(10,3)=10.9.8=720

EsempioIl numero di modi in cui si possono disporre r palline in n scatole (numerate da 1 a n), in modo che ogni scatola contenga al più una pallina, è uguale al numero delle disposizioni semplici di classe r di n elementi, cioè uguale a

n(n-1)(n-2) … (n-r+1).

Dato un insieme S di n elementi, una disposizione semplice di classe n estratta da S si dice permutazione di n elementi.

Il numero delle permutazioni di n elementi è quindi uguale a

n(n-1)(n-2)…2.1=n!

(n! n fattoriale)

Osserviamo che per ogni numero naturale n2 si han!=n(n-1)!

e quindi, per dare significato a questa formula anche per n=1, si pone 0!=1

(significa che c’è una sola permutazione dell’insieme vuoto).

Esempio

Sia S={1,2,3} (n=3). Le permutazioni degli elementi di S sono:

123 213 231 321 312 132 ovvero 3!=3.2.1=6

Esempio Calcolare quanti numeri di 5 cifre distinti si possono calcolare con le cifre 1,2,5,7,9.

Sol.: P5=5!=5.4.3.2.1=120

Esempio In quanti modi si possono sistemare in una libreria 10 libri di cui 6 di letteratura italiana e 4 di matematica, in un ordine qualsiasi? E se si volessero sistemarli in modo che tutti i libri di una stessa materia siano vicini?

Sol.: P10=10!=10.9.8.7.6.5.4.3.2.1

P6=6!, P4=4! 2.6!.4!

Esempio

Una parola di lunghezza r è una qualsiasi successione ordinata di lettere dell’alfabeto.

Se l’alfabeto ha n lettere, il numero di parole di r lettere è uguale a nr.

In particolare, quelle senza lettere ripetute (r=8, “studiare”) sono in tutto n(n-1)(n-2) … (n-r+1).

Gli anagrammi di parole con n lettere distinte (n=4, “rima”, “rami”, “mari”) sono particolari permutazioni e quindi al più n!.

Osserviamo che il numero delle disposizioni semplici di classe r di n elementi, si può scrivere anche sotto questa

forma

n(n-1)(n-2) … (n-r+1)=[n(n-1)…(n-r+1)(n-r)!]/(n-r)!=n!/(n-r)!

Esempio

Nel gioco del lotto da un’urna contenente 90 palline numerate da 1 a 90 vengono estratte una dopo l’altra 5 palline. A quante possibili sequenze ordinate può dare luogo l’estrazione?

Sol.: Ogni sequenza ordinata corrisponde ad una disposizione semplice di classe 5 di 90 elementi e quindi

90.89.88.87.86=90!/(90-5)!.

Esempio

Nelle gare di discesa libera l’ordine di partenza dei 15 migliori sciatori viene determinato per sorteggio. Quanti sono i possibili ordini di partenza?

Sol.: Ciascun ordine di partenza corrisponde ad una permutazione dei 15 sciatori. Pertanto il numero dei possibili ordini di partenza è 15!.

Combinazioni

Dato un insieme S ={a1, a2,…, an} formato da n elementi, abbiamo considerato gruppi ordinati di elementi estratti da S (disposizioni, disposizioni semplici, permutazioni).

Sia ora

{a1, a2,…, ar}S

un gruppo non ordinato di r elementi, tutti distinti di S (rn).

Un tale gruppo prende il nome di combinazione di classe r estratta da S (oppure di n elementi).

EsempioSia S={1,2,3,4,5}. Le combinazioni di classe 2 dei 5 elementi dati sono le seguenti{1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5}.

Il numero delle combinazioni di classe r di n elementi è uguale a

C(n,r)=n(n-1)(n-2). … . (n-r+1)/r!=n!/(n-r)!r! .

Dim: Ciascuna di esse rappresenta una particolare disposizione semplice di classe r di n elementi.

Considerando tutte le sue permutazioni si ottengono ancora delle disposizioni semplici di classe r di n elementi (esattamente r!) formate dagli stessi elementi.

Questo significa che ad ogni combinazione di classe r di n elementi corrispondono r! (diverse) disposizioni semplici di classe r di n elementi, e quindi il numero delle disposizioni semplici di classe r di n elementi si ottiene dal numero incognito delle combinazioni di classe r di n elementi moltiplicato per r!.

Esempio Calcolare quante cinquine si possono estrarre da un’urna che contiene 90 palline numerate da 1 a 90?

Sol.: C(90,5)=90!/5!(90-5)!=90.89.88.87.86/120

Esempio In un’azienda vi sono 10 impiegati e 25 operai. Si vuole formare un comitato composto da 2 impiegati e 4 operai. In quanti modi si può formare il comitato?

Sol.: C(10,2)=10!/2!(10-2)! modi di scegliere 2 impiegati su 10

C(25,4)=25!/4!(25-4)! modi di scegliere 4 operai su 25

C(10,2)X C(25,4)

Esempio

Il numero delle possibili distribuzioni di r palline in n scatole in modo che ogni scatola contenga al più una pallina, ma non considerando diverse fra loro quelle distribuzioni che utilizzano le stesse r scatole (cioè l’ordine delle scatole non conta) è uguale ad n!/r!(n-r)!.