LABORATORIO DI ALGEBRA Elementi di calcolo combinatorio

(1)

UNIVERSITA’ DEGLI STUDI DI PALERMO

SCUOLA INTERUNIVERSITARIA SICILIANA DI

SPECIALIZZAZIONE PER L’INSEGNAMENTO SECONDARIO

LABORATORIO DI ALGEBRA

Elementi di calcolo combinatorio

Specializzandi : Dott.ssa Paola Brigaglia Dott.ssa Cinzia Cerroni Ing. Roberta Ducato Dott.ssa Giuseppina Morreale Dott.re Francesco Quartana

Prof.re: M. Cipolla

(2)

UNITA’ DIDATTICA

Elementi di Calcolo Combinatorio

Classi coinvolte

La presente Unità Didattica è rivolta agli allievi del biennio di una scuola superiore e ha la durata prevista di circa 8 ore.

Prerequisiti

• Nozioni di teoria degli insiemi.

• Le quattro operazioni e relative proprietà.

• L’operazione di elevazione a potenza.

• Le proprietà delle potenze.

• Elementi di base del calcolo letterario.

• Nozioni generali sulle frazioni algebriche.

Obiettivi

• Individuare il numero di scelte e di raggruppamenti possibili in un insieme finito di elementi.

• Comprendere le formule per permutazioni, disposizioni e combinazioni.

• Risolvere problemi di calcolo combinatorio.

• Rappresentare con diagrammi ad albero situazioni combinatorie.

Contenuti

La presente Unità Didattica è costituita da sei parti, i cui contenuti sono correlati agli obiettivi prefissati.

(3)

• Gli alberi per rappresentare ordinamenti.

• Il numero delle permutazioni di n elementi.

• Permutazioni con ripetizione.

• Le disposizioni (semplici) di n elementi a k a k.

• Combinazioni (semplici) di n elementi a k a k.

• Combinazioni con ripetizione.

Competenze

• Sapere individuare, anche elencandoli, il numero dei possibili raggruppamenti in un insieme finito.

• Sapere individuare, anche elencandoli, il numero dei possibili sottoinsiemi (scelte) in un insieme finito.

• Essere in grado di applicare correttamente le formule per permutazioni, disposizioni e combinazioni in contesti diversi.

• Sapere distinguere fra permutazioni, disposizioni e combinazioni.

Metodologia Didattica

Durante le lezioni si alterneranno tecniche e metodologie tradizionali, quali l’impostazione frontale, il più possibile dialogata, a metodologie didattiche attive quali i brain-storming, le discussioni guidate e il lavoro di gruppo.

Il lavoro di gruppo rappresenta una risorsa ad alto potenziale, sia come strumento che consente l’emergere di aspetti emozionali, sia come veicolo che, facilitando lo scambio di idee ed esperienze induce un maggiore coinvolgimento e assunzione di impegno da parte degli allievi.

Riteniamo più proficuo affrontare gli argomenti, oggetto delle lezioni, dapprima da un punto di vista intuitivo, utilizzando appropriati esempi e, solo successivamente mediante formalizzazione matematica. In questo modo si vuole rendere la trattazione degli argomenti quanto più semplice possibile, senza tuttavia trascurare la correttezza logica e terminologica.

A completamento dell’unità didattica vengono proposte due prove di valutazione finale sugli argomenti affrontati, una di tipo più tradizionale (compito in classe) e l’altra formulata in una delle tipologie più nuove per la nostra scuola (test a scelta multipla, questionario aperto).

(4)

I

^a

Lezione

Introduzione

Tutte le volte che si vuole mettere in ordine degli elementi appartenenti a un insieme finito o sceglierne alcuni, si pone il problema di calcolare quanti siano gli ordinamenti o le scelte possibili.

Problemi di questo tenere sono piuttosto frequenti, sia nella vita quotidiana sia all’interno della matematica:quanti numeri di telefono di 9 cifre si possono formare? Quante parole di 4 lettere si possono formare con le 21 lettere dell’alfabeto? In quanti modi diversi si possono sedere 5 persone se vi è una coppia di fidanzati, i quali vogliono stare seduti vicini?

Premettiamo la seguente definizione:

Due raggruppamenti sono differenti se gli elementi compaiono in ordine differente.

Gli alberi per rappresentare ordinamenti

Il primo problema che esamineremo riguarda il calcolo del numero degli ordinamenti che possono avere n elementi di un insieme, essendo n un qualunque numero naturale.

Consideriamo un insieme di tre elementi, che indichiamo con le prime tre lettere dell’alfabeto:

A = {a,b,c}.

