esercizi di combinatoria

Universita di Torino

QUADERNI DIDATTICI

del

Dipartimento di Matematica “G. Peano ”

D. Romagnoli

Problemi di combinatorica

A.A. 2007/2008

Quaderno # 43 - Giugno 2008

............................................................................................................

..............................................................................

........

...................

........................

............................................................................................

..............................................................................................................................

..................................

...............................................................

... .....................................................................................................

...................................................

............................................................................................................

..............................................................................

........

...................

........................

PREFAZIONE In questo quaderno sono contenute alcune lezioni del Laboratorio di Combinatorica per il corso di laurea triennale in Matematica di Torino (anno accademico 2007-2008). Le lezioni si propongono sia di richiamare i prerequisiti necessari di teoria degli insiemi finiti che di introdurre strumenti nuovi per la presentazione e la discussione di alcuni problemi classici del calcolo combinatorio . Ogni problema presentato è corredato con esempi ed esercizi svolti. Per una trattazione completa dei temi presentati si rimanda alla bibliografia che riporta i testi consigliati ed usati dai frequentanti il laboratorio per la stesura di tesine attinenti gli argomenti trattati. In particolare si rimanda al Quaderno didattico n.23 del Dipartimento di Matematica di Torino : D.Romagnoli , Elementi di Matematica discreta, naturale complemento di queste dispense.

INDICE Prefazione

Capitolo1 – IL PRINCIPIO DI INDUZIONE MATEMATICA 1

Capitolo 2 – ALCUNI PROBLEMI COMBINATORICI 7

1. Contare i sottoinsiemi di un insieme finito 7

2. Contare gli elementi dell’unione di due insiemi finiti 8

3. Contare gli elementi del prodotto cartesiano di due insiemi finiti 10

4. Contare le funzioni tra due insiemi finiti 12

5. Contare le biiezioni di un insieme finito in se stesso 13

6. Contare le funzioni iniettive tra due insiemi finiti 18

7. Contare i sottoinsiemi di ordine k di un insieme di ordine n 22

8. Contare le scelte non ordinate e non distinte di k elementi scelti tra n 31

9. Contare le sequenze ordinate con elementi ripetuti un numero fissato di volte 35

10. Contare le funzioni suriettive tra due insiemi finiti 38

11. Contare le partizioni di un insieme finito 39

12. Contare le relazioni su un insieme finito 43

Bibliografia

Daniela Romagnoli – Problemi di combinatorica

Quaderni Didattici del Dipartimento di Matematica

1

Capitolo 1

Il principio di induzione matematica

Alla base del contare vi sono l’insieme N dei numeri naturali, a tutti ben noto fin dalle scuole elementari, e le sue proprietà. L’insieme N dei numeri naturali viene formalmente determinato dai cinque assiomi seguenti, dovuti al matematico Giuseppe Peano ( 1858-1931): i) 0 è un numero naturale ii) ad ogni numero naturale n corrisponde un altro unico numero naturale detto successore di n

iii) due numeri naturali distinti hanno due successori distinti iv) 0 non è il successore di nessun numero naturale v) qualunque sottoinsieme A di N avente le due proprietà

a) 0∈A b) per tutti gli n ∈N, n∈A ⇒ il successore di n ∈A deve essere l’insieme N.

L’assioma v) viene detto principio di induzione matematica . Invece di n∈A si può dire "n ha la proprietà P". Con questa terminologia il principio di induzione matematica diventa l’assioma seguente:

v’) qualsiasi proprietà dei numeri naturali valida per 0 e valida per il successore di n ogniqualvolta valga per n vale per tutti i numeri naturali .

Dagli assiomi di Peano si può dedurre formalmente tutta l’aritmetica; il primo passo consiste nell' introdurre l’operazione di somma di numeri naturali, in base alla quale, indicato con 1 il successore di 0, si trova subito che il successore di n è n+1, l’operazione di moltiplicazione e nel dimostrarne le proprietà . Non ci inoltriamo in queste definizioni, accenniamo solo al fatto che, a partire dagli assiomi di Peano, è possibile dotare N di un ordinamento totale, il consueto ordinamento secondo grandezza, definito come la relazione ≤ seguente : dati m, n ∈ N , m ≤ n ⇔ ∃ x ∈ N tale che m+x = n .

Capitolo 1 – Il principio di induzione matematica

Università di Torino

2

Si può provare che tale relazione è una relazione di ordine totale verificante la seguente proprietà : v") dato comunque un sottoinsieme non vuoto A di N, A possiede un primo elemento, cioè un elemento m tale che m ≤ a , ∀a ∈ A . Diciamo allora che la relazione data è un buon ordinamento e che l’insieme N è bene ordinato . La proprietà v" può venire assunta come quinto assioma al posto del principio di induzione matematica . In tal caso è semplice dimostrare la validità del principio di induzione : assumiamo quindi che N sia un insieme bene ordinato e dimostriamo il Principio di induzione matematica ( 1a forma ) Sia ( P(n) ) una successione di proposizioni tali che i) P(0) (P(n 0 )) è vera ( base dell’induzione ) ii) La verità di P( k ) implica la verità di P( k + 1 ) , k ≥ 0 (n 0 ) (ipotesi induttiva) Allora P(n) è vera, ∀n ≥ 0 (n 0 ) . Dimostrazione . Sia S = {x > 0 (n0) | P(x) è falsa }. Supponiamo, per assurdo, che S non sia vuoto. Per l’assioma del buon ordinamento di N, S ha un primo elemento, che indichiamo con m. Consideriamo ora la proposizione P(m) : poiché m∈S, P(m) è falsa; inoltre, poiché m è il primo elemento di S, m – 1 ∉ S (e m – 1 ≥ 0 (n0)), quindi la proposizione P(m-1) è vera e la ii) ci dice allora che P(m) è vera . Abbiamo una contraddizione, dunque S è vuoto . In modo del tutto analogo si dimostra il Principio di induzione matematica ( 2a forma ) . Sia ( P(n) ) una successione di proposizioni tali che i) P(0) (P(n 0 )) è vera ( base dell’induzione ) ii) La verità di P(k), ∀ 0 (n 0 ) ≤ k < m, implica la verità di P(m) (ipotesi induttiva) Allora P(n) è vera, ∀n ≥0 (n 0 ) . Il principio di induzione matematica si rivela molto utile per dimostrare proposizioni il cui enunciato dipenda da n ∈ N . Vediamone negli esempi l’uso corretto . Esempi 1.1

1.1.1) Si provi la validità della formula di Gauss : 1 + 2 + …+ n = 2

)1n(n + .



3

Soluzione : in questo caso P(n) è l’affermazione : la somma dei primi n naturali è 2

)1n(n +

.

Base dell’induzione : 1 = 221.

, quindi P(1) è vera

Ipotesi induttiva : P(k) è vera , cioè 1 + 2 +…+ k = 2

)1k(k +

Proviamo la verità di P(k + 1) usando l’ipotesi induttiva .

1 + 2 +…+ k + (k + 1) = 2

)1k(k + + (k + 1) = 2

)2k)(1k( ++

Il principio di induzione matematica (1° forma) ci permette di concludere che P(n) è vera, ∀n ≥1.

Dalla formula di Gauss segue subito la formula che ci dà la somma dei primi n termini di una successione aritmetica di termine iniziale a e di ragione d

a + (a + d) + (a + 2d) + …+ (a + (n-1)d) = 2

)d)1n(a2(n −+ ,

che naturalmente può essere dimostrata indipendentemente per induzione su n .

Lasciamo per esercizio la verifica della formula che dà la somma dei primi n termini di una successione geometrica di termine iniziale a e ragione q ≠1 :

a + aq + aq2 + … + aqn-1 = q1

aqa n

−− .

1.1.2) Come esempio di applicazione del principio di induzione matematica nella 2a forma , dimostriamo la nota proposizione P(n) : ogni numero naturale n > 1 può essere fattorizzato in un prodotto di numeri primi . Base dell’induzione . P(2) è vera : infatti 2 è un numero primo ed è lui la sua fattorizzazione. Ipotesi induttiva : vale P(k), ∀ 2 ≤ k < m Proviamo P(m) . Abbiamo due casi : i) m è primo ed è lui la sua fattorizzazione ii) m non è primo, allora m = m1m2 , con 2 ≤ m1,m2 <m . Per l’ipotesi induttiva m1 e m2 fattorizzano in numeri primi e così avviene quindi per m . Esercizi 1.1



4

1.1.1) Si provi che la somma dei primi n numeri naturali dispari consecutivi vale n2 . Soluzione . Dobbiamo verificare, per induzione su n, che vale la relazione

1 + 3 + 5 +…+ (2n-1) = n2 Base induttiva : 1 = 12 vera Supponiamo ora che 1 + 3 + 5 +…+ (2n-1) uguagli n2 (ipotesi induttiva) e proviamo che

1 + 3 + 5 +…+ (2(n+1)-1) = 1 + 3 + 5 +…+ (2n+1) = (n + 1)2 .

Svolgendo e usando l’ipotesi abbiamo :

1 + 3 + 5 +…+ (2n-1) + (2n +1) = n2 + (2n+1) = n2 + 2n+1 = n2 + 2n+1 = (n+1)2. 1.1.2) Chiamiamo n - stringa binaria una sequenza di n cifre scelte tra 0 e 1 . Si provi , per induzione su n , che il loro numero è 2n

Base dell’induzione : le 1-stringhe binarie sono 2 , precisamente 0 e 1 . Ipotesi induttiva : supponiamo che le k-stringhe binarie siano in totale 2k . Costruiamo le k + 1 – stringhe binarie , conoscendo quelle di lunghezza k : possiamo procedere premettendo la cifra 0 a tutte e poi ripetere il procedimento premettendo 1 . Otteniamo così 2k + 2k = 2k+1 k + 1 – stringhe . 1.1.3) Si provi per induzione che ogni affrancatura di importo maggiore o uguale a otto centesimi di euro può essere ottenuta usando solamente francobolli da tre e da cinque centesimi di euro.

Soluzione : la base induttiva è ovviamente vera : 8 = 5 + 3 . Ipotesi induttiva : l’affermazione è vera per un importo di k centesimi , ottenibile con h francobolli da tre e con n francobolli da cinque centesimi ( k = h3 + n5 ). Se n = 0 , h ≥3 e k + 1 = h3 + 1 = (h – 3)3 + 2 . 5 ( invece di tre francobolli da tre ne abbiamo due da cinque ). Se n ≥1 , k + 1 = h3 + n5 + 1 = (h + 2)3 + (n – 1)5 (abbiamo due francobolli da tre invece di uno da cinque ). Naturalmente questo esercizio equivale a dimostrare che 8k ≥∀ , k∈N, può essere scritto come combinazione lineare a coefficienti in N di 3 e di 5. 1.1.4) Sia I un insieme finito di ordine n . Si provi per induzione su n che il suo insieme delle parti P(I) ha 2n elementi . Soluzione . Base dell’induzione : n = 0 . In questo caso I = ∅ e P(I) = {∅}.Quindi P(I)= 20 = 1 Ipotesi induttiva : supponiamo n > 0 e la proprietà vera per un insieme di n – 1 elementi .



5

