Pages From Estratto Calcolo Discreto r

Idee e Strumenti

Tonolo_2400pt_def.pdf 1 05/09/12 10.16

Dal catalogo Apogeo

Matematica e statistica

Anderson, Sweeney, Williams, Statistica per le analisi economico-aziendaliBarutello, Conti, Ferrario, Terracini, Verzini, Analisi matematica, Volume dueBland, Statistica medicaConti, Ferrario, Terracini, Verzini, Analisi matematica, Volume unoCrivellari, Analisi statistica dei dati con REspa, Micciolo, Problemi ed esperimenti di statistica con REspa, Micciolo, Analisi esplorativa dei dati con RLuenberger, Finanza e investimenti. Fondamenti matematiciMiddleton, Analisi statistica con ExcelMoore, Statistica di baseNaldi, Pareschi, Matlab. Concetti e progetti, seconda edizioneRomano, Meccanica analiticaRoss, Calcolo delle probabilita`, seconda edizioneRoss, Introduzione alla statisticaRoss, Probabilita` e statistica per lingegneria e le scienze, seconda edizioneStewart, Calcolo. 1. Funzioni di una variabileStewart, Calcolo. 2. Funzioni di piu` variabiliStrang, Algebra lineareTommei, Matematica di baseWaner, Costenoble, Strumenti quantitativi per la gestione aziendaleWelkowitz, Cohen, Ewen, Statistica per le scienze del comportamento

Tonolo_2400pt_def.pdf 2 06/09/12 09.49

Calcolo discretoMetodi per contare

Carlo MaricondaAlberto Tonolo

Tonolo_2400pt_def.pdf 3 06/09/12 09.49

Calcolo discretoMetodi per contare

Autori:Carlo Mariconda, Alberto Tonolo

Copyright c2012 APOGEO s.r.l.Socio Unico Giangiacomo Feltrinelli Editore s.r.l.Via Natale Battaglia 12 20127 Milano (Italy)Telefono: 02-289981 Fax: 02-26116334Email: [email protected]. www.apogeonline.com

ISBN 978-88-503-2494-1

Impaginazione in LATEX: CompoMat s.r.l.Editor: Alberto Kratter ThalerRedazione: Patrizia VillaniCopertina: Enrico MarcandalliImmagine di copertina di Graziella Giacobbe

Tutti i diritti sono riservati a norma di legge e a norma delle convenzioni interna-zionali. Nessuna parte di questo libro puo` essere riprodotta con sistemi elettronici,meccanici o altri, senza lautorizzazione scritta dellEditore.Nomi e marchi citati nel testo sono generalmente depositati o registrati dalle rispettivecase produttrici.Le fotocopie per uso personale del lettore possono essere effettuate nei limiti del15% di ciascun volume dietro pagamento alla SIAE del compenso previsto dallart.68, commi 4 e 5, della legge 22 aprile 1941 n. 633.Le fotocopie effettuate per finalita` di carattere professionale, economico o commer-ciale o comunque per uso diverso da quello personale possono essere effettuate aseguito di specifi ca autorizzazione rilasciata da CLEARedi, Centro Licenze e Auto-rizzazioni per le Riproduzioni Editoriali, Corso di Porta Romana 108, 20122 Milano,e-mail [email protected] e sito web www.clearedi.org.

Finito di stampare nel mese di ottobre 2012presso Grafica Veneta Trebaseleghe (PD)

Tonolo_2400pt_def.pdf 4 06/09/12 09.49

Sommario

Introduzione ix

1 Impariamo a contare 11.1 Operazioni sugli insiemi finiti . . . . . . . . . . . . . . . . . . . . . 1

1.1.1 Richiami di teoria degli insiemi . . . . . . . . . . . . . . . . 11.1.2 La cardinalita` di un insieme finito . . . . . . . . . . . . . . . 4

1.2 Sequenze, collezioni, spartizioni, scomposizioni e partizioni . . . . . 51.3 Princ`pi fondamentali . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3.1 Principio di moltiplicazione . . . . . . . . . . . . . . . . . . 121.3.2 Principio di divisione . . . . . . . . . . . . . . . . . . . . . . 17

1.4 Spazi campionari e probabilita` uniforme . . . . . . . . . . . . . . . . 191.5 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2 Contare sequenze e collezioni 252.1 Sequenze e collezioni di elementi distinti . . . . . . . . . . . . . . . 25

2.1.1 Sequenze senza ripetizione . . . . . . . . . . . . . . . . . . . 252.1.2 Collezioni senza ripetizione (sottoinsiemi) . . . . . . . . . . . 28

2.2 Sequenze e collezioni arbitrarie . . . . . . . . . . . . . . . . . . . . . 382.2.1 Sequenze (con eventuali ripetizioni) e/o spartizioni . . . . . . 382.2.2 Collezioni (con eventuali ripetizioni) e/o risoluzioni

di numeri naturali . . . . . . . . . . . . . . . . . . . . . . . . 392.2.3 Risoluzioni con vincoli e disequazioni . . . . . . . . . . . . . 42

2.3 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3 Vincoli di occupancy 513.1 Sequenze e spartizioni con vincoli di occupancy . . . . . . . . . . . . 51

3.1.1 Sequenze e spartizioni con sequenza di occupancy:permutazioni e anagrammi . . . . . . . . . . . . . . . . . . . 51

3.1.2 Sequenze e spartizioni con collezione di occupancy . . . . . . 563.2 Collezioni e risoluzioni con vincoli di occupancy . . . . . . . . . . . 58

3.2.1 Collezioni e risoluzioni con sequenza di occupancy . . . . . . 583.2.2 Collezioni e risoluzioni con collezione di occupancy . . . . . 58

3.3 Numeri di Catalan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603.4 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

Tonolo_2400pt_def.pdf 5 05/09/12 10.16

vi Sommario

4 Inclusione/esclusione 674.1 Il principio di inclusione/esclusione . . . . . . . . . . . . . . . . . . 67

4.1.1 Cardinalita` di unione di insiemi . . . . . . . . . . . . . . . . 674.1.2 Cardinalita` di intersezioni di insiemi . . . . . . . . . . . . . . 71

4.2 Gli scombussolamenti . . . . . . . . . . . . . . . . . . . . . . . . . . 764.3 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

5 Partizioni, cicli e partizioni in cicli 815.1 Partizioni e numeri di Stirling . . . . . . . . . . . . . . . . . . . . . . 81

5.1.1 Il numero di n-partizioni di Ik . . . . . . . . . . . . . . . . . 815.1.2 Partizioni con vincolo di occupancy . . . . . . . . . . . . . . 86

5.2 Cicli e partizioni in cicli . . . . . . . . . . . . . . . . . . . . . . . . 875.2.1 Cicli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 875.2.2 Le n-partizioni in cicli di Ik . . . . . . . . . . . . . . . . . . 895.2.3 Partizioni in cicli con vincoli di occupancy . . . . . . . . . . 94

5.3 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

6 Manipolazione di somme 976.1 Alcune tecniche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

6.1.1 Il metodo di Gauss . . . . . . . . . . . . . . . . . . . . . . . 976.1.2 La tecnica di perturbazione . . . . . . . . . . . . . . . . . . . 986.1.3 Il metodo delle derivate . . . . . . . . . . . . . . . . . . . . . 99

6.2 Il calcolo finito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1006.2.1 Loperatore differenza e le potenze fattoriali discendenti . . . 1006.2.2 Primitive discrete e teorema fondamentale del calcolo discreto 1036.2.3 Primitive discrete di alcune funzioni notevoli . . . . . . . . . 105

6.3 La formula di addizione per parti . . . . . . . . . . . . . . . . . . . . 1126.4 Il criterio di convergenza di AbelDirichlet . . . . . . . . . . . . . . 1136.5 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

7 Serie formali e funzioni generatrici 1197.1 Serie formali: prime definizioni . . . . . . . . . . . . . . . . . . . . . 1197.2 Funzioni generatrici di una successione . . . . . . . . . . . . . . . . 1227.3 Serie formali composte e inverse . . . . . . . . . . . . . . . . . . . . 130

7.3.1 Somme infinite e composte di serie formali . . . . . . . . . . 1307.3.2 Serie formali invertibili . . . . . . . . . . . . . . . . . . . . . 135

7.4 Le forme chiuse di una serie formale . . . . . . . . . . . . . . . . . . 1397.4.1 Serie formale di Maclaurin e forme chiuse di serie formali . . 1397.4.2 Proprieta` delle forme chiuse . . . . . . . . . . . . . . . . . . 1427.4.3 Serie formali e convergenza: la forma chiusa somma . . . . . 1497.4.4 Forme chiuse di funzioni generatrici di successioni notevoli . 1517.4.5 Forme chiuse razionali . . . . . . . . . . . . . . . . . . . . . 160

7.5 Le funzioni generatrici di probabilita` . . . . . . . . . . . . . . . . . . 1667.6 Frazioni di serie formali . . . . . . . . . . . . . . . . . . . . . . . . . 170

Tonolo_2400pt_def.pdf 6 05/09/12 10.16

Sommario vii

7.6.1 Numeri di Bernoulli . . . . . . . . . . . . . . . . . . . . . . 1717.6.2 Equazioni di secondo grado in R[[X]] . . . . . . . . . . . . . 175

7.7 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

8 Calcolo simbolico 1818.1 Insiemi con valutazione . . . . . . . . . . . . . . . . . . . . . . . . . 1818.2 Operazioni tra insiemi compatibili con le OGF . . . . . . . . . . . . . 1838.3 Pattern nelle stringhe . . . . . . . . . . . . . . . . . . . . . . . . . . 190

8.3.1 Il teorema della scimmia . . . . . . . . . . . . . . . . . . . . 1978.4 Triangolazioni di un poligono convesso . . . . . . . . . . . . . . . . 1988.5 Alberi con radice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2018.6 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

9 Relazioni di ricorrenza 2079.1 Definizioni di base e modelli . . . . . . . . . . . . . . . . . . . . . . 2079.2 Relazioni lineari a coefficienti costanti . . . . . . . . . . . . . . . . . 214

9.2.1 Relazioni lineari omogenee a coefficienti costanti . . . . . . . 2169.2.2 Soluzioni particolari di una relazione di ricorrenza lineare . . 225

9.3 Relazioni lineari a coefficienti variabili . . . . . . . . . . . . . . . . . 2399.4 Relazioni Dividi e Conquista . . . . . . . . . . . . . . . . . . . . . 2429.5 Ricorrenze e funzioni generatrici . . . . . . . . . . . . . . . . . . . . 250

9.5.1 Ricorrenze lineari a coefficienti costanti e loro OGF . . . . . 2509.5.2 La OGF del Quicksort . . . . . . . . . . . . . . . . . . . . . 260

9.6 Dimostrazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2629.7 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268

10 Formule di approssimazione e di asintoticita` 27510.1 Le formule di Eulero Maclaurin di ordine 1 e 2 . . . . . . . . . . . 27510.2 Stime asintotiche con gli O grande e gli o piccolo: nozioni di base 28510.3 Versione asintotica delle formule di Eulero Maclaurin

di ordine 1 e 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29110.4 Approssimazione di somme di Cauchy . . . . . . . . . . . . . . . . . 299

10.4.1 Il caso 0 < < 1 . . . . . . . . . . . . . . . . . . . . . . . . 29910.4.2 Il caso = 1: le somme di Riemann . . . . . . . . . . . . . . 30610.4.3 Il caso > 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 310

10.5 Lo sviluppo di Eulero Maclaurin di ordine qualunque . . . . . . . . 31210.5.1 I numeri armonici generalizzati . . . . . . . . . . . . . . . . 31210.5.2 Polinomi di Bernoulli . . . . . . . . . . . . . . . . . . . . . . 31510.5.3 La formula di Eulero Maclaurin . . . . . . . . . . . . . . . 31910.5.4 Versioni asintotiche della formula di Eulero Maclaurin . . . 324

10.6 Approssimiamo il fattoriale e i binomiali . . . . . . . . . . . . . . . 32710.6.1 Successioni a due indici . . . . . . . . . . . . . . . . . . . . 32810.6.2 La formula di Stirling . . . . . . . . . . . . . . . . . . . . . 336

Tonolo_2400pt_def.pdf 7 05/09/12 10.16

viii Sommario

10.6.3 Funzioni e distribuzioni di Ramanujan . . . . . . . . . . . . . 34210.7 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347

A Tavole riassuntive 351A.1 Principali formule della combinatoria . . . . . . . . . . . . . . . . . 351A.2 Formule per il calcolo di primitive/somme indefinite discrete . . . . . 353A.3 Forme chiuse di alcune serie formali di uso frequente . . . . . . . . . 354A.4 Approssimazioni ed asintoticita` . . . . . . . . . . . . . . . . . . . . . 356