Per ordinare questi tre elementi, dobbiamo innanzitutto scegliere l’elemento da collocare per primo; poiché gli elementi sono tre, vi sono tre scelte possibili:

•

I elemento a b c

Occorre ora scegliere l’elemento da collocare per secondo:

(5)

• se il primo elemento scelto è stato b, il secondo può essere a oppure c ;

• se il primo elemento scelto è stato c, il secondo può essere a oppure b .

Riassumiamo questa possibilità disegnando un albero con due livelli di profondità:

•

I elemento a b c

II elemento b c a c a b

Avendo solo tre elementi da ordinare, una volta che ne siano stati collocati due, il terzo è anche l’ultimo e la scelta è obbligata.

L’albero completo è il seguente:

•

I elemento a b c

II elemento b c a c a b

III elemento c b c a b a

Ognuno dei percorsi che va dalla radice dell’albero a un nodo terminale dà un possibile ordinamento. Tutti i possibili ordinamenti dei tre elementi sono perciò:

abc, acb, bac, bca, cab, cba.

(6)

II° Lezione

Il numero delle permutazioni di n elementi

PARTE 1°

Prendete due confezioni di colori a spirito da 12. Provate a sistemarli sul tavolo ordinandoli di volta in volta, per esempio, a tre atre. Scrivete sul vostro quaderno le varie triplette di colori che ottenete.

Osserviamo alcuni possibili casi (ne otterrete tanti altri):

• GIALLO ROSSO BLU

• GIALLO BLU ROSSO

• GIALLO GIALLO ROSSO

• GIALLO ROSSO VERDE

Osserviamo in particolare che i primi due raggruppamenti di colori differiscono tra loro per l’ordine con cui sono disposti gli elementi sul tavolo. Il primo raggruppamento ed il quarto differiscono tra loro per un elemento, hanno uguali il giallo ed il rosso ma differiscono per il blu ed il verde. Il terzo raggruppamento ha un colore ripetuto.

Alla fine dell’unità riusciremo a contare i diversi raggruppamento che si possono ottenere da un insieme di oggetti dati prendendo ogni volta un certo numero di essi.

Dall’esempio deduciamo che possiamo distinguere:

• I raggruppamenti senza ripetizioni di oggetti,

• I raggruppamneti con ripetizione di oggetti.

In particolare in questa lezione ci occuperemo di imparare a calcolare il numero delle permutazioni di n oggetti, e naturalmente acquisiremo la nozione di permutazione.

Facciamo un esempio.

Prendete quattro sedie e sistematele accanto alla cattedra, in quanti modi diversi quattro di voi, per esempio Alberto, Barbara, Claudio e Daniela , si possono sedere nelle sedie? Provate a scrivere tutte le possibilità sul quaderno.

(7)

A B C D

B C D A C D A B D A B C

C D B D B C C D A D A C D B A D A B B C A C A B

D C D B C B D C D A C A B D D A B A C B C A B A

Come potete osservare i diversi raggruppamneti sono 24.

Per l’albero relativo a 4 elementi le ramificazioni sono :

• 4 rami per il 1° elemento (4 scelte possibili);

• 1 ramo per il 4° elemento (scelta obbligata).

Il numero delle permutazioni si ottiene moltiplicando 4⋅3⋅2⋅1, abbiamo infatti ottenuto che il numero dei modi diversi con cui quattro di voi si possono sedere in quattro sedie è proprio 24.

Facciamo un altro esempio: quanti numeri di tre cifre (le cui cifre non si ripetono) fra loro diverse si possono formare con i numeri 3,5,7?

Rappresentiamo le possibilità con un albero:

3 5 7

5 7 3 7 3 5

7 5 7 3 5 3

(8)

Anche in questo caso abbiamo:

• 1 ramo per il 3° elemento (scelta obbligata).

Il numero delle permutazioni (in questo caso dei numeri di tre cifre) è 6.

Generalizziamo quanto detto all’albero delle permutazioni di n elementi esso avrà:

• n rami per il 1° elemento (n scelte possibili);

• (n-1) rami per il 2° elemento (n-1 scelte possibili);

•

• 1 ramo per il l’ultimo elemento (scelta obbligata).

Il numero delle permutazioni di n elementi è il prodotto dei primi n numeri naturali e viene indicato con n! (si legge n fattoriale).

Per alcuni valori di n calcoliamo n!:

1 2 3 4 5 6

! 6

1 2 3 4 5

! 5

1 2 3 4

! 4

1 2 3

! 3

1 2

! 2

1

! 1

⋅

=

⋅

=

⋅

=

⋅

=

⋅

=

…

DEF. Si dice permutazione ognuno dei raggruppamenti che è possibile dare agli elementi di un insieme.