Sia I = {a1,…,an-1,an} e fissiamo la nostra attenzione su an . I sottoinsiemi di I che non lo contengono sono esattamente i sottoinsiemi di I - {an} , quindi sono 2n-1, per l’ipotesi induttiva . I sottoinsiemi di I che lo contengono sono del tipo A∪{an}, dove A è un sottoinsieme di I - {an}, quindi anch’essi sono 2n-1 . In totale dunque i sottoinsiemi di I sono 2n-1 + 2n-1 = 2 . 2n-1= = 2n . L’esercizio 1.1.4) dà la stessa risposta dell’esercizio 1.1.3) : tra l’insieme delle parti di un insieme con n elementi a1,…, an e l’insieme delle n - stringhe binarie c’è una corrispondenza biunivoca ottenuta associando a ogni sottoinsieme S di I la stringa in cui la i-sima cifra binaria vale 1 se ai S∈ , vale 0 altrimenti ( ovviamente a I si associa (1,1,…, 1) , all’insieme vuoto (0,0,…, 0) ) .

1.1.5) Si dimostri, con la 2a forma del principio di induzione matematica, l’algoritmo di divisione in N :

∀ m , n ∈N , m>0,n≥0 , ∃q,r∈N (0≤ r <m) n = qm + r

Soluzione : Per induzione sul numero n . Se n = 0 ( base dell’induzione ) , basta porre q = r = 0, ottenendo P(0). Se m > n , basta porre q = 0 e r = n < m . Se m ≤ n , supponiamo P(k) vera , ∀0 ≤ k <n (ipotesi induttiva) e proviamo P(n). Poiché m ≤ n , 0 ≤ n – m < n e P(n-m) vale .Quindi esistono q’ e r’, con 0≤ r’<m tali che n-m=q’m + r’ da cui n = (q’+1)m + r’ .



6

Daniela Romagnoli – Problemi di combinatorica 7


Capitolo 2

Alcuni problemi combinatorici

Il calcolo combinatorio prende in considerazione degli insiemi finiti particolari e ne conta l’ordine . Questo può dar luogo ad interessanti e utili applicazioni . Premettiamo che se I è un insieme contenente solo un numero finito di elementi , tale numero è un numero naturale , detto ordine o cardinalità di I , e indicato con I oppure con # I . Un insieme finito I ha ordine 0 se e solo se I = ∅ e ha ordine n ≥ 1 se e solo se è in corrispondenza biunivoca con il sottoinsieme In = {1,…,n-1,n} di N . Se I è un insieme finito di ordine n e A è un suo sottoinsieme di ordine m , allora m ≤ n , cioè A ≤ I . Ci occupiamo in questo capitolo di qualche problema di combinatorica e delle sue applicazioni Problema 1 . Contare i sottoinsiemi di un insieme finito . Ricordiamo che , dato un insieme I , finito o infinito , si dice suo insieme delle parti , o insieme potenza l’insieme

P(I) = {A A ⊆ I }. P(I) non è mai vuoto ( ogni insieme I ha i sottoinsiemi banali ∅ e I stesso ) , se I è infinito anche P(I) contiene infiniti elementi , se I è finito vale la Proposizione 1.1. Sia I un insieme finito di ordine n . Allora P(I) ha 2n elementi . Dimostrazione . Vedi l’esercizio 1.1.3 del capitolo 1, in cui si dimostra la proposizione 1.1 per induzione su n. Esempio 1.1 Costruiamo l’insieme delle parti dell’insieme I = {V,R,N} contenente tre palline di colore verde, rosso e nero

P(I) = {∅, {V}, {R}, {N}, {V,R}, {V,N}, {R,N}, {V, R, N } } .

Capitolo 2 – Alcuni problemi di combinatorica


8

Problema 2 . Contare gli elementi dell’unione di due insiemi finiti . Proposizione 2.1 Siano A e B due insiemi finiti disgiunti di ordine n ed m rispettivamente. Allora

A∪B= A + B = n + m Dimostrazione. Sia f la biiezione di In = {1,…,n-1,n} in A e g quella di Im = {1,…,m-1,m} in B. E’ possibile definire una biiezione h di In+m = {1,…,n+m -1, n+m} in AUB nel modo seguente :

h(i) = f(i) , ∀ i = 1,2,…, n , h(n+i) = g(i) , ∀ i = 1,2,…, m .

La Proposizione 2.1 si generalizza al caso di n insiemi finiti Ai , i = 1, 2, …, n , disgiunti , fornendo l’uguaglianza :

A1∪ … ∪An = ∑n

iA1

Dimostrazione. Per induzione su n. Proposizione 2.2 . Siano A e B due insiemi finiti di ordine n ed m rispettivamente e sia k l’ordine di A∩B . Allora

A∪B= A + B - A ∩B

cioè

A∪B = n + m – k

Dimostrazione. Se gli insiemi A e B hanno k elementi in comune, sommando l’ordine di A con l’ordine di B questi vengono contati due volte, dunque occorre sottrarli una volta per ottenere l’ordine di AUB. Queste due proposizioni risultano utili per risolvere semplici problemi combinatorici Esempi 2.1 2.1.1) Su 25 studenti , 15 hanno superato l’esame di Matematica , 12 quello di Chimica e 5 hanno superato entrambi gli esami . Quanti studenti hanno superato almeno un esame ? Quanti studenti hanno fallito entrambi gli esami ? Sia A l’insieme degli studenti che hanno superato l’esame di Matematica , A ha ordine 15. Sia B l’insieme degli studenti che hanno superato l’esame di Chimica , B ha ordine 12 . A∩B è l’insieme degli studenti che hanno superato entrambi gli esami , A∩B ha ordine 5. La risposta alla prima domanda è l’ordine dell’insieme A∪B , dato da 15 + 12 – 5 = 22 . Non hanno superato nessuno dei due esami 25 – 22 = 3 studenti .



2.1.2) Sia I = {1, 2,…, 20}. Quanti sono i numeri di I divisibili per 2 o per 3 ? Sia A l’insieme dei numeri pari di I , l’ordine di A è 10. Sia B l’insieme dei multipli di 3 minori di 20 , B = {3, 6, 9, 12, 15, 18} ha ordine 6 . A∩B è l’insieme dei multipli di 6 minori di 20 , A∩B = { 6, 12, 18} ha ordine 3. I numeri di I divisibili per 2 o per 3 sono 10 + 6 – 3 = 13 . La Proposizione 2.2 si generalizza al caso di n insiemi finiti Ai , i = 1, 2, …, n , dando luogo al principio di Inclusione-Esclusione , che ci permette di calcolare l’ordine di un’unione finita di insiemi finiti, conoscendo l’ordine delle intersezioni. Lo useremo per contare le permutazioni prive di punti fissi ( problema 5) e per contare le funzioni suriettive tra due insiemi finiti ( problema 10). Principio di Inclusione-Esclusione . Siano A1, A2, …, An n insiemi di ordine finito.Si ha :

A1∪ … ∪An = ∑n

iA1

- ∑<

∩ji

ji AA + ∑<<

∩∩kji

kji AAA - …

La dimostrazione di questo principio non presenta particolari difficoltà , la riportiamo per il caso n = 3 , con un esempio di applicazione . Dunque , per n = 3 , dobbiamo provare che A1∪A2 ∪A3 = A1+ A2+A3 - A1∩ A2 - A1∩ A3 - A2∩ A3 + A1∩ A2∩A3 Dimostrazione. Sia x un elemento che appartiene solo ad A1 : x dà il contributo 1 all’addendo A1e 0 a tutti gli altri . Così se x appartiene solo ad A2 o ad A3.

Se x appartiene sia ad A1 che ad A2, ma non ad A3, esso dà contributo 1 agli addendi A1, A2e A1∩ A2e contributo 0 a tutti gli altri. In totale quindi esso viene conteggiato 1+1-1 = 1 volte . Così se x appartiene sia ad A1 che ad A3, ma non ad A2 oppure sia ad A2 che ad A3, ma non ad A1. Se, infine, x appartiene ad A1, ad A2 e ad A3, la somma dei vari addendi vale 1+1+1-1-1-1+1 = 1 . Ne deduciamo che la somma a secondo membro ci conta esattamente una volta l’elemento x , comunque sia scelto in A1∪A2 ∪A3 , e quindi essa ci dà l’ordine di A1∪A2 ∪A3 Esempio 2.2 In un gruppo di amici , 8 hanno visto il film x , 12 il film y e 9 il film z . Inoltre 6 hanno visto x e y , 4 x e z , 7 y e z e soltanto uno di essi ha assistito alle tre proiezioni . Da quante persone è formato il gruppo ? Abbiamo:



10

X = 8 ,Y= 12 ,Z= 9 , X∩Y = 6 , X∩ Z= 4 , Y∩ Z= 7 , X∩ Y∩Z= 1 e quindi : X∪Y ∪Z = 8 + 12 + 9 – 6 – 4 – 7 + 1 = 13 . Problema 3. Contare gli elementi del prodotto cartesiano di due insiemi finiti. Proposizione 3.1 Siano A e B due insiemi finiti di ordine n e m rispettivamente. Allora

A x B = A.B= nm Dimostrazione . Sia A = {a1, a2, …, an} . Consideriamo gli n sottoinsiemi Ai a due a due disgiunti formati ognuno dalle m coppie aventi ai come prima componente . Per la Proposizione 2.2 generalizzata abbiamo

A x B = A1∪ … ∪An = ∑n

iA1

= nm

Osservazione Disponendo in colonna e in riga gli n elementi di A e gli m elementi di B , il prodotto cartesiano A x B può essere visualizzato come una tabella di nm quadretti .. La Proposizione 3.1 motiva il “ metodo delle scelte “ , di cui si fa un grande uso in combinatorica e in molte applicazioni della vita pratica : supponiamo di voler contare in quanti modi si può costruire una coppia (a,b) , se a appartiene a un insieme con n elementi e b ad uno con m elementi , cioè se posso scegliere a in n modi e b in m modi . La proposizione 3.1 dice che la coppia (a,b) può essere costruita in nm modi . Questo metodo viene anche chiamato “ principio di moltiplicazione delle scelte “ e così formulato : Se una scelta può essere compiuta in n modi diversi e , per ciascuno di essi ,una seconda scelta può essere compiuta in m modi diversi , allora la successione delle due scelte può essere effettuata in n.m modi distinti . In modo naturale tutto quanto visto per il prodotto cartesiano di due insiemi finiti si estende al caso del prodotto cartesiano di un numero finito di insiemi finiti . Il “ principio di moltiplicazione delle scelte “ (anche nella sua forma estesa a più di due scelte) ci permette di risolvere molti problemi combinatorici . Esempio 3.1 . Usiamo il metodo delle scelte per dare un’altra dimostrazione della Proposizione 1.1 Sia I un insieme finito di ordine n . Allora P(I) ha 2n elementi .



Dimostrazione . Sia I = {a1,…,an} . Vogliamo contare i modi per costruire un sottoinsieme A di I . Ogni elemento di I può appartenere o non appartenere ad A , cioè abbiamo due possibilità di scelta per ogni ai , i = 1,…,n . Vi sono quindi 2.2.….2 = 2n modi per costruire A da cui la tesi . Esercizi 3.1 3.1.1) Quanti oggetti possiamo differenziare con delle targhe di due simboli di cui il

primo è una lettera scelta tra a,b,c,d e il secondo è una cifra da 1 a 5 ? Le lettere possono essere scelte in 4 modi , le cifre in 5 modi : possiamo costruire 20 targhe diverse .

3.1.2) Supponiamo che il menu di un ristorante consista di 5 antipasti , 6 primi , 6 secondi e 4 dolci : quanti pasti completi ( di quattro piatti ) possiamo ordinare ?