Bibliografia 357

Indice analitico 361

Tonolo_2400pt_def.pdf 8 05/09/12 10.16

Introduzione

Nella nostra attivita` didattica trattiamo da molti anni vari argomenti di caratte-re elementare generalmente svolti nei corsi di Matematica Discreta, alcuni deiquali trovano sempre piu` spazio nei programmi dei corsi tradizionali con contenutomatematico, come la combinatoria, il calcolo finito, le serie formali, le ricorrenze e letecniche di approssimazione di somme finite. Si tratta di argomenti che fanno partetradizionalmente del bagaglio iniziale di chi si occupa ad esempio di analisi degli al-goritmi. Nei testi che abbiamo consultato, spesso ci siamo imbattuti in due difficolta`:trattazioni nelle quali, una volta illustrati i concetti di base, la risoluzione dei proble-mi appare basata piu` su trucchi o abilita` dellautore che su tecniche precise; oppureargomentazioni applicative carenti ed incomplete da un punto di vista matematico.Questo risulta particolarmente evidente nei testi di combinatoria elementare, dovela parte teorica raramente fornisce strumenti sufficienti a trattare lenorme varieta` diproblemi concreti, ognuno dei quali sembra costituire un caso a se. Abbiamo percio`pensato innanzitutto di sviluppare nel corso di questi anni dei metodi che permettanoallo studente di inquadrare ogni problema in un ambito chiaro e definito. Dobbia-mo per questo ringraziare gli studenti che abbiamo involontariamente utilizzato comecavie e che hanno infine espresso notevole gradimento a quanto qui prodotto.

Nella parte di calcolo combinatorio, cerchiamo innanzitutto di ricondurre tuttii ragionamenti a pochi essenziali concetti di riferimento. Hanno un ruolo chiave lenozioni di sequenza e collezione, che preferiamo ai termini disposizione e combina-zione, a nostro avviso potenzialmente ambigui e non facili da ricordare: perche mai,di fronte allesperienza quotidiana, una combinazione dovrebbe essere un insiemenon ordinato di simboli? Trattiamo poi i classici princ`pi di moltiplicazione e divi-sione in modo preciso ed approfondito. Sorvolare velocemente su tali argomenti, edil conseguente loro uso improprio, e` a nostro parere la causa principale degli errorinella risoluzione dei problemi. Esaminiamo poi in dettaglio i problemi con vincolo dioccupancy, il principio di inclusione/esclusione ed infine le partizioni.

Introduciamo poi varie tecniche per il calcolo delle somme di un numero finitodi termini di una successione; particolare attenzione e` dedicata al calcolo finito cheriproduce nel caso discreto le tecniche del calcolo infinitesimale.

Nellampia parte dedicata alle serie formali e le funzioni generatrici, introdottele prime definizioni e proprieta` di base, accompagniamo il lettore attraverso i concettidelicati di forma chiusa e composta di serie formali. Teniamo ben distinti il concet-to algebrico di serie formale da quello analitico di serie di potenze, che coinvolgeinevitabilmente problemi di convergenza, sfruttandone tuttavia appieno la sinergia.

Tonolo_2400pt_def.pdf 9 05/09/12 10.16

x Introduzione

Calcoliamo in modo elementare le funzioni generatrici delle principali successioni dinumeri notevoli, come i numeri armonici, i binomiali, i numeri di Stirling, Bell, Ber-noulli, Catalan, Fibonacci. Le applicazioni in questo capitolo affrontano raffinati pro-blemi di conteggio con vincoli, e, per chi conosce qualcosa di probabilita`, il calcolodei momenti (valore atteso e varianza) delle principali variabili aleatorie discrete.

Le funzioni generatrici entrano poi in gioco anche nei capitoli successivi tantonelle tecniche dimostrative quanto in molteplici ulteriori applicazioni. Ad esempioaffrontiamo il cosiddetto calcolo simbolico che permette tra laltro di contare, dato unpattern in un alfabeto con un dato numero di lettere, il numero di parole di lunghezzaassegnata che non lo contengono: troviamo cos` il numero medio di caratteri che unascimmia (che batte i tasti a caso su una tastiera) deve digitare affinche esca la famosafrase to be or not to be.

Le relazioni di ricorrenza costituiscono forse la parte del testo piu` vicina alletrattazioni tradizionali. Dopo alcuni problemi classici che le motivano passiamo adanalizzare in dettaglio le relazioni di ricorrenza lineari e le loro soluzioni. Offria-mo anche un metodo risolutivo basato sulle funzioni generatrici. Il legame tra serieformali e ricorrenze torna utile per le dimostrazioni di tutti gli enunciati relativi allastruttura delle soluzioni delle ricorrenze trattate, che, per non appesantire la lettura,abbiamo condensato in una sezione dedicata. Il capitolo termina poi con le relazionidel tipo dividi e conquista, utili nello studio della complessita` di vari algoritmi, e lastima a priori delle loro soluzioni.

Nellultima parte del testo ci occupiamo dellapprossimazione di somme finite edella stima asintotica delle ridotte di una serie numerica generata dai valori sui natura-li di funzioni regolari. Lo strumento basilare del capitolo risulta essere lo sviluppo diEulero-Maclaurin che permette di approssimare le somme considerate con lintegraledella funzione e altri addendi. Abbiamo pensato ad un percorso semplice che si limitaagli sviluppi di ordine 2; questi sono dimostrati in modo elementare evitando lo stu-dio approfondito dei numeri e dei polinomi di Bernoulli, necessario per gli sviluppidi ordine superiore. Tale percorso permette comunque di raggiungere tutti i risultatiimportanti, compresa la dimostrazione della famosa formula di Stirling di approssi-mazione del fattoriale. In tal caso lordine di asintoticita` del fattoriale (quindi la suastima a meno di una costante moltiplicativa) deriva immediatamente dalle formule diEulero-Maclaurin, mentre, per i lettori piu` attenti, il calcolo della costante richiedeuna analisi fine delle successioni a due indici, presentate qui in modo il piu` possi-bile chiaro e semplice. Questultime permettono poi di ottenere una stima asintoticadelle funzioni Q di Ramanujan, di frequente utilizzo nel calcolo combinatorio. Percompletezza presentiamo infine, in tutti i dettagli, lo sviluppo di Eulero-Maclaurin diqualunque ordine.

Il testo e` corredato da numerosi esempi interamente svolti ed esercizi, in granparte risolti alla pagina web www.math.unipd.it/librocombinatoria.Suggeriamo allo studente di provare sempre a cimentarsi da solo con gli eserciziprima di leggerne la soluzione. Infine delle tavole riassuntive delle principali formulepermettono al lettore unagile consultazione.

Tonolo_2400pt_def.pdf 10 05/09/12 10.16

Introduzione xi

Il libro si presta a diversi possibili percorsi. Potrebbero essere trattati in modo indi-pendente la parte di calcolo combinatorio (Capitoli 1-5), le somme ed il calcolo finito(Capitolo 6), le serie formali (Capitolo 7) e le loro applicazioni al calcolo simbolico(Capitolo 8), le relazioni di ricorrenza (Capitolo 9), le tecniche di approssimazione(Capitolo 10).

Saremo grati a coloro i quali ci segnaleranno allindirizzo di posta [email protected] suggerimenti, commenti ed eventualierrori.

Nel testo alcune parti sono indicate con dei simboli. Il simbolo e` general-mente attribuito a considerazioni che riteniamo importante non sottovalutare; se-gnala invece le parti piu` complicate o fastidiose che possono essere tralasciate senzacompromettere la comprensione degli altri contenuti.

Infine una parola su di noi. Siamo entrambi veneziani, e questo e` forse lunicoaspetto che ci accomuna. Carlo Mariconda si occupa di Analisi Matematica, mentreAlberto Tonolo di Algebra. Le inevitabili diversita` dei punti di vista sulle questionimatematiche, oltre che su ogni altro dettaglio, giustificano in parte la durata dellapreparazione di questo libro che si e` protratta nellarco di una decina di anni. Ognipagina scritta da ciascuno di noi e` stata dapprima aspramente criticata dallaltro, perpoi, modificata, giungere ad una sintesi soddisfacente per entrambi. Speriamo che illettore accolga con favore il prodotto di questo distillato.

Tonolo_2400pt_def.pdf 11 05/09/12 10.16

Tonolo_2400pt_def.pdf 12 05/09/12 10.16

1 Impariamo a contare

Contenuto1.1 Operazioni sugli insiemi finiti1.2 Sequenze, collezioni, spartizioni, scomposizioni e partizioni1.3 Princ`pi fondamentali1.4 Spazi campionari e probabilita` uniforme1.5 Esercizi

In questo capitolo, dopo un veloce richiamo dei concetti della teoria degli insiemi,introdurremo le nozioni ed i princ`pi fondamentali del calcolo combinatorio, equindi introdurremo la probabilita` uniforme su spazi campionari finiti.

1.1 Operazioni sugli insiemi finiti

Questa sezione e` dedicata allapprendimento delle operazioni di base e delle primetecniche di conteggio.

1.1.1 Richiami di teoria degli insiemi

Introduciamo il concetto di insieme in modo ingenuo: una trattazione assiomaticarigorosa esula dagli scopi di questo testo.

Un insieme e` definito quando comunque dato un oggetto si sa dire se esso ap-partiene o meno allinsieme. Gli oggetti appartenenti ad un insieme vengono dettielementi dellinsieme. Essi possono essere qualsiasi cosa: numeri, persone, oggetti,altri insiemi, ...

Le isole della laguna di Venezia definiscono un insieme. Qualunque cosa si con-sideri, sappiamo decidere se si tratta o meno di un elemento di tale insieme: il nume-ro 3, gli Stati Uniti, Padova e molte altre cose ad esempio non appartengono a taleinsieme; le isole di Murano, Mazzorbo e Torcello si.

Tonolo_2400pt_def.pdf 13 05/09/12 10.16


Gli insiemi che non appartengono a se stessi non formano un insieme: infatti se for-massero un insieme I , dato lelemento insieme I non si saprebbe decidere se essoappartiene o no ad I . Infatti se vi appartenesse, allora, in quanto elemento di I , nondovrebbe appartenere a se stesso, e quindi non apparterebbe ad I : contraddizione.Se invece non vi appartenesse, allora, per la definizione di I , dovrebbe appartenervi:contraddizione.

Due insiemi sono uguali se e solo se gli elementi che stanno in uno, stanno anchenellaltro; in particolare, ad esempio, {1, 1, 2} e {1, 2} sono insiemi coincidenti percheentrambi contengono il numero 1, il numero 2 e nientaltro.

Per dire che un elemento a appartiene ad un insieme A scriveremo a A.Nel descrivere formalmente un insieme o ne elenchiamo gli elementi, ad

esempio {2, 4, 5, 7, 1}, o, con qualche attenzione, descriviamo la qualita` che necontraddistingue gli elementi, ad esempio {le automobili rosse}.

Nel seguito denotiamo con N, N1, Z, Q, R e C rispettivamente gli insiemi deinumeri naturali, naturali diversi da zero, interi, razionali, reali e complessi.

Ricordiamo brevemente alcune nozioni insiemistiche ben note che useremo intutto il volume.

Definizione 1.1 Dati due insiemi A e B, diciamo che A e` un sottoinsieme di B (escriveremo A B) se A e` contenuto in B , ovvero se

(a A) (a B).

Definizione 1.2 Sia X un insieme. Indichiamo con P(X) linsieme delle parti di X ,ovvero linsieme dei sottoinsiemi di X , compresi il sottoinsieme vuoto ed X stesso.