Potremmo dire che ogni permutazione è un diverso raggruppamento degli elementi di un insieme.

(9)

PARTE 2°

All’inizio della lezione si era detto che vi sono dei sottoinsiemi nella cui costruzione non è prevista la possibilità di ripetizio ne di oggetti (per esempio le permutazioni semplici) e sottoinsiemi nella cui costruzione è prevista la possibilità che, all’interno di uno stesso sottoinsieme, vi sia la possibilità che un oggetto sia ripetuto è il caso delle permutazioni con ripetizione.

Provate a calcolare quanti anagrammi potete formare con le parole tre, afa, Anna

.

T R E

R E T E T R

E R E T R T

Questo è il caso di una permutazione semplice il numero è 6.

A F A

F A A A A F

A F A A A F

(10)

Questo è il caso di una permutazione di tre elementi in cui una coppia di elementi si ripete.

A N N A

N N A A N A A N A N N A

N A N A N N N A A A A N N A A A A N N A N A N N

A N A N N N A N A A N A A N A A N A A N A N N N

Questo è il caso di una permutazione di 4 elementi in cui due coppie di elementi si ripetono.

Adesso scrivete le permutazioni che si ripetono in riga e quelle distinte in colonna:

FAA FAA

AFA AFA

AAF AAF

Le coppie di permutazioni che si ripetono sono 2 ossia il numero delle permutazioni degli elementi che si ripetono. Per ottenere il numero delle permutazioni con ripetizione dobbiamo dividere il numero delle permutazioni semplici per 2!:

! 2

! 3 =3.

ANNA ANNA ANNA ANNA ANNA

ANAN ANAN ANAN ANAN ANAN

AANN AANN AANN AANN AANN

NANA NANA NANA NANA NANA

NAAN NAAN NAAN NAAN NAAN

NNAA NNAA NNAA NNAA NNAA

(11)

Di ogni permutazione ne otteniamo quattro uguali ossia il prodotto delle permutazioni degli oggetti che si ripetono. Per ottenere il numero delle permutazioni con ripetizione dobbiamo dividere il numero delle permutazioni semplici per !2 ⋅2!:

! 2

! 4

⋅ =6.

Generalizzando i ragionamenti fati possiamo dare una formula generale.

Dati n oggetti di cui α identici il numero delle permutazioni con ripetizione è dato da:

( ) .

!

! α

α n

P_N =

Se degli n oggetti α,β,γ... sono identici fra loro risulta: P_N⁽^α^,^β^,^γ^,^,^,⁾

!...

!

! γ β α

= n .

Provate a svolgere i seguenti esercizi:

1. In un gioco a premi si vince con la combinazione 11222333. Quante diverse permutazioni si possono effettuare con 9 cifre di cui qualche cifra si ripete?

2. A cena fuori puoi scegliere tra 3 antipasti, 5 primi, 6 secondi, frutta o dolce. In quanti modi si può ordinare una cena completa?

3. Una sera avete deciso di uscire avete in programma di andare in pizzeria, al cinema e a pattinare, ma siete indecisi su cosa fare prima e su cosa fare dopo.

Stabilite tutti i modi con cui potete organizzare la serata

(12)

III

^a

Lezione

Le disposizioni di n elementi a k a k

Consideriamo il seguente esempio:

supponiamo di avere due sedie e quattro ragazzi : Alfredo, Benedetto, Carlo e Davide. In quanti modi possibili si possono sedere i quattro ragazzi? E quali sono?

Indichiamo i quattro ragazzi con le loro iniziali A, B, C, D e scriviamo le varie possibilità con cui i ragazzi si possono sedere. Esse sono

AB AC AD

BA BC BD

CA CB CD

DA DB DC

Contando tutte le possibilità troveremo che esse saranno nel numero di 12.

Osserviamo che quando ordiniamo gli elementi di un dato insieme, scrivendo così una loro permutazione, il numero dei posti è uguale al numero degli elementi: se vi sono n elementi vi sarà un elemento al primo posto, un altro elemento al secondo posto e così via fino all’ultimo elemento.

In questo caso il numero dei posti (le due sedie) è inferiore al numero degli elementi (i quattro ragazzi).

Occorre quindi disporre gli elementi in diversi posti, scartando di volta in volta, altri ottenendo un certo numero di scelte possibili.

Volendo generalizzare questo tipo di problema e trovare una formula che consente di calcolare il numero delle scelte ordinate di n elementi da disporre in k posti, essendo k, n∈N e k≤n.

DEF. Si dice DISPOSIZIONE di n elementi in k posti ognuna delle scelte ordinate di k elementi tra gli n disponibili.