Le quaterne ordinate ( e quindi le scelte possibili ) sono 5 . 6 . 6 . 4 = 720 .

3.1.3) In una regione vi sono venti città , collegate a coppie da una strada comunale . Quante strade comunali possiede la regione in questione ?

Osserviamo che ogni strada collega due diverse città . Abbiamo 20 scelte diverse per la partenza e 19 per l’arrivo di una strada : le scelte possibili sono quindi 20 . 19 . In tal modo però ogni strada ab è stata contata due volte : una volta con a città di partenza e b di arrivo e una volta con b partenza e a arrivo ; ne segue che il numero cercato è (20 . 19) : 2 = 190 3.1.4) Quante diagonali ha un poligono convesso di 6 lati ? Osserviamo che ognuno dei 6 vertici può essere scelto come primo punto di una diagonale mentre come scelta per il secondo punto dobbiamo escludere il vertice in questione e i due a lui adiacenti . Abbiamo dunque 6-3 = 3 scelte per il secondo punto di ogni diagonale e 6 scelte per il primo . Il prodotto delle scelte deve però essere diviso per due (detti v1,…v6 i vertici dell’esagono, la diagonale v1v3 coincide con la v3v1 ecc.). Dunque le diagonali di

un esagono sono2

)36(6 − = 9.

Con le stesse argomentazioni si dimostra che le diagonali di un n-gono sono 2

)3n(n − .

3.1.5) Quanti numeri di sei cifre hanno almeno una cifra pari ? Soluzione :Abbiamo dieci cifre ( 0,1,…,9 ) : di queste ve ne sono cinque pari ( 0,2,4,6,8 ) e cinque dispari ( 1,3,5,7,9 ) . Vi sono 9 . 10 . 10 . 10 . 10 . 10=900000 numeri con sei cifre ( per la prima cifra devo escludere lo 0 e quindi ho 9 scelte anziché 10 ) e 56 = 15625



12

numeri con sei cifre tutte dispari I numeri di sei cifre aventi almeno una cifra pari sono quindi 900000 – 15625 = 884375 . Problema 4 . Contare le funzioni tra due insiemi finiti.

Ricordiamo che si definisce corrispondenza dell’insieme I nell’insieme I’ un sottoinsieme F del prodotto cartesiano I x I’ e che una corrispondenza è detta : funzionale se ogni x di I ha al più una immagine ovunque definita se ogni x di I ha almeno una immagine iniettiva se ogni elemento di I’ ha al più una controimmagine (o equivalentemente se elementi distinti hanno immagini distinte ) suriettiva se ogni elemento di I’ ha almeno una controimmagine Come corollario immediato del problema 1 abbiamo che le corrispondenze tra un insieme di ordine n e uno di ordine m sono 2nm , tante quante i sottoinsiemi di In x Im . Le corrispondenze più importanti sono le funzioni, cioè le corrispondenze ovunque definite e funzionali . Una funzione iniettiva e suriettiva è detta corrispondenza biunivoca o biiezione e il loro numero sarà oggetto del problema 5. Proposizione 4.1 Le funzioni da un insieme di ordine n in un insieme di ordine m sono mn . . Dimostrazione (con il metodo delle scelte). Dare una funzione da un insieme di ordine n in un insieme di ordine m significa dare le immagini degli n elementi del dominio . Per l’immagine del primo elemento ho m scelte , tante quanti sono gli elementi del codominio , per l’immagine del secondo elemento ho ancora m scelte ,…, così per l’immagine dell’n-simo elemento . In totale avrò m m ...m = mn scelte . Osservazione 4.1 Una funzione di un insieme con n elementi in un insieme di m elementi può essere vista come una n-pla ordinata di elementi (le immagini) scelti tra m , con possibilità di ripetizioni . Per questo motivo tali funzioni sono anche dette disposizioni con ripetizione : per quanto provato sopra il numero delle disposizioni con ripetizione di m elementi a n a n è mn . Esempi 4.1 4.1.1) Le funzioni di I3 in I2 sono identificabili con le 8 terne (1,1,1),(1,1,2),(1,2,1),(1,2,2) , (2,1,1) , (2,1,2) , (2,2,1) , (2,2,2) . La prima è la funzione costante di valore 1 , la seconda è la funzione che manda 1 in 1, 2 in 1,3 in 2 , … , l’ultima è la funzione costante di valore 2 . 4.1.2) Vogliamo calcolare il numero delle colonne tra loro diverse che si possono giocare al totocalcio . Come è noto , il gioco consiste nell’assegnare uno dei tre simboli 1 , x , 2 ad



ognuna delle 13 partite . Ogni colonna può essere identificata con una sequenza ordinata di elementi scelti tra 1,x,2 e quindi con una funzione di un insieme con 13 elementi (le tredici partite) in un insieme con 3 elementi (i tre simboli citati) . Le colonne possibili sono quindi 313 = 1594323 .Giocando tutte queste colonne si ha la certezza del tredici (purtroppo con una spesa superiore alla vincita !!) . Problema 5. Contare le biiezioni di un insieme finito con n elementi in se stesso . Premettiamo alcune notazioni . Definizione 5.1 Dato un numero naturale n > 0 , chiamiamo fattoriale di n il numero

n! = 1 . 2 . …. (n – 2) . (n-1) . n Si pone inoltre 0! = 1 . Osservazione 5.1 n! cresce rapidamente al crescere di n : ne diamo i primi dieci valori n n!

1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 3628800

Proposizione 5.1 Siano A e B due insiemi finiti dello stesso ordine n. Le biiezioni tra di essi sono n! . Dimostrazione 1. Con il metodo delle scelte . Per individuare una biiezione, noti il dominio e il codominio, basta assegnare le n immagini degli n elementi del dominio . Ora, per l’immagine del primo elemento di A abbiamo n scelte (qualunque elemento di B), per l’immagine del secondo elemento di A abbiamo n-1 scelte (dobbiamo escludere l’elemento di B immagine del primo elemento di A ), … , per l’immagine dell’n-simo elemento di A la scelta è unica . Si possono dunque effettuare n! scelte : ad ognuna corrisponde una diversa biiezione di A in B . Dimostrazione 2. Con l’induzione .



14

Sia n = 1 ( Base dell’induzione ) . Se A e B hanno un elemento ciascuno l’unica biiezione è quella che li fa corrispondere ( e 1 = 1! ) Ipotesi induttiva : supponiamo di sapere che tra due insiemi di ordine n-1 vi sono (n-1)! biiezioni . Sia ora A di ordine n : una biiezione di A in B (anch’esso di ordine n ) si ottiene dando una biiezione su n-1 elementi e dando l’immagine dell’elemento rimasto : Si hanno così (n-1)! biiezioni con la stessa immagine per il primo elemento di A , (n-1)! con la stessa immagine per il secondo elemento di A ,…, (n-1)! con la stessa immagine per l’n-simo elemento di A . In totale le biiezioni cercate sono n . (n-1)! = n ! Nel caso in cui i due insiemi A e B coincidano , le biiezioni di A in se stesso vengono dette permutazioni di A . Abbiamo così il Corollario 5.2. Le permutazioni di un insieme di ordine n sono n! Per comodità di scrittura poniamo , nel seguito , A = In = { 1, 2,…, n } ( identifichiamo in pratica gli elementi dell’insieme con i loro indici ) e facciamo alcune considerazioni . Ricordiamo che è notazione standard indicare con

)n(f...)2(f)1(f

n...21

la biiezione f che manda 1 in f(1) , 2 in f(2), … , n in f(n) . Così , per esempio , per n = 4 , la scrittura

32144321

rappresenta la biiezione che manda 1 in 4 , 2 in 1 , 3 in 2 e 4 in 3 .

Con questa notazione diventa semplice comporre due permutazioni e trovare l’inversa di una permutazione . Vediamolo su un esempio .

Esempio 5.1 Sia n = 4 e siano f la permutazione precedente e g la seguente :

34124321

g ° f è la permutazione che otteniamo applicando i due fattori successivamente (prima f poi g): possiamo pensare di scrivere su tre righe , omettendo poi il passaggio intermedio :

412332144321



da cui troviamo la composizione cercata :

41234321

L’inversa di una permutazione si ottiene scambiando le due righe e riordinando poi le colonne in modo che la prima riga diventi la riga 1 2 3 4 . Scambiando le righe di f , abbiamo :

.

43213214

e, riordinando le colonne , abbiamo f -1 :

14324321

Ricordando che la composizione di funzioni è un operazione associativa e non commutativa , si ha la Proposizione 5.3 L’insieme di tutte le permutazioni di un insieme di ordine n , rispetto all’operazione di composizione , è un gruppo non abeliano . Tale gruppo , che ha un’ importanza fondamentale all’interno della teoria dei gruppi , si indica solitamente con il simbolo Sn e si chiama gruppo simmetrico(totale) : abbiamo provato che esso ha ordine n! . Se scriviamo le n! permutazioni dei numeri da 1 a n , vediamo che nella seconda riga delle tabelline abbiamo scritto gli n numeri in tutti gli ordini possibili esattamente una volta : abbiamo ordinato (allineato ) in tutti i modi possibili i nostri elementi . Possiamo dedurre che n oggetti distinti possono essere ordinati in n! modi possibili . Si dice quindi ,per estensione, permutazione di n oggetti distinti un qualunque loro ordinamento o allineamento . Questi ordinamenti si ottengono uno dall’altro permutando gli n oggetti e la teoria svolta ci dice che ne otteniamo in totale n! (corrispondenti alle seconde righe delle tabelline precedenti ) . Si scrive anche Pn = n! , per indicare il numero totale delle permutazioni di n oggetti distinti . Esempi 5.2 5.2.1) Scriviamo tutte le 3! = 6 permutazioni di 3 palline di colore B (bianco),R (rosso), V (verde) .



16

Abbiamo due allineamenti che mettono la pallina B al primo posto , altrettanti per R e V

B R V B V R R V B R B V V B R V R B .

5.2.2) Quanti sono gli anagrammi della parola madre ? E della parola mamma ? Osserviamo che si definisce alfabeto un insieme finito di simboli e, dato un certo alfabeto (qui si tratta dell’alfabeto latino di 26 lettere), si definisce parola un qualunque allineamento dei suoi simboli . Il numero di simboli è detto lunghezza della parola. Se n è l’ordine dell’alfabeto, le parole di lunghezza m sono in totale nm . Non è richiesto quindi che la parola che si ottiene anagrammando madre abbia un significato nella lingua italiana, né che ne segua le regole grammaticali, quindi dobbiamo contare in quanti modi si possono allineare le cinque lettere m,a,d,r,e . I modi sono tanti quante le permutazioni di 5 oggetti , cioè 5! = 120 . Osserviamo che, in generale, gli anagrammi di una parola con n lettere distinte sono n! Nella parola mamma vi sono invece delle lettere ripetute , due a e tre m : gli anagrammi

saranno 3! 2!

!5. . Motiviamo così questo fatto: passiamo da mamma (che ha due lettere

ripetute) a mamme ( che ha una sola lettera ripetuta ) e da mamme a madre (che ha tutte lettere distinte) . Gli anagrammi di mamme sono la sesta parte di quelli di madre : da ogni anagramma di mamme ne ottengo 6 = 3! di madre ,sostituendo nelle posizioni delle tre m i 3! anagrammi della parola mdr . A loro volta gli anagrammi di mamme sono il doppio (2 = 2!) di quelli di mamma ( ogni anagramma di mamma ci dà due anagrammi di mamme sostituendo al posto delle due a i due anagrammi di ae ) . Sia ora Dn l’insieme delle permutazioni di In prive di punti fissi. In simboli:

Dn = { nSf ∈ / f(i) }n,...,1i,i =∀≠ .

Le permutazioni senza punti fissi vengono anche chiamate dismutazioni o derangements. Possiamo calcolare l’ordine di Dn usando il principio di inclusione-esclusione dimostrato nel problema 2 . Proposizione 5.4

nD = n!∑=

−n

0i

i

!i)1(

Dimostrazione. Sia Ai = { nSf ∈ / f(i) }i= l’insieme delle permutazioni che fissano i. Osserviamo che, data una k-pla di elementi, le permutazioni che la fissano sono tante quante le permutazioni dei restanti n-k elementi, cioe sono (n-k)! , e che le k-ple sono le

Cn,k, quindi sono)!kn(!k

!n−

(vedi problema 7).



Abbiamo dunque che l’ordine dell’insieme delle permutazioni che fissano k elementi è, per

il principio delle scelte, (n-k)! )!kn(!k

!n−

= !k!n .

Quindi, l’insieme delle permutazioni che fissano un elemento ha ordine n!, l’insieme di

quelle che ne fissano 2 ha ordine !2!n , … , l’insieme delle permutazioni che fissano n

elementi ha ordine !n!n . Il principio di inclusione-esclusione ci dà :

A1∪ … ∪An = ∑n

iA1

- ∑<

∩ji

ji AA + ∑<<

∩∩kji

kji AAA - … =

= n! - !2!n +

!3!n -…+ (-1)n+1

!n!n = ∑

=

+−n

1i

1i

!i!n)1(

Questo è l’ordine dell’insieme delle permutazioni che fissano almeno un elemento, quindi l’ordine dell’insieme Dn delle permutazioni che non ne fissano nessuno sarà dato dalla differenza

n! – ( n! - !2!n +

!3!n -…+ (-1)n+1

!n!n ) = n! - ∑

=

+−n

1i

1i

!i!n)1( = ∑

=

−n

0i

i

!i!n)1( = n!∑

=

−n

0i

i

!i)1(

Esempio 5.3 Gli spiazzamenti di 1,2,3, sono 2 : 2,3,1 e 3,1,2 . Numerando in tal modo i vertici di un triangolo equilatero , le 6 permutazioni del gruppo S3 danno il gruppo diedrale delle isometrie del triangolo , formato dalle tre rotazioni di 120, 240, 360 gradi e dai tre ribaltamenti rispetto alle altezze . I 2 spiazzamenti corrispondono alle due rotazioni di 120 e 240 gradi . I ribaltamenti hanno ciascuno un punto fisso, la rotazione di 360 gradi ha tre punti fissi . Esercizi 5.1

5.1.1) Dire quanti sono gli anagrammi della parola logica e della parola matematica .

Soluzione : sono 6! e 2!3!2!

!10.. rispettivamente .

5.1.2) Scrivere tutti i numeri formati dalle cifre 1 , 2 , 3 non ripetute

Soluzione : 123, 132 , 213 , 231 , 312 , 321 .

5.1.3) In quanti modi si possono trovare disposte le carte di un mazzo da 40 ? Soluzione : 40!



18

5.1.4) Uno studente deve sostenere 5 esami ogni anno per i 4 anni di durata del suo corso

di studi, senza poter rimandare un esame da un anno all’altro, nell’ordine da lui preferito .

Quante sono le possibili sequenze dei 20 esami ?

Soluzione : 5! . 5! . 5! . 5! 5.1.5) In quanti modi diversi si possono sedere ad un tavolo circolare 3 persone ?

Il problema equivale a segnare 3 punti su un cerchio ed è chiaro che operando una rotazione degli stessi si ottiene la stessa configurazione , quindi la sequenza 123 non è diversa da 312 e da 231, mentre la sequenza 132 equivale a 213 e a 321 . La risposta è

quindi 2 = 3!3 .

Si prova che in generale le possibili configurazioni di n persone intorno ad un tavolo

circolare sono )!1n(n!n

−= . Il loro insieme viene detto insieme delle permutazioni

circolari di n elementi. 5.1.6) Contare quante collane diverse possono essere costruite con 15 perle di colore

differente. Soluzione . Ogni collana è vista come una permutazione circolare di 15 oggetti, il cui

numero è 14! . Osserviamo che una collana può essere ruotata, ma anche ribaltata (ciò non poteva accadere al tavolo dell’esercizio precedente), quindi il numero di collane

differenti è 2

!14

Problema 6. Contare le funzioni iniettiva da un insieme di ordine k in un insieme di ordine n . Definizione 6.1 Si dice disposizione ( di n oggetti a k a k ) una funzione iniettiva di un insieme di ordine k in un insieme di ordine n (k ≤ n) . Il numero totale delle disposizioni di n oggetti a k a k si indica con Dn,k . Proposizione 6.1 Sia A un insieme di ordine k e B un insieme di ordine n . Vi sono

Dn,k = n.(n-1).….(n-k+1) =

)!kn(!n−

funzioni iniettive di A in B . Dimostrazione 1 . Per induzione su k .



Base dell’induzione . Sia k = 1 . L’insieme A ha un solo elemento , si hanno evidentemente n funzioni iniettive di A in B e Dn,1 = n Ipotesi induttiva . Supponiamo di sapere che se A ha k elementi vi sono Dn,k funzioni iniettive di A in B . Sia ora A di ordine k+1 . Abbiamo aggiunto ad A un elemento : per ognuna delle funzioni iniettive già considerate ne otteniamo n-k di A in B perché k elementi di B sono già immagini di elementi di A (per l’iniettività elementi distinti devono avere immagini distinte) , quindi abbiamo la relazione

Dn,k+1 = Dn,k . (n-k) = n.(n-1).….(n-k+1)(n-k) = )!1kn(

!n−−

Dimostrazione 2. Con il metodo delle scelte.

Sia A = {a1, … , ak }. Contiamo in quanti modi si può costruire una funzione iniettiva f : A → B . Per f(a1) si hanno n scelte (f(a1) può essere uno qualunque degli elementi di B), per f(a2) si hanno n-1 scelte (f(a2) deve essere diversa da f(a1) per l’iniettività) , … , per f(ak) si hanno n-k+1 scelte . Si hanno quindi n(n-1) … (n-k+1) = n!/(n-k)! modi di costruire una funzione iniettiva di A in B e , quindi ci sono Dn,k funzioni iniettive di A in B . Osservazione 6.1 . Se A = B ( e quindi n = k) ogni funzione iniettiva di A in A è una biiezione e Dn,n = n!/0! = n! = Pn diventa il numero delle permutazioni di n oggetti distinti . Osservazione 6.2 Come già osservato nel caso delle permutazioni, il numero Dn,k può essere visto come il numero di modi in cui si possono allineare (ordinare) k oggetti presi in un insieme di n : possiamo pensare al dominio A come a un insieme di k caselle e far corrispondere a ciascuna di esse l’oggetto che la occupa , oggetto preso dall’insieme B . Così , per esempio, se B è l’insieme formato da tre palline di colore verde (V), rosso (R), nero (N) le disposizioni di queste tre palline a due a due sono D3,2 = 3!/1!=6 , e precisamente, sono gli allineamenti seguenti

VR,RV,VN,NV,RN,NR, che corrispondono alle sei funzioni iniettive di A = {a1, a2 } in B = {V, R, N } :

f1(a1) = V, f1(a2) = R f2(a1) = R, f2(a2) = V f3(a1) = V, f3(a2) = N f4(a1) = N, f4(a2) = V f5(a1) = R, f5(a2) = N

f6(a1) = N, f6(a2) = R .



20

Esercizi 6.1

6.1.1) Scrivere le disposizioni dei quattro numeri 1,2,3,4 a due a due (equivalentemente , quanti numeri diversi di due cifre scelte tra le quattro assegnate si possono formare ? )

Soluzione : si hanno dodici coppie ordinate di numeri , precisamente 1 2 , 1 3 , 1 4 , 2 3 , 2 4 , 3 4 2 1 , 3 1 , 4 1 , 3 2 , 4 2 , 4 3 6.1.2) In quanti modi 3 oggetti possono essere colorati con 5 colori diversi ?

Soluzione : Il numero richiesto è D5,3 = !2!5 = 3.4.5 = 60 .

6.1.3) A un campionato di calcio partecipano nove squadre. Se ogni squadra incontra tutte le

altre due volte , quante partite devono essere giocate ? Soluzione : Si giocano 72 partite , il numero delle disposizioni di 9 oggetti a due a due 6.1.4) Uno studente ha costruito in cartone i modelli di 5 poligoni regolari con 3, 4, 5, 6, 8

lati rispettivamente e li vuole colorare con i 7 colori a sua disposizione : bianco, nero, giallo, verde, blu , rosso e viola. a) In quanti modi diversi può colorare i poligoni con i sette colori ?

b) In quanti modi diversi può colorare i poligoni con i sette colori in modo che ogni poligono abbia un colore diverso ? Soluzione : a) I modi diversi di colorare sono dati dalle disposizioni con ripetizione di 7 elementi a cinque a cinque : sono dunque 75 . Ricordiamo che le disposizioni con ripetizione di 7 elementi a cinque a cinque sono le funzioni da un insieme con 5 elementi in uno con 7 . Si pensi di associare ad ogni poligono un colore : per il triangolo abbiamo 7 scelte, così per il quadrato (che può essere dello stesso colore del triangolo), per il pentagono ecc. b ) Se si richiede che non vi siano due modelli con lo stesso colore , le scelte possibili sono date dal numero 7 . 6 . 5 . 4 . 3 , cioè dal numero delle funzioni iniettive da un insieme con 5 elementi in uno con 7, le disposizioni semplici di 7 oggetti a cinque a cinque :