Esempio 1.3 Sia X = {1, 2}; allora linsieme delle parti di X e`

P(X) = {, {1}, {2}, X}.

Si osservi che P() = {} = : infatti P() ha un elemento (linsieme vuoto),mentre non ha alcun elemento.

Definizione 1.4 Siano A, B sottoinsiemi di un insieme X ; allora lunione,lintersezione e la differenza di A e B, e il complementare Ac di A in Xsono cos` definiti:

A B = {x X : x A o x B}; A B = {x X : x A e x B}; A \ B = {x X : x A e x / B}; Ac = {x X : x / A}.`E facile verificare le seguenti semplici proprieta`.

Tonolo_2400pt_def.pdf 14 05/09/12 10.16

1.1 Operazioni sugli insiemi finiti 3

Proposizione 1.5 Sia X un insieme ed A, B e C tre suoi sottoinsiemi. Allora si ha

1. A (B C) = (A B) (A C);2. A (B C) = (A B) (A C);3. A \ (B C) = (A \ B) (A \ C);4. A \ (B C) = (A \ B) (A \ C);5. (A B)c = Ac Bc;6. (A B)c = Ac Bc.

Dimostrazione. A titolo di esempio verifichiamo luguaglianza

A \ (B C) = (A \ B) (A \ C).Due insiemi coincidono se e solo se hanno gli stessi elementi; pertanto per dimostrarelassunto controlleremo che se un elemento x di X appartiene ad A \ (B C), alloraappartiene anche ad (A\B)(A\C), e viceversa, che se un elemento x di X appartienead (A \ B) (A \ C) allora appartiene anche ad A \ (B C). Sia x A \ (B C);allora x appartiene ad A, ma non appartiene ne a B, ne a C . Pertanto x appartienesia ad A \ B che ad A \ C , e quindi appartiene allintersezione (A \ B) (A \ C).Viceversa sia x (A \ B) (A \ C); allora x appartiene sia ad A \ B che ad A \ C .Dunque x appartiene ad A, ma non appartiene ne a B, ne a C , ovvero non appartienea B C . Pertanto x appartiene ad A \ (B C).

X Y

x1

x4x5 y3

x1x2x3

y1

y2

1f (y )1Im( f)

Figura 1.1. Un esempio di funzione.

La seguente nozione permette di collegaredue insiemi.

Definizione 1.6 Una funzione

f : X Y consiste di:1. un insieme X detto dominio di f ;2. un insieme Y detto codominio di f ;3. una legge che ad ogni elemento x in X as-

socia uno ed un solo elemento y in Y . Taleelemento e` detto immagine di x tramitef ed e` indicato con f (x).

Dato y Y linsieme {x X : f (x) = y} e` detto controimmagine o antiimmaginedi y tramite f ed e` indicato con f 1(y). Il sottoinsieme { f (x) : x X} di Y e` dettoimmagine di f ed e` indicato con Im( f ).Ricordiamo anche la seguente classificazione delle funzioni.

Definizione 1.7 Una funzione f : X Y si dice iniettiva se ( f (x) = f (y)) (x = y), ovvero elementi distinti del dominio

hanno immagini distinte;

Tonolo_2400pt_def.pdf 15 05/09/12 10.16


suriettiva se Im( f ) = Y , ovvero se ogni elemento del codominio e` immagine diqualche elemento del dominio;

biiettiva se e` iniettiva e suriettiva; in tal caso diremo che X ed Y sono incorrispondenza biunivoca.

Dati due insiemi A e B possiamo considerare linsieme delle coppie realizzateprendendo nellordine un elemento di A ed uno di B. Piu` in generale:

Definizione 1.8 Dati n insiemi A1, ..., An , il loro prodotto cartesiano e` linsiemeA1 ... An delle n-uple (a1, ..., an) con ai Ai , i = 1, ..., n. Il prodotto cartesianoA ... A

n volte

viene indicato con An .

Il prodotto cartesiano e` una costruzione formale molto utilizzata in matematica percostruire insiemi complessi a partire da insiemi semplici. Si osservi che, dati dueinsiemi distinti A e B, gli insiemi A B e B A sono distinti! Tra i due insiemi e`pero` possibile costruire una corrispondenza biunivoca:

f : A B B A, (a, b) (b, a)

e` ovviamente una funzione biiettiva.

1.1.2 La cardinalit di un insieme finito

Caratteristica fondamentale di un insieme finito e` la sua grandezza.

Definizione 1.9 La cardinalita` di un insieme finito X e` il numero dei suoi elementidistinti. Tale numero viene indicato con il simbolo |X |.Per contare il numero di elementi di un insieme, spesso sara` conveniente interpretar-lo come unione, o intersezione o prodotto (o altro ancora) di insiemi piu` semplici.`E dunque importante saper calcolare la cardinalita` di un insieme ottenuto con talioperazioni.

Proposizione 1.10 Siano A, B due sottoinsiemi finiti di un insieme X .

1. Se A e B sono disgiunti, ovvero A B = , allora |A B| = |A| + |B|;2. |A B| = |A| + |B| |A B|;3. |A B| = |A| |B|;4. Se X e` finito allora |Ac| = |X | |A|.Dimostrazione. Siano A = {a1, ..., am} e B = {b1, ..., bn} due insiemi di cardinalita`rispettive |A| = m e |B| = n.1. Se A e B sono disgiunti allora A B = {a1, ..., am, b1, ..., bn} ha m + n elementi.

Tonolo_2400pt_def.pdf 16 05/09/12 10.16

1.2 Sequenze, collezioni, spartizioni, scomposizioni e partizioni 5

2. A B e` lunione degli insiemi a due a due disgiunti A \ B, A B, B \ A; essendoA unione disgiunta di A \ B e A B, si ha |A \ B| = |A| |A B|. Allora

|A B| = |A \ B| + |A B| + |B \ A|= |A| |A B| + |A B| + |B| |A B|= |A| + |B| |A B|.

3. Chiaramente

A B = ({a1} B) ({a2} B) ... ({am} B) ,con gli {a1} B a due a due disgiunti. Linsieme {a1} B ha n elementi:

(a1, b1), (a1, b2), ..., (a1, bn).

Analogamente |{ai } B| = n per qualunque elemento ai di A. Per il punto 1 si ha|A B| = |{a1} B| + ...+ |{am} B| = m n.

4. Essendo X = AAc e AAc = , si ha |X | = |A|+|Ac|, da cui |Ac| = |X ||A|.

Proposizione 1.11 Due insiemi finiti X ed Y hanno la stessa cardinalita` se e solo seX e` in corrispondenza biunivoca con Y .

Dimostrazione. Se |X | = |Y | = n, possiamo indicare con x1, ..., xn tutti gli elementidi X e con y1, ..., yn tutti gli elementi di Y . In tal caso lapplicazione che mandaxi in yi , i = 1, ..., n, e` una biiezione. Viceversa se f : X Y e` una biiezione,e |X | = n, siano x1, ..., xn tutti gli elementi di X . Allora f (x1), ..., f (xn) sonodistinti (essendo f iniettiva) e costituiscono lintero insieme Y (essendo f suriettiva).Pertanto Y = { f (x1), ..., f (xn)} ha cardinalita` n.

Esempio 1.12 Contare il numero di possibili comitati composti da un uomo ed unadonna scelti da un insieme U di 8 uomini e D di 10 donne.Soluzione. Sia Y linsieme di tali comitati; ogni elemento di Y si rappresenta in modounico come una coppia (u, d) dove u e` uno degli uomini e d una delle donne. EssendoY in corrispondenza biunivoca con U D, si ha |Y | = 8 10 = 80.

1.2 Sequenze, collezioni, spartizioni, scomposizioni e partizioni

Introduciamo la terminologia che ci permettera` di descrivere con precisione le variesituazioni che ci troveremo a studiare.

Nel seguito tratteremo insiemi finiti; per semplicita`, associando un numero adogni elemento, identificheremo un insieme X con n elementi con linsieme In dei

Tonolo_2400pt_def.pdf 17 05/09/12 10.16


numeri 1, ..., n dotato dellordine naturale:

n N1 In = ({1, ..., n},


Osservazione 1.14 (Casi limite) Con riferimento alle nozioni introdotte nella Defi-nizione 1.13, chiariamo i seguenti casi, certo non particolarmente significativi nelleapplicazioni:

a1) Per ogni n N esiste una ed una sola 0-sequenza di In: la sequenza vuota. Perogni k 1, non esistono k-sequenze di I0.

a2) Per ogni n N esiste una ed una sola n-spartizione di I0: (, ..., n-volte

). Per ogni

k 1, non esistono 0-spartizioni di Ik .a3) Per ogni n N esiste una ed una sola n-risoluzione di 0: la n-sequenza

(0, ..., 0 n-volte

). Per ogni k 1, non esistono 0-risoluzioni di k.

b1) Per ogni n N esiste una ed una sola 0-collezione di In: la collezione vuota.Per ogni k 1, non esistono k-collezioni di I0.

b2) Vi e` una ed una sola 0-partizione di I0: la partizione vuota. Per ogni n N1non esistono ne 0-partizioni di In , ne n-partizioni di I0.

Si presti attenzione alla differenza tra partizione e spartizione:

gli insiemi che formano una spartizione possono esser vuoti, e sono elencati inordine;

gli insiemi che formano una partizione devono essere non vuoti, e il loro ordinenon conta.

3, 7 5, 1, 6 2, 4

3, 7 5, 1, 6 2, 4

5

1

62

4

7

3

I 7

1 3 4

1 2 3 4

2

Figura 1.2. Schematizzazione di una 4-spartizione di I7, una 4-risoluzione di 7, ed una3-partizione di I7.

Tonolo_2400pt_def.pdf 19 05/09/12 10.16


Definizione 1.15 Data una k-sequenza (a1, ..., ak) di In , diciamo permutazione di(a1, ..., ak) ogni altra k-sequenza (b1, ..., bk) di In tale che [a1, ..., ak] = [b1, ..., bk],ovvero ogni altra k-sequenza che si ottiene riordinando in qualunque modo glielementi a1, ..., an .

Abbiamo preso a prestito dal linguaggio comune i termini di sequenza, collezione,spartizione, risoluzione, partizione, permutazione e li abbiamo trasformati in terminitecnici assegnando loro un preciso significato. I significati tratti dal vocabolario, diseguito riportati, ci sembra possano permettere di ricordare il significato tecnico chedora in poi assumeranno nelle pagine seguenti:

sequenza: serie ordinata di cose o fatti che si susseguono. Una sequenza di disgrazie.Serie di inquadrature successive.

spartizione: lo spartire, lessere spartito. Divisione, distribuzione. La spartizionedelleredita`.

risoluzione: soluzione, scioglimento, suddivisione in componenti.collezione: raccolta sistematica di oggetti della stessa specie che abbiano interesse

storico, artistico o scientifico. Collezione di monete, di francobolli, difigurine.

partizione: il dividere, lessere suddiviso in piu` parti.permutazione: lo scambiare una cosa con unaltra.

Le nozioni introdotte si rivelano particolarmente utili per descrivere in modo pre-ciso diverse situazioni frequenti nel calcolo combinatorio. Ad esempio, le sequenzee collezioni ben descrivono le diverse tipologie di estrazioni (totocalcio, lotto, ...); lenozioni di spartizione e risoluzione, introdotte qui e non diffuse in letteratura, tornanoutili ad esempio nella descrizione della distribuzione di oggetti (caramelle a bambi-ni, libri a studenti, ...); le partizioni permettono di trattare le suddivisioni in partidi insiemi di oggetti (formazione di squadre, suddivisione di una comitiva in tavolial ristorante, ...); le permutazioni infine si occupano di problemi di rimescolamento(anagrammi di parole o codici).

Esempio 1.16 Alcuni esempi degli oggetti definiti in 1.13.

(1, 1, 3, 2, 2) e (1, 3, 1, 2, 2) sono due 5-sequenze distinte di I4; la 5-sequenza ({1, 4},, {3}, {2},) e` una 5-spartizione di I4; la 4-sequenza (1, 0, 1, 3) e` una 4-risoluzione di 5. [1, 1, 3, 2, 2] e cos` pure [1, 3, 2, 1, 2] rappresentano la 5-collezione di I4 che