(13)

Rappresentazione mediante gli alberi

Supponiamo di avere un insieme di 4 elementi: A={a,b,c,d}

e di avere due posti in cui disporre gli elementi. Possiamo seguire un ragionamento analogo a quello seguito per le permutazioni, rappresentando con un albero tutte le scelte per il primo e il secondo posto.

L’albero sarà, allora, formato da due livelli di profondità, cioè

a b c d

b c d a c d a b d a b c

Il numero di tutte le disposizioni di 4 elementi in 2n posti è allora 4*3 = 12.

Esse sono: ab, ac, ad, ba,bc, bd, ca, cb, cd, da, db, dc.

Quindi il numero delle disposizioni di 4 elementi in 2 posti è il prodotto di 2 fattori (tanti quanti sono i posti): il primo fattore è 4 (le scelte possibili per l’elemento al primo posto); il secondo fattore è 3 (le scelte possibili per il secondo posto).

Generalizzando i ragionamenti fatti in precedenza, si giunge alla conclusione che il numero delle disposizioni di n elementi in k posti è dato dal prodotto di k fattori, cioè tanti quanti sono i posti.

Il primo fattore è n, il secondo n-1, il terzo n-2, e così via fino ad arrivare al k-esimo fattore che è n-(k-1). Si ha quindi:

Il numero delle disposizioni di n elementi in k posti è:

D_n,k= n(n-1)(n-2)...(n-(k-1)) o anche

Dn,k = n! / (n-k)!

(14)

IV Lezione

Le combinazioni semplici

Metodologia

Riteniamo proficuo trattare tale argomento - che è senza dubbio tra i più ostici del calcolo delle probabilità – utilizzando il cosiddetto metodo induttivo, strategia didattica che consiste, in buona sostanza, nel partire da esempi concreti della vita quotidiana per passare poi, gradatamente, alla formalizzazione dei concetti introdotti.

Tenuto presente che l’argomento in questione è rivolto ad alunni di una seconda classe superiore, e quindi a ragazzi che, secondo quanto stabilito dagli psicologi, non hanno ancora sviluppato pienamente il pensiero logico-deduttivo, preferiamo non riportare le dimostrazioni delle formule di volta in volta utilizzate, scelta che oltretutto dovrebbe rendere meno sgradevole agli alunni un argomento ritenuto difficile come le combinazioni.

Situazione stimolo n.1

Si hanno a disposizione 3 fiori diversi tra loro, una rosa (R), una margherita (M) e un papavero (P).

Si chiede alla classe, dovendo comporre un mazzetto di due fiori, quante sono le varianti che si presentano.

Soluzione

Prima di risolvere la questione, osserviamo che non è significativo l’ordine con cui i fiori compaiono nel mazzetto (in altri termini, è evidente che il mazzetto costituito, ad esempio, dalla rosa e dalla margherita è identico a quello costituito dalla margherita e dalla rosa!)

Si vede facilmente che tali varianti sono:

1) R-M 2) R-P 3) M-P

cioè sono in numero di 3.

(15)

Determiniamo le varianti che si presentano volendo comporre sempre un mazzetto di due fiori.

Soluzione

In questo caso troviamo:

1) R-M 2) R-P 3) M-P 4) M-T 5) P-T 6) R-T

Notiamo che, a partire da 4 fiori, sono state trovate 6 varianti, contro le 3 del caso precedente.

Formalizzazione del concetto di combinazione semplice

In generale, dati n oggetti distinti tra loro, il numero dei possibili raggruppamenti distinti di )

