=t$%R$r s I$ qB$tB

+=V*eiWy *y*Vqqy]y
Ij

*$}s$8tB I$ s8s${s

-! iC9stCj'

VjAs Ij {sj{BjB {B8A$tsB$B NsABsB$B 7y7 ss 1(((\1((d

+ZsItB ' 1 T s$B 1((d

! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !

PREFAZIONE

In questo quaderno didattico contenuta la traccia delle lezioni da me tenute nel laboratorio didattico svolto presso la SIS di Torino nellanno accademico 2000-2001 . Le lezioni hanno lo scopo di richiamare i prerequisiti necessari al docente per una presentazione elementare, ma rigorosa , di alcune tematiche del calcolo combinatorio . Scopo del laboratorio quello di rendere il materiale presentato nelle lezioni comprensibile e fruibile da parte dei ragazzi della scuola superiore , sviluppando in essi la capacit di utilizzare metodi, strumenti e modelli matematici in situazioni diverse e lattitudine a riesaminare criticamente ed a sistemare logicamente conoscenze a livelli pi elevati di astrazione e di formalizzazione . Per una pi vasta trattazione dei temi presentati si rimanda alla bibliografia , che riporta i testi da me consigliati e usati dai frequentanti il laboratorio per la stesura di tesine didattiche attinenti gli argomenti trattati .

INDICE
Capitolo 1 Capitolo 2 Capitolo 3
I NUMERI NATURALI E IL PRINCIPIO DI INDUZIONE MATEMATICA .

p.1 5

TEORIA DEGLI INSIEMI : ALCUNI PROBLEMI COMBINATORICI . . CORRISPONDENZE TRA INSIEMI .

3.1 Corrispondenze tra insiemi . .. 9 3.2 Corrispondenze tra insiemi finiti . . 11 Capitolo 4
PERMUTAZIONI E DISPOSIZIONI .

4.1 Le permutazioni di n elementi ...14 4.2 Le disposizioni di n elementi di classe k ... 18 Capitolo 5
COMBINAZIONI

5.1 I coefficienti binomiali e il triangolo di Tartaglia . 20 5.2 Le combinazioni di n elementi di classe k . 23 .

D.Romagnoli Algebra del calcolo combinatorio

CAPITOLO 1
I numeri naturali e il principio di induzione matematica .

Il calcolo combinatorio una tecnica per contare il numero degli elementi (che si dice ordine o cardinalit) di particolari insiemi finiti . Alla base del contare vi sono linsieme N dei numeri naturali, a tutti ben noto fin dalle scuole elementari , e le sue propriet . Linsieme 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 numero naturale, unico, 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) 0A b) per tutti gli n N , nA il successore di n A deve essere linsieme N

Lassioma v) viene detto principio di induzione matematica . Invece di nA si pu dire n ha la propriet P . Con questa terminologia il principio di induzione matematica diventa lassioma 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 laritmetica ; il primo passo consiste nello introdurre loperazione 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 , e loperazione 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 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 .

Quaderni Didattici del Dipartimento di Matematica

Capitolo 1 I numeri naturali e il principio di induzione matematica

Diciamo allora che la relazione data un buon ordinamento e che linsieme 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

3ULQFLSLR GL LQGX]LRQH PDWHPDWLFD  D IRUPD  

Sia ( P(n) ) una successione di proposizioni tali che i) ii) P(0) (P(n0 )) vera ( base dellinduzione ) La verit di P(k) implica la verit di P(k + 1 ) , k 0 (n0) ( ipotesi induttiva )

Allora P(n) vera , n 0 ( n0 ) . Dimostrazione . Sia S = {x > 0 (n0) | P(x) falsa }. Supponiamo , per assurdo , che S non sia vuoto. Per lassioma del buon ordinamento di N , S ha un primo elemento , che indichiamo con m Consideriamo ora la proposizione P(m) : poich mS , 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

3ULQFLSLR GL LQGX]LRQH PDWHPDWLFD  D IRUPD  

Sia ( P(n) ) una successione di proposizioni tali che i) ii) P(0) (P(n0 )) vera ( base dellinduzione ) La verit di P(k), 0 (n0) k < m , implica la verit di P(m) ( ipotesi induttiva )

Allora P(n) vera , n 0 ( n0 ) . Il principio di induzione matematica si rivela molto utile per dimostrare proposizioni il cui enunciato dipenda da n N . Vediamone negli esempi luso corretto .

(VHPSL 
1) Si provi la validit della formula di Gauss : 1 + 2 + + n =

n (n + 1) 2

Soluzione : in questo caso P(n) laffermazione : la somma dei primi n naturali Base dellinduzione : 1 = 1 .2 / 2 , quindi P(1) vera Ipotesi induttiva : P(k) vera , cio 1 + 2 ++ k =

n (n + 1) 2

k (k + 1) 2

Universit di Torino

D.Romagnoli Algebra del calcolo combinatorio

Proviamo la verit di P(k + 1) : 1 + 2 ++ k + (k + 1) =

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

Il principio di induzione matematica (1 forma) ci permette di concludere che P(n) vera ,n1. Dalla formula di Gauss segue subito la formula che ci d la somma dei primi n termini di una progressione aritmetica di termine iniziale a e di ragione d a + (a + d) + (a + 2d) + + (a + (n-1)d) =

n (2a + (n 1)d ) , 2

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 progressione geometrica di termine iniziale a e ragione q 1 : a + aq + aq2 + + aqn-1 = (a aqn) / (1 q)

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 dellinduzione . 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 lipotesi induttiva m1 e m2 fattorizzano in numeri primi e cos avviene quindi per m .