contiene due 1, due 2, un 3 e zero 4; la 2-collezione [{2}, {1, 3, 4}] e` una 2-partizione di I4; le sequenze (2, 2, 3, 5), (2, 2, 5, 3), (2, 3, 2, 5), (2, 5, 2, 3), (2, 3, 5, 2), (2, 5, 3, 2),(3, 2, 2, 5), (5, 2, 2, 3), (3, 2, 5, 2), (5, 2, 3, 2), (3, 5, 2, 2), (5, 3, 2, 2) sono tutte esole le permutazioni della 4-sequenza (2, 3, 2, 5) di I5.

Tonolo_2400pt_def.pdf 20 05/09/12 10.16


Esempio 1.17 (Estrazioni di numeri) Siano ,m N1. Le estrazioni di numeridi Im possono essere ordinate o non ordinate: ad ogni estrazione corrisponde nelprimo caso una -sequenza di Im , nel secondo una -collezione di Im . A seconda chelestrazione avvenga con o senza reimmissione, le sequenze e le collezioni ottenutesono con o senza possibili ripetizioni.Ad esempio estraiamo 3 numeri da I4. La 3-sequenza (2, 4, 2) rappresenta una estra-zione ordinata dei numeri 2, 4, 2. La collezione [2, 2, 4] rappresenta una estrazionenella quale, senza tenere conto dellordine, sono stati estratti due volte il 2 ed unavolta il 4.

Esempio 1.18 (Distribuzioni di oggetti) Siano ,m N1. Le distribuzioni di ca-ramelle a m bambini, etichettati rispettivamente con I ed Im , si distinguono a secondache

le caramelle siano tutte diverse tra loro: ogni tale distribuzione individua univo-camente (ed e` individuata dal) la m-spartizione (C1, ...,Cm) dellinsieme I dellecaramelle, dove Ci e` il sottoinsieme delle caramelle che vengono date al bambino i .

Ad esempio distribuiamo 3 caramelle a due bambini. Se le caramelle sono tutte di-verse, la distribuzione della caramella 1 al bambino 2 e delle rimanenti caramelle 2e 3 al bambino 1 e` descritta dalla 2-spartizione ({2, 3}, {1}) di I3. La 2-spartizione({1}, {2, 3}) invece descrive la distribuzione della caramella 1 al bambino 1 e dellerimanenti caramelle 2 e 3 al bambino 2.

le caramelle siano uguali: in tal caso ogni distribuzione individua univocamente(ed e` individuata dal) la m-risoluzione (n1, ..., nm) di , dove ni e` il numero dicaramelle date al bambino i .

Ad esempio, se le caramelle sono uguali e si danno due caramelle al bambino 1 eduna al bambino 2, allora resta individuata la 2-risoluzione (2, 1) di 3. La 2-risoluzione(1, 2) di 3 descrive invece il caso in cui il bambino 1 riceve una sola caramella, mentreil bambino 2 ne riceve due.

Esempio 1.19 (Funzioni tra insiemi finiti) Siano ,m N1. Una qualunque fun-zione f : I Im individua univocamente ed e` individuata da ciascuno dei seguentioggetti:

1. la -sequenza ( f (1), ..., f ()) di Im ;2. la m-spartizione ( f 1(1), ..., f 1(m)) di I.La funzione f e`: iniettiva se e solo se la sequenza ( f (1), ..., f ()) non ha ripetizioni o equivalente-

mente, ciascuna componente della spartizione ( f 1(1), ..., f 1(m)) ha cardinalita`al piu` uguale a 1; in tal caso necessariamente m.

Tonolo_2400pt_def.pdf 21 05/09/12 10.16


suriettiva se e solo se nella sequenza ( f (1), ..., f ()) compaiono almeno unavolta tutti gli elementi di Im , o equivalentemente se e solo se nella spartizione( f 1(1), ..., f 1(m)) delle controimmagini non compare mai linsieme vuoto. Intal caso necessariamente m .

Osservazione 1.20 Ogni permutazione della sequenza ( f (1), ..., f ()) determinatada una funzione f : I Im determina ancora una funzione I Im . La nuovafunzione ottenuta e` iniettiva (risp. suriettiva) se e solo se lo era la funzione f dipartenza.

Esempio 1.21 Sia f : I5 I3 la funzione definita ponendof (1) = f (3) = 1, f (2) = f (4) = f (5) = 2.

La sequenza individuata dalla funzione f e` la 5-sequenza (1, 2, 1, 2, 2) di I3 le cuicomponenti sono le immagini degli elementi di I5 dotato dellordine naturale; la spar-tizione individuata da f e` la 3-spartizione ({1, 3}, {2, 4, 5},) delle controimmaginidegli elementi di I3 dotato dellordine naturale. La f non e` una funzione iniettiva:nella sequenza (1, 2, 1, 2, 2) vi sono ripetizioni, come analogamente nella spartizio-ne ({1, 3}, {2, 4, 5},) vi sono componenti di cardinalita` maggiore di 1. La f non e`una funzione suriettiva: nella sequenza (1, 2, 1, 2, 2) non compare il 3, come analoga-mente la collezione [{1, 3}, {2, 4, 5},] associata alla spartizione ({1, 3}, {2, 4, 5},)delle controimmagini non e` una partizione di I3. Ogni permutazione della sequenza(1, 2, 1, 2, 2) determina una funzione I5 I3 che certamente non e` ne suriettiva, neiniettiva.

1

2

3

4

5

I31

2

3

I5

1 2 31

3 2 45

Figura 1.3. Funzione f : I5 I3 e schematizzazione della corrispondente 3-spartizioneassociata ad f .

Esempio 1.22 Vi e` una sorta di dualismo tra le nozioni di sequenza e di spartizione,e tra le nozioni di collezione e risoluzione.

1. Consideriamo la 8-sequenza (5, 5, 1, 1, 4, 2, 4, 1) di I5; indichiamo con C1 ={3, 4, 8} linsieme delle posizioni dove compare 1, C2 = {6} linsieme delleposizioni dove compare 2, C3 = linsieme delle posizioni dove compare 3,C4 = {5, 7} linsieme delle posizioni dove compare 4, ed infine C5 = {1, 2}

Tonolo_2400pt_def.pdf 22 05/09/12 10.16


linsieme delle posizioni dove compare 5. La sequenza (C1, ...,C5) e` una 5-spartizione di I8. Viceversa, la 5-spartizione ({3, 4, 8}, {6},, {5, 7}, {1, 2}) di I8determina la 8-sequenza di I5 di partenza dove 1 compare nelle posizioni tre, quat-tro e otto; 2 compare in posizione sei, il 4 compare nelle posizioni cinque e setteed infine il 5 nelle posizioni uno, due.

2. Consideriamo la 8-collezione [5, 5, 1, 1, 4, 2, 4, 1] di I5; indichiamo con k1 = 3 ilnumero di ripetizioni di 1, k2 = 1 il numero di ripetizioni di 2, k3 = 0 il numero diripetizioni di 3, k4 = 2 il numero di ripetizioni di 4, k5 = 2 il numero di ripetizionidi 5. La sequenza (k1, ..., k5) e` una 5-risoluzione di 8. Viceversa, la 5-risoluzione(3, 1, 0, 2, 2) di 8 determina la 8-collezione di I5 di partenza dove 1 compare trevolte, 2 compare una volta, 3 non compare, 4 compare due volte e 5 compare 2volte.

In generale vale il seguente immediato ma illuminante risultato che mette in cor-rispondenza k-sequenze di In e n-spartizioni di Ik , nonche k-collezioni di In en-risoluzioni di k:

Teorema 1.23 (Corrispondenze sequenze-spartizioni e collezioni-risoluzioni)Siano n, k N.1. Associando ad ogni n-spartizione (C1, ...,Cn) di Ik la k-sequenza (a1, ..., ak) di

In , dove ai e` lindice dellinsieme che contiene i (ovvero ai = j se i sta in C j ) siottiene una corrispondenza biunivoca tra le n-spartizioni di Ik e le k-sequenze diIn .

2. Associando ad ogni n-risoluzione (k1, ..., kn) di k la k-collezione di In

[1, ..., 1 k1

, ..., n, ..., n kn

]

formata da k1 termini uguali a 1, ..., kn termini uguali a n si ottiene unacorrispondenza biunivoca tra le n-risoluzioni di k e le k-collezioni di In .

2, 5

(2, 1, 2, 2, 1)

1 2 3

1,3,4

3+

1+

4

1 1 1

2

3 3 3 3

Figura 1.4. A sinistra: schematizzazione di una 3-spartizione di I5 e la corrispondente5-sequenza di I3 - A destra: una 3-risoluzione di 8 e la schematizzazionedella corrispondente 8-collezione di I3.

Dimostrazione. 1. Siano (C1, ...,Cn) e (D1, ..., Dn) due diverse n-spartizioni di Ik .Esiste allora un numero 1 j k ed un indice 1 i n tale che j Ci e j /

Tonolo_2400pt_def.pdf 23 05/09/12 10.16


Di . Le sequenze associate alle spartizioni (C1, ...,Cn) e (D1, ..., Dn) differisconoallora almeno nella j-esima componente: nella prima trovo i , nella seconda qualcosa= i . La funzione descritta nellenunciato e` pertanto iniettiva; vediamo che e` anchesuriettiva. Si consideri una qualunque k-sequenza (a1, ..., ak) di In; indico con Ci ,i = 1, ..., n, il sottoinsieme di Ik formato dalle posizioni occupate dal numero i nellasequenza (a1, ..., ak). La sequenza (C1, ...,Cn) cos` ottenuta e` una n-spartizione diIk a cui corrisponde per costruzione la sequenza (a1, ..., ak).2. Ogni collezione di In e` univocamente individuata dal numero di ripetizioni di 1, 2,..., n.

Osservazione 1.24 Nella prima corrispondenza stabilita nel Teorema 1.23 la k-sequenza (a1, ..., ak) ha esattamente |Ci | ripetizioni di i per ogni i in {1, ..., n}; inparticolare le k-sequenze di In dove compaiono almeno una volta tutti gli elementi diIn corrispondono alle n-spartizioni di Ik formate da insiemi non vuoti. Analogamen-te, nella seconda corrispondenza stabilita nel Teorema 1.23, le k-collezioni di In dovecompaiono almeno una volta tutti gli elementi di In corrispondono alle n-risoluzionidi k in naturali di N1.

1.3 Princ`pi fondamentali

In questa sezione evidenzieremo due princ`pi che saranno continuamente utilizzatinei problemi di conteggio.

1.3.1 Principio di moltiplicazione

Spesso capitera` di dover contare la cardinalita` di certi insiemi, la cui strutturageneralizza quella del prodotto cartesiano.

Esempio 1.25 Estraiamo uno dopo laltro due numeri da unurna contenente 10 pal-line numerate da 1 a 10. Consideriamo linsieme X di tutte le possibili coppie ordi-nate ottenibili con questa estrazione. Linsieme X e` costituito dalle coppie (a, b) cona X1 = {1, ..., 10} e b X2(a) = {1, ..., 10} \ {a}. Si presti attenzione al fatto chelinsieme di numeri nel quale si sceglie la seconda componente dipende dalla sceltafatta per la prima componente, mentre invece la sua cardinalita` e` comunque sempreuguale a 9.

Definizione 1.26 Sia k N1. Dati i numeri naturali m1, ..., mk , diciamo prodottocondizionato di molteplicita` (m1, ...,mk) un insieme X di k-sequenze (x1, ..., xk)dove:

x1 appartiene ad un insieme X1 di m1 elementi, per ogni scelta di x1, la componente x2 sta in un insieme X2(x1), che puo` dipendere

da x1, comunque formato da m2 elementi; ...

Tonolo_2400pt_def.pdf 24 05/09/12 10.16

1.3 Princ`pi fondamentali 13

per ogni scelta di x1, ..., xk1, la componente xk sta in un insieme Xk(x1, ..., xk1),che puo` dipendere da x1, ..., xk1, comunque formato da mk elementi.

Esempio 1.27 1. Linsieme X dellEsempio 1.25 e` un prodotto condizionato dimolteplicita` (10, 9).

2. Il prodotto cartesiano X1 ...Xk di insiemi di cardinalita` rispettivamente m1, ...,mk e` un caso particolare di prodotto condizionato di molteplicita` (m1, ...,mk); intal caso linsieme Xi in cui viene scelta la i-esima componente non dipende dallascelta delle precedenti i 1 componenti.

3. Linsieme X delle coppie ordinate formate da numeri compresi tra 1 e 20 nonentrambi pari o non entrambi dispari e` un prodotto condizionato di molteplicita`(20, 10): infatti X e` formato dalle coppie (x1, x2) con x1 X1 = I20 e x2 X2(x1) dove, se x1 e` pari, allora X2(x1) = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}, men-tre se x1 e` dispari, allora X2(x1) = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}. LinsiemeX1 ha cardinalita` 20, mentre X2(x1) ha cardinalita` 10 qualunque sia x1 X1.

