COMBINATORIO

ELEMENTI DI CALCOLO COMBINATORIO

Start

Prof. Laura Garozzo

indICE

Permutazioni

Disposizioni

Premessa

Schema riassuntivo

Esercizi svolti

Combinazioni

Coefficiente binomiale

Binomio di Newton

Fattoriale

Premessa

Il calcolo combinatorio fornisce gli strumenti di calcolo per determinare il numero di raggruppamenti diversi che si possono formare con un numero k di oggetti presi da un insieme contenenti n oggetti, o elementi, a1 ,a2 ,a3 ,a4 , … an-1, an

TIPI DI RAGGRUPPAMENTI

DISPOSIZIONI: quando l’ordine dei k elementi è importante. PERMUTAZIONI: casi particolari di disposizioni (k = n) COMBINAZIONI: quando l’ordine degli elementi non ha alcuna importanza.

I Raggruppamenti possono essere:

SEMPLICI: quando gli oggetti sono tutti diversiCON RIPETIZIONE: quando gli oggetti vi figurano una o più volte

DISPOSIZIONI

DISPOSIZIONI SEMPLICI

Si chiamano Disposizioni semplici di classe k i raggruppamenti composti da k elementi che si possono formare a partire da un insieme di n elementi, dove tali raggruppamenti differiscono tra loro o per la loro natura o per l’ordine. ( k <=n )

Il numero di DISPOSIZIONI SEMPLICI di n oggetti distinti presi k per volta è dove n! è il fattoriale del numero n.

Fattoriale

DISPOSIZIONI SEMPLICI - ESEMPIO

DATE LE 4 LETTERE A,B,C,D QUANTI SONO I GRUPPI DI DUE LETTERE CHE DIFFERISCONO TRA LORO PER ORDINE O NATURA?

AB AC AD

BA BC BD

CA CB CD

DA DB DC

B C D

A C D

A B D

A B C

Il n° di disposizioni semplici di 4 oggetti distinti presi a 2 a 2 è: D4,2 = 4!/(4-2)! = 4!/2!= 4‧3 = 12

VideoEsercizio

VideoEsercizio

DISPOSIZIONI CON RIPETIZIONE

Il numero di DISPOSIZIONI CON RIPETIZIONE di n oggetti distinti presi k per volta è

e non è necessariamente n > k

DISPOSIZIONI CON RIPET. - ESEMPIO

DATE LE 4 LETTERE A,B,C,D QUANTI SONO I GRUPPI di DUE LETTERE CHE DIFFERISCONO TRA LORO PER ORDINE O NATURA CON RIPETIZIONE?

Il n° di disposizioni con ripetizione di 4 oggetti distinti presi a 2 a 2 è: D’4,2 = 42 = 16

AA AB AC AD

BA BB BC BD

CA CB CC CD

DA DB DC DD

A B C D

A B C D

A B C D

A B C D

VideoEsercizio

VideoEsercizio

DISPOSIZIONI - Esercizi