Un altro classico esempio di utilizzo della 2a forma del principio di induzione matematica la dimostrazione dellalgoritmo di divisione in N : m , n N , m>0,n0 , q,rN (0 r <m) n = qm + r Dimostrazione : Per induzione sul numero n . Se n = 0 ( base dellinduzione ) , 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=qm + r da cui n = (q+1)m + r .

Quaderni Didattici del Dipartimento di Matematica

Capitolo 1 I numeri naturali e il principio di induzione matematica

3) Chiamiamo n- stringa binaria una sequenza di n cifre scelte tra 0 e 1 . Proviamo , per induzione su n , che il loro numero 2n Base dellinduzione : 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 . 4) Linduzione permette di risolvere semplici problemi combinatorici quali , per esempio : 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 : laffermazione 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 ).

Universit di Torino

D. Romagnoli Algebra del calcolo combinatorio

CAPITOLO 2
Teoria degli insiemi : alcuni problemi combinatorici .
In questo capitolo prenderemo in considerazione degli insiemi finiti particolari . 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 ( per questo tipo di considerazioni si veda anche il capitolo sulle corrispondenze tra insiemi ) . Ricordiamo che , dato un insieme I , finito o infinito , si dice suo insieme delle parti , o insieme potenza linsieme 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

3URSRVL]LRQH  Sia I un insieme finito di ordine n . Allora P(I) ha 2n elementi .

Dimostrazione . Per induzione su n = I. Base dellinduzione : 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 . 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 lipotesi induttiva . I sottoinsiemi di I che lo contengono sono del tipo A{an}, dove A un sottoinsieme di I - {an}, quindi anchessi sono 2n-1 . In totale dunque i sottoinsiemi di I sono 2n-1 + 2n-1 = 2 . 2n-1 = 2n .

Vedremo altre dimostrazioni di questa proposizione ( con il metodo delle scelte e con le funzioni tra insiemi finiti) .

(VHUFL]LR  Costruire linsieme delle parti di I3 = {1,2,3} , osservando che gli 8 elementi che lo
formano si costruiscono in modo induttivo ( o ricorsivo ) . Dalla definizione di unione e di intersezione di insiemi , segue subito la

3URSRVL]LRQH  Siano A e B due insiemi finiti disgiunti di ordine n ed m rispettivamente.

Allora

Quaderni Didattici del Dipartimento di Matematica

Capitolo 2 Teoria degli insiemi : alcuni problemi combinatorici

AB= A + B = n + m e da questa la

3URSRVL]LRQH  Siano A e B due insiemi finiti di ordine n ed m rispettivamente e sia k lordine di
AB . Allora AB+ A B= A + B, cio AB = n + m k

Dimostrazione. AB+ AB = A ( B A )+ AB = A+ B - A+ AB , poich A e B A sono disgiunti . Anche B A e AB sono disgiunti , quindi B - A+ AB = (B A) (AB ) = B, da cui la tesi . Queste due evidenti proposizioni risultano utili per risolvere semplici problemi combinatorici La proposizione 2.1 si estende facilmente,per induzione su n,al caso di n insiemi disgiunti: precisamente si prova che , detti Ai (i = 1,,n) gli insiemi disgiunti ,

Ai= Ai, (i = 1,,n) .

Come conseguenza otteniamo lordine del prodotto cartesiano di due insiemi finiti .

&RUROODULR  Siano A e B due insiemi finiti di ordine n e m rispettivamente .Allora

A x B = A.B= nm Dimostrazione . Siano A = {a1,,an } e B = { b1, . . costruito come lunione degli n insiemi disgiunti Ai = { (ai ,b1), . . aventi ognuno ordine m , da cui la tesi . bm } . Il loro prodotto cartesiano pu essere

. ,

. , (ai ,bm )}

, i = 1, ,n

2VVHUYD]LRQH  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 . Il corollario 2.4 motiva il metodo delle scelte , di cui si fa un grande uso in combinatorica e in molte applicazioni della vita pratica :

Universit di Torino

D. Romagnoli Algebra del calcolo combinatorio

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 . Il corollario 2.4 dice che la coppia (a,b) pu essere costruita in nm modi . Tale metodo , da noi giustificato sopra , 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 .

(VHPSLR  Usiamo il metodo delle scelte per dimostrare la proposizione 2.1 . Sia I = {a1,,an } . Vogliamo contare i modi per costruire un sottoinsieme A di I . Ogni elemento di A 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 . In altre parole , potremmo pensare di indicare con 1 lappartenenza di un elemento di I al sottoinsieme A e con 0 la non appartenenza : in questo modo ogni sottoinsieme di I una stringa di lunghezza n di due cifre ( per esempio , per n = 4 , la stringa 1010 indica il sottoinsieme {a1,a3} di {a1,a2 ,a3, a4} ) e tali stringhe sono in totale 2n ( vedi lesempio 3) di esempi 1.1, p.4 ) . (VHUFL]L 
1) Quanti oggetti possiamo differenziare con delle targhe di due simboli di cui il primo una lettera dellalfabeto latino e il secondo una cifra da 0 a 9 ? Le lettere possono essere scelte in 26 modi , le cifre in 10 modi : possiamo costruire 260 targhe diverse .

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) Quanti numeri di sei cifre hanno almeno una cifra pari ? 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

Quaderni Didattici del Dipartimento di Matematica

Capitolo 2 Teoria degli insiemi : alcuni problemi combinatorici