Osservazione 1.28 Si osservi che se X e` un prodotto condizionato di molteplicita`(m1,m2, ...,mk) come nella Definizione 1.26, allora per ogni x1 X1 linsieme

{(x2, ..., xk) : (x1, x2, ..., xk) X}

e` un prodotto condizionato di molteplicita` (m2, ...,mk).

Teorema 1.29 (Principio di moltiplicazione) Un prodotto condizionato di moltepli-cita` (m1, ...,mk) ha m1 ... mk elementi.Dimostrazione. Svolgiamo la dimostrazione per induzione su k. Il caso k = 1 e` im-mediato, dato che un prodotto condizionato di molteplicita` m1 e` un insieme con m1elementi. Sia ora k > 1 e supponiamo vera laffermazione per k1. Sia X un prodottocondizionato di moltepicita` (m1, ...,mk). Indichiamo con {x1, ..., xm1} linsieme nelquale si sceglie la prima componente delle sequenze che compongono il prodottocondizionato X . Per ogni i = 1, ...,m1, le sequenze di X che iniziano con xi sonotante quante gli elementi di un prodotto condizionato di molteplicita` (m2, ...,mk) (ve-di lOsservazione 1.28). Per ipotesi induttiva, per ogni i = 1, ...,m1, vi sono quindim2 ... mk sequenze in X che iniziano con xi . Linsieme X e` lunione degli m1sottoinsiemi disgiunti formati dalle sequenze che cominciano con xi , i = 1, ...,m1,ciascuno dei quali ha cardinalita` m2 ...mk . Per la Proposizione 1.10 si concludeche |X | = m1 m2 ... mk .

Osservazione 1.30 Un insieme A e` in corrispondenza biunivoca con un prodottocondizionato di molteplicita` (m1, ...,mk), e quindi ha m1 ... mk elementi, sei suoi elementi sono i risultati di una procedura suddivisibile in k fasi successive, perla quale

Tonolo_2400pt_def.pdf 25 05/09/12 10.16


1. la prima fase abbia m1 diversi esiti possibili, e, qualunque siano gli esiti delle primei fasi, 1 i k 1, vi siano mi+1 diversi esiti possibili per la fase (i + 1)-esima,

2. esiti parziali distinti nelle k fasi conducano ad elementi distinti di A (o, equiva-lentemente, ogni elemento di A determini univocamente gli esiti parziali delle kfasi che lo individuano).

Il punto 1 garantisce lesistenza di una mappa suriettiva tra un prodotto condizionatodi molteplicita` (m1, ...,mk) ed A, mentre il punto 2 garantisce liniettivita` di talemappa.

Proposizione 1.31 Se X e` un insieme finito, allora linsieme delle parti P(X) hacardinalita`

|P(X)| = 2|X |.

Dimostrazione. Posto |X | = n, etichettiamo con In linsieme X . Costruiamo un sot-toinsieme di In decidendo per ogni elemento i se inserirlo o meno nel sottoinsieme. Sitratta di una procedura composta da n fasi (una per ogni elemento di In) in ciascunadelle quali abbiamo due possibili esiti (inseriamo o meno lelemento). Ovviamen-te modificare lesito di una qualunque fase porta a costruire un diverso sottoinsie-me di In . Pertanto per lOsservazione 1.30 linsieme P(In) dei sottoinsiemi di Ine` un prodotto condizionato di molteplicita` (2, 2, ..., 2

n

) e quindi per il principio di

moltiplicazione ha 2n = 2|X | elementi.

Esempio 1.32 Contare in quanti modi e` possibile scegliere un presidente ed unvicepresidente in unassemblea di 15 persone.Soluzione. Ogni possibile scelta e` ottenibile in due fasi: nella prima si sceglie il presi-dente, mentre nella seconda si sceglie il vicepresidente. La prima fase ha 15 possibiliesiti, la seconda invece ne ha 14; comunque data una coppia di persone, scelte rispet-tivamente come presidente e vicepresidente, e` chiaro chi e` stato scelto nella primafase (il presidente) e chi nella seconda fase (il vice). Per lOsservazione 1.30 pertantolinsieme delle possibili scelte e` un prodotto condizionato di molteplicita` (15, 14) equindi per il principio di moltiplicazione ha 15 14 = 210 elementi.

Esempio 1.33 Si estraggono a caso ordinatamente 3 palline, senza reimmissione,da unurna che contiene 10 palline numerate da 1 a 10. Lestrazione si suddividenaturalmente in tre fasi:

(1a estrazione, 2a estrazione, 3a estrazione ).

Sono verificate le due condizioni dellOsservazione 1.30; pertanto linsieme delleestrazioni e` un prodotto condizionato di molteplicita` (10, 9, 8). Infatti per ognuno dei10 esiti della prima estrazione, ci sono 9 esiti possibili per la seconda e 8 esiti possibili

Tonolo_2400pt_def.pdf 26 05/09/12 10.16


