Matematica Capitolo 3 - ivanzivko.chivanzivko.ch/onewebmedia/C3_Calcolo_Combinatorio.pdf · •I...

Matematica Calcolo Combinatorio

Docente: Ivan Zivko 1

Matematica Capitolo 3

Calcolo combinatorio

Ivan Zivko

INTRODUZIONE

• Nel calcolo combinatorio vengono sviluppate delle tecniche per determinare, senza enumerazione diretta, il numero dei possibili risultati di un esperimento, o il numero degli elementi di un insieme.

Matematica 2



INTRODUZIONE

• I padri del calcolo combinatorio e della probabilità possono essere considerati Blaise Pascal (1623-1662) e Pierre de Fermat (1601-1665).

Matematica 3

Esempio introduttivo• Le località A B C D sono collegate da diverse

strade come indicato:

• Un possibile percorso da A a D sarebbe “z2c”.

• Quanti diversi percorsi da A a D sarebbero possibili in totale?

Matematica 4

A B C D

z

x

y

1

2

a

b

c

d

e

N



PRINCIPIO MOLTIPLICATIVO FONDAMENTALE

• Se un esperimento viene eseguito in k fasi successive e quest’ultime si possono effettuare rispettivamente in n1, n2, …,nk modi differenti, allora l’esperimento può essere effettuato in

modi differenti.

Matematica 5

knnnn ....21

PRINCIPIO MOLTIPLICATIVO FONDAMENTALE

• Esempio: le targhe automobilistiche di un paese sono composte per i primi due simboli da lettere scelte tra le 21 dell’alfabeto e per gli altri tra le 10 cifre arabiche.

• Quante targhe di 7 simboli è possibile costruire?

Matematica 6

T I 4 0 3 3 9



DIAGRAMMI AD ALBERO

• Nel calcolo combinatorio si incontrano spesso problemi che possono essere capiti più facilmente con l’ausilio di diagrammi ad albero.

Matematica 7

DIAGRAMMI AD ALBERO

• Esempio: Marco e Claudio giocano a tennis, vince chi fa sue due partite consecutivamente o chi per primo vince tre partite. Il gioco prosegue fin quando uno dei due vince.

• Descrivere tutti i possibili esiti del gioco attraverso un diagramma ad albero.

Matematica 8



DIAGRAMMI AD ALBERO• Soluzione:

Matematica 9

DISPOSIZIONI CON RIPETIZIONE

• Definizione

• Si chiama disposizione con ripetizione di n elementi diversi a k a k( con k numero intero qualunque) ogni sequenza ordinata che si può formare con k degli n elementi, potendo uno stesso elemento figurare nella sequenza fino a k volte.

Matematica 10



DISPOSIZIONI CON RIPETIZIONE• Esempio:

Matematica 11

0 A

24 7 154

1 32

7 ELEMENTIPresi a 3 a 3


Matematica 12

0 A

24 7 154

1

323224




Matematica 13

0 A

24 7 154

1

32

32

24 32


• Teorema

• In ogni posizione potremo scegliere sempre tra tutti gli n elementi. Quindi dal principio moltiplicativo fondamentale segue:

knnnnnknD ....),(*

Matematica 14




• Esempio 2: quali terne di risultati (testa o croce) si possono ottenere lanciando tre volte una moneta?

Matematica 15

DISPOSIZIONI SEMPLICI

• Definizione

• Si chiama disposizione di n elementi diversi presi a k a k ogni sequenza ordinata che si può formare scegliendo k elementi fra gli n dati (k≤n).

Matematica 16




• Osservazione: il fattoriale di un numero n qualsiasi è definito come segue.

• Inoltre vale per definizione:

Matematica 17

123....)2()1(! nnnn

1!0

1!1

DISPOSIZIONI SEMPLICI• Esempio:

Matematica 18

0 A

24 7 154

1 32





Matematica 19

0 A

7 154 1 24 32


• Teorema

• Nella prima posizione potremo scegliere tra n elementi, nella seconda tra (n-1) elementi, nella terza tra (n-2).... Nella k-esima posizione potremo scegliere quindi tra (n-k+1) elementi.

Matematica 20




• Teorema

• Quindi, dal principio moltiplicativo fondamentale segue che:

)!(

!)1(....)2()1()(

kn

nknnnnn,kD

Matematica 21


• Esempio 2: Sia E un insieme con gli elementi E={a; b; c}. Le possibili disposizioni semplici di classe 2 di questi 3 elementi sono soltanto le seguenti:

.,,,,, cbcabcbaacab

Matematica 22




• Esempio 3: un bambino ha 6 cartoncini con disegnate su ognuno una lettera tra A, B, C, D, E, F. Può inserirli in una scacchiera, ma solo 3 alla volta. Quante „paraole“ diverse di 3 lettere può creare?

Matematica 23

PERMUTAZIONI SEMPLICI

• Definizione

• Si chiama permutazione di n elementi diversi ogni sequenza ordinata che si può formare usando tutti gli n elementi.

Matematica 24




• Osservazione

• Ogni permutazione contieni tutti gli n elementi, quindi differisce dalle altre sequenze solo per l‘ordine degli elementi.

Matematica 25


• Esempio:

Matematica 26

0 A

24 7 154

1 32





Matematica 27

0 A24 71541 32


0 241541 32


• Teorema

• Nella prima posizione potremo scegliere tra n elementi, nella seconda tra (n-1) elementi, nella terza tra (n-2).... Nella n-esima dovremo per forza mettere l‘ultimo elemento rimasto.

Matematica 28




• Teorema

• Quindi, dal principio moltiplicativo fondamentale segue che:

!12....)3()2()1()( nnnnnnP

Matematica 29


• Esempio 2: In quanti modi 7 persone si possono sedere su 7 sedie alineate?

Matematica 30



Permutazioni circolari

• Se l’allineamento degli n oggetti avviene su una circonferenza, avremo una permutazione circolare, il cui numero di possibilità si calcolerà come segue:

Matematica 31

!1)( nnPc

Permutazioni circolari• Esempio: in quanti modi 4 persone possono

prendere posto attorno ad un tavolo circolare?

Matematica 32



PERMUTAZIONI CON RIPETIZIONE

• Definizione

• Una permutazione di n elementi, di cui almeno due sono uguali, si dice permutazione con ripetizioni.

Matematica 33


Matematica 34

0 24

24 1 154

1 32





Matematica 35

0 2424 1 1541 32



• Anche se scambiamo di posto due elementi potremmo ottenere la stessa disposizione:

Matematica 36

0 2424 1 1541 32 0 2424 1 1541 32



PERMUTAZIONI CON RIPETIZIONI

• Teorema

• Il numero di permutazioni di n elementi di cui k1

sono uguali, k2 sono uguali,..., kn sono uguali è:

!!...!

!

21

,...,, 21

n

kkk

nkkk

nP n

Matematica 37

PERMUTAZIONI CON RIPETIZIONI• Esempio 2: Consideriamo la parola TROTTO. Quanti

anagrammi diversi potremmo creare scambiando tra di loro queste 6 lettere?

Matematica 38



COMBINAZIONI SEMPLICI

• Definizione

• Si chiama combinazione di n elementi diversi presi a k a k ogni insieme che si può formare scegliendo k elementi fra gli n dati (k≤n).

Matematica 39


• Osservazione

• L‘ordine degli elementi non ha nessuna importanza!!

• Due combinazioni sono diverse quando differiscono per almeno un elemento.

Matematica 40



COMBINAZIONI SEMPLICI• Esempio:

Matematica 41

0 A

24 7 154

1 32



Matematica 42

7 0 A 7 0A

!




• Esempio 2: dobbiamo scegliere due lettere tra A, B e C. Se non conta l’ordine con cui si scelgono, quante possibilità abbiamo?

Matematica 43


• Teorema

• Le combinazioni semplici equivalgono alle disposizioni semplici togliendo però le varie permutazioni di ogni sequenza, in questo modo l‘ordine degli elementi non avrà più importanza.

Matematica 44




• Teorema

)!(!

!

)(

),(),(

knk

n

kP

knDknC

Matematica 45


• Osservazione

• Spesso si scrive:

• Ogni combinazione di n elementi a k a k determina automaticamente una combinazione „complementare“ di questi n elementi a n-k.

k

nknC ),(

Matematica 46



COMBINAZIONI CON RIPETIZIONI

• Definizione

• Si chiama combinazione con ripetizioni di n elementi diversi presi a k a k ogni insieme che si può formare scegliendo k elementi fra gli n dati, potendo uno stesso elemento figurare nella sequenza fino a k volte.

Matematica 47


• Osservazione

• Due combinazioni sono diverse quando differisce qualche elemento o il numero delle volte che un elemento compare.

Matematica 48




Matematica 49

0 A

24 7 154

1 32


7

A


Matematica 50

7 0 7 0

!

77




• Teorema

)!1(!

)!1(1),(*

nk

kn

k

knknC

Matematica 51


• Esempio 2: elenchiamo le combinazioni con ripetizione delle 3 lettere A, B e C prese a 2 a 2.

Matematica 52

Matematica Capitolo 3 - ivanzivko.chivanzivko.ch/onewebmedia/C3_Calcolo_Combinatorio.pdf · •I...

Documents

Transcript of Matematica Capitolo 3 - ivanzivko.chivanzivko.ch/onewebmedia/C3_Calcolo_Combinatorio.pdf · •I...