Un club ha 15 membri. In quanti modi possono essere scelti un presidente, un vice-presidente e un segretario (supponendo che nessun membro possa avere piu`di una carica)?

Quanti numeri di 6 cifre, tutte pari e diverse da zero, si possono scrivere?

DISPOSIZIONI - Esercizi

Quanti sono i numeri di 4 cifre tutte distinte e non nulle nel sistema decimale?

Soluzione

Quante sono le combinazioni possibili per un lucchetto a 5 cifre?

Soluzione

DISPOSIZIONI - Esercizi

Quante parole anche prive di significato si possono formare con 3 lettere dell’alfabeto italiano tutte diverse tra loro? In quanti modi diversi 7 persone si possono sedere su 5 poltrone allineate di un cinema? Quanti numeri di 3 cifre anche uguali tra loro si possono costruire con i primi 5 numeri naturali? In quanti modi si possono scegliere, tra 10 ragazzi, un portiere, un arbitro e un attaccante?

PERMUTAZIONI

PERMUTAZIONI SEMPLICI

Le permutazioni semplici di n oggetti distinti sono tutti i possibili raggruppamenti contenenti la totalità degli n oggetti che differiscono solo per l’ordine. Sono un caso particolare di disposizioni Dn,k dove n = k

PERMUTAZIONI - Esempi

Costruire e contare tutti i possibili anagrammi della parola «APE» A P E - A E P - P A E - P E A - E A P - E P A

P3 = D3,3 = n! = 3‧2‧1 = 6

Quanti numeri di 4 cifre, fra loro diversi, si possono formare con le cifre 1, 3, 5, 7 ?

PERMUTAZIONI CON RIPETIZIONE

Nel caso in cui tra gli n oggetti sono presenti oggetti uguali in numero α, β, γ, etc, tra tutte le permutazioni possibili dobbiamo escludere quelle che si ripetono come ordine e tipo di oggetto. In questo caso il numero delle permutazioni possibili è dato dalla formula:

PERMUTAZIONI CON RIPETIZIONE - Esempi

COSTRUIRE E CONTARE GLI ANAGRAMMI (anche privi di senso) DELLA PAROLA «ALA»

ALA - ALA - AAL - AAL - LAA - LAA

PERMUTAZIONI - Esercizi

Tra tutti i numeri di 10 cifre tutte diverse tra loro, quanti sono i multipli di 10?

PERMUTAZIONI - Esercizi

Quanti sono gli anagrammi possibili della parola MAMMA?

Calcolare il numero di anagrammi distinti che si possono costruire con la parola MATEMATICAQuanti sono gli anagrammi della parola MATEMATICA che iniziano con MAT ? Quanti numeri naturali diversi di 6 cifre si possono formare con le cifre del numero 775551 ?

Click sul numero per le soluzioni

COMBINAZIONI

COMBINAZIONI SEMPLICI

Si chiamano combinazioni tutti i raggruppamenti formati da k oggetti che si possono formare a partire da n elementi (con k < n) tenendo conto che ogni gruppo si differenzia da un altro solo per la natura degli elementi componenti e non per il loro ordine

Il numero di combinazioni semplici si indica anche con il simbolo che si legge “n su k”, ed è detto “coefficiente binomiale” di ordine n e di classe k

Approfondimenti:Coefficienti binomiali e Binomio di Newton

COMBINAZIONI - Esempio

DATE LE 4 LETTERE A, B, C, D QUANTE SONO LE COPPIE DISTINTE CHE SI POSSONO FORMARE CHE DIFFERISCONO SOLO PER LA NATURA DEGLI ELEMENTI CHE LI COMPONGONO E NON PER L’ORDINE?

AB AC AD

BA BC BD

CA CB CD

DA DB DC

B C D

A C D

A B D

A B C

Si tratta di combinazioni semplici di n = 4 oggetti di classe k = 2

COMBINAZIONI CON RIPETIZIONE

Si chiamano combinazioni con ripetizione le combinazioni in cui un elemento può comparire più volte o meglio può essere ripetuto più volte all’interno di un raggruppamento. In generale il numero di COMBINAZIONI CON RIPETIZIONE è dato dalla formula:

COMBINAZ. con RIP. - Esempio

DATE LE 2 LETTERE a,b QUANTE SONO LE COMBINAZIONI CON RIPETIZIONE DI TALI OGGETTI PRESI A 3 A 3?

a a a a a b a b b b b b

COMBINAZIONI - Esercizi

Quanti ambi, terne e quaterne si possono formare con i 90 numeri del Lotto?

Schema riassuntivo

FATTORIALE DI UN NUMERO

FATTORIALE

Il fattoriale di un numero positivo n è una funzione avente come dominio N ed è il prodotto di tutti gli interi positivi minori o uguali ad n.

Si può scrivere in modo ricorsivo Per convenzione si pone:

0! = 1

Back

COEFFICIENTE BINOMIALE

COEFFICIENTE BINOMIALE

Il coefficiente binomiale (che si legge “n su k”) è un numero intero non negativo definito dalla seguente formula: con k, n numeri interi; 0 ≤ k ≤ n

PROPRIETÀ DEL COEFFICIENTE BINOMIALE

ALTRE PROPRIETÀ DEL COEFFICIENTE BINOMIALE

COEFFICIENTI BINOMIALI E IL BINOMIO DI NEWTON

IL TRIANGOLO DI TARTAGLIA

Il coefficiente binomiale è utile nello sviluppo della potenza di un binomio. Si considerino due numeri reali qualunque . Sono già note le formule:

(a + b)1 = a + b (a + b)2 = a2 + 2ab + b2 (a + b)3 = a3 + 3a2b + 3ab2 + b3

Analizzando il calcolo della generica potenza di un binomio è evidente che tutti gli sviluppi sono dei polinomi omogenei e completi, di grado uguale all’esponente della potenza. Ordinando gli sviluppi secondo le potenze decrescenti di uno dei due monomi, si nota che i loro coefficienti sono numeri del seguente schema, chiamato Triangolo di Tartaglia

Questo triangolo può essere riscritto con lo sviluppo della potenza secondo Newton che fa uso delle combinazioni:

Ebbene, qualunque siano i due numeri a e b e qualunque sia n intero positivo, si ha

Back

1 - SOLUZIONE

Abbiamo n = 5, α = 3 (lettera M), β = 2 (lettera A),

D10,3 = 10!/(10-3)!

4 - SOLUZIONE

Si tratta di permutazioni con ripetizione quindi: P2,3 6 = 6!/(2! 3!) = 60

Soluzione

P3 = 4! = 24

D7,5 = 7!/(7-5)!

2 - SOLUZIONE

Abbiamo n = 10, α = 2 (lettera M), β = 3 (lettera A), γ = 2 (lettera T)

3 - SOLUZIONE

MATEMATICA MAT_ _ _ _ _ _ _ Si tratta di permutazioni di 7 oggetti di cui solo 2 si ripetono (lettera A) quindi:N = 7!/2!

SOLUZIONE

D'4,6 = 46

SOLUZIONE

D10,3

D'5,3 = 53

Calcoliamo ad esempio il numero di anagrammi della parola ESSERE:E1S1S2E2RE3Le permutazioni possibili sono 6! = 720, ma teniamo presente che, ad es., E1RE2S1S2E3 ed E2RE3S2S1E1 sono la stessa parola. In qualunque modo si permutano le tre E, mantenendole nelle stesse posizioni, si ottiene lo stesso anagramma. Le tre E si possono permutare in 3! modi diversi. Dobbiamo dividere quindi il totale delle permutazioni per 3! Stesso discorso per le 2 S che si possono permutare in 2! modi diversi. In definitiva le permutazioni possibili sono: 6!/(3! 2!)

SOLUZIONE

Si osservi che ogni riga inizia e termina con 1 e gli altri valori si ottengono come somma dei due elementi sovrastanti.

SOLUZIONE

D21,3 = 21!/(21-3)! = 21*20*19