D7,5 = =− )!57(!7

!2! 7 = 3 . 4 . 5 . 6 . 7

Abbiamo assunto in precedenza che k fosse minore di n . Proviamo ora la



Proposizione 6.4 . Se k > n , non esistono funzioni iniettive da un insieme I di ordine k in un insieme I’ di ordine n . Dimostrazione. Non è restrittivo supporre I = I k = {1,2,…,k}e I’ = I n = {1,2,…,n}. Procediamo per induzione su n . Base dell’induzione : n = 0. In questo caso I’ = ∅ e non esiste alcuna funzione da un insieme non vuoto nell’insieme vuoto ( I x ∅ = ∅ , da I in ∅ esiste solo la corrispondenza vuota). Ipotesi induttiva : supponiamo vera la proposizione per n , cioè supponiamo che, ∀ k > n, non esista una iniezione da Ik in I n e proviamo la affermazione per n +1. Supponiamo, per assurdo, che ∃ k > n + 1 con una iniezione f da Ik in In+1 = {1,2,…,n,n+1}. Poiché In+1 = I n∪{n+1}, deve essere n + 1 = f(i), per qualche i di Ik, altrimenti f sarebbe una iniezione da Ik in In . Se i = k , eliminiamo la coppia (k , n + 1); altrimenti, scambiamo tra di loro le immagini g(i) e g(k) ed eliminiamo la nuova coppia (k, n + 1) : consideriamo cioè la funzione f’ tale che f’(i) = f(k) e f’(j) = f(j) per ogni altro j < k, j ≠ i . Questa funzione f’ risulta una funzione iniettiva da Ik - 1 in In , contro l’ipotesi induttiva . La proposizione 6.4 è detta principio dei cassetti (o principio delle gabbie dei piccioni) e può venire così riformulata se chiamiamo oggetti (piccioni) gli elementi del dominio e cassetti (gabbie) le loro immagini : se in n cassetti (gabbie ) ho k > n oggetti (piccioni) , qualche cassetto (gabbia) contiene almeno 2 oggetti (piccioni). Osservazione 6.3 Il principio dei cassetti può essere esteso , diventando il Principio generale dei cassetti ( o delle gabbie dei piccioni ) : Se ho nk + 1 oggetti (piccioni) da riporre in n cassetti (gabbie) , qualche cassetto (gabbia) ne contiene almeno k + 1 . Per k = 1 , si ritrova il principio enunciato prima ( se ho n + 1 oggetti in n cassetti , qualche cassetto ne contiene almeno 2 ) . Esempio 6.2 Dobbiamo riporre 25 mele in 3 ceste : 25 = 3.8 + 1 . Usando il principio generale dei piccioni con n = 3 e k = 8 , avremo che qualche cesta contiene almeno 8 + 1 = 9 mele Con il principio generale dei cassetti si risolvono i seguenti esercizi : Esercizi 6.2



22

6.2.1) Assumendo che nessun essere umano abbia più di un milione di capelli , provare che in una città con più di un milione di abitanti ci sono almeno due persone aventi lo stesso numero di capelli . Soluzione : Numeriamo da 0 a 1.000.000 dei cassetti virtuali e vediamo gli abitanti come gli oggetti con cui riempirli . Metteremo la persona nel cassetto x se e solo se essa possiede esattamente x capelli . Per il principio dei cassetti , ce n’è almeno uno contenente due persone , aventi quindi lo stesso numero di capelli .

6.2.2) Supponiamo che i numeri da 1 a 10 siano posizionati casualmente su una circonferenza . Allora la somma di qualche terna di numeri consecutivi è almeno 17 . Soluzione : vi sono 10 terne di numeri consecutivi sulla circonferenza e ogni numero da 1 a 10 compare in tre di esse esattamente : indichiamo con S1,S2,…S10 le somme di ognuna di esse . Da quanto osservato si ha che S1 + S2 +… + S10 = 3 ( 1 + 2 +…+10 ) = 165 . E’ come sistemare 165 oggetti in 10 cassetti : qualche Si vale almeno 17 .

6.2.3) Su un quadrato di lato 1 metro vengono disegnati in modo casuale 51 punti . Provare che almeno 3 di questi punti giacciono su un quadrato di lato 20 centimetri . Soluzione : se dividiamo il quadrato iniziale in 25 quadrati di lato 20 centimetri , poiché 51 = 25.2 + 1 , uno di essi contiene almeno 3 punti . 6.2.4) Dati dodici numeri interi diversi , provare che almeno due di essi possono essere scelti in modo che la loro differenza sia divisibile per 11 . Soluzione : I resti della divisione per 11 sono i numeri da 0 a 10 , quindi almeno due dei dodici interi divisi per 11 hanno lo stesso resto e quindi la loro differenza è un multiplo di 11 . Problema 7 . Contare il numero dei sottoinsiemi di k elementi scelti in un insieme di n elementi . Affrontiamo come problema 7 l’argomento da cui prende il nome il calcolo combinatorio . Definizione 7.1 Sia A un insieme di ordine n . Si dice combinazione di n oggetti a k a k ( o di classe k ) ogni sottoinsieme di ordine k di A . Il numero delle combinazioni di n oggetti a k a k si indica con la notazione Cn,k . Dato un insieme di ordine n , esso possiede Cn,k sottoinsiemi con k elementi . Per dare la risposta al problema abbiamo bisogno di introdurre dei numeri particolari e particolarmente importanti : i coefficienti binomiali , e di enunciarne alcune proprietà .



Definizione 7.2 Si dice coefficiente binomiale n su k , 0 ≤ k ≤ n , il numero

kn

= )!kn(!k

!n−

Proposizione 7.1

i)

0n

=

nn

=1

ii)

kn

=

− knn

iii)

kn

=

−k

1n+

−−

1k1n

( formula di Stifel ) , 1 ≤ k ≤ n-1 .

Dimostrazione . Tutte e tre le proprietà sono di semplice verifica con il calcolo diretto, ma possono anche essere dimostrate con alcune semplici considerazioni , come faremo nel seguito. Scriviamo ora i coefficienti binomiali disponendoli in un triangolo illimitato , chiamato triangolo di Tartaglia o triangolo di Pascal :

00

01

11

02

12

22

03

13

23

33

… … … … Per il punto i) della proposizione 6.1 il primo e l’ultimo coefficiente binomiale in ogni riga del triangolo sono uguali a 1, per il punto ii) il secondo e il penultimo coefficiente binomiale in ogni riga sono uguali tra loro e per il punto iii) ogni coefficiente binomiale all’interno del triangolo è la somma dei due coefficienti binomiali alla sua destra e alla sua sinistra nella riga precedente .



24

Queste osservazioni ci permettono di riscrivere il triangolo di Tartaglia calcolando molto facilmente i numeri di ogni riga

1

1 1 1 2 1

1 3 3 1

1 4 6 4 1 … ... … … … ... . Chi già conosce il triangolo di Tartaglia sa che i numeri delle sue righe sono i coefficienti delle potenze del binomio : (a+b)0 = 1 (a+b)1 = a + b (a+b)2 = a2 +2 ab +b2 (a+b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4 ………………………………………. Si prova infatti la Proposizione 7.2 Per qualsiasi numero naturale n e per ogni a , b reali si ha

(a+b)n = ∑n

o

kn

an-kbk

(Formula del binomio di Newton ). Dimostrazione . Per induzione su n .

Per n = 1, (a+b)1 = a + b =

01

a +

11

b.

Supponiamo vera la formula per n e proviamola per n+1.

Dunque, (a+b)n = ∑n

o

kn

an-kbk =

0n

an +

1n

an-1b + … +

kn

an-kbk +…+

nn

bn e



(a+b)n+1 = (a+b)n (a+b) = [

0n

an +

1n

an-1b + … +

kn

an-kbk +…+

nn

bn ](a+b) =

=

0n

an+1 +

1n

anb +…+

kn

an-k+1bk +…+

nn

abn +

0n

anb +…+

−1kn

an-k+1bk +

…+

nn

bn+1 =

0n

an+1 + [

0n

+

1n

] anb +…+ [

−1kn

+

kn

] an-k+1bk +…+

nn

bn+1 = (a + b)n+1, poichè

1 =

0n

=

+0

1n ,

0n

+

1n

=

+1

1n,…,

−1kn

+

kn

=

+k

1n, 1 =

nn

=

=

++

1n1n

.

Il triangolo di Tartaglia è uno strumento molto utile per calcolare rapidamente i coefficienti binomiali e per visualizzarne altre proprietà , quali quelle enunciate nella proposizione seguente . Proposizione 7.3

i) +

0n

1n

+ … +

nn

= 2n

ii)

0n

-

1n

+

2n

… + (-1)n

nn

= 0

iii)

0n

+

2n

+… =

1n

+

3n

+… = 2n-1

Dimostrazione.

i) Si ottiene dalla formula del binomio di Newton , ponendo a = b = 1. ii) Si ottiene dalla formula del binomio di Newton , ponendo a = 1, b = -1 iii) Sommando membro a membro i) e ii) si ottiene

2 [ +

0n

2n

+ … ] = 2n ,

quindi la prima uguaglianza di iii). La seconda si ottiene invece sottraendo membro a



26

membro i) e ii) .

Quindi : le somme dei numeri di ogni riga del triangolo di Tartaglia sono le potenze successive di 2, le somme con segno alterno dei numeri di ogni riga sono nulle, le somme dei numeri di posto pari e di posto dispari in ogni riga sono uguali tra loro e coincidono con la somma di tutti i numeri della riga precedente . Segnaliamo un’altra delle innumerevoli proprietà del triangolo di Tartaglia : se ne diamo la seguente rappresentazione 1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

. . . . . . .

leggiamo, sommando in diagonale, i famosi numeri di Fibonacci F0 = F1 =1 , F2 = 1+1 = 2, F3 = 1+2 = 3 , F4 = 2+3 = 5 ,…, Fn = Fn-1 + Fn-2 . Si prova infatti, per induzione su n e usando sia la relazione ricorsiva che definisce i

numeri di Fibonacci sia la formula di Stifel, che Fn = ∑ ≤−=+

kh,1nkh k

h = ∑

≥

−−

0k k1kn

.

La risposta al problema 7 è data dalla proposizione che segue.

Proposizione 7.4 . Sia A un insieme di ordine n . A possiede

kn

sottoinsiemi di ordine k

Dimostrazione. Il numero Cn,k si ottiene dal numero Dn,k delle disposizioni semplici di n oggetti a k a k e dal numero Pk delle permutazioni di k elementi mediante le seguenti considerazioni : il numero delle disposizioni semplici di n oggetti a k a k ci dà il numero di tutte le k-ple (ordinate)di tali oggetti, mentre Pk ci dà il numero degli ordinamenti degli oggetti di ciascuna di esse . Un sottoinsieme di ordine k si ottiene quindi da k ! k-ple di oggetti , per cui vale la relazione :

Cn,k = k

k,n

PD

= !k)!kn(!n

− =

kn



Osservazione 6.1 Dalla definizione di combinazione e dalla proposizione 6.4 deduciamo che i coefficienti binomiali sono numeri naturali non nulli . Esempi 7.1 7.1.1) Se I è l’insieme formato da tre palline di colore verde (V), rosso (R), nero (N) le disposizioni di queste tre palline a due a due sono D3,2 = 6, e, precisamente, sono gli allineamenti

VR,RV,VN,NV,RN,NR .

Le combinazioni di queste tre palline a due a due sono tre : corrispondono ai tre sottoinsiemi seguenti ( che scriviamo senza parentesi e virgola )

VR,VN,RN ,

ottenuti ciascuno da due delle disposizioni precedenti, trascurando l’ordine degli elementi . 7.1.2) Aggiungiamo all’insieme I una pallina gialla G e scriviamo tutte le combinazioni

delle 4 palline a 2 a 2 . Otteniamo C4,2 =

24

= !2)!24(

!4−

= 1.2.3 = 6 sottoinsiemi :

VR, VN, RN, VG, NG, RG ,

i tre dell’esempio precedente più quelli ottenuti con l’aggiunta della pallina gialla . Usando la definizione di combinazione e l’uguaglianza

Cn,k =

kn

si dimostrano senza calcoli le proprietà dei coefficienti binomiali .

Così la i)

0n

=

nn

=1 della proposizione 7.1 può essere motivata osservando che ci sono

solo un sottoinsieme con 0 elementi (l’insieme vuoto ) e uno con n ( tutto l’insieme) . Per

la ii)

kn

=

− knn

basta osservare che, quando scegliamo k elementi tra n, isoliamo

automaticamente i restanti n-k . La iii)

kn

=

−k

1n+

−−

1k1n

(formula di Stifel) , 1 ≤ k ≤



28

n-1, si ottiene osservando che , fissato un elemento tra gli n , vi sono

−k

1n sottoinsiemi

di ordine k che non lo contengono e

−−

1k1n

che lo contengono ( quest’ultimo numero si

calcola escludendo l’elemento fissato e contando il numero dei sottoinsiemi di k-1 elementi che si possono formare con gli n-1 elementi rimasti ) . Anche la formula del binomio di Newton