devo escludere lo 0 e quindi ho 9 scelte anzich 10 ) e 56 = 15625 numeri con sei cifre tutte dispari I numeri di sei cifre aventi almeno una cifra pari sono quindi 900000 15625 = 884375 .

4) 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 larrivo 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 .

5) Quante diagonali ha un poligono convesso di n lati ? Osserviamo che ognuno degli n 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 n 3 scelte per il secondo punto di ogni diagonale ed n scelte per il primo . Il prodotto delle scelte deve per essere diviso per due , per le stesse argomentazioni di 4) . Dunque le diagonali di un n-gono sono

n (n 3) . 2

Universit di Torino

D.Romagnoli Algebra del calcolo combinatorio

CAPITOLO 3
Corrispondenze tra insiemi .
3.1 Corrispondenze tra insiemi. 3.2 Corrispondenze tra insiemi finiti.  &RUULVSRQGHQ]H WUD LQVLHPL  'HILQL]LRQH  Si definisce corrispondenza dellinsieme I nellinsieme I un sottoinsieme F del
prodotto cartesiano I x I.

F esprime un legame tra gli elementi di I e gli elementi di I : precisamente dice che lelemento x di I legato allelemento x di I se e solo se la coppia ordinata (x,x) appartiene a F. Diciamo allora che x una immagine di x nella corrispondenza F e che x una controimmagine di xnella corrispondenza F . I detto dominio della corrispondenza. I detto codominio della corrispondenza.

(VHPSLR  Dati I ={a,b,c } e I = {1,2,3 } una corrispondenza di I in IlinsiemeF={(a,2),(c,3),

(c,2)}. Visualizzarla mediante un diagramma di Eulero Venn .

'HILQL]LRQH  Una corrispondenza detta :

IXQ]LRQDOH se ogni x di I ha al pi una immagine RYXQTXH GHILQLWD se ogni x di I ha almeno una immagine LQLHWWLYD se ogni elemento di I ha al pi una controimmagine ( o equivalentemente se elementi distinti hanno immagini distinte ) VXULHWWLYD se ogni elemento di I ha almeno una controimmagine La corrispondenza dellesempio 3.1.1 non ha nessuna di queste propriet . Le corrispondenze pi importanti sono quelle ovunque definite e funzionali : esse sono dette funzioni e sono i sottoinsiemi F di I x I in cui ogni elemento x di I primo elemento di una e una sola coppia . Il concetto di funzione basilare in matematica ; ne diamo unaltra definizione equivalente a quanto detto finora .

'HILQL]LRQH  Dato un insieme I (detto dominio) e un insieme I (detto codominio ) ,

una funzione f di I in I una legge che associa ad ogni elemento di I uno ed un solo elemento di I . Scriveremo f : I I e per indicare che x viene mandato in xscriveremo x x oppure

Quaderni Didattici del Dipartimento di Matematica

10

Capitolo 3 Corrispondenze tra insiemi

f(x) = x. x detto l immagine di x ; x detta una controimmagine di x . La legge f sopra definita come sottoinsieme di I x I linsieme F = {(x,x) x = f(x) }. F viene in tal caso detto grafo (o grafico) di f . Nel caso di funzioni reali di variabile reale linsieme F linsieme dei punti appartenenti al grafico della funzione nel piano cartesiano . 2VVHUYD]LRQH  In qualche caso una funzione pu essere identificata con la sequenza delle immagini degli elementi del dominio : il caso , per esempio, delle successioni ( o progressioni ) . Si dice successione a valori in un insieme C ( codominio , negli esempi pi noti R ) una funzione a avente come dominio linsieme N . Si scrive : a(0),a(1),,a(n), o, come pi abituale, a0 ,a1,,an, Cos la successione 1,2,22,23,,2n, il modo usuale per rappresentare la funzione f : N R , f(n) = 2n . f iniettiva e non suriettiva . Sono particolarmente importanti, nel calcolo combinatorio , le funzioni tra insiemi finiti iniettive , suriettive e quelle aventi entrambe le propriet : le biiezioni o corrispondenze biunivoche , su cui torneremo nel seguito . Richiamiamo ancora la composizione di funzioni :

'HILQL]LRQH  Date due funzioni f : I I e g : I I si dice funzione composizione (o

funzione composta) di f e di g la funzione g f di I in I cos definita : (g f )(x) = g(f(x)) . In termini di grafo , indicati con F e G i grafi di f e g rispettivamente e con H il grafo della loro composizione , abbiamo H = { ( x,x) I x I x I , (x,x) F e (x,x)G } . E immediato verificare che la composizione di due funzioni una operazione associativa e che la composizione di due funzioni iniettive iniettiva , di due suriettive suriettiva . Da ci segue che la composizione di due biiezioni ancora una biiezione . Data una biiezione f , la sua funzione inversa secondo la

'HILQL]LRQH  Se f : I I una biiezione , si definisce inversa di f la funzione f

associa ad ogni x di I lunico x tale che f(x) = x ancora una biiezione . Sono esempi di biiezioni le permutazioni di n oggetti che tratteremo in seguito .

-1

: I I che

Universit di Torino

D.Romagnoli Algebra del calcolo combinatorio

11

 &RUULVSRQGHQ]H WUD LQVLHPL ILQLWL 

Ogni insieme finito con n elementi A = {a1, ,an } in corrispondenza biunivoca con linsieme In = { 1 ,2 , , n }( suo insieme di indici ) , quindi sufficiente ragionare con tali insiemi . Enunciamo alcune propriet di tipo combinatorico .