( n

k < di tali oggetti, tali che in ogni raggruppamento ciascun oggetto figuri una sola volta e che si assumano “eguali” raggruppamenti che differiscono solo per l’ordine con cui i k oggetti vi compaiono, è dato da:

(1)

( )

^!

!

, k n k

C_n_k n

= − .

Tali raggruppamenti vengono detti combinazioni semplici di n elementi a k a k.

Osserviamo che due qualsiasi raggruppamenti si intendono distinti se, e solo se, uno di essi contiene almeno un oggetto che non figura nell’altro.

Giova ancora notare come le combinazioni semplici di n elementi a k a k costituiscano un sottoinsieme delle disposizioni semplici di n elementi a k a k.

Per convincersi di ciò, basta riprendere in considerazione la situazione stimolo numero 1 e determinarne, appunto, le disposizioni semplici mediante rappresentazione ad albero. Tra queste, rimangono subito individuate le combinazioni; infatti:

(16)

R M

P

M P R P R

m

M Fig.1

dall’albero segue che l’elenco completo delle disposizioni semplici è:

R-M R-P M-R M-P P-R P-M

e le combinazioni semplici da noi individuate sono:

R-M R-P M-P

che ne costituiscono un sottoinsieme:

M-R

M-P

P-R P-M M-P R-M R-P

Fig.2

Si invita a questo punto la classe a riprendere in esame le due situazioni precedenti, per verificare come la formula (1) sia in effetti corretta.

Nella situazione 1 erano n =3 e k =2, così, applicando la formula:

(17)

(

³ ²

)

^! ³

! 2

! 3

2 ,

3 =

= − C

che è appunto quanto era stato trovato per altra via.

Nella situazione 2 cambiava solo il numero dei fiori disponibili, n=4. In questo caso, applicando sempre la formula (1) troviamo:

(

⁴ ²

)

^! ⁶

! 2

! 4

2 ,

4 =

= − C

che, ancora una volta, è quanto era stato ottenuto altrove.

Esercizio svolto

Diciotto persone partecipano ad un concorso e soltanto le prime tre saranno assunte. Quante sono le possibili terne di concorrenti assunti?

Svolgimento dell’esercizio

Osserviamo, innanzitutto, che si tratta di un problema di combinazioni semplici. Gli elementi di partenza (le persone) infatti, sono tutti diversi tra loro e figurano, in ciascuna terna, una e una sola volta. Inoltre, le possibili terne non sono caratterizzate dall’ordine di composizione, essendo indifferente l’ordine in cui i primi tre concorrenti si classificano.

Utilizzando, a questo punto, la formula (1) con n =18 e k =3 si trova:

(

¹⁸ ³

)

^! ⁸¹⁶

! 3

! 18

3 ,

18 =

= − C

le quali rappresentano tutte le possibili terne di concorrenti assunti.

Un barman dispone di 30 liquori diversi. Quanti coktails diversi potrà preparare utilizzando, ogni volta, tre dei predetti liquori?

E’ evidente che l’ordine con cui i tre liquori vengono uniti non ha importanza quindi il numero dei coktails diversi è:

1 4060 2 3

28 29 30 27 3

30

3

30 =

⋅

= ⋅

= ! !

C _, !

(18)

Quanti terni si possono fare con i 90 numeri del gioco del lotto?

E’ noto che nel gioco del Lotto non conta l’ordine con cui i numeri vengono estratti sicchè il numero dei terni è uguale a quello delle combinazioni semplici di 90 oggetti a tre a tre, ossia:

117480 1

2 3

88 89 90 87 3

90

3

90 =

⋅

= ⋅

= ! !

C _, !

(19)

V Lezione

Combinazioni con ripetizione

Vediamo con un esempio in che cosa consiste il problema di trovare le combinazioni con ripetizione.

Consideriamo la classica schedina totocalcio. Per potere determinare il numero di tutte le possibili schedine di una colonna che è possibile compilare, dobbiamo disporre con ripetizione a 13 a 13 i 3 simboli 1, x, 2. Applicando la formula studiata si ottiene:

D^r3,13=1.594.323

Vogliamo risolvere il seguente problema: quante diverse schedine di due colonne sarà possibile compilare considerando anche le schedine contenenti due colonne uguali?

Si tratta evidentemente di un problema di combinazioni, perché non ha assolutamente importanza se all’interno della schedina la colonna vincente è la prima o la seconda, e, come abbiamo già detto, vogliamo considerare anche le schedine con due colonne uguali (ammesso che esista un giocatore che sia disposto a giocarle tali). Dunque dobbiamo combinare a 2 a 2 le 1.594.323 colonne possibili.

Allora possiamo dare la seguente definizione:

Dati n oggetti distinti e indicato con k un numero intero positivo qualsiasi (ossia anche maggiore di n), si chiamano combinazioni con ripetizione di questi n oggetti, presi a k a k (o di classe k), tutti i raggruppamenti diversi che si possono formare con gli oggetti dati, in modo che valgano le seguenti proprietà:

1. ogni raggruppamento contiene k oggetti;

2. in ogni raggruppamento uno stesso oggetto può figurare ripetuto sino ad un massimo di k volte;

3. l’ordine degli oggetti non conta, e quindi due raggruppamenti sono da considerarsi diversi quando uno di essi contiene almeno un elemento che non figura nell’altro, oppure contengono gli stessi elementi ma non sono ripetuti lo stesso numero di volte.

Dalla definizione risulta chiaro che, per esempio, data la terna A, B, C

(20)

le terne AAB, ABA e BAA devono considerarsi una sola volta dato che esse differiscono solo per l’ordine in cui compaiono gli elementi.

Individuato il problema, enunciamo la formula che ci consente di risolverlo.

Indichiamo le combinazioni con ripetizione con il simbolo C^rn,k

!

) 1 (

k k n n

n + ⋅ ⋅⋅ + −

=

k n,

Cr

ricordando che

!

) 1 (

k k n n

n − ⋅ ⋅⋅ − +

k =

Cn, (per le combinazioni semplici)

otteniamo che:

C^rn,k = Cn+k -1,k

In questo modo, riconduciamo il problema delle combinazioni con ripetizione al calcolo di combinazioni semplici. Non si ritiene per la classe a cui è destinata tale unità didattica di dimostrare la formula C^rn,k.

Tornando al problema precedente, si ha n=3¹³ e k =2 e dunque si tratta di calcolare:

326 . 711 . 933 . 270 .

! 1 2

) 3 )(

1 3

( ¹³ ¹³

+ =

=

= ₃ ₊₂_-_1,2 ₃ ₊_1,2

,2 3 r

13

13 C 13 C

C

se invece si pensa di evitare le ripetizioni, si ottiene:

003 . 117 . 932 . 270 . 2 1

) 1 3 (

3¹³ ¹³ − =

,2 =

3¹³

C

questo risultato si può ottenere più semplicemente calcolando ^r

1,2 1,2 3

3 r

13 D 13

C + − ₊ visto

che le ripetizioni sono pari al numero di schedine di una colonna.

Osservazione:

In generale, i problemi riguardanti le modalità di distribuzione in gruppi di oggetti indistinguibili, ossia per i quali non si opera distinzione tra gli oggetti stessi, si risolvono mediante combinazioni con ripetizione.

Esempio:

Calcoliamo il numero delle combinazioni con ripetizione di tre oggetti: {a, b, c} presi a tre a tre.

In tal caso si ha n=3 k=3 Perciò

(21)

( )

¹⁰

! 3

) 3 4

5 5

3 3 ,

3 = = ⋅ ⋅ =

Cr

Ora, utilizzando un diagramma ad albero per scrivere effettivamente le combinazioni con ripetizione dei tre oggetti dati, presi prima a uno a uno, poi a due a due, ed infine a tre a tre.

Così facendo si ha:

Notiamo che nel raffronto tra l’albero delle disposizioni con quello delle combinazioni, si può notare come il primo sia simmetrico mentre il secondo non lo sia. Nel primo caso infatti è importante l’ordine con cui compaiono gli elementi, al contrario del secondo caso dove alcuni gruppi vanno contati una sola volta.

Per evidenziare meglio la distinzione tra disposizione e combinazione è utile effettuare il seguente esempio:

“Calcoliamo le differenti modalità con cui sei penne identiche possano essere riposte in quattro cassetti A, B, C, D. supponendo, invece, che le penne siano distinguibili, quante diventano le modalità?”

1) Poiché le sei penne sono tutte uguali, ossia indistinguibili l’una dall’altra, allora le differenti modalità con cui esse possono essere collocate nei 4 cassetti sono tante quante le combinazioni con ripetizioni di n=4 oggetti di classe k=6, ossia:

1 84 2 3 4 5 6

4 5 6 7 8 ' 9

9

6 1 6 4

6 6 ,

4 =

⋅

= ⋅





=

 

= ⁺ ⁻ C

a a a

a a b

a a c

a b b

a b c

a c c

b b b

b b c

b c c

c c c

c c b

c b a

a

c

b c b c a

b c c

c c c

(22)

2) Se invece le penne sono distinguibili l’una dall’altra, ad esempio perché di colore diverso:

Bianco, nero, rosso, verde, giallo, blu

allora il numero dei modi con cui queste penne possono essere collocate nei quattro cassetti sarebbe maggiore. Per convincersi di ciò, basti pensare che, ad esempio, la seguente situazione:

cassetto A B C D

N° di penne in esso contenute 1 5 0 0

mentre si realizza secondo un’unica modalità, nel caso in cui le penne siano indistinguibili, si può invece ottenere mediante sei modalità differenti, nell’eventualità in cui le penne siano colorate, e cioè una distinta modalità per ogni colore della penna riposta nel cassetto A.

Dunque, questa volta, l’ordine ha importanza quindi occorre utilizzare le disposizioni.

Ciò constatato, vediamo come può essere interpretata una qualsiasi disposizione con ripetizione dei quattro cassetti A, B, C, D di classe 6; ad esempio, la seguente disposizione con ripetizione:

A A B B B C

Può essere interpretata:

cassetto A B C D

Penne in esso contenute

bianca nera

rossa verde gialla

blu

Consideriamo adesso un’altra disposizione con ripetizione di A, B, C, D di classe 6:

B A C C C D