(a+b)n = ∑n

o

kn

an-kbk

può essere dimostrata con considerazioni di tipo combinatorico . Infatti basta osservare che gli addendi an-kbk sono tanti quanti sono i modi di scegliere k volte b e n-k volte a negli n fattori a+b di (a+b)n, quindi sono tanti quanti i sottoinsiemi di k elementi scelti tra n, cioè

Cn,k =

kn

.

Osserviamo che , sempre per il significato dei coefficienti binomiali , nel triangolo di Tartaglia la somma dei numeri della riga n-sima ci dà l’ordine dell’insieme delle parti di un insieme di ordine n ( Problema 1 ) . Proviamo infine la Proposizione 7.5 Sia In = {1,2,3,…,n}⊂ N . Il numero dei sottoinsiemi di In che non contengono due suoi numeri consecutivi è dato da Fn+2 . Dimostrazione . Identifichiamo un sottoinsieme A di In con una stringa di lunghezza n formata con le due cifre 1 e 0 . La cifra 1 indica l'appartenenza di un elemento di In ad A , la cifra 0 la non appartenenza . Per esempio, per n = 4, la stringa 1010 indica il sottoinsieme {1,3} dell' insieme I4 = {1,2,3,4} . I sottoinsiemi di In che non contengono due suoi numeri consecutivi sono dati dalle stringhe che non hanno mai due cifre 1 consecutive . Consideriamo tra questi quelli di ordine k : la stringa che li rappresenta contiene k volte la cifra 1 . Per contarli tutti , partiamo da n-k cifre tutte uguali a 0

44 344 21kn

0...000−

e contiamo in quanti modi possiamo inserire k cifre 1 in modo che due di esse non siano mai adiacenti . Essendo i posti vuoti disponibili n - k + 1 , le k cifre 1 si possono inserire in

Cn-k+1,k =

+−k

1kn

modi . Quindi i sottoinsiemi cercati sono



∑≥0k

+−k

1kn .

poichè , Fn = ∑≥

−−

0k k1kn

, il numero cercato è proprio l'(n+2)-simo numero di Fibonacci.

Osservazione 7.1 Considerare un sottoinsieme di ordine k di un insieme di n elementi equivale a considerare un’estrazione di k palline da un’urna che ne contiene n , distinguibili tra loro, senza tener conto dell’ordine di estrazione e senza reimbussolare la pallina estratta e anche a disporre k oggetti in n cassetti con la condizione che in ogni cassetto non cada più di un oggetto e senza tener conto di quale oggetto si pone nel cassetto. Così, se abbiamo 4 oggetti a,b,c,d, le C4,3 sono i quattro possibili sottoinsiemi formati da 3 elementi su a o, equivalentemente le quattro possibili estrazioni di tre palline senza reimbussolamento :

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

o, ancora, indicando con x ognuno dei tre oggetti i modi per riporre tre oggetti indistinguibili nei quattro cassetti a,b,c,d con le condizioni precisate sopra :

x x x x x x x x x x x x

Esercizi 7.1 7.1.1) Quattro giocatori di tennis vogliono giocare un doppio . Quante coppie distinte si possono formare ? Soluzione . Vi sono C4,2 = 6 formazioni distinte di due giocatori ciascuna . 7.1.2) Nel gioco del Superenalotto bisogna indovinare 6 numeri scelti tra il numero 1 e il numero 90 . Quanti insiemi di sei numeri si possono formare ?

Soluzione :

6

90 = 622614630 .



30

7.1.3) Calcolare il numero di modi distinti in cui può essere servito un giocatore di scala quaranta in una singola mano . Soluzione. Supponendo di giocare con 54x2 = 108 carte e sapendo che si danno 13 carte ,

abbiamo

13

108 possibilità .

7.1.4) (a) Quanti insiemi di 5 carte si possono avere con un mazzo da poker di 52 carte ?

(b) Quanti poker di assi si possono formare ? (c) Quanti poker diversi si possono formare ?

Soluzione . (a) C52,5 = 2.598.960 (b) 48 ( tante infatti sono le scelte per la quinta carta ) (c) 13 . 48 = 624 ( ci sono infatti 13 scelte per il grado del poker e per ognuna 48 possibilità per la quinta carta ) 7.1.5) Supponiamo di avere un mazzo usuale di 40 carte da gioco. a) Se facciamo pescare a una persona tre carte dal mazzo , quante sono le terne di carte che la persona si può ritrovare in mano ?

b) se dal mazzo estraiamo 5 carte successivamente, annotando ogni carta estratta e rimettendo ogni carta nel mazzo prima di estrarre la successiva , quante sequenze distinte di 5 carte otteniamo ?

c) in quanti modi diversi possiamo formare la coppia formata da un re e da una regina ?

Soluzione : a) gli insiemi di tre carte scelte da 40 sono le combinazioni semplici di 40 elementi a tre a tre , quindi sono

C40,3 =

340

= !37!3

!40

b) sono le disposizioni con ripetizione di 40 elementi a cinque a cinque (rimettendo la carta nel mazzo ogni volta, le scelte possibili sono 40 per la prima estrazione , 40 per la seconda, 40 per la terza…, ottenendo in totale 405 ).

c) in un mazzo abbiamo 4 re e 4 regine di seme diverso . Le coppie diverse sono 4x4 = 16. 7.1.6) Una pasticceria produce 25 tipi diversi di cioccolatini.



a) La stessa pasticceria confeziona scatolette contenenti 12 cioccolatini tutti tra loro diversi. Quante sono le confezioni differenti che si possono formare ? b) Nella vetrina della pasticceria sono esposti su un ripiano, in fila, tutti i tipi di cioccolatino prodotti . In quanti modi si può esporre tutta la produzione ? Soluzione : a) Ogni scatoletta può essere vista come un sottoinsieme di ordine 12 di un insieme di ordine 25 , in totale quindi le confezioni diverse sono

C25,12 =

1225

= !13!12

!25

b) Esporre uno accanto all’altro i 25 tipi di cioccolatino significa permutarli in tutti i modi possibili , ottenendo P25 = 25 ! ripiani differenti. Problema 8 . Contare il numero delle scelte non ordinate e non distinte di k elementi scelti tra n . Sappiamo che le combinazioni semplici sono gli insiemi di k elementi distinti scelti in un insieme di ordine n . Se lasciamo cadere l’ipotesi che i k elementi siano distinti, cioè se consentiamo la ripetizione degli elementi, quante sequenze di k oggetti scelti tra n possiamo formare? Il problema proposto è equivalente al seguente : supponiamo di avere oggetti di n tipi diversi e di voler costruire un insieme I di k elementi , prendendo x1 oggetti del primo tipo, x2 del secondo tipo,…,xn dell’n-simo tipo ( qualche xi può valere zero), naturalmente con la condizione che x1+…+ xn = k. In quanti modi è possibile costruire I ? Equivalentemente : dato il numero naturale k in quanti modi esso può essere scritto come somma di n numeri naturali ( 0 compreso) ? Definizione 8.1 Dati n elementi distinti , si dice combinazione con ripetizione di classe k di questi oggetti ogni scelta non ordinata di k elementi anche non distinti scelti tra essi. Proposizione 8.1 . Se A è un insieme di ordine n , il numero delle combinazioni con

ripetizione di n elementi di classe k è Cn+k-1,n-1 = Cn+k-1,k .=

−+k

1kn

Dimostrazione. Sia A = {a1, a2,…,an }. Consideriamo n+k-1 simboli di cui k x e n-1 sbarrette . Ogni riga di questi simboli determina una combinazione . Il numero di x a sinistra della prima sbarra rappresenta la scelta di altrettante a1 , il numero di x tra la prima e la seconda sbarra la scelta di altrettante a2 e così via . Poiché vi sono Cn+k-1,n-1 modi per posizionare le n-1 sbarre , altrettante sono le selezioni con ripetizione di k elementi di A .



32

Esempio 8.1 Sia A = {a1, a2, a3 }. Le scelte con ripetizione di due suoi elementi sono C4,2 = 6 e precisamente : a1, a2 ; a1, a3 ; a2, a3 ; a1, a1 ; a2, a2 ; a3, a3 . La a1, a2 corrisponde alla sequenza di 2 x e 2 sbarre : x/x/ . Le altre sono rispettivamente le sequenze : x//x ; /x/x ; xx// ; /xx/ ; //xx . Osservazione 8.1 Elencare le combinazioni con ripetizione di n oggetti a k a k equivale a elencare le possibili estrazioni di k palline da un’urna che ne contiene n, supponendo di reimbussolare ogni pallina dopo averla estratta (ed avere contrassegnato la sua estrazione), senza tenere conto dell’ordine di estrazione o, anche, a elencare i modi in cui è possibile riporre k oggetti indistinguibili in n cassetti con la condizione che conti solo il numero di oggetti per cassetto e che qualche cassetto possa essere vuoto. Nel caso n = 4 e k = 2 abbiamo che C r

2,4 = 10 e altrettante sono le estrazioni possibili con reimbussolamento delle quattro palline a,b,c,d , precisamente

a b a c a d b c b d c d a a bb cc dd

o le configurazioni di due oggetti indistinguibili x in 4 cassetti a,b,c,d :

x x (un oggetto nel primo cassetto,uno nel secondo e gli altri vuoti) x x x x x x x x x x xx (due oggetti nel primo cassetto e gli altri vuoti) xx xx xx . Per quanto osservato in precedenza, 10 sono anche le decomposizioni diverse del numero k = 2 in n = 4 addendi :

1+1+0+0 (in analogia con la prima configurazione scelta sopra), 1+0+1+0 1+0+0+1 0+1+1+0 0+1+0+1 0+0+1+1 2+0+0+0



0+2+0+0 0+0+2+0 0+0+0+2 . Esercizi 8.1

8.1.1) Quante sono le tessere del gioco classico del domino ? Soluzione : sono tante quante le combinazioni con ripetizione di 7 elementi ( i numeri da 0 a 6)

di classe 2 , cioè

−+2

127 =

28

= !6!2

!8 = 28.

8.1.2) Data una funzione reale di 4 variabili reali x1, x2, x3, x4 , quante sono le sue derivate parziali del secondo ordine , nell’ipotesi che si possa scambiare l’ordine di derivazione , cioè sotto l’ipotesi di continuità delle funzioni derivate parziali (Teorema di Schwarz) ? Soluzione : si tratta delle combinazioni con ripetizione dei 4 oggetti x1, x2, x3, x4 di classe 2, in numero di 10, come visto negli esempi precedenti . In generale, per f(x1, x2, …, xn) reale di n variabili reali, nell’ipotesi che non conti l’ordine in cui si scelgono le variabili, le derivate parziali di ordine k sono le C r

k,n . 8.1.3) In quanti modi possiamo mettere 12 palline identiche (e quindi indistinguibili) in 6 cassetti ammettendo che qualche cassetto sia vuoto?

Soluzione : mettiamo in riga 17 oggetti , le 12 palline e le 5 sbarrette e osserviamo che ognuna di queste righe ci dà una e una sola ripartizione delle palline : le palline a sinistra della prima sbarra corrispondono a quelle del primo cassetto , quelle tra la seconda e la terza a quelle del secondo cassetto , …. Se le due sbarre sono adiacenti il cassetto è vuoto. Ogni riga è completamente determinata dalle cinque posizioni delle sbarrette , vi sono quindi

5