3URSRVL]LRQH  Le corrispondenze tra In e Im sono 2nm .

Dimostrazione . Le corrispondenze sono tante quante i sottoinsiemi del prodotto In x Im ,che sono 2nm .

3URSRVL]LRQH  Le funzioni di In in Im sono mn .

Dimostrazione . Con linduzione su n . Se n=1, si hanno m = m1 funzioni di I1 in Im , poich una singola funzione assegnata dando limmagine di 1 . Supponiamo vera la propriet per n e proviamola per n + 1 . Una funzione f di In+1 in Im si ottiene dando una funzione g di In in Im ed una immagine ad n + 1 . Poich le g ,per lipotesi induttiva, sono mn ne segue che vi sono mn funzioni che mandano n + 1 in 1 , mn funzioni che mandano n + 1 in 2 , , mn funzioni che mandano n + 1 in m cio m . mn = mn+1 funzioni di In+1 in Im c.v.d. Dimostrazione . Con il metodo delle scelte . Dare una funzione di In in Im significa dare f(1) ,f(2),,f(n) . Per f(1) ho m scelte , tante quanti sono gli elementi del codominio , per f(2) ho ancora m scelte ,, cos per f(n) . In totale avr m m ...m = mn scelte .

2VVHUYD]LRQH  Diamo la traccia di una dimostrazione della proposizione 2.1 :

I= n P(I)=2n che usa quanto sopra dimostrato . Per ogni sottoinsieme A di I , sia A : I{0,1} la funzione cos definita : A(x) = 0 , se xA A(x) = 1 , se xA A detta la funzione caratteristica di A . Sia f : P(I) { funzioni di I in {0,1}} la funzione cos definita : f(A) = A . Si prova che f una biiezione e da questo segue che lordine di P(I) pari allordine dellinsieme delle funzioni di un insieme con n elementi in un insieme con 2 elementi , che abbiamo provato essere 2n .

2VVHUYD]LRQH  Una funzione di un insieme con n elementi in un insieme di m elementi pu essere vista come una n-pla ordinata di elementi 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 .

Quaderni Didattici del Dipartimento di Matematica

12

Capitolo 3 Corrispondenze tra insiemi

(VHPSLR  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 , , lultima la funzione costante di valore 2 . (VHPSLR  Vogliamo calcolare il numero delle colonne tra loro diverse che si possono giocare al
totocalcio . Come noto , il gioco consiste nellassegnare 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 !!) .

3URSRVL]LRQH  Sia f una funzione di In in Im .

i) ii) iii) Se f iniettiva , n m Se f suriettiva , n m Se n = m , f biiettiva se e soltanto se f iniettiva o suriettiva .

Tralasciamo la dimostrazione della propriet 3.2.3 , intuitiva ma non banale . Osserviamo che la proposizione contrapposta di i) (ad essa logicamente equivalente) : se n > m ,allora f non iniettiva detta principio dei cassetti ( o principio delle gabbie dei piccioni ) e pu venire cos riformulata (chiamando oggetti gli elementi di In e cassetti le loro immagini ) : se in m cassetti (gabbie ) ho n > m oggetti (piccioni) , qualche cassetto (gabbia) contiene almeno 2 oggetti(piccioni). La propriet 3 ci dice anche che non possono esistere biiezioni tra insiemi finiti di ordini diversi , quindi , in particolare, tra un insieme finito e un suo sottoinsieme proprio . Al contrario , un insieme infinito pu essere messo in corrispondenza biunivoca con un suo sottoinsieme proprio : per esempio la funzione f : Z 2Z , f(x) = 2x una corrispondenza biunivoca tra linsieme Z dei numeri interi relativi e il suo sottoinsieme proprio 2Z (insieme dei numeri relativi pari).

2VVHUYD]LRQH  Il principio dei cassetti pu essere esteso , diventando il Principio generale dei
cassetti ( o delle gabbie dei piccioni ) : Se ho nk + 1 oggetti da riporre in n cassetti , qualche cassetto contiene almeno k + 1 oggetti. Per k = 1 , si ritrova il principio enunciato prima ( se ho n + 1 oggetti in n cassetti , qualche cassetto ne contiene almeno 2 ) . La dimostrazione per assurdo di questa proposizione la seguente : se ogni cassetto contenesse al pi k oggetti , avremmo al pi nk oggetti , contro lipotesi .