per la terza: a seconda dellesito delle estrazioni precedenti cambiano i possibili esitidellestrazione in corso, ma non il loro numero. Per il principio di moltiplicazionelinsieme delle terne ottenute ha 10 9 8 elementi.Talvolta non si presta abbastanza attenzione al rispetto di entrambe le condizionienunciate nellOsservazione 1.30: cio` e` spesso fonte di errore come si puo` vederenei due esempi che seguono.

Esempio 1.34 Si lancia una moneta; se viene Testa si lancia un dado con 6 facce nu-merate da 1 a 6, mentre se viene Croce si rilancia la moneta. Consideriamo linsiemedelle 2-sequenze che riportano i possibili esiti dei due lanci. Ogni elemento di taleinsieme si ottiene in due fasi: prima il lancio della moneta, e poi il lancio, a secondadei casi, del dado o della moneta. Il numero di esiti del secondo lancio varia a secondadellesito del primo, e quindi tale suddivisione in fasi non rispetta la prima condizionedellOsservazione 1.30: non siamo pertanto in grado di individuare una struttura diprodotto condizionato.In questo caso possiamo suddividere linsieme delle 2-sequenze che riportano i pos-sibili esiti dei due lanci in due sottoinsiemi disgiunti: le 2-sequenze il cui primo ele-mento e` testa (e quindi il cui secondo elemento e` un numero tra 1 e 6) costituite da{T } {1, 2, 3, 4, 5, 6}, e le 2-sequenze il cui primo elemento e` croce (e quindi ilcui secondo elemento e` testa o croce) costituite da {C} {T,C}. Il primo insiemeha 6 elementi, il secondo ne ha 2; allora vi sono in tutto 6 + 2 = 8 possibili esiticomplessivi.

Esempio 1.35 Vogliamo formare una commissione di due persone, contenente al-meno una donna, scegliendo tra 5 donne e 7 uomini. Uno potrebbe utilizzare la se-guente procedura per dar vita alla commissione: innanzitutto scegliere una donna, epoi scegliere una persona tra quelle rimaste. Tale procedura sembra suggerire che lecommissioni cercate formino un prodotto condizionato di molteplicita` (5, 11). At-tenzione, non e` cos`! Infatti dalla commissione composta da Elena e Paola non e`possibile risalire alle scelte effettuate nelle due fasi in cui abbiamo suddiviso la pro-cedura. Potremmo infatti aver prima scelto Paola tra le 5 donne e poi aver scelto Elenatra le rimanenti 11 persone, o viceversa aver prima scelto Elena tra le 5 donne e poiPaola tra le rimanenti 11 persone. In altri termini la procedura seguita non rispetta laseconda condizione dellOsservazione 1.30.Possiamo invece procedere distinguendo due casi: le commissioni contenenti esatta-mente una donna, e quelle contenenti due donne. Si tratta di due insiemi disgiunti lacui unione da` linsieme delle possibili commissioni. Le commissioni contenenti esat-tamente una donna possono essere formate scegliendo dapprima una donna e poi unuomo: si tratta pertanto di un prodotto condizionato di molteplicita` (5, 7) e dunquesono 35. Le commissioni con due donne sono 10: infatti le coppie ordinate di don-ne formano un prodotto condizionato di molteplicita` (5, 4) e quindi per il principiodi moltiplicazione sono 20; ogni commissione con due donne individua due diversecoppie ordinate, e pertanto le commissioni tutte al femminile sono 20/2 = 10 (si

Tonolo_2400pt_def.pdf 27 05/09/12 10.16


veda piu` avanti la sezione 1.3.2). In tutto vi sono pertanto 45 possibili commissionicon almeno una donna.

Riprendiamo con altri esempi di applicazione corretta del Principio di moltiplicazio-ne 1.29.

Esempio 1.36 Contare il numero di automobili che possono essere immatricolateutilizzando le targhe adottate in Italia formate da due lettere tre numeri ed altre duelettere. Quante sono poi le targhe nelle quali non sono presenti ne lettere, ne numeriripetuti?Soluzione. Indicato con L linsieme delle 26 lettere dellalfabeto inglese e con Dlinsieme {0, 1, 2, ..., 9}, dobbiamo calcolare la cardinalita` dellinsieme prodotto LL D D D L L . Si tratta di un prodotto condizionato di molteplicita`(26, 26, 10, 10, 10, 26, 26) e pertanto per il principio di moltiplicazione

|L L D D D L L| = 264 103 = 456 976 000.Le targhe senza ripetizioni formano invece un prodotto condizionato di molteplicita`(26, 25, 10, 9, 8, 24, 23): esse sono pertanto

26 25 10 9 8 24 23 = 258 336 000.

Esempio 1.37 In quanti modi puo` essere formata una parola di tre lettere utilizzandolalfabeto {a, b, c, d, e, f }:1. con eventuali ripetizioni delle lettere?2. senza ripetizioni delle lettere?3. senza ripetizioni e contenente la lettera e?4. con eventuali ripetizioni e contenente la lettera e?

Soluzione. 1. Posto X = {a, b, c, d, e, f }, le possibili parole sono in corrispondenzabiunivoca con il prodotto cartesiano X X X . Si tratta di un prodotto condizionatodi molteplicita` (6, 6, 6); quindi per il principio di moltiplicazione abbiamo in tutto6 6 6 = 216 parole differenti di tre lettere.2. Le possibili parole senza ripetizioni sono in corrispondenza biunivoca con un pro-dotto condizionato di molteplicita` (6, 5, 4): infatti, ci sono 6 scelte per la prima lettera,5 per la seconda e 4 per la terza. In tutto quindi per il principio di moltiplicazione cisono 6 5 4 = 120 parole di tre lettere senza ripetizioni.3. Possiamo seguire la seguente procedura: in una prima fase decidere la posizionedella lettera e (vi sono 3 possibilita`); nella seconda scegliere una lettera diversa da eda collocare nel primo posto libero a sinistra (vi sono 5 possibilita`); infine scegliereuna lettera diversa dalle due precedenti da collocare nel posto rimanente (vi sono 4possibilita`). Si tratta di contare il numero di elementi di un prodotto condizionato dimolteplicita` (3, 5, 4): per il principio di moltiplicazione ci sono dunque 354 = 60parole di tre lettere distinte contenenti la lettera e.

Tonolo_2400pt_def.pdf 28 05/09/12 10.16


4. Sia A linsieme delle parole di tre lettere con eventuali ripetizioni e contenenti lalettera e ed linsieme di tutte le possibili parole di tre lettere che si possono formareutilizzando le lettere a, b, c, d, e, f . Per il punto 1 si ha || = 63 e | \ A| = 53;infatti \ A e` linsieme di tutte le possibili parole di tre lettere che si possono formareutilizzando le lettere a, b, c, d, f . Pertanto |A| = 63 53 = 91.

Esempio 1.38 Ci sono cinque libri distinti di autori spagnoli, sei libri distinti di autorifrancesi e otto libri distinti di autori inglesi. In quanti modi e` possibile prendere duelibri di autori provenienti da paesi diversi?Soluzione. Linsieme delle possibili scelte di un libro di un autore spagnolo ed unodi un autore francese e` un prodotto condizionato di molteplicita` (5, 6) ed ha pertantoper il principio di moltiplicazione 5 6 = 30 elementi. Analogamente un libro di unautore spagnolo e di un autore inglese puo` essere scelto in 5 8 = 40 modi, mentreun libro di un autore francese e di un autore inglese puo` essere scelto in 6 8 = 48modi. Gli insiemi formati da questi tre tipi di scelte sono disgiunti, e quindi ci sono30 + 40 + 48 = 118 modi in tutto di prendere due libri di autori provenienti da paesidiversi.

1.3.2 Principio di divisione

Formalizziamo ora un altro ragionamento estremamente naturale nei problemi di con-teggio.

y

y

1

2

x 1

x 2

x 3

x 4

x 5

x 6

Y

X

|Y|= |X|/3Figura 1.5. Una applicazione del principio

di divisione.

Teorema 1.39 (Principio di divisione)Siano X ed Y due insiemi finiti. Sup-poniamo che ogni elemento y di Ycorrisponda a m elementi di un insiemeX tramite una funzione f : X Y .Allora |Y | = |X |/m.Dimostrazione. Sia Y = {y1, ..., yn}.Gli insiemi f 1(y1), ..., f 1(yn) for-mano una partizione di X . Essendo| f 1(y1)| = ... = | f 1(yn)| = m siottiene

|X | = f 1(y1) ... f 1(yn) = n

i=1| f 1(yi )| = n m

da cui |Y | = n = |X |/m. Vediamo alcuni esempi di possibile applicazione del principio di divisione.

Esempio 1.40 Vogliamo contare il numero di commissioni di tre persone scelte tra27. Sia X linsieme delle terne ordinate di persone ed Y linsieme delle commissioni

Tonolo_2400pt_def.pdf 29 05/09/12 10.16


cercate. Ogni commissione corrisponde a 6 terne ordinate. Per il principio di mol-tiplicazione vi sono 27 26 25 diverse terne ordinate. Allora per il principio didivisione 1.39 il numero di commissioni e` (27 26 25)/6.

Esempio 1.41 Quante mani di 2 carte si possono formare da un mazzo di 52 carte?Soluzione. Ogni mano {a, b} corrisponde alle due 2-sequenze (a, b), (b, a). Per ilprincipio di moltiplicazione il numero di 2-sequenze di carte distinte e` 52 51, epertanto per il principio di divisione il numero di mani cercato e` 26 51 = 1 326.

Esempio 1.42 Determinare il numero di anagrammi della parola AL A.Soluzione. Si tratta di calcolare le permutazione della sequenza (A, L , A). Distin-guendo artificiosamente le due A chiamandole A1, A2, a ciascuno degli anagram-mi di AL A restano associati due anagrammi della parola A1L A2. Gli anagrammi diA1L A2 formano un prodotto condizionato di molteplicita` (3, 2, 1) e pertanto per ilprincipio di moltiplicazione sono in tutto 6. Per il principio di divisione si concludeche AL A ha 6/2 = 3 anagrammi.

Esempio 1.43 In quanti modi si possono disporre 8 persone attorno ad un tavolorotondo?Soluzione. Sia Y linsieme delle disposizioni delle 8 persone attorno al tavolo. Adogni disposizione restano associate le otto 8-sequenze che si ottengono procedendo inmodo orario a partire da una qualunque delle persone sedute al tavolo. Per il principiodi moltiplicazione linsieme delle 8-sequenze delle otto persone ha 87 ...21elementi; pertanto, per il principio di divisione, si ha

|Y | = 8 7 ... 2 18

= 7 ... 2 1.

(3, 6, 8, 1, 7, 5, 2, 4)

(6, 8, 1, 7, 5, 2, 4, 3)

(8, 1, 7, 5, 2, 4, 3, 6)

(1, 7, 5, 2, 4, 3, 6, 8)

(7, 5, 2, 4, 3, 6, 8, 1)(5, 2, 4, 3, 6, 8, 1, 7)

(2, 4, 3, 6, 8, 1, 7, 5)

(4, 3, 6, 8, 1, 7, 5, 2)

3

2

15

7

4 6

8

Figura 1.6. Una disposizione e relative 8-sequenze.

Tonolo_2400pt_def.pdf 30 05/09/12 10.16

1.4 Spazi campionari e probabilita` uniforme 19

1.4 Spazi campionari e probabilita` uniforme

Strettamente collegata ai problemi di conteggio e` la frequenza con cui si presentanocerti fenomeni.

Definizione 1.44 Sia un insieme. Un esperimento aleatorio con spazio campio-nario e` una procedura che determina aleatoriamente la scelta di un elemento di. Gli elementi di si chiamano eventi elementari o esiti dellesperimento; si diceevento dellesperimento un qualunque sottoinsieme di .

Esempio 1.45 Lanciare un dado e` una procedura affidata al caso per scegliere unnumero da 1 a 6. Si tratta pertanto di un esperimento aleatorio con spazio campionario

= {1, 2, 3, 4, 5, 6}.Levento esce un numero pari e` il sottoinsieme A = {2, 4, 6}.Spesso lo spazio campionario di un esperimento aleatorio viene sottinteso. Ad esem-pio quando si lancia una moneta, solitamente si sottintende che si tratta di una pro-cedura per scegliere tra Testa e Croce, ovvero che lo spazio campionario e` ={T,C}.

Nel seguito identificheremo, per comodita` di notazione, un evento elementare con levento {} costituito da un solo elemento.

Definizione 1.46 Diremo che P e` una probabilita` uniforme sullo spazio campiona-rio finito se P e` la funzione

P : P() [0, 1]che associa ad ogni sottoinsieme A di il numero

P(A) = |A||| .

La probabilita` uniforme di un evento e` dunque il rapporto tra il numero di casi favore-voli, ovvero il numero di elementi dellevento, ed il numero di casi possibili, ovveroil numero di elementi dello spazio campionario.

Teorema 1.47 Siano A, B due eventi di uno spazio campionario finito conprobabilita` uniforme P . Allora1. per ogni evento elementare si ha

P() = 1|| ;

2. P() = 0 e P() = 1;

Tonolo_2400pt_def.pdf 31 05/09/12 10.16


3. P(A B) = P(A)+ P(B) P(A B);4. se A e B sono disgiunti allora P(A B) = P(A)+ P(B);5. P(Ac) = 1 P(A).Dimostrazione. I punti 1 e 2 sono immediate conseguenze della definizione diprobabilita` uniforme.3. Per definizione si ha

P(A B) = |A B||| =|A| + |B| |A B|

|| = P(A)+ P(B) P(A B).

4. Segue subito dai punti 2 e 3.5. Essendo Ac ed A disgiunti, per il punto 4 si ha

1 = P() = P(Ac A) = P(Ac)+ P(A).

Osservazione 1.48 La probabilita` uniforme fornisce una corretta indicazione sullafrequenza con cui un certo evento si verifica solo se lo spazio campionario e` costitui-to da elementi equiprobabili. Ad esempio, gli esiti del lancio di un dado non truccatopossono essere ritenuti equiprobabili; invece non e` generalmente equiprobabile le-sito di una corsa automobilistica o di una partita di calcio. Di fronte ad un eserciziodi probabilita` che vogliamo risolvere utilizzando la probabilita` uniforme, la primacosa da fare e` formalizzare il problema in un esperimento con spazio campionariocostituito da elementi equiprobabili.

Esempio 1.49 Si effettui una estrazione di due numeri da 1 a 50; si vuole calcolarela probabilita` che il numero piu` alto sia uguale al doppio del numero piu` basso. Cio`puo` essere visto come un esperimento con spazio campionario linsieme 1 delle 2-sequenze di I50 senza ripetizioni, o quello con spazio campionario 2 costituito dalle2-collezioni di I50 senza ripetizioni. Nel primo esperimento pensiamo di tener contodellordine di estrazione, nel secondo invece questo viene trascurato. Se lestrazionee` fatta in modo casuale, gli eventi elementari di entrambi gli spazi sono da ritenersiequiprobabili. Nel primo caso levento al quale siamo interessati e`

A1 = {(x, 2x) : 1 x 25} {(2x, x) : 1 x 25}.Chiaramente A1 ha 25+ 25 = 50 elementi, mentre per il principio di moltiplicazionelo spazio 1 ha 50 49 elementi; pertanto la probabilita` cercata e`

P(A1) = |A1||1| =50

50 49 =149

.

Nel secondo caso levento al quale siamo interessati e`

A2 = {[x, 2x] : 1 x 25}.

Tonolo_2400pt_def.pdf 32 05/09/12 10.16

1.5 Esercizi 21

Chiaramente A2 ha 25 elementi, mentre 2 ha (50 49)/2 elementi (vediEsempio 1.41); pertanto la probabilita` cercata e`

P(A2) = |A2||2| =25

(50 49)/2 =149

.

Ovviamente la probabilita` che nellestrazione il numero piu` alto sia uguale al doppiodel numero piu` basso non dipende dallo spazio campionario scelto.

Esempio 1.50 Si effettui una estrazione casuale di due numeri da 1 a 50 con rim-piazzo; si vuole calcolare la probabilita` che i due numeri estratti siano uguali. Cio`puo` essere visto come un esperimento con spazio campionario linsieme 1 delle2-sequenze di I50, o quello con spazio campionario 2 costituito dalle 2-collezionidi I50. Mentre nel primo caso gli elementi di 1 sono da ritenersi equiprobabili, nelsecondo caso gli elementi di 2 non sono equiprobabili: infatti, ad esempio, la colle-zione [1, 1] si realizza se sia nella prima che nella seconda estrazione esce il numero1, mentre la collezione [1, 2] si realizza quando la prima volta esce 1 e la seconda 2 oviceversa. Volendo utilizzare la probabilita` uniforme, affinche il risultato sia veritiero,scegliamo lo spazio campionario 1. La probabilita` cercata e`

|{(x, x); 1 x 50}||1| =

50502

= 150

.

Esempio 1.51 Qual e` la probabilita` che un numero di quattro cifre contenga una opiu` cifre ripetute?Soluzione. I numeri di 4 cifre sono i numeri dal 1 000 al 9 999; in tutto sono pertanto9 000. I numeri senza cifre ripetute formano un prodotto condizionato di molteplicita`(9, 9, 8, 7): si osservi infatti che la prima cifra (quella delle migliaia) e` compresa tra1 e 9, mentre le altre sono comprese tra 0 e 9, ma diverse da quelle gia` fissate! Quindii numeri che contengono una o piu` cifre ripetute sono

9 000 9 9 8 7 = 9 000 4 536 = 4 464.

La probabilita` cercata vale dunque4 4649 000

= 0.496.

1.5 Esercizi

Esercizio 1.1 Un negozio ha 8 marche diverse di pantaloni. Per ogni marca ci sono 10taglie, 6 lunghezze e 4 colori. Quanti differenti tipi di pantaloni ci sono nel negozio?

Esercizio 1.2 Quante parole di quattro lettere ci sono utilizzando un alfabeto di 26lettere? E quante parole di quattro lettere senza ripetizioni?

Tonolo_2400pt_def.pdf 33 05/09/12 10.16


Esercizio 1.3 Dati 8 libri di inglese diversi tra loro, 7 di francese diversi tra loro e5 di tedesco diversi tra loro: in quanti modi possono essere scelti tre libri, uno perciascuna lingua?

Esercizio 1.4 In quanti modi possiamo pescare due carte da un mazzo di 52 carte dagioco in modo tale che:

(a) la prima carta sia un asso e la seconda non sia una regina?(a) una sia un asso e laltra non sia una regina?(b) la prima carta sia di picche e la seconda non sia una regina?(b) una sia di picche e laltra non sia una regina?

Esercizio 1.5 In quanti modi si possono lanciare due dadi, uno rosso ed uno verde,in modo da ottenere una somma divisibile per 3?

Esercizio 1.6 Si consideri linsieme X dei numeri di 5 cifre, ovvero dei numericompresi tra 10 000 e 99 999.

(a) Determinare la cardinalita` di X ;(b) Quanti sono i numeri pari in X?(c) Quanti sono i numeri in X nei quali compare esattamente un 3?(d) Quanti sono i numeri di 5 cifre palindromi (ovvero tali che il numero stesso

rimanga inalterato se si invertono le sue cifre ad esempio 15 251)?

Esercizio 1.7 Qual e` la probabilita` che le due carte in cima ad un mazzo di 52 cartenon formino una coppia, ovvero non siano due carte con lo stesso valore?

Esercizio 1.8 Una notizia e` stata diffusa in un gruppo di 10 persone nel modo se-guente: la prima persona ha telefonato ad una seconda, la quale ha telefonato a suavolta ad una terza, e cos` via, in modo casuale. Una persona puo` passare la notizia achiunque altro, eccetto alla persona che lo ha appena chiamato.

(a) In quanti modi differenti puo` essere diffusa la notizia in tre chiamate? Ed in nchiamate?

(b) Qual e` la probabilita`, sapendo che A diffonde la notizia, che A riceva la terzachiamata?

(c) Qual e` la probabilita`, sapendo che A non diffonde la notizia, che A riceva la terzachiamata?

Esercizio 1.9 Quante parole di tre lettere senza ripetizioni si possono fare utilizzandole lettere a, b, c, d, e, f in modo che compaia o la lettera e o la lettera f oppureentrambe?

Esercizio 1.10 Qual e` la probabilita` che un numero naturale tra 1 e 10 000 contengauna volta la cifra 8 e una volta la cifra 9?

Tonolo_2400pt_def.pdf 34 05/09/12 10.16

1.5 Esercizi 23

Esercizio 1.11 Unassemblea di 20 persone deve scegliere a voto palese il propriopresidente tra 7 candidati: A, B, C, D, E, F, G.

(a) In quanti differenti modi puo` esprimersi lassemblea?(b) Quanti sono i possibili esiti in cui A e D ottengono esattamente un voto?

Esercizio 1.12 Quanti numeri di 4 cifre si possono formare utilizzando le cifre1,2,3,4,5 (con eventuali ripetizioni) che siano divisibili per 4?

Esercizio 1.13 In quanti modi si possono mettere due torri identiche nella stessa ri-ga o nella stessa colonna di una scacchiera con 8 righe ed 8 colonne? Ed in unascacchiera con n righe ed m colonne?

Esercizio 1.14 In quanti modi si possono mettere due regine identiche in una scac-chiera con 8 righe ed 8 colonne, in modo che le due regine non stiano nella stessariga, nella stessa colonna, oppure nella stessa diagonale?

Esercizio 1.15 In quanti modi si possono invitare degli amici (almeno uno!) scelti tra10 persone?

Esercizio 1.16 In quanti modi, operando come nel gioco della Dama, si possono met-tere una pedina bianca ed una pedina nera in due quadrati neri di una scacchiera inmodo che quella bianca possa mangiare quella nera? (Si ricordi che una pedina man-gia in diagonale, saltando la pedina che viene mangiata, e che le pedine non possonotornare indietro).

Tonolo_2400pt_def.pdf 35 05/09/12 10.16

Tonolo_2400pt_def.pdf 36 05/09/12 10.16

2 Contare sequenzee collezioni

Contenuto2.1 Sequenze e collezioni di elementi distinti2.2 Sequenze e collezioni arbitrarie2.3 Esercizi

In questo capitolo approfondiremo le nostre conoscenze su sequenze e collezioni,acquisendo gli strumenti indispensabili per il calcolo combinatorio.2.1 Sequenze e collezioni di elementi distinti

In questa sezione impareremo a contare le sequenze e le collezioni senza elementiripetuti.

2.1.1 Sequenze senza ripetizione

Nei problemi di conteggio interviene molto spesso la nozione di fattoriale di unnumero naturale.

Definizione 2.1 Sia n 0 un numero naturale. Il fattoriale di n e`

n! ={

n (n 1) ... 2 1 per n 1 ,1 per n = 0.

Osservazione 2.2 (Formula di Stirling) `E piuttosto laborioso calcolare n! per valorialti di n. Si puo` pero` dimostrare (si veda la Sezione 10.6.2) che n! e` asintotico a

2pin(n/e)n per n , cioe`

limn

n!2pin(n/e)n

= 1.

Tonolo_2400pt_def.pdf 37 05/09/12 10.16

26 Contare sequenze e collezioni

La seguente tabella mostra laccuratezza di tale approssimazione, detta approssima-zione di Stirling1, gia` per valori di n piuttosto piccoli:

n

1234567891011121314151617181920

n!

1.2.6.24.120.720.5040.40320.362880.

3.6288 1063.99168 1074.79002 1086.22702 1098.71783 10101.30767 10122.09228 10133.55687 10146.40237 10151.21645 10172.4329 1018

2pin(n/e)n

0.9221371.919

5.8362123.5062118.019710.0784980.439902.4359537.

3.5987 1063.96156 1074.75687 1086.18724 1098.6661 10101.30043 10122.08141 10133.53948 10146.3728 10151.21113 10172.42279 1018

Esempio 2.3 Utilizzando la formula di Stirling e` possibile fornire una stima del nu-mero di cifre decimali di 100! Il numero delle cifre decimali di un naturale k e` ugualea [log10 k] + 1, dove [x] indica la parte intera o floor di x . Per la formula di Stirlingsi ha 2

log10 100! log10(

2pi 100(100/e)100)= 1

2(log10(2pi)+ 2)+ 100 log10(100/e)

= 12

log10(2pi)+ 1 + 200 100 log10 e = 157.97...Il numero di decimali cercato e` dunque approssimativamente uguale a 158. Si puo`verificare che in realta` 100! ha esattamente proprio 158 cifre decimali.

1James Stirling (1692-1770)2Si usa qui il fatto che se an e bn sono due successioni divergenti a + con an bn ( sta per

asintotico) per n +, allora log10 an log10 bn . Si faccia attenzione che in generale per unafunzione f se an bn non e` detto che f (an) f (bn) per n +.

Tonolo_2400pt_def.pdf 38 05/09/12 10.16

2.1 Sequenze e collezioni di elementi distinti 27

Quante sono le sequenze di lunghezza fissata senza ripetizioni, ovvero di elementidistinti, di un insieme finito?

Definizione 2.4 Siano n, k N. Indichiamo con S(n, k) il numero di k-sequenzesenza ripetizioni di In , ovvero il numero di k-sequenze di elementi distinti di In .

Osservazione 2.5 Per il Teorema 1.23 S(n, k) e` anche il numero di n-spartizioni(C1, ....,Cn) di Ik con al piu` un elemento in ogni Ci , i = 1, ..., n.Il valore di S(n, k) si ricava facilmente utilizzando la nozione di prodottocondizionato ed il principio di moltiplicazione introdotti nel capitolo precedente.

Teorema 2.6 Siano n, k N. Allora

S(n, k) =

n!(n k)! se k n,0 altrimenti.

In particolare S(n, 0) = 1 e S(n, n) = n! per ogni n N.Dimostrazione. Se k > n, non vi sono k-sequenze senza ripetizioni di In , e quindiS(n, k) = 0. Sia ora k n. Se k = 0 si ha S(n, 0) = 1: infatti la sequenza vuotae` lunica 0-sequenza di In . Supponiamo k 1. Linsieme delle k-sequenze senzaripetizione di In e` un prodotto condizionato di molteplicita` (n, n1, ..., n (k1)):infatti possiamo scegliere uno qualunque degli n elementi di In come prima compo-nente della sequenza; per la seconda componente abbiamo n 1 scelte, non potendoripetere lelemento scelto per la prima componente; abbiamo n 2 scelte per la terzacomponente, e cos` via. Per il principio di moltiplicazione linsieme delle k-sequenzesenza ripetizione di In ha pertanto cardinalita`

n (n 1) ... (n (k 1)) = n!(n k)! .

Esempio 2.7 In quanti modi e` possibile redigere una lista di n persone? Qual e` laprobabilita` che il Sig. Caruso sia al secondo posto della lista?Soluzione. Una tale lista e` semplicemente una n-sequenza senza ripetizionidellinsieme delle n persone: vi sono pertanto S(n, n) = n! liste possibili. Pertanto

P(Caruso secondo) = numero di liste con Caruso secondonumero totale di liste

Ogni lista con Caruso secondo e` individuata dalla sequenza delle altre n 1 personeche formano la lista; queste pertanto sono (n 1)! La probabilita` cercata quindi vale(n 1)!/n! = 1/n.

Tonolo_2400pt_def.pdf 39 05/09/12 10.16


Esempio 2.8 (Numero di funzioni iniettive) NellEsempio 1.19 abbiamo visto co-me ogni funzione f : I Im , ,m N1, sia individuata da una -sequenza diIm ; la funzione f e` iniettiva se e solo se la sequenza associata e` priva di ripetizioni.Pertanto S(m, ) rappresenta anche il numero di funzioni iniettive f : I Im .Esempio 2.9 Qual e` la probabilita` che due (o piu`) persone in un gruppo di 25 per-sone scelte a caso siano nati lo stesso giorno? (questo e` il famoso Paradosso delcompleanno.)Soluzione. Etichettiamo le 25 persone con I25. I giorni del loro compleanno costitui-scono una 25-sequenza di I365. La probabilita` che le 25 persone non siano nate lostesso giorno e`

Q(365, 25) := 365 364 ... 34136525

0, 431.Pertanto la probabilita` cercata e` 1 Q(365, 25) 0, 569. I numeri Q(n, k) :=

n!(n k)!nk sono detti di Ramanujan

3; essi saranno studiati nella Sezione 10.6.3, dovene verra` data una stima per valori alti di k e n.

2.1.2 Collezioni senza ripetizione (sottoinsiemi)

Accanto alla nozione di fattoriale, grande importanza ricopre anche quella dibinomiale di una coppia di numeri naturali.

Definizione 2.10 Siano n, k 0 due numeri naturali. Il binomiale n su k e` il numero(

n

k

)=

n!k!(n k)! se k n,0 altrimenti.

Osservazione 2.11 Si osservi, e si tenga a mente, che per ogni n N(n

0

)= 1,

(n

1

)= n,

(n

n

)= 1,

(n

n 1)

= n.

Inoltre segue immediatamente dalla definizione la seguente simmetria:

k {0, ..., n}(

n

k

)=(

n

n k)

Vedremo in seguito che(

n

k

)e` un numero intero per ogni k, n N.

3Srinivasa Ramanujan (1887-1920)

Tonolo_2400pt_def.pdf 40 05/09/12 10.16


n =10

n =100

120

5exp(28)

Figura 2.1. Grafico dei valori assunti da C(10, k) e C(100, k).

Osservazione 2.12 Fissato n, il binomiale(

n

k

)cresce per k che varia tra 0 e la parte

intera [n/2] di n/2, e decresce da [n/2] + 1 a n. Infatti per ogni 1 k n si ha(n

k 1)

(n

k

) = kn k + 1 1 se e solo se k

n + 12

.

Pertanto, per n fissato, il binomiale(

n

k

)assume valore massimo in k = [n/2].

Tramite la Formula di Stirling si vede che tale valore e` asintotico a

2n+ 12pin

per n +.

Definizione 2.13 Siano n, k N. Indichiamo con C(n, k) il numero di k-collezionisenza ripetizione di In , ovvero il numero di sottoinsiemi di k elementi di In .

Osservazione 2.14 Per il Teorema 1.23 C(n, k) e` anche il numero di n-risoluzioni(k1, ...., kn) di k con ki 1 per ogni i = 1, ..., n.

Tonolo_2400pt_def.pdf 41 05/09/12 10.16


Teorema 2.15 Siano n, k N. Allora

C(n, k) = S(n, k)k! =

(n

k

).

In particolare(

n

k

) N.

Dimostrazione. Se k > n, non vi sono k-collezioni senza ripetizioni di In , e quindi

C(n, k) = 0 =(

n

k

). Sia ora k n. Se k = 0, si ha C(n, 0) = 1 =

(n

0

): infatti

la collezione vuota e` lunica 0-collezione di In . Supponiamo k 1. Si consideri lafunzione che associa ad ogni k-sequenza senza ripetizioni di In la k-collezione che siottiene dimenticando lordine degli elementi (vedi Figura 2.2).

[1,2]

[1,3]

[2,3]

(1,2)

(2,3)

(1,3)

2-collezioni senza ripetizioni di I3

2-sequenze di I3

(2,1)

(3,2)

(3,1)

Figura 2.2. Funzione che associa ad ogni 2-sequenza senza ripetizioni di I3 la2-collezione che si ottiene dimenticando lordine degli elementi.

Tramite tale funzione ogni k-collezione senza ripetizioni e` immagine di esattamentek! sequenze senza ripetizioni, precisamente le k-sequenze che si ottengono ordinandoin tutti i modi possibili i suoi elementi. Per il principio di divisione 1.39 le k-collezionisenza ripetizione di In sono dunque S(n, k)/k!

Esempio 2.16 Siano 0 k n interi. Abbiamo visto utilizzando la definizione dibinomiale che (

n

k

)=(

n

n k).

Tale formula si puo` anche ricavare osservando che scegliere k tra n oggetti equivale a

scartare n k tra n oggetti; dunque il numero(

n

k

)= C(n, k) delle possibile scelte

Tonolo_2400pt_def.pdf 42 05/09/12 10.16


di k oggetti e` uguale al numero(

n

n k)

= C(n, n k) dei possibili scarti di n koggetti.

Il seguente risultato motiva il termine binomiale.

Proposizione 2.17 (Formula del binomio) Siano 0 k n. Il coefficiente dixk ynk nellespansione di (x + y)n e`

(n

k

). Piu` precisamente lo sviluppo di (x + y)n

e` dato da

(n

0

)x0yn+

(n

1

)xyn1+

(n

2

)x2yn2+...+

(n

n 1)

xn1y+(

n

n

)xn y0.

Dimostrazione. La formula e` banalmente vera per n = 0. Sia ora n 1. Moltiplican-do x + y per se stesso n volte otteniamo una somma di monomi del tipo xk ynk ; iltermine xk ynk appare ogniqualvolta negli n fattori si sceglie per k volte la x e pern k volte la y. I k fattori nei quali si sceglie la x formano una k-collezione del-linsieme degli n fattori; essi dunque possono essere selezionati in C(n, k) =

(n

k

)modi. Il termine xk ynk pertanto si ripete C(n, k) =

(n

k

)volte e questo e` dunque il

coefficiente del monomio xk ynk nello sviluppo del binomio. La seguente formula ricorsiva e` di uso frequente.

Proposizione 2.18 (Formula ricorsiva per i binomiali) Siano k, n N1. Allora(n 1k 1

)+(

n 1k

)=(

n

k

).

Dimostrazione. Trattiamo in modo distinto i casi n 1 < k 1, n 1 = k 1 en 1 > k 1. Se n 1 < k 1 o n 1 = k 1, per la definizione di binomiale leeguaglianze da dimostrare diventano rispettivamente le identita` 0+0 = 0 e 1+0 = 1.Supponiamo ora n1 > k1, ovvero n > k. Utilizzando la definizione del binomialesi ha (

n 1k 1

)+(

n 1k

)= (n 1)!

(k 1)!(n k)! +(n 1)!

k!(n k 1)!= k(n 1)!

k(k 1)!(n k)! +(n 1)!(n k)

k!(n k)(n k 1)!= n!

k!(n k)! =(

n

k

).

Tonolo_2400pt_def.pdf 43 05/09/12 10.16


Alternativamente si poteva osservare che(

n

k

)= C(n, k) e` il numero di sottoinsiemi

di k elementi di In . Questi si possono suddividere in due classi disgiunte: quelli checontengono 1 e quelli che non lo contengono. La prima classe ha tanti elementi quantisono i sottoinsiemi di k 1 elementi di {2, ..., n}: basta aggiungere a ciascuno diquesti ultimi il numero 1. La seconda classe e` costituita dai sottoinsiemi di k elementi

di {2, ..., n}. La prima classe ha C(n 1, k 1) =(

n 1k 1

)elementi, la seconda ne

ha C(n 1, k) =(

n 1k

).

La proposizione precedente mostra che per calcolare i binomiali con primo ar-gomento uguale a n e` sufficiente conoscere i binomiali con primo argomento ugua-le a n 1. Questa considerazione e` alla base della costruzione del triangolo diTartaglia-Pascal4 5 : (

00

)(

10

) (11

)(

20

) (21

) (22

)(

30

) (31

) (32

) (33

)(

40

) (41

) (42

) (43

) (44

)... ... ... ... ... ... ... ... ... ... ...

Essendo(

n

k

)=(

n

n k)

, il triangolo di Tartaglia-Pascal e` simmetrico rispetto alla

verticale che passa per il suo vertice. I valori(

n

0

)e

(n

n

)sui lati poi sono tutti uguali

ad uno. Utilizzando la formula(n

k

)=(

n 1k 1

)+(

n 1k

), 1 k n 1

provata sopra, possiamo facilmente ricavare i valori di una riga conoscendo i va-lori della riga precedente: questi infatti sono uguali alla somma dei due valori adia-centi della riga sopra. Esplicitando i valori dei binomiali alla luce di quanto appenaosservato, il triangolo di Tartaglia-Pascal assume i seguenti valori:

4Niccolo` Tartaglia (1499-1557)5Blaise Pascal (1623-1662)

Tonolo_2400pt_def.pdf 44 05/09/12 10.16


11 1

1 2 11 3 3 1

1 4 6 4 1... ... ... ... ... ... ... ... ... ... ...

Il triangolo di Tartaglia-Pascal puo` anche essere rappresentato tramite il seguenteschema ottenuto applicando la regola

a bcn

k

c = a + b

Seguono i valori dei primi binomiali.

n

(n

0

) (n

1

) (n

2

) (n

3

) (n

4

) (n

5

) (n

6

) (n

7

) (n

8

)...

0 1 0 0 0 0 0 0 0 0 ...1 1 1 0 0 0 0 0 0 0 ...2 1 2 1 0 0 0 0 0 0 ...3 1 3 3 1 0 0 0 0 0 ...4 1 4 6 4 1 0 0 0 0 ...5 1 5 10 10 5 1 0 0 0 ...6 1 6 15 20 15 6 1 0 0 ...7 1 7 21 35 35 21 7 1 0 ...8 1 8 28 56 70 56 28 8 1 ...... ... ... ... ... ... ... ... ... ... ...

Verifichiamo nella successiva proposizione altre interessanti identita` combinatorie:

Proposizione 2.19 Siano n, k due numeri naturali. Allora

1.(

n

0

)+ ...+

(n

n

)= 2n;

2.(

n

0

)2+(

n

1

)2+(

n

2

)2+ ...+

(n

n 1)2

+(

n

n

)2=(

2nn

);

3.(

n

0

)+(

n + 11

)+(

n + 22

)+ ...+

(n + k

k

)=(

n + k + 1k

).

Tonolo_2400pt_def.pdf 45 05/09/12 10.16


Dimostrazione. Le tre formule sono banalmente vere per n = 0. Sia ora n 1.1. Il termine C(n, i) =

(n

i

)conta il numero di sottoinsiemi di In di cardinalita` i .

Pertanto la somma di essi al variare di i tra 0 e n e` uguale al numero di sottoinsiemidi In , che per la Proposizione 1.31 vale 2n .

2. Il numero C(2n, n) =(

2nn

)rappresenta il numero di sottoinsiemi di cardinalita`

n di I2n . Un generico sottoinsieme di n elementi di I2n e` formato da k elementi di{1, ..., n} e da n k elementi di {n + 1, ..., 2n}, per qualche k {0, 1, ..., n}. Laprima scelta puo` essere fatta in C(n, k) =

(n

k

)modi, mentre la seconda scelta puo`

essere fatta in C(n, n k) =(

n

n k)

modi. Si ottiene quindi che il numero di modi

per scegliere un sottoinsieme di I2n formato da n elementi, di cui esattamente k sceltiin {1, 2, ..., n} e` (

n

k

)(n

n k)

=(

n

k

)2.

Il numero totale di sottoinsiemi di n elementi di I2n e` quindi dato dalla somma diquesti termini per k = 0, 1, ..., n.3. Per dimostrare la formula, utilizziamo la tecnica dellinduzione (su k).Per k = 0 lidentita` e` vera dato che(

n

0

)= 1 =

(n + 0 + 1

0

).

Supponiamo ora che lidentita` sia vera per un dato valore di k 0, e dimostriamolaper k + 1. Vogliamo in altre parole provare che(

n

0

)+(

n + 11

)+ ...+

(n + k

k

)+(

n + k + 1k + 1

)=(

n + k + 2k + 1

)(2.1)

La somma dei primi k termini a primo membro coincide con(

n + k + 1k

)per ipotesi

induttiva, dunque possiamo sostituire il termine a sinistra delluguaglianza in (2.1)con (

n + k + 1k

)+(

n + k + 1k + 1

).

Ora, per la Proposizione 2.18 esso coincide con(

n + k + 2k + 1

).

Forniamo una dimostrazione alternativa del punto 3 interpretando dal punto di vista

combinatorio i binomiali coinvolti. Infatti(

n + k + 1k

)e` il numero di (n + k + 1)-

sequenze binarie con esattamente k copie di 0 ed n + 1 copie di 1: una talesequenza infatti e` determinata quando si conoscono le posizioni, ad esempio, dei k

Tonolo_2400pt_def.pdf 46 05/09/12 10.16


zeri. Fissata una tale sequenza, lultimo 1 puo` essere in posizione n + 1 (qualorala sequenza veda tutti gli 1 allinizio), n + 2, ..., n + k + 1 (qualora la sequenzatermini con 1). In generale lultimo 1 e` necessariamente in posizione n +1+ j per unopportuno j con 0 j k; esso e` seguito da una sequenza di 0, ed e` preceduto dauna (n + j)-sequenza binaria che contiene 1 esattamente n volte. Le sequenze chehanno lultimo 1 in posizione n +1+ j sono tante quante le (n + j)-sequenze binarienelle quali 1 compare n volte. Essendo questultime pari a

(n + j

n

)=(

n + jj)

,

le (n + k + 1)-sequenze binarie nelle quali 1 compare n + 1 volte sono quindi(n + k + 1

k

)=

kj=0

(n + j

j).

Vediamo ora alcuni esempi di applicazione dei concetti descritti.

Esempio 2.20 (La passeggiata di G. Polya6) Si immagini che il seguente diagram-ma descriva il reticolo di strade di una citta`. Ogni vertice e` individuato da una coppia(n, k) dove n 0 e` il numero della riga e k 0 e` il numero della colonna. Voglia-mo determinare quante diverse passeggiate conducono dal vertice (0, 0) al genericovertice (n, k).

k = 0

n = 0

k = 1

n = 1

k = 2

n = 2

k = 3

n = 3

n = 4 Possiamo descrivere un qualunque cammino congiungente il vertice (0, 0) al verti-ce (n, k) attraverso una sequenza di Sinistra - Destra: ad esempio un cammino checongiunge (0, 0) a (3, 1) e` (S, S, D); un altro cammino congiungente i medesimivertici e` (S, D, S), oppure ancora (D, S, S). In generale per arrivare al vertice (n, k)

6Gyorgy Polya (1887-1985)

Tonolo_2400pt_def.pdf 47 06/09/12 09.49


si deve voltare esattamente k volte a destra e, di conseguenza, n k volte a sini-stra. Ogni cammino e` univocamente individuato da una n-sequenza di {S, D} nellaquale compare esattamente k volte il simbolo D. Una tale sequenza e` determinata

dalle k posizioni della D: pertanto vi sono(

n

k

)possibili cammini che conducono da

(0, 0) a (n, k).

Esempio 2.21 1. Quante mani di 5 carte si possono formare utilizzando un mazzostandard di 52 carte?

2. Se si sceglie una mano di 5 carte a caso, qual e` la probabilita` che tutte le carteappartengano allo stesso seme?

3. Se si sceglie

Pages From Estratto Calcolo Discreto r

Documents

Transcript of Pages From Estratto Calcolo Discreto r