Essa può essere così interpretata:

cassetto A B C D

Penne in esso

contenute nera bianca

rossa verde gialla

blu

(23)

Procedendo su questa via, si comprende che le differenti modalità con cui le sei penne distinguibili (perché di diverso colore) possono essere collocate in quattro cassetti sono tante quante le disposizioni con ripetizione di n=4 oggetti di classe k=6, ossia:

D’4,6 = 4⁶= 4096

Esercizi di verifica:

1) In quanti modi dodici caramelle indistinguibili possono essere distribuite a quattro bambini?

2) In quanti modi diversi quattro libri possono essere riposti in tre cartelle, supponendo che:

a) I libri siano indistinguibili;

b) I libri siano di differenti materie.

3) Dati nove punti di un piano, a tre a tre non allineati, quanti sono i triangoli diversi che hanno i vertici nei punti dati?

(24)

Compito in classe

A) Determina in quanti modi diversi si possono sistemare 4 palline diversamente colorate in 4 scatole, in modo tale che una scatola rimanga vuota, una scatola contenga due palline e le altre scatole contengano una pallina ciascuna.

B) Determina quanti sono i numeri naturali con cifre tutte diverse, che si possono ottenere con le cifre 1, 3, 5, 7, 9.

C) In quanti modi diversi 10 ragazzi possono essere divisi in tre gruppi di lavoro

se questi debbono essere composti di 4, 5 e 3 persone rispettivamente ?

(25)

QUESTIONARIO

1) Quanti sono gli anagrammi (anche senza senso) della parola ROMA ?

2) In un cinema vi sono 5 posti liberi affiancati. In quanti modi diversi si possono sedere 5 persone se vi sono due coppie di fidanzati che vogliono stare seduti vicini ?

3) Quale è il numero delle disposizioni di 8 elementi in 3 posti ?

4) Di un numero telefonico si ricorda soltanto che esso è formato da sette cifre tutte diverse tra loro e la prima è 3. Quanti sono i possibili numeri di telefono ?

5) Quante e quali sono le combinazioni di 5 elementi di classe 3 ?

6) In un compito con cinque esercizi si chiede di farne tre; non interessa l’ordine.

Quante scelte sono possibili ?

7) Ogni giorno l’insegnante, in una classe di 25 persone, interroga due persone a caso.

Quante scelte sono possibili ?

8) Determina il numero dei sottoinsiemi di 3 elementi in un insieme di 8 elementi.

9) Calcola il numero di terni possibili con i 90 numeri del lotto (non importa l’ordine di estrazione).

(26)

Scheda di approfondimento: dalle permutazioni al concetto di gruppo.

A partire dalle permutazioni di n oggetti, è possibile introdurre in modo elementare, ma comunque significativo l’importante concetto matematico di gruppo.

Tre amici, Antonio, Barbara e Carlo, dopo aver studiato le permutazioni di n oggetti, provano a determinare in quanti modi diversi possono occupare tre sedie numerate da 1 a 3.

Se hanno ben capito, tale numero dovrebbe essere pari a 3!=6, come verificano facilmente costruendo il seguente schema:

.) (

) (

.) (

) (

config sesta A

B C

config quinta B

A C

config.

quarta A

C B

config.

terza C

A B

config seconda B

C A

iniziale seq.

o config.

C B A

33 22 11

Nella configurazione iniziale, Antonio occupa la sedia 1, Barbara la sedia 2 e Carlo la sedia 3.

Nella configurazione successiva, Barbara e Carlo si scambiano di posto (sequenza A C B), mentre invece, nella terza configurazione, Barbara occupa la sedia 1, Antonio la 2 e Carlo la 3 (sequenza B A C); e così via per le rimanenti configurazioni.

A questo punto Antonio – il più sveglio dei tre – osserva che il passaggio dalla configurazione iniziale alla successiva (dalla sequenza A B C alla sequenza A C B) può essere rappresentato con semplicità utilizzando la tabella:

(1)





2 3 1

3 2 1

la quale indica, in sostanza, che colui che occupava il posto 1 (Antonio) continua ad occupare quel posto; Barbara, che occupava il posto 2, occupa ora il posto 3 e, infine, Carlo, che occupava il posto 3, occupa adesso il posto 2.

Allo stesso modo, il passaggio dalla seconda configurazione alla terza, la B A C, sarà rappresentato dalla tabella:

(2)



1 2 3

(27)

dato che ora Antonio, che occupava il posto 1, si è spostato in 2; Carlo, che occupava il posto 2, in 3 e infine Barbara, che si trovava in 3, si è spostata in 1.

Lasciamo un attimo da parte i tre amici e osserviamo che, il passaggio dalla terza alla quarta configurazione è anch’esso rappresentato dalla tabella (1). Quello dalla quarta alla quinta dalla tabella:

(3)





2 1 3

3 2 1

e quello dalla quinta alla sesta ancora una volta dalla tabella (1).

Il passaggio dalla prima alla terza configurazione è rappresentato dalla tabella:

(4)





3 1 2

3 2 1

ed infine il passaggio dalla prima alla sesta configurazione dalla tabella:

(5)





1 2 3

3 2

1 .

Alle cinque tabelle precedenti possiamo aggiungerne una sesta:

(6)





3 2 1

la quale esprime la circostanza che i tre amici continuano ad occupare le rispettive posizioni.

Le sei tabelle precedenti esauriscono tutte le possibili combinazioni dei numeri 1, 2 e 3, pertanto, il passaggio da una qualunque delle sei configurazioni dello schema visto all’inizio ad una qualunque altra è sempre rappresentato da una, ed una sola delle sei tabelle precedenti.

Indichiamo con S l’insieme costituito dalle sei tabelle precedenti, cioè: ₃

3 =

S {





2 3 1

3 2

1 ,





1 3 2

3 2

1 ,





2 1 3

3 2

1 ,





3 1 2

3 2

1 ,





1 2 3

3 2

1 ,





3 2 1

3 2

1 }.

E’ possibile eseguire una particolare operazione tra gli elementi (tabelle) di questo insieme.

Esattamente, considerando la prima e la seconda di queste tabelle si ha:





2 3 1

3 2

1 



1 3 2

3 2

1 =





3 1 2

3 2 1

dove la tabella a destra dell’uguale è stata ottenuta a partire dalla prima seguendo gli spostamenti di ogni singolo numero.(Si noti che la tabella ottenuta esprime il passaggio dalla prima alla terza configurazione…)

(28)

Si verifica subito che, eseguendo tale operazione tra due qualunque tabelle dell’insieme, eventualmente anche eguali tra loro, si ottiene sempre una tabella dell’insieme medesimo.

In particolare, eseguendo l’operazione tra una qualunque tabella, ad esempio la terza, e la sesta tabella di S , in qualunque ordine, si ha: ₃





2 1 3

3 2

1 



3 2 1

3 2

1 =





2 1 3

3 2

1 =





3 2 1

3 2

1 



2 1 3

3 2 1

che si interpreta pensando che ciascun occupante delle sedie non muta la posizione da cui parte.

Si può anche verificare che, per qualunque tabella dell’insieme ne esiste sempre un’altra – non necessariamente diversa da quella in esame – tale che, l’operazione tra le due, indipendentemente dall’ordine con la quale si effettua, dà come risultato la sesta tabella di S . Ad ₃ esempio, considerando ancora la terza tabella di S : ₃





2 1 3

3 2 1

l’operazione con la tabella





1 3 2

3 2

1 , in qualunque ordine, dà come risultato sempre la sesta

tabella:





2 1 3

3 2

1 



1 3 2

3 2

1 =





3 2 1

3 2

1 =





1 3 2

3 2

1 



2 1 3

3 2

1 .

Infine, l’operazione tra tabelle introdotta in S gode della proprietà associativa, come si ₃ verifica senza alcuna difficoltà.

A questo punto, viene da chiedersi se, in generale, l’operazione introdotta è anche commutativa, cioè se il risultato è sempre indipendente dall’ordine con cui si dispongono le tabelle.

Per rispondere a tale domanda, basta osservare che, in particolare:





1 3 2

3 2

1 



2 3 1

3 2

1 =





1 2 3

3 2

1 ≠ 



3 1 2

3 2

1 =





2 3 1

3 2

1 



1 3 2

3 2 1

pertanto concludiamo che l’operazione, in generale, non è commutativa.

Qui giunti, è possibile formalizzare il concetto matematico di gruppo dando la seguente:

(29)

Definizione : un insieme non vuoto G si dice un gruppo rispetto ad un’operazione “∗” se, e solo se:

a) ∀a,b∈G, (a∗b)∈G;

b) ∀a∈G, esiste un elemento (detto elemento neutro di G) e∈G tale che: a∗e=e∗a =a; c) ∀a∈G,esiste un elemento (detto simmetrico di a) a∈G tale che: a∗a=a∗a =e; d) l’operazione ∗ è associativa.

Per quanto osservato prima, l’insieme S delle permutazioni di 3 oggetti è un gruppo (non ₃ commutativo) rispetto all’operazione tra tabelle che abbiamo introdotto.

L’elemento neutro di tale gruppo è la tabella:





3 2 1

3 2

1 .