(VHPSLR  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

(VHUFL]L  Con il principio generale dei cassetti si risolvono i seguenti esercizi :

Universit di Torino

D.Romagnoli Algebra del calcolo combinatorio

13

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 .

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 . 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 .

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 .

Quaderni Didattici del Dipartimento di Matematica

14

Capitolo 4 Permutazioni e disposizioni

CAPITOLO 4
Permutazioni e disposizioni .
4.1 Le permutazioni di n elementi . 4.2 le disposizioni di n elementi di classe k . 4.1 Le permutazioni di n elementi . Ritorniamo ad occuparci di biiezioni tra insiemi finiti .
Premettiamo alcune notazioni .

Definizione 4.1.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 4.1.1 n! cresce rapidamente al crescere di n : ne diamo i primi dieci valori

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

Proposizione 4.1.1 Siano A e B due insiemi finiti dello stesso ordine n . Le biiezioni tra di essi sono
n! . Dimostrazione . Con linduzione . Sia n = 1 ( Base dellinduzione ) . Se A e B hanno un elemento ciascuno lunica 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 (anchesso di ordine n ) si ottiene dando una biiezione su n-1 elementi e dando limmagine dellelemento 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 ln-simo elemento di A . In totale le biiezioni cercate sono n . (n-1)! = n ! Dimostrazione . Con il metodo delle scelte .

Universit di Torino

D.Romagnoli Algebra del calcolo combinatorio

15

Per individuare una biiezione , noti il dominio e il codominio , basta assegnare le n immagini degli n elementi del dominio . Ora , per limmagine del primo elemento di A abbiamo n scelte (qualunque elemento di B) , per limmagine del secondo elemento di A abbiamo n-1 scelte ( per liniettivit ) , , per limmagine delln-simo elemento di A la scelta unica . Si possono dunque effettuare n! scelte : ad ognuna corrisponde una diversa biiezione di A in B . 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 4.1.1 Le permutazioni di un insieme di ordine n sono n!

Per comodit di scrittura poniamo , nel seguito , A = In ( identifichiamo in pratica gli elementi dellinsieme con i loro indici ) e facciamo alcune considerazioni . Ricordiamo che notazione standard indicare con

2 . . . n 1 f (1) f (2) . . . f (n )
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

1 2 3 4 4 1 2 3
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 linversa di una permutazione . Vediamolo su un esempio .

Esempio 4.1.1 Sia n = 4 e siano f la permutazione precedente e g la seguente : 1 2 3 4 2 1 4 3

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 :

1 2 3 4 4 1 2 3 3 2 1 4
da cui troviamo la composizione cercata :

Quaderni Didattici del Dipartimento di Matematica

16

Capitolo 4 Permutazioni e disposizioni

1 2 3 4 3 2 1 4
Linversa 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 : .

4 1 2 3 1 2 3 4
e, riordinando le colonne , abbiamo f -1 :

1 2 3 4 2 3 4 1
Ricordando che la composizione di funzioni un operazione associativa e non commutativa , si ha la

Proposizione 4.1.2.

Linsieme di tutte le permutazioni di un insieme di ordine n , rispetto alloperazione di composizione , un gruppo non abeliano . Tale gruppo , che ha un importanza fondamentale allinterno 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 dallaltro 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 .

Esempio 4.1.2 Scriviamo tutte le 3! = 6 permutazioni di 3 palline di colore B (bianco),R (rosso), V

(verde) . Abbiamo due allineamenti che mettono la pallina B al primo posto , altrettanti per R e V (stiamo usando il procedimento induttivo usato nella dimostrazione della proposizione 4.1.1) BRV BVR RVB RBV VBR VRB.

Esercizio 4.1.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 dellalfabeto latino di 26 lettere), si definisce parola un qualunque allineamento dei suoi simboli . Il

Universit di Torino

D.Romagnoli Algebra del calcolo combinatorio

17

numero di simboli detto lunghezza della parola. Se n lordine dellalfabeto, 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 5! / 2! . 3! . 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 ) .

r1 volte , a2 preso r2 volte , , an preso rn volte ogni (r1 + r2 ++ rn ) upla in cui a1 compare r1 volte , a2 compare r2 volte , , an compare rn volte . Il numero totale di questi allineamenti

Osservazione 4.1.2 Si chiama permutazione con ripetizione di n oggetti a1, a2 ,, an di cui a1 preso

( r 1 + r 2 + ... r n )! r 1! r 2!... r n!
Proveremo questo fatto nel paragrafo 5.2 dedicato alle combinazioni . Osserviamo ancora che tale numero ci d il numero delle funzioni suriettive di un insieme di ordine r1 + r2 ++ rn nell insieme di ordine n {a1, a2 ,, an } aventi la propriet che r1 elementi hanno immagine a1, r2 elementi hanno immagine a2 , , rn elementi hanno immagine an .

Esercizio 4.1.3
1) Dire quanti sono gli anagrammi della parola logica e della parola matematica . Soluzione : sono 6! e 10! / 2!.3!.2! rispettivamente . Osserviamo che questo esercizio si pu cos riformulare : in quanti modi possibile sistemare 6 oggetti numerati in sei cassetti in modo tale che ogni cassetto contenga esattamente un oggetto? In quanti modi si possono disporre 10 oggetti numerati in 6 cassetti con la condizione che vi siano tre cassetti che contengono 2,3,2 oggetti e tre cassetti che ne contengono uno ciascuno ? In altre parole : quante sono le funzioni suriettive di I6 in I6 ? Quante sono le funzioni suriettive di I10 in {m,a,t,e,i,c } con la condizione che due numeri abbiano immagine m, tre abbiano immagine a , due t , uno abbia immagine e, uno i, uno c ? 2) Scrivere tutti i numeri formati dalle cifre 1 , 2 , 3 non ripetute Soluzione : 123, 132 , 213 , 231 , 312 , 321 . 3) 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 allaltro, nellordine da lui preferito .

Quaderni Didattici del Dipartimento di Matematica

18

Capitolo 4 Permutazioni e disposizioni

Quante sono le possibili sequenze dei 20 esami ? Soluzione : 5! . 5! . 5! . 5! 4) In quanti modi si possono trovare disposte le carte di un mazzo da 40 ? Soluzione : 40!

4.2 Disposizioni semplici

Nel paragrafo 4.1 abbiamo considerato le permutazioni di n oggetti e abbiamo visto il loro legame con gli allineamenti degli stessi . Supponiamo ora di voler disporre in fila (allineare) k oggetti presi in un insieme di n ( quindi supporremo sempre nel seguito k n ) : il nome di questi allineamenti disposizioni semplici di n oggetti a k a k . Abbiamo gi parlato delle disposizioni con ripetizione di n oggetti nel capitolo dedicato alle funzioni di dominio In : anche le disposizioni semplici di n oggetti a k a k sono funzioni . Precisamente :

