Argomentare & Dimostrare - math.unipa.itmath.unipa.it/~fbenanti/calcolocombinatorioUmberto.pdf ·...

Calcolo Combinatorio

Francesca Benanti

Dipartimento di Matematica ed Informatica Università degli Studi di Palermo, Via Archirafi 34, 90123 Palermo

Tel.: 091-23891105

E-mail: [email protected]

mailto:[email protected]

LABORATORIO DI ALGEBRA, PROGETTO LAUREE SCIENTIFICHE, LICEO CLASSICO UMBERTO, a.a. 2015-2016

Il calcolo combinatorio è il termine che denota tradizionalmente la branca della matematica che studia i modi per raggruppare e/o ordinare secondo date regole gli elementi di un insieme finito di oggetti. Il calcolo combinatorio si interessa soprattutto di contare tali modi, ovvero le configurazioni e solitamente risponde a domande quali "Quanti sono...", "In quanti modi...", "Quante possibili combinazioni...“ Da Wikipedia, l'enciclopedia libera.

Qualcuno ha definito il calcolo combinatorio o combinatoria come

"l'arte di contare ... senza contare"

mettendo in evidenza la maggiore importanza che in combinatoria ha la conoscenza del numero di combinazioni, rispetto alla conoscenza delle combinazioni stesse.

Significato e origini

https://it.wikipedia.org/wiki/Calcolo_combinatorio



http://it.wikipedia.org/wiki/Matematica

http://it.wikipedia.org/wiki/Insieme

"Quasi tutta la matematica classica, dall'algebra elementare alla

teoria delle equazioni differenziali, è applicabile al mondo reale solo nell'ipotesi che questo sia costituito di oggetti e di eventi a carattere continuo. Però, in molte situazioni comuni in fisica e in chimica ed in altre scienze, si può parlare realisticamente solo di collezione di oggetti a carattere discreto, i quali agiscono in combinazione, un passo per volta; la matematica applicata a tali situazioni si chiama

CALCOLO COMBINATORIO

Molti problemi di analisi combinatoria, tra i più interessanti, si sono presentati nella forma di ingegnosi indovinelli, a sfida di matematici e non matematici assieme: a prima vista, alcuni di essi possono sembrare addirittura frivolezze, eppure quasi tutti hanno delle applicazioni immediate ed importanti a problemi scientifici concreti"

Gian Carlo Rota- Analisi combinatoria ( Le Scienze Matematiche -UMI-Zanichelli, 1973)



Gli enigmi creano dipendenza. Uno dei primi nella storia a essere affetto da questa dipendenza fu niente meno che Carlo Magno (742-814), fondatore del Sacro Romano Impero, il qual sviluppò una tale mania per gli enigmi da assumere un esperto perché ne creasse appositamente per lui. La persona a cui venne affidato l’incarico fu il celebre studioso ed ecclesiastico inglese Alcuino di York



https://it.wikipedia.org/wiki/Carlo_Magno




Alcuino di York (735-804) è stato un filosofo, teologo e beato anglosassone. Alcuino fu uno dei principali artefici del Rinascimento carolingio: insegnò soprattutto grammatica e arti liberali.

da wikipedia

Alcuino raccolse cinquantasei degli enigmi inventati

per Carlo Magno in un manuale educativo, dal titolo

“Propositiones ad acuendos juvenes”

(problemi per rendere acuta la mente dei giovani), con l’intento di stimolare l’interesse per la matematica nei giovani del suo tempo.



https://it.wikipedia.org/wiki/Alcuino_di_York





Un enigma presente in quell’antologia, noto come

ENIGMA DELL’ATTRAVERSAMENTO DEL FIUME,

rientra tra i dieci più importanti di tutti i tempi. Molti storici matematici ritengono che lo schema concettuale su cui si basa sia l’intuizione fondamentale che portò, secoli dopo, alla nascita del Calcolo combinatorio.