17possibilità .

Avevamo già osservato in osservazione 8.1 che le combinazioni con ripetizione di n oggetti di classe k possono essere pensate come la suddivisione di k oggetti (qui k = 12) in n cassetti (n = 6) con la condizione che conti solo il numero degli oggetti in ogni cassetto e non il tipo di oggetto (le palline sono indistinguibili) e supponendo cassetti vuoti ) . 8.1.4) In quanti modi possiamo scrivere il numero naturale non nullo k come somma di n numeri interi non negativi ? Si considerano diverse due rappresentazioni che differiscono per l’ordine degli addendi . La risposta è data dalle considerazioni precedenti , cioè dalle soluzioni di x1+…+xn = k ed è

−−+1n

1kn : nel caso k = 5 e n = 2 si trovano le

−−+12

125= 6 decomposizioni seguenti :



34

5+0, 4+1, 3+2, 2+3, 1+4, 0+5. ( equivalentemente, è possibile mettere 5 palline indistinguibili in 2 cassetti nei 6 modi seguenti: 5,0; 4,1; 3,2; 2,3; 1,4; 0,5 o scrivere, con ovvia analogia, le 6 combinazioni con ripetizione di n = 2 oggetti a,b di classe k = 5 seguenti :

aaaaa aaaab aaabb aabbb abbbb bbbbb )

8.1.5) In quanti modi possiamo mettere 12 palline identiche (e quindi indistinguibili) in 6 cassetti (numerati da 1 a 6) in modo tale che nessun cassetto sia vuoto?

Soluzione . Poniamo le palline in una riga : possiamo ripartire la riga in 6 parti usando 5 sbarrette per ottenere una delle configurazioni richieste . Per esempio la configurazione

OO/OOO/O/OO/OOO/O indica che vi sono due palline nel primo cassetto , tre nel secondo ,una nel terzo , due nel

quarto , tre nel quinto e una nel sesto . Ora , vi sono 11 buchi (tra le dodici palline) in cui inserire 5 pareti per ottenere sei cassetti ogni sbarretta ha 11 posizioni in cui può essere inserita e in nessun buco ve ne possono

essere due perché ciò corrisponderebbe a un cassetto vuoto , vi sono dunque

5

11possibilità

e quindi altrettante ripartizioni di palline . 8.1.6) In quanti modi possiamo scrivere il numero naturale non nullo k come somma di n numeri naturali non nulli ? Si considerano diverse due rappresentazioni che differiscono per l’ordine degli addendi. Soluzione : Pensando a k come alla somma 1+1+…+1 di k 1 , agli 1 come palline e alle n

somme come cassetti , l’esercizio 8.1.5) generalizzato ci dice che le possibilità sono

−−

1n1k

.

Se k è minore di n il problema non ha soluzione.

Per esempio , il numero 5 si può scrivere in

−−

1215

= 4 modi come somma di due naturali

non nulli : 5 = 1+ 4 = 2+3 =3+2 = 4+1. Così il numero 4 = 1+3 = 2+2 = 3+1 ha

−−

1214

= 3

decomposizioni in due addendi non nulli, invece il numero 2 non si scrive in alcun modo come somma di quattro addendi se non si ammette lo zero ( ammettendolo i modi sono i 10 elencati nell’osservazione 8.1). Con la tecnica usata nell’esercizio 8.1.6) si dimostra la



Proposizione 8.2 Se A è un insieme di ordine n , il numero delle combinazioni con ripetizione di classe k , nelle quali ogni elemento compare almeno una volta , è Ck -1, n-1 =

=

−−

1n1k

.

Problema 9 . Contare le sequenze ordinate con elementi ripetuti un numero fissato di volte . Definizione 9.1 Si dice permutazione con ripetizione di n oggetti a1,…,an di cui a1 preso r1 volte,…, an preso rn volte ogni (r1 +…+ rn ) – upla in cui a1 compare r1 volte,…, an compare rn volte . Proposizione 9.1 Il numero delle permutazioni con ripetizione di n oggetti a1,…,an di cui a1 preso r1 volte,…, an preso rn volte è dato dalla frazione

!!...

)!...(

1

1

n

n

rrrr ++

Dimostrazione Sia S una sequenza di lunghezza (r1 +…+ rn ) = m formata con r1 oggetti ripetuti di tipo 1 , r2 di tipo 2 , … , rn di tipo n. Dobbiamo dare una “posizione” a ognuno degli n elementi per ottenere una sequenza : possiamo dare posizione agli r1 elementi di tipo 1 in C m,r1 modi . Fatto questo possiamo dare posizione agli r2 elementi di tipo 2 in Cm-r1,,r2 modi , … , possiamo dare posizione agli rn elementi di tipo n in Cm-r1-…-rn modi . Otteniamo così :

C m,r1 . Cm-r1,,r2

. …

. Cm-r1-…-rn =

)!rm(!r!m

11 −.

)!rrm(!r)!rm(

212

1

−−− …

!0!r)!r...rm(

n

1n1 −−−− =

=!r!...r!r

!m

n21

c.v.d.

Osserviamo che !!...

)!...(

1

1

n

n

rrrr ++

è anche il numero delle funzioni suriettive di un insieme di

ordine r1 +…+ rn nell’insieme di ordine n di elementi a1,…,an aventi la proprietà che r1 elementi hanno immagine a1 , … , rn elementi hanno immagine an , o, equivalentemente aventi la proprietà che la controimmagine di ai consista di ri elementi per ogni i =1,…, n. Come esempio , si consideri la parola mamma , formata da due lettere distinte a1 = a e a2 = m prese r1 = 2 volte e r2 = 3 volte con r1 + r2 = 5 Gli anagrammi di mamma sono le permutazioni



36

con ripetizione di 2 oggetti presi 2 e 3 volte e in totale sono !3!2

!5 = 10 . Ad ognuno di essi si fa

corrispondere una funzione suriettiva di I 5 = }{ 5,4,3,2,1 in { }m,a nel modo seguente : sia per esempio ammma l’anagramma in questione . La corrispondente funzione suriettiva sarà la funzione f di dominio I 5 = }{ 5,4,3,2,1 e codominio { }m,a tale che f(1) = a = f(5) e f(2) = f(3) = f(4) = m . Quindi vi sono 10 funzioni suriettive di I 5 = }{ 5,4,3,2,1 in { }m,a che mandano due elementi in a e tre in m. Ad ognuna di esse corrisponde una partizione di I5 = }{ 5,4,3,2,1 in due blocchi di 2 e 3 elementi ciascuno : ad ammma corrisponde la partizione di I5 in f –1(a) = }{ 5,1 e f –1(m) = }{ 4,3,2 . Esercizio 9.1 In quanti modi possiamo distribuire 5 libri ai due studenti Alice e Matteo in modo che Alice ne abbia due e Matteo tre ? Ordiniamo i libri e consideriamo le sequenze di lunghezza 5 contenenti due a e tre m : per esempio la sequenza ammma determina la distribuzione seguente : Alice ha il primo e l’ultimo libro , Matteo gli altri tre . E’ evidente che la risposta al quesito è il numero degli anagrammi della parola mamma , cioè 10 . Il numero totale delle funzioni suriettive da un insieme con 5 elementi in un insieme con 2 elementi sarà dato dalla seguente somma di ovvio significato

!3!2!5 +

!2!3!5 +

!4!1!5 +

!1!4!5 = 10+10+5+5 = 30

( !4!1

!5 è il numero delle funzioni suriettive che mandano un elemento in a e 4 in m e anche

quello delle partizioni di I 5 = }{ 5,4,3,2,1 in due blocchi , uno unitario e uno di ordine 4 ). Come vedremo nel problema 11, il numero totale delle funzioni suriettive da un insieme con n elementi in un insieme con m elementi è legato ai numeri di Stirling di seconda specie, indicati con la notazione S(n,m) e definiti come il numero delle partizioni di In in m parti: nel nostro esempio S(5,2) è il numero delle partizioni di I 5 = }{ 5,4,3,2,1 in due parti . Si avrà che S(5,2) = 15 , in base a quanto osservato in precedenza (le lettere a ed m sono intercambiabili e quindi ad una stessa partizione in due blocchi corrispondono due suriezioni diverse, per esempio le sequenze ammma e maaam danno due suriezione diverse ma la stessa parizione di I5 nei due blocchi { },5,1 e { }4,3,2 ) . Quindi, sempre nel caso particolare , l’ordine dell’insieme J delle suriezioni da un insieme con 5 elementi in un insieme con 2 elementi è legato a S(5,2) dalla relazione :

=)2,5(J 2 S(5,2) = 2! S(5,2) .



Si prova che , in generale ,

=)m,n(J m! S(n,m) , dove l’ordine di J(n,m) è il numero totale delle funzioni suriettive da un insieme con n elementi in un insieme con m elementi , n≥ m (vedi problemi 10 e 11).

Il numero !!...

)!...(

1

1

n

n

rrrr ++

viene anche indicato così :

++

n1

n1

r...r

r...r

e viene detto coefficiente multinomiale . Si osservi che , per n = 2 , si ritrovano i soliti coefficienti binomiali:

=

+

21

21

rr

rr=

+

1

21

r

rr

+

2

21

r

rr

Analogamente ai coefficienti binomiali, di cui sono una generalizzazione, i coefficienti multinomiali hanno numerose proprietà e compaiono nello sviluppo della potenza n-sima di una somma . Si prova infatti che vale la formula seguente :

( ) k1

k1

rk

r1

nr...r k1

k1nk1 x...x

r...rr...r

x...x ∑=++

++=++ ,

che generalizza la formula del binomio di Newton. A tale scopo si osservi che il coefficiente multinomiale

++

k1

k1

r...r

r...r

è il numero delle stringhe di lunghezza n = k1 r...r ++ delle lettere x1,…, xk , in cui x1 è ripetuta r1 volte, x2 è ripetuta r2 volte,…, xk è ripetuta rk volte quindi, poiché le xi commutano, è il coefficiente di k1 r

kr1 x...x nello sviluppo del polinomio ( )n

k1 x...x ++ . Esercizi 9.2 9.1.1) In quanti modi possiamo distribuire 8 videocassette diverse a tre amici, Silvio, Daniele



38

ed Elisa , dandone quattro a Silvio e due a ciascuno degli altri ?

Soluzione . Basta calcolare il numero multinomiale

224

8. Si ottiene 420 .

9.1.2) Trovare il coefficiente di x4y2z2 nello sviluppo di (x+y+z)8.

Soluzione . E’ il coefficiente multinomiale

224

8 = 420 .

9.1.3) Quanti sono gli anagrammi della parola miosotis? Soluzione . Abbiamo una parola di lunghezza 8 in cui m e t compaiono una volta, i,o,s due volte, quindi il numero dei possibili anagrammi è il valore del multinomiale

222

8 =

!2!2!2!8 = 5040

Problema 10 . Contare il numero delle funzioni suriettive tra due insiemi finiti. Proposizione 10.1 Sia J(n,m) l’insieme delle funzioni suriettive da un insieme A di cardinalità n a un insieme B di cardinalità m, m < n. Si ha:

=)m,n(J ∑−

=

−1

0

)1(m

i

i n)im(im

−

Dimostrazione : Siano 1b , …, mb gli elementi di B . Per ogni i = 1, …, m, sia iX l’insieme delle funzioni da A in B che non contengono ib nell’ immagine:

iX = { /BA:f → ib }fIm∉ .

Una funzione appartenente ad uno di questi m insiemi non potrà essere suriettiva: per trovare il numero di quelle suriettive dovremo sottrarre al numero totale delle funzioni da A in B, che vale mn (Problema 4) il numero di quelle che appartengono alla unione degli iX , cioè l’ordine di m1 X...X ∪∪ . Per il Principio di inclusione-esclusione ( Problema 2) si ha

m1 X...X ∪∪ . = ∑m

1iX - ∑

<

∩ji

ji XX + …-(-1)m-1X1∩ … ∩X 1−m ,

dobbiamo quindi contare le funzioni negli insiemi iX e nelle loro intersezioni.



Si ha che le funzioni negli insiemi iX sono tutte le funzioni da A in B - }{ ib ,cioè (m-1)n, le funzioni negli insiemi iX jX∩ sono tutte le funzioni da A in B - }{ ji b,b ,cioè (m-2)n e così via. Otteniamo dunque

=)m,n(J mn - ∑ −m

1

n)1m( + ∑<

−ji

n)2m( -…+(-1)m-11n

e, osservando che ∑<

−ji

n)2m( =

2m

(m-2)n (le coppie (i,j) , con 1≤ i<j m≤ sono

2m

), si

ha:

=)m,n(J mn -

1m

(m-1)n +

2m

(m-2)n -…+ (-1)m-1n1

mm

,

cioè la tesi. Osservazione 8.1 Se n = m , =)n,n(J n! , e la formula ci dà l’identità non banale seguente :

n! = ∑−

=

−1n

0i

i)1( n)in(in

−

Esempio 10. Se ricontiamo le funzioni suriettive da un insieme con 5 elementi in un insieme di ordine 2 ( vedi problema 9), troviamo

=)2,5(J 25 – 2 + 1 – 1 = 30 Problema 11 . Contare il numero delle partizioni di un insieme A di cardinalità n in m parti . Nel problema 9 abbiamo introdotto i numeri di Stirling di seconda specie, indicati con la notazione S(n,m) e definiti come il numero delle partizioni di In in m parti. Proviamo ora la Proposizione 11.1 Il numero delle partizioni di un insieme A di cardinalità n in m parti è dato da :

S(n,m) = ∑−

=

−1

0

)1(m

i

i

!m)im(

im n−

=

!m)m,n(J

Dimostrazione. Sia f una funzione suriettiva da In = {1,2, …,n} in Im. Essa induce una



40

partizione dell’insieme A formata dagli insiemi Ai = {a∈A | f(a) = i }, i =1, 2, …, m. Inoltre, data una partizione di A in m parti, vi sono m! funzioni suriettive da In = {1,2, …,n} in Im che la inducono nel modo descritto (tante quante sono le permutazioni di 1, 2, …, m). Si ha

dunque che S(n,m) = !m

)m,n(J .

Esempio 11.1 Le funzioni suriettive da un insieme con 5 elementi in un insieme di ordine 2

sono =)2,5(J 30. Le partizioni di un insieme di 5 elementi in due parti sono 15 = !2

30 ( le

funzioni suriettive f e g tali che f(1) = f(2) = f(3) = f(4) = 1 , f(5) = 2 e g(1) = g(2) = g(3) = g(4) = 2 , g(5) = 1 sono diverse , ma inducono la stessa partizione ). Proposizione 11.2 Il numero delle partizioni di un insieme A di cardinalità n è dato da

B(n) = ∑=

n

1i)i,n(S

Dimostrazione. Il numero totale delle partizioni di un insieme di n elementi è la somma dei numeri delle partizioni in i parti, per ogni i = 1, 2, …, n. I numeri S(n,m) e i numeri B(n) sono detti rispettivamente numeri di Stirling di seconda specie e numeri di Bell . Dalle proposizioni che seguono ricaviamo la relazione ricorsiva tra i numeri di Stirling e quelli di Bell. Proposizione 11.3 Sia )m,n(S il numero di partizioni di un insieme I di n elementi in m parti, con 1≤ m ≤ n . Allora: 1)1,n(S =

1)n,n(S = )m,1n(mS)1m,1n(S)m,n(S −+−−= 2 ≤m≤ 1n − .

Dimostrazione. Proviamo banalmente le prime due asserzioni osservando che c’è un’unica partizione dell’insieme con una parte, l’insieme stesso, ed un’unica partizione dell’insieme in n parti, quella formata dai sottoinsiemi unitari . Detto z un elemento di I, sia { }zII \'= . Allora una partizione di I in m parti si ottiene in uno, e uno soltanto dei seguenti modi: - aggiungendo la parte formata dall’insieme unitario z ad una partizione in m – 1 blocchi di I’ - aggiungendo l’elemento z ad una delle m parti della partizione di I’e questo si può fare in m modi diversi.

Come conseguenza di questa Proposizione si rappresentano i numeri di Stirling mediante una tabella infinita detta triangolo di Stirling, avente come riga n -esima:



)n,n(S)1n,n(S),...,2,n(S),1,n(S − .

Indichiamo le prime sette righe del triangolo di Stirling:

Si osserva subito che, poiché ∑=

=n

1k)k,n(S)n(B , l’n-esimo numero di Bell è la somma degli

elementi dell’n- esima riga del triangolo di Stirling. Per calcolare i primi sette numeri di Bell è sufficiente allora sommare i numeri delle sette righe del triangolo riportato in precedenza, ottenendo:ù

1)1( =B , 2)2( =B , 5)3( =B , 15)4( =B , 52)5( =B , 203)6( =B , 877)7( =B . Con la figura che segue diamo una rappresentazione dei modi in cui è possibile raggruppare 4 oggetti in insiemi di ordine 1, 2 3, 4.



42

La figura conferma i risultati ottenuti per entrambi i tipi di numeri :

1)1,4( =S 7)2,4( =S 6)3,4( =S 1)4,4( =S 15)4( =B . Anche i numeri di Bell sono legati da una relazione ricorsiva: Proposizione 11.4 Dato un insieme I di ordine n ≥ 1, siano )in(B − e )n(B l’ )in( − -esimo e l’n - esimo numero di Bell. Si ha:

.

)in(B1i1n

)n(Bn

1−

−−

= ∑ ( formula di Aitken )

Dimostrazione . Sia P una partizione dell’insieme I. L’elemento a di I appartiene ad uno e uno solo dei sottoinsiemi A di P ; ciò significa che ogni partizione di I è determinata univocamente dal sottoinsieme A che contiene a e da una partizione di I− A . L’ordine i dell’insieme A è compreso tra 1 ed n (i≠ 0 perché A ≠ ∅).

A può essere scelto in

−−1i1n

modi, poiché tanti sono i sottoinsiemi di I che contengono a; le

partizioni di I− A , che è un insieme di ordine n - i, risultano invece essere )in(B − . Dunque, per ogni i, con 1≤ i≤n, vi sono esattamente (per il principio delle scelte)

−−1i1n

)in(B − partizioni di I nelle quali a appartiene ad un elemento A di ordine i .



Ne segue che le partizioni distinte di I sono )in(B1i1n

)n(Bn

1−

−−

= ∑ .

Problema 12. Contare le relazioni in un insieme di ordine n . Ricordiamo che una relazione in un insieme è definita come un sottoinsieme (detto grafo o grafico) del prodotto cartesiano IxI = I2, quindi, se I ha ordine n, le relazioni definibili su di esso sono tante quanti gli elementi di P(IxI) , cioè 2

2n . Una relazione su un insieme finito può essere rappresentata in forma matriciale, costruendo una matrice quadrata nxn di 0 e di 1 che all’incrocio tra la riga che contiene l’elemento a e la colonna che contiene b ha il coefficiente 0 oppure 1 a seconda che la coppia (a,b) non appartenga alla relazione oppure vi appartenga. Per altra via si ritrova che le relazioni sono 2

2n : infatti tante sono le matrice quadrate di ordine n formate da due soli simboli. Esempio 12.1 La matrice 3x3 seguente

100110111

rappresenta la relazione σ in I = }{ c,b,a :

=σ }{ )c,c(),c,b(),b,b(),c,a(),b,a(),a,a( .

Sappiamo che ogni relazione di equivalenza in I ne determina una partizione nelle sue classi e, viceversa, che ogni partizione di I determina una relazione di equivalenza in I , avente come classi i sottoinsiemi della partizione, quindi il numero delle relazioni di equivalenza in I di ordine n è dato dall’n-simo numero di Bell, B(n) (vedi problema 11). Ci chiediamo ora quante siano le relazioni riflessive e quante le simmetriche in un insieme I di ordine n. Da queste risposte, per differenza o usando il principio di inclusione-esclusione sapremo calcolare il numero delle non riflessive, delle non simmetriche , di quelle con almeno una o con entrambe le proprietà. Nel caso delle relazioni transitive il problema è più complicato . Diamo il numero delle relazioni riflessive identificando una relazione con la matrice nxn a lei associata : per avere la proprietà riflessiva si devono avere tutti 1 sulla diagonale principale, quindi per definire una tale relazione dobbiamo scegliere quale tra i due simboli mettere in n2- n posti . Esistono quindi 2

2n n− relazioni riflessive su I. Per ottenere una relazione simmetrica, dobbiamo verificare che, se il grafo contiene la coppia (a,b), contenga anche la coppia (b,a). In termini di matrice, questo si riduce a richiedere che essa sia simmetrica rispetto alla diagonale principale:



44

?????????

?????

?

Abbiamo 2 scelte possibili nella prima riga, 22 nella seconda,…, 2n nell’ultima. In totale, per il

principio di moltiplicazione delle scelte e la formula di Gauss, abbiamo 2.22 . …. 2n = 2 2)1n(n +

matrici della forma voluta. Per differenza con 2

2n abbiamo le relazioni non riflessive e non simmetriche, per ottenere quelle con entrambe le proprietà dobbiamo fissare il simbolo 1 negli n posti della diagonale , ottenendo

in totale 2 2)1n(n −

matrici. Per le relazioni riflessive o simmetriche, il principio di inclusione-esclusione ci dà il numero:

22n n− + 2 2

)1n(n +

- 2 2)1n(n −

.

Esercizio 12.1 Calcolare il numero delle relazioni simmetriche o riflessive definibili su I5. Soluzione. Le relazioni riflessive sono 220 = 1.048.576. Le relazioni simmetriche sono 215 = 32.768 Le relazioni riflessive e simmetriche sono 210 = 1024, da cui il numero cercato 1.080.320 = 220 + 215 – 210 .

Bibliografia [1] N.L.Biggs , Discrete mathematics , Clarendon presse – Oxford 1985 [2] Cerasoli - Eugeni - Protasi , Elementi di matematica discreta, Zanichelli, Bologna 1988 [3] J.H.Conway-R.K.Guy , The book of numbers , Copernicus - Springer - Verlag 1955 [4] Fomin D.- Genkin S.- Itenberg I., Mathematical circles (Russian experience) 1996 Mathematical world.Vol.7 American Mathematical Society

[5] Graham-Knuth-Patashnik , Matematica discreta , Hoepli 1992 [6] E.Lucas ,Theorie des nombres ,Librairie scientifique et technique Albert Blanchard 1961 [7] G. M. Piacentini Cattaneo , Algebra . Un approccio algoritmico , Decibel Zanichelli 1996

. [8] D.Romagnoli, Elementi di matematica discreta, Quaderno didattico n.23. Dipartimento di Matematica di Torino 2004.

esercizi di combinatoria

Documents

Transcript of esercizi di combinatoria