Definizione 4.2.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 . Il numero totale delle disposizioni di n oggetti a k a k si indica con Dn,k . Proposizione 4.2.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) = funzioni iniettive di A in B . Dimostrazione . Per induzione su k . Base dellinduzione . Sia k = 1 . Linsieme 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 liniettivit 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) =

n! (n k )!

n! (n k 1)!

Dimostrazione. Con il metodo delle scelte.

Universit di Torino

D.Romagnoli Algebra del calcolo combinatorio

19

Sia A = {a1, , ak }. Contiamo in quanti modi si pu costruire una funzione iniettiva f:AB. 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 liniettivit) , , 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 4.2.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 4.2.3 . 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 loggetto che la occupa , oggetto preso dallinsieme B . Cos , per esempio, se B linsieme 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 VR,RV,VN,NV,RN,NR che corrispondono alle sei funzioni iniettive di A = {a1, a2 } in B = {V, R, N } seguenti : f(a1) = V, f(a2) = R f(a1) = R, f(a2) = V f(a1) = V, f(a2) = N f(a1) = N, f(a2) = V f(a1) = R, f(a2) = N f(a1) = N, f(a2) = R .

Esercizio 4.2.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 12,13,14,23,24,34 21,31,41,32,42,43 2) In quanti modi 3 oggetti possono essere colorati con 5 colori diversi ? Soluzione : Il numero richiesto D5,3 =

5! . . = 3 4 5 = 60 . 2!

2) 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 .

Quaderni Didattici del Dipartimento di Matematica

20

Capitolo 4 Permutazioni e disposizioni

Universit di Torino

20

Capitolo 5 - Combinazioni

CAPITOLO 5
Combinazioni .
5.1 I coefficienti binomiali e il triangolo di Tartaglia . 5.2 Le combinazioni di n elementi di classe k .  , FRHIILFLHQWL ELQRPLDOL H LO WULDQJROR GL 7DUWDJOLD  'HILQL]LRQH  Si dice coefficiente binomiale n su k , 0 k n , il numero n n! k = k!(n k )! 3URSRVL]LRQH 
L 0 = n =1

LL k = n k
LLL =

n k

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

Dimostrazione . Immediata dalla definizione di coefficiente binomiale .

3URSRVL]LRQH  Per qualsiasi numero naturale non nullo n e per ogni a , b reali si ha
(a+b)n = (Formula del binomio di Newton ).

n n-k k k a b

Dimostrazione . Per induzione su n . n =1 ( Base dellinduzione ) : (a+b) = a+b = 0 a + 1 b

Ipotesi induttiva : supponiamo che (a+b)n-1 =

n 1

n 1 n-1-k k k a b .

Universit di Torino

D.Romagnoli Algebra del calcolo combinatorio

21

Calcoliamo (a+b)n. (a+b)n = (a+b)n-1(a+b) = (

n 1

n 1

n 1 n-k k n 1 k a b + 0

n 1 n-1-k k k a b )(a+b) = 0 n 1 n-1-k k+1 . k a b n 1 n 1 n

Il coefficiente del termine an-kbk k + = per la formula di Stifel , da cui la tesi . k 1 k

Dopo aver visto il significato combinatorico di k , daremo una dimostrazione alternativa di queste due proposizioni . Scriviamo ora i coefficienti binomiali disponendoli in un triangolo illimitato , chiamato triangolo di Tartaglia o triangolo di Pascal :

0 0 1 0 2 0 3 0

1 1 2 1 2 2 3 2

3 1

3 3

Per il punto i) della proposizione 5.1.1 il primo e lultimo 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 allinterno del triangolo la somma dei due coefficienti binomiali alla sua destra e alla sua sinistra nella riga precedente . Queste osservazioni ci permettono di riscrivere il triangolo di Tartaglia calcolando molto facilmente i numeri di ogni riga : 1 1 1 1 1 ... 4 3 6 2 3 4 1 1 1 1 ... .

Quaderni Didattici del Dipartimento di Matematica

22

Capitolo 5 - Combinazioni

Abbiamo cos uno strumento molto utile per calcolare rapidamente i coefficienti binomiali e per visualizzarne altre propriet , per esempio :

3URSRVL]LRQH  n n n

n L n = 2 0 + 1 + +

n LL 0 - 1 + 2 + (-1) n = 0

n n

n-1 LLL 0 + 2 + = 1 + 3 + = 2

n n

n n

Dimostrazione . La i) si ottiene scrivendo la formula del binomio di Newton con a = b = 1 . La ii) si ottiene sempre dalla formula del binomio di Newton con a = 1 , b = -1 . Per la iii) , sommiamo membro a membro la i) e la ii) . Otteniamo :
n 2. ( 0 + 2 +) = 2 e quindi

n n

n n n-1 0 + 2 + = 2 .
Da questa relazione e dalla i) si ha :

n n n n-1 n-1 1 + 3 + = 2 - 2 = 2 c.v.d.

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 unaltra delle innumerevoli propriet del triangolo di Tartaglia : se ne diamo la seguente rappresentazione 1 1 1 1 2 1 3 1 4 1 5 . .

1 3 6 10 .

1 4 1 10 5 1 . . . .

Universit di Torino

D.Romagnoli Algebra del calcolo combinatorio

23

