Calcolo Combinatorio

CALCOLO COMBINATORIO

CONSIDERAZIONI: IL CALCOLO COMBINATORIO RIGUARDA LO STUDIO O LA RICERCA DI QUELLO CHE PUÒ SUCCEDERE QUANDO SI HANNO A DISPOSIZIONE DEGLI UN CERTO NUMERO DI OGGETTI, CHE CHIAMEREMO ELEMENTI, E IL LORO NUMERO m.

IN GENERALE CHIAMEREMO

1. I GLI OGGETTI -----> ELEMENTI
2. IL LORO NUMERO -----> m
3. IL LORO GRUPPO -----> CLASSE K

ESEMPIO:

SUPPONIAMO DI AVERE 20 LIBRI E LI PRENDIAMO A QUATTRO A QUATTRO

DOMANDA

QUANTI GRUPPI DI QUATTRO SI POSSONO FORMARE?

IN CONCLUSIONE PER DARE RISPOSTA A QUELLO CHE PUÒ ACCADERE CON m ELEMENTI BISOGNA STUDIARE:

1. LE DISPOSIZIONI SEMPLICI
2. LE DISPOSIZIONI CON RIPETIZIONE
3. LE PERMUTAZIONI SEMPLICI
4. LE PERMUTAZIONI CON RIPETIZIONE
5. LE COMBINAZIONI SEMPLICI
6. LE COMBINAZIONI CON RIPETIZIONE

DISPOSIZIONI SEMPLICI

Supponiamo di avere n oggetti distinti e supponiamo di prenderli a gruppi che chiameremo di classe k

con k ≤ n

Allora chiameremo disposizione semplice di classe k tutti i possibili gruppi che si possono formare con k degli n oggetti, considerando distinti i due gruppi che differiscono fra di loro:

1. Per l'ordine ABC e BCA
2. O per qualche elemento ABD

Risposta

Per calcolare le disposizioni semplici basta applicare la formula che proviene dal seguente teorema:

Teorema

Il numero delle disposizioni semplici di n oggetti di classe k è data dalla seguente formula:

D_n,k = n (n-1) (n-2) ... (n-k+1)

Esempio

Calcolare qual è la probabilità di vincere al totocalcio facendo 13 con una sola schedina, con tre schedine, con 100 schedine.

Risposta

Datir=3n=13k=13

D_r,13=3¹³=1.594.323

Quindi si hanno 1.594.323 di casi possibili.

Per calcolare la probabilità, intanto possiamo dire che nel caso della probabilità

P=^{n° dei casi favorevoli}/_{n° dei casi possibili}

Pertanto nel caso di:

1. Una sola schedinaP=¹/_1.594.323=0,00000063
2. Nel caso di 3 schedineP=³/_1.594.323Aumenta la probabilità di tre volte
3. Nel caso di 100 schedineP=¹⁰⁰/_1.594.323=0,000063
4. Nel caso di 1 milione di schedineP=^1.000.000/_1.594.323=0,63

COMBINAZIONI

C_n,k = ⁿC_k

DEFINIZIONE

1. Supponiamo di avere m elementi
2. Supponiamo di prenderli a gruppi di k (a k a k) con k < m

Allora chiameremo combinazione semplice di m elementi presi a k i tutti gruppi che si possono formare prendendo k di m elementi e considerandoli distinti soltanto quei gruppi che differiscono per la natura di qualche elemento ma non per l'ordine.

N.B. Le combinazioni semplici sono minori delle disposizioni.

FORMULE DELLE COMBINAZIONI SEMPLICI

1. C_n,k = ^D_k/_K!
2. C_n,k = ^{n(n-1)(n-2)...(n-k+1)}/_K!
3. C_n,k = ^n!/_K!(n-k)!

ALTRE FORMULE

1. C_n,k = ^n!/_K!(m+k)!
2. ^(n)_(k) = m!

Esercizio:

Dati 5 elementi di classe 3 calcolare:

1. Disposizioni semplici e con ripetizioni
2. Permutazioni semplici e con ripetizioni
3. Combinazioni semplici e con ripetizioni

DATI:

• m = 5
• k = 3

D_5,3 = 5⁴ · 3 = 60

1. D_5,3^R = 5³ = 125
2. P_m m!= 5! = 5 · 4 · 3 · 2 · 1 = 120

3. P^R_{m m1 m2 m3} = m! / (m₁! m₂! m₃!)

   = 5 · 4 · 3 · 2 · 1 / (3 · 2 · 1 · 1 · 1) = 120 / 6 = 20

4. C_5,3 = ⁵C₃ = D_5,3^R / 3!

   = 5 · 4 · 3 / 3 · 2 · 1 = 60 / 6 = 10

5. C_m,k^R = (m + k - 1)! / (k! (m - 1)!)

   = (7) / 3 = 7 · 6 · 5 / 3! = 35

CALCOLO COMBINATORIO - FORMULARIO

ESERCIZIO: QUANTI SONO I NUMERI PARI DI 6 CIFRE CONTENENTI DUE 5 CONSECUTIVI

RISPOSTA

DATI m = 10 k = 6

1. POICHÉ IL PROBLEMA PARLA DI CIFRE NON DISTINTE VUOL DIRE CHE SI POSSONO ANCHE RIPETERE QUINDI SI TRATTA DI DISPOSIZIONI CON RIPETIZIONE

D_n,k = 10⁶ = 1.000.000

2. DI QUESTE 1.000.000, DISPOSIZIONI META SONO PARI
3. PER CALCOLARE QUANTI FRA QUESTI GRUPPI PARI HANNO DUE 5 CONSECUTIVI A TALE SCOPO FACCIAMO LE SEGUENTI CONSIDERAZIONI:

• 5 5 × × × 0
• × 5 5 × × 0
• × × 5 5 × 0
• × × × 5 5 0
• 5 5 × × × 2
• × 5 5 × × 2
• × × 5 5 × 2
• × × × 5 5 2
• 5 5 × × × 4
• × 5 5 × × 4
• × × 5 5 × 4
• × × × 5 5 4
• 5 5 × × × 6
• × 5 5 × × 6
• × × 5 5 × 6
• × × × 5 5 6
• 5 5 × × × 8
• × 5 5 × × 8
• × × 5 5 × 8
• × × × 5 5 8

SONO CINQUE GRUPPI

RICORDARSI

ⁿ C_k = (n k) = n! / k!(n-k)!

(n+1)^m = ((n+1) n)^m

(n n) = 1

(n 0) = 1

(0 0) = 1

NB: C_n,k = (n k) = D(n,k) / k!

C_n,k = (n k) = n^' / k^'(n-k)^'!

LEGGE DEI TRE FATTORIALI

C_n,k = (n k) = n / (n-k)

LEGGE DELLE CLASSI COMPLEMENTARI

E.g.

(9 7) = (9 2)

(X 8) = (X 5) => X = 13

(n k) = (n-1 k) + (n-1 k-1)

FORMULA DI STIFE