LABORATORIO DI ALGEBRA, PROGETTO LAUREE SCIENTIFICHE, ,LICEO CLASSICO UMBERTO, a.a. 2015-2016


“Un viaggiatore si avvicina alla sponda di un fiume con un lupo, una capra e un cavolo. Con grande disappunto, nota che c’è solo una barca per attraversare il fiume, sulla quale c’è spazio solo per due: il viaggiatore e uno dei due animali oppure il cavolo. Come il viaggiatore ben sa, se li lascia insieme da soli, la capra mangerà il cavolo e il lupo mangerà la capra. Il lupo però non mangia i cavoli. Come può il viaggiatore portare tutti gli animali e il cavolo sull’altra riva, nel minor numero possibile di viaggi avanti e indietro?”

Esercizio 1

Enigma dell’attraversamento del fiume



ESERCIZIO 1.docx


Giochi matematici alla corte di Carlomagno Problemi per rendere acuta la mente dei giovani link


http://www.edizioniets.com/scheda.asp?n=9788846713513

Propositiones ad acuendos juvenes 18. Propositio de lupo et capra et fasciculo cauli Homo quidam debebat ultra fluvium transferre lupum et capram et fasciculum cauli, et non potuit aliam navem invenire, nisi quae duos tantum ex ipsis ferre valebat. Praeceptum itaque ei fuerat, ut omnia haec ultra omnino illaesa transferret. Dicat, qui potest, quomodo eos illaesos ultra transferre potuit. Solutio Simili namque tenore ducerem prius capram et dimitterem foris lupum et caulum. Tum deinde venirem lupumque ultra transferrem, lupoque foras misso rursus capram navi receptam ultra reducerem, capraque foras missa caulum transveherem ultra, atque iterum remigassem, capramque assumptam ultra duxissem. Sicque faciente facta erit remigatio salubris absque voragine lacerationis.




18. Il lupo, la capra e il cavolo Un uomo doveva trasportare aldilà di un fiume un lupo, una capra e un cavolo e non potè trovare altra barca se non una che era in grado di portare soltanto due di essi. Gli era stato ordinato però di trasportare tutte queste cose di là senza alcun danno. Chi è in grado dica in che modo poté trasferirli indenni. Soluzione In modo analogo allora io dapprima porterei la capra e lascerei il lupo e il cavolo. Poi tornerei e trasferirei sull’altra riva il lupo e sbarcato questo e imbarcata di nuovo la capra ritornerei indietro, e lasciata la capra trasferirei di là il cavolo, e tornerei di nuovo indietro, e presa la capra la porterei sull’altra sponda. In questo modo, la traversata sarà tranquilla senza disastri che incombano.



Riva di partenza

0. L C V U

1. L V

2. L V

3. V

4. V

5. C

6. C

7.

0.

Barca 0.

1. U C

2. U

3. U L

4. U C

5. U V

6. U

7. U C

0.

Riva di arrivo

0.

1.

2. C

3. C

4. L

5. L

6. L V

7. L V

0 . L C V U.


Anche in questo caso la soluzione data da Alcuino non è l’unica possibile, ve ne è anche un’altra che richiede, comunque, lo stesso numero di viaggi. Infatti nel primo viaggio il traghettatore non può fare altro che portare la capra sull’altra riva e tornare solo. A questo punto però egli ha due possibilità, traghettare il lupo, come suggerisce Alcuino, oppure il cavolo. Nel secondo caso dopo aver trasferito il cavolo egli riporta indietro la capra, quindi fa passare il lupo, ritorna solo ed infine traghetta la capra.


LABORATORIO DI ALGEBRA, PROGETTO LAUREE SCIENTIFICHE, , LICEO CLASSICO UMBERTO, a.a. 2015-2016

Il problema ebbe grande diffusione nel Medioevo e nel Rinascimento, ma non se ne conoscono versioni più antiche di quella di Alcuino. Recentemente però alcuni studiosi di etno matematica hanno scoperto che questo rompicapo è noto in molte parti dell’Africa, dove, ovviamente, i protagonisti sono più adeguati ai luoghi. Così per esempio, in Liberia sono coinvolti un ghepardo, un pollo e del riso; in Algeria uno sciacallo, una capra e un fascio di fieno. Allo stato attuale non siamo in grado di stabilire se le versioni africane sono autoctone oppure se sono adattamenti del problema europeo portato in Africa dalla cultura coloniale.



Una versione interessante dell’enigma fu

ideata dal matematico italiano Nicolò

Tartaglia nel XVI secolo.

Niccolò Fontana (Brescia, 1499 circa –

Venezia, 13 dicembre 1557) è stato un

matematico italiano. Al suo soprannome

(Tartaglia), dovuto al suo linguaggio

balbettante, è legato il noto triangolo

numerico, detto triangolo di Tartaglia e la

scoperta della risoluzione algebrica delle

equazioni di terzo grado .



https://it.wikipedia.org/wiki/Niccol%C3%B2_Tartaglia




L’enigma delle tre spose

“Tre bellissime spose con i loro mariti giungono nei pressi di un fiume. La barchetta che li trasporterà sull’altra riva può ospitare soltanto due persone. Per evitare situazioni compromettenti, gli attraversamenti devono essere organizzati in modo tale che nessuna donna venga lasciata sola con un uomo a meno che non sia presente anche suo marito. Come si può ottenere questo risultato, sapendo che la barca può essere condotta da qualsiasi uomo o qualsiasi donna? “

Esercizio 2


ESERCIZIO 2.docx

ESERCIZIO 2.docx

ESERCIZIO 2.docx

Riva di partenza

0. U1 D1 U2 D2 U3 D3

1 . U2 D2 U3 D3

2. U2 D2 U3 D3

3. U2 U3 D3

4. U2 U3 D3

5. U3 D3

6. U3 D3

7. U3

8. U3

9 .

0 .

Barca

0.

1 . U1 D1

2. D1

3. D1 D2

4. D2

5. U2 D2

6. D2

7. D2 D3

8 . D3

9 . U3 D3

0 .

Riva d’arrivo

0.

1 .

2. U1

3. U1

4. U1 D1

5. U1 D1

6. U1 D1 U2

7. U1 D1 U2

8 . U1 D1 U2 D2

9 . U1 D1 U2 D2

0 . U1 D1 U2 D2 U3 D3



Un problema basato su un certo ordinamento di oggetti, siano essi animali, coppie di spose, lettere di alfabeto, può essere studiato in modo sistematico.

Questa è la lezione principale che possiamo trarre dall’enigma di Alcuino.

Gli enigmi dell’attraversamento del fiume, delle tre spose hanno svolto un ruolo importante per gettare le fondamenta concettuali sulle quali nel XIX secolo è stata costruita la scienza del Calcolo Combinatorio.



Quanti numeri di telefono di 9 cifre si possono formare?

Quante parole di quattro lettere si possono formare con 21 lettere dell’alfabeto?

Quanti sottoinsiemi di 3 elementi ha un insieme di 10 elementi?


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

Oggetti del Calcolo Combinatorio

PERMUTAZIONI

DISPOSIZIONI

COMBINAZIONI


Oggetti del Calcolo Combinatorio

Permutazioni

Problema:

A teatro vogliamo contare in quanti modi possiamo far sedere due persone su due sedie, tre persone su tre sedie, quattro persone su quattro sedie. La prima persona sarà indicata con A, la seconda con B, la terza con C e la quarta con D.

LABORATORIO DI ALGEBRA, PROGETTO LAUREE SCIENTIFICHE, LICEO LICEO CLASSICO UMBERTO, a.a. 2015-2016

ESERCIZIO 3.docx

ESERCIZIO 3.docx

Permutazioni

Problema:

A teatro vogliamo contare in quanti modi possiamo far sedere due persone su due sedie. La prima persona sarà indicata con A, la seconda con B.

A B

B A

AB BA

LABORATORIO DI ALGEBRA, PROGETTO LAUREE SCIENTIFICHE, LICEO LICEO CLASSICO UMBERTO, a.a. 2015-2016

Le 2 possibili soluzioni : AB, BA.

Problema:

A teatro vogliamo contare in quanti modi possiamo far sedere tre persone su tre sedie. La prima persona sarà indicata con A, la seconda con B e la terza con C.

Permutazioni


Le 6 possibili soluzioni : ABC, ACB, BAC, BCA, CAB, CBA.

Problema:

A teatro vogliamo contare in quanti modi possiamo far sedere 4 persone su 4 sedie. La prima persona sarà indicata con A, la seconda con B, la terza con C e la quarta con D.

Permutazioni


Le 24 possibili soluzioni :

Si dice permutazione di n oggetti un ordinamento degli n oggetti.

Permutazioni


Permutazioni

Dato un insieme di n oggetti in quanti modi si possono ordinare i suoi elementi?

n=2: 2 x 1

n=3: 3 x 2 x 1

n=4: 4 x 3 x 2 x 1

In generale: n x (n-1) x … x 2 x 1


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

n fattoriale

Permutazioni

2! = 2 x 1= 2 3! = 3 x 2 x 1 = 6 4! = 4 x 3 x 2 x 1 = 24 5! = 5 x 4 x 3 x 2 x 1 = 120 6! = 6 x 5 x 4 x 3 x 2 x 1 = 720


Permutazioni

ESERCIZI:


EserciziPermutazioni.docx

EserciziPermutazioni.docx

Problema:

Un concessionario di automobili vuole esporre nella vetrina del suo salone quattro vetture tutte dello stesso tipo ma con 4 colori diversi (blu, grigio, rosso e nero). La vetrina però dispone di soli due posti: uno fisso e l’altro fornito di una piattaforma rotante. Il concessionario desidera sapere in quanti modi diversi è possibile disporre le auto.

Disposizioni


ESERCIZIO 4.docx

ESERCIZIO 4.docx

Disposizioni

Si hanno le seguenti 12 possibilità:

NB, NG, NR, BG, BR, BN, RN, RG, RB, GN, GR, GB


Disposizioni

Si dice disposizione di n oggetti in k posti ognuna delle scelte ordinate di k elementi tra gli n disponibili, k<=n.


Quante sono le disposizioni di n oggetti in k modi?

Esempio: D4,2 = 4 x 3 = 4!/2! = 12

Disposizioni


ESERCIZI:

Disposizioni


EserciziDisposizioni.docx

EserciziDisposizioni.docx

Combinazioni

Problema:

Determinare il numero di strette di mano che di scambiano n persone.


Combinazioni

Se non vi va di fare tanti conti, disegna alcuni cerchi. Ad ogni cerchio aggiungi una lettera

Poi collegate tutte le lettere


Combinazioni

1, 3, 6, 10, …. Non vi dice niente?

I Numeri Triangolari


Combinazioni

Come funzionano?


Combinazioni

Problema:

Quanti gruppi di tre persone possiamo determinare da un insieme di n persone?


Combinazioni

1, 4, 10, 20, ….

Confrontiamo questa successione con la successione dei numeri triangolari

1, 3, 6, 10, …. 1, 4, 10, 20, …. LABORATORIO DI ALGEBRA, PROGETTO LAUREE SCIENTIFICHE, , LICEO CLASSICO UMBERTO, a.a. 2015-2016

Combinazioni

Si dice combinazione di n elementi di classe k ognuna delle scelte di k elementi tra gli n (senza che interessi l’ordine in cui sono disposti).


Combinazioni

Quante sono le combinazioni di n oggetti in k modi?


Coefficienti binomiali e potenza di un binomio

Il numero delle combinazioni semplici è spesso indicato con il simbolo seguente:

che si legge « n su k » e viene detto

coefficiente binomiale



Proprietà:

1.

2.

3. Formula di Stifel



Il coefficiente binomiale è detto tale perché se ne fa uso nello sviluppo della potenza di un binomio. Consideriamo due numeri reali qualunque a e b. Sono note le formule:

Lo sviluppo della potenza del binomio con il metodo di Newton


Problema:

Quanti numeri a 5 cifre si possono formare usando le cifre 1,1,2,3 e 4?

Alcuni numeri sono indistinguibili:

1121254=12154 1221154=12154

Saranno

5!/2!=120/2=60

In generale:


Indicando dunque con k1, k2 il numero di volte che si ripetono rispettivamente gli elementi 1, 2 le permutazioni con ripetizione divengono:

Problema:

Quanti sono gli anagrammi della parola MAMMA?

Risposta:

5!/3!2!= 120/12=10


In generale, dato un insieme di n elementi dei quali α uguali fra loro, β uguali fra loro, ecc., il numero delle permutazioni distinte con elementi ripetuti che si possono ottenere è dato da


Disposizioni con ripetizioni

Problema: Consideriamo l'insieme:

A = {1,3,5,8} vogliamo determinare quanti numeri a due cifre si possono scrivere con gli elementi di A, considerando che sono ammesse le ripetizioni.


Disposizioni con ripetizioni

Riferendoci anche alla solita rappresentazione ad albero, si intuisce facilmente che si hanno n possibilità per scegliere il primo componente, n per il secondo ed altrettante per il terzo e così via

sino al k - esimo che completa la configurazione.

Il numero cercato è pertanto:

n × n × n × … × n

k volte, ossia nk , in formula


Combinazioni con ripetizioni

Problema: Dato l’insieme:

A = {a, b, c}

Determinare i ‘sottoinsiemi’ di A con 1, 2 e 3 elementi, con ripetizione.



Le combinazioni di classe 2, con ripetizione, sono sei :

(a, a) (a, b) (a, c) (b, b) (b, c) (c, c)

Le combinazioni di classe 1, con ripetizione, sono tre :

(a)(b) (c)

Le combinazioni di classe 3, con ripetizione, sono dieci :

(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) (a, c, c)



La formula che dà il numero delle combinazioni con ripetizione di n elementi di classe k è:

Nell’esempio precedente:


Riassumendo

Permutazioni semplici di n elementi n!

Disposizioni semplici di n elementi di classe k

Combinazioni semplici di n elementi di classe k

Permutazioni di n elementi, con ripetizioni assegnate di α, β ..

Disposizioni con ripetizione di n elementi di classe k

Combinazioni con ripetizione di n elementi di classe k


Riassumendo


Esercizi

Triangolo di Tartaglia


Scriviamo i coefficienti binomiali disponendoli in un triangolo illimitato, Triangolo di Tartaglia o di Pascal, nel modo seguente

https://it.wikipedia.org/wiki/Triangolo_di_Tartaglia







Proprietà



1+1=2 1+2+1=4=22

1+3+3+1=8=23

1+4+6+4+1=16=24

1+5+10+10+5+1=32=25

1+6+15+20+15+6+1=64=26

Per a=b=1:



1, 3, 6, 10, …. 1, 4, 10, 20, ….



Link: http://areeweb.polito.it/didattica/polymath/htmlS/argoment/ ParoleMate/Nov_07/TriangoloTartaglia.htm

http://areeweb.polito.it/didattica/polymath/htmlS/argoment/ParoleMate/Nov_07/TriangoloTartaglia.htm















Argomentare & Dimostrare - math.unipa.itmath.unipa.it/~fbenanti/calcolocombinatorioUmberto.pdf ·...

Documents

Transcript of Argomentare & Dimostrare - math.unipa.itmath.unipa.it/~fbenanti/calcolocombinatorioUmberto.pdf ·...