leggiamo in diagonale i famosi numeri di Fibonacci F0 = F1 =1 , F2 = 1+1 = 2, F3 = 1+2 = 3 ,F4 = =1+3+1 = 5 ,, Fn = Fn-1 + Fn-2 .

 /H FRPELQD]LRQL GL Q HOHPHQWL GL FODVVH N 

Affrontiamo come ultimo problema largomento da cui prende il nome il calcolo combinatorio .

'HILQL]LRQH  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 .

n 3URSRVL]LRQH  Sia A un insieme di ordine n . A possiede k sottoinsiemi di ordine k .

Dimostrazione . Per induzione su n . n = 0 ( Base dellinduzione ) .Allora anche k = 0 : A linsieme vuoto e possiede 1= sottoinsiemi . Ipotesi induttiva . Supponiamo vera la propriet per un insieme di ordine n-1 . Sia ora A = {a1,,an }.Fissiamo la nostra attenzione su an e sui sottoinsiemi di ordine k n-1: quelli che non contengono an sono , per lipotesi induttiva ,

0 0

{ an } di ordine k ) , quelli che invece lo contengono sono tanti quanti quelli di A - {an } di ordine k-1 , cio , sempre per lipotesi induttiva

n 1 (sono infatti i sottoinsiemi di A k

n 1 ( tali sottoinsiemi si ottengono infatti da quelli di A - {an } k 1

di ordine k-1 aggiungendo an ) Otteniamo dunque che i sottoinsiemi di A di ordine k n-1 sono

n 1 n 1 n k + = . k 1 k
Osserviamo inoltre che, se k = n , allora i sottoinsiemi di A di ordine n sono 1 = n , c.v.d .

2VVHUYD]LRQH  Dalla definizione di combinazione e dalla proposizione 5.2.1 deduciamo che i coefficienti binomiali sono numeri naturali non nulli . 2VVHUYD]LRQH  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 :

Quaderni Didattici del Dipartimento di Matematica

24

Capitolo 5 - Combinazioni

Cn,k =

n Dn, k n! = = k Pk (n k )!k!

(VHPSLR  Se B linsieme 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 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 .

Usando la definizione di combinazione e luguaglianza Cn,k = si dimostrano senza calcoli le propriet dei coefficienti binomiali . Cos la i) 0 = n =1 della proposizione 5.1.1 pu essere motivata osservando che ci sono solo un

n k

sottoinsieme con 0 elementi (linsieme vuoto ) e uno con n ( tutto linsieme) . Per la ii) k =

n basta osservare che quando scegliamo k elementi tra n,isoliamo automaticamente i restanti n k n n 1 n 1 n-k . La iii) k = + ( formula di Stifel ) , 1 k n-1, si ottiene osservando che , k k 1 n 1 fissato un elemento tra gli n , vi sono k sottoinsiemi di ordine k che non lo contengono e n 1 k 1 che lo contengono ( questultimo numero si calcola escludendo lelemento 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 n-k k k a b

pu essere ottenuta con considerazioni di tipo combinatorico : svolgendo i conti (a+b)n = (a+b)(a+b)(a+b) si ottiene una somma di n addendi , ognuno dei quali un prodotto di n copie di a o di b in cui se a

Universit di Torino

D.Romagnoli Algebra del calcolo combinatorio

25

compare n- k volte , b compare k volte . Il coefficiente di an-kbk dato dal numero dei fattori in cui ci sono n-k a , e quindi k b (ricordiamo che vale la propriet commutativa del prodotto) : questo numero , in quanto il numero di modi in cui possiamo scegliere k binomi (a+b) tra gli n totali . Osserviamo infine che , sempre per il significato dei coefficienti binomiali , nel triangolo di Tartaglia la somma dei numeri della riga n-sima ci d lordine dellinsieme delle parti di un insieme di ordine n ( Proposizione 5.2.2 , punto i) ) . Terminiamo dimostrando quanto affermato nella osservazione 4.1.2 del capitolo 4 .

n k

3URSRVL]LRQH  Sia S una sequenza di lunghezza n formata con n1 oggetti ripetuti di tipo 1 , n2
di tipo 2 , , nt di tipo t . Il numero totale di tali S (dette anche permutazioni con ripetizioni )

n! n1!n 2!...nt!
Dimostrazione . Dobbiamo dare una posizione a ognuno degli n elementi per ottenere una sequenza : possiamo dare posizione agli n1 elementi di tipo 1 in Cn,n1 modi . Fatto questo , possiamo dare posizione agli n2 elementi di tipo 1 in Cn-n1,n2 modi , , possiamo dare posizione agli nt elementi di tipo t in Cn-n1--nt-1,nt modi . Otteniamo cos : Cn,n1 . Cn-n1,n2 . . Cn-n1--nt-1,nt =

n! (n n1)! . ( n n1 ... nt 1)! = n1!(n n1)! n 2!(n n1 n 2)! nt!0!

n! c.v.d n1!n 2!...nt! n! viene anche indicato con il simbolo n1!n 2!...nt!

2VVHUYD]LRQH  Il numero

n n1 n 2 .

nt

e chiamato numero (o coefficiente) multinomiale . Tali numeri sono una generalizzazione dei binomiali . Per t = 2 ogni numero multinomiale coincide con un binomiale . Non difficile , tenendo presente il loro significato combinatorico , provare la seguente formula , che generalizza la formula del binomio di Newton : dati gli interi positivi n e t,

( x1+x2++xt)n =

n1 n 2

n .

n1 n2 x1 x2 xtnt , nt

dove la somma fatta su tutte le t-uple di interi non negativi (n1, n2,nt) con n1+n2+ +nt = n .

Quaderni Didattici del Dipartimento di Matematica

26

Capitolo 5 - Combinazioni

2VVHUYD]LRQH  Osservando che , come gi detto nellosservazione 4.1.2 , il coefficiente multinomiale n n1 n 2 . . . nt conta anche il numero delle suriezioni di un insieme di ordine n in un insieme di
ordine t con la condizione che n1 elementi abbiano immagine il primo elemento del codominio , , nt il tesimo , si ottiene che lordine dellinsieme delle suriezioni di In in It dato da

n1 n 2

n .

nt

dove la somma fatta su tutte le t-uple di interi non negativi (n1, n2,nt) con n1+n2+ +nt = n .

(VHPSLR  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 lultimo libro , Matteo gli altri tre . E evidente che la risposta al quesito il numero degli anagrammi della parola mamma , cio 10 . La sequenza ammma determina la seguente suriezione f di I5 in {a,m} : f(1) = f(5) = a , f(2) = f(3) = f(4) = m .

(VHUFL]L 
1) Quattro giocatori di tennis vogliono giocare un doppio . Quante coppie distinte possono formarsi ? Soluzione . Vi sono C4,2 = 6 formazioni distinte di due giocatori ciascuna . 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 :

90 = 622614630 . 6

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

108 possibilit . 13

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 si possono formare ? Soluzione . (a) C52,5 = 2.598.960 (b) 48 ( tante infatti sono le scelte per la quinta carta )

Universit di Torino

D.Romagnoli Algebra del calcolo combinatorio

27

(c) 13.48 (si hanno infatti 13 scelte per il grado del poker e per ognuna 48 scelte per la quinta carta).

5) In quanti modi possiamo distribuire 8 videocassette diverse a tre amici, Silvio, Daniele ed Elisa , dandone quattro a Silvio e due a ciascuno degli altri ? Soluzione . Basta calcolare il numero multinomiale

8 . Si ottiene 420 . 4 2 2

6) 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 possibilit e quindi altrettante ripartizioni di palline .

11

7) In quanti modi possiamo scrivere il numero naturale non nullo n come somma di k numeri naturali non nulli ?Si considerano diverse due rappresentazioni che differiscono per lordine degli addendi. Soluzione : Pensando a n come alla somma 1+1++1 di n 1 , agli 1 come palline e alle k somme come cassetti , lesercizio 5 generalizzato ci dice che le possibilit sono

n 1 . k 1

Per esempio , il numero 5 si pu scrivere in quattro modi come somma di due naturali non nulli : 5 = 1+4 = 2+3 =3+2 = 4+1.

8) In quanti modi possiamo mettere 12 palline identiche (e quindi indistinguibili) in 6 cassetti (numerati da 1 a 6) 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

Quaderni Didattici del Dipartimento di Matematica

28

Capitolo 5 - Combinazioni

17 5 possibilit .
9) In quanti modi possiamo scrivere il numero naturale non nullo n come somma di k numeri interi non negativi ? Si considerano diverse due rappresentazioni che differiscono per lordine degli addendi . La risposta data dallesercizio 8 ( lo zero il cassetto vuoto ) ed

n + k 1 k 1

Con la stessa tecnica usata nellesercizio 8 si prova la

3URSRVL]LRQH   Se A un insieme di ordine n , il numero delle scelte non ordinate di k

elementi , con ripetizioni, Cn+k-1,n-1 = Cn+k-1,k . 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 scelta . 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 .

(VHPSLR   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 .

Universit di Torino

D.Romagnoli Algebra del calcolo combinatorio

29

Quaderni Didattici del Dipartimento di Matematica

Bibliografia
 I. Anderson , A first course in combinatorial mathematics,Clarendon press-Oxford 1974  N.L.Biggs , Discrete mathematics , Clarendon presse Oxford 1985  A.Conte - L.Picco Botta - D.Romagnoli , Algebra , LevrottoBella Torino 1986

 J.H.Conway-R.K.Guy , The book of numbers , Copernicus - Springer - Verlag 1995  A. De Marco , Algebra per i licei scientifici , Poseidonia - Bologna 1976  K.Devlin , Dove va la matematica , Bollati Boringhieri 1994  S.S.Epp , Discrete Mathematics with applications , PWS publishing Company 1995  A.Facchini, Algebra e matematica discreta , Decibel Zanichelli 2000  Fomin D.- Genkin S. - Itenberg I. , Mathematical circles ( Russian experience ) , 1996 Mathematical world . Vol. 7 American Mathematical Society  M. Gardner , Carnevale matematico, Zanichelli 1977  Graham-Knuth-Patashnik , Matematica discreta , Hoepli 1992  R. Johnsonbaugh , Discrete Mathematics, Macmillan Publishing Company Macmillan Publishers 1984 Collier

 E.Lucas ,Theorie des nombres , Librairie scientifique et technique Albert Blanchard , 1961

 W.Maraschini-M.Palma, Format ,SPE.La formazione matematica per il triennio 1

Paravia 1996

 S.B.Maurer A.Ralston , Discrete algorithmic mathematics , Addison-Wesley

publishing company 1991  G. M. Piacentini Cattaneo , Algebra . Un approccio algoritmico , Decibel Zanichelli 1996  PMA ProgettoMatematica Archimede,Corso modulare di matematica 2, Archimede Edizioni Bruno Mondadori 1999  K.H.Rosen , Elementary number theory and its applications , Addison Wesley 1993  M. Townsend , Discrete mathematics : applied combinatorics and graph theory , the Benjamin Cummings publishing Company , Inc . 1987