IL CALCOLO COMBINATORIO APPUNTI ED ESERCIZI Andrea Prevete, 2016

(1)

CALCOLO IL

COMBINATORIO

APPUNTI ED ESERCIZI

(2)

INTRODUZIONE

Per calcolo combinatorio intendiamo le definizioni, i concetti e le tecniche di calcolo che consentono di ragionare sui modi in cui è possibile raggruppare o elencare un certo numero di elementi appartenenti ad un insieme finito di partenza.

Chiamiamo I l’insieme i cui elementi siano le vocali dell’alfabeto:

I={a, e, i, o, u}

I sottoinsiemi di classe 2 (cioè contenenti due elementi) A={e, u} e B={u, e} possono essere considerati distinti? No. Sono identici perchè contengono gli stessi elementi.

Per un insieme infatti non conta l’ordine in cui gli elementi sono presentati!

Gli insiemi ordinati (o elenchi) C=(e, u) e D=(u, e) sono identici? La risposta, questa volta, è no. In un elenco non contano, infatti, solo gli elementi presenti, ma anche l’ordine di presentazione.

Andrea Prevete, 2016

(3)

PERMUTAZIONI

Siamo pronti per il primo concetto, quello di PERMUTAZIONE.

Consideriamo ancora il precedente insieme I. Possiamo elencare i suoi elementi in vario modo. Per esempio:

M=(e, a, i, o, u) N=(e, a, i, u, o)

M ed N, per quanto abbiamo detto sugli insiemi ordinati, sono chiaramente distinti. Infatti, risulta scambiata la posizione degli elementi u ed o.

Quindi, da un insieme dato possiamo ottenere più elenchi distinti scambiando (permutando) la posizione di coppie di elementi.

Ma quanti elenchi distinti possiamo ottenere?

La risposta è un numero sorprendentemente grande, 120.

(4)

PERMUTAZIONI

Per comprendere l’origine di questo numero proviamo a ragionare sulle

alternative che via via ci si presentano mentre costruiamo uno degli elenchi distinti.

Partiamo dall’insieme d’origine I={a, e, i, o, u}.

Per ottenere un elenco valido dobbiamo scegliere come primo elemento una qualsiasi delle vocali in I. Le vocali sono 5, quindi abbiamo 5 possibili

alternative. Supponiamo di optare per la e, l’elenco sarà al momento L=(e).

Dobbiamo scegliere la seconda vocale dell’elenco. Avendo già scelto la e ci restano solo 4 alternative. Se scegliamo la u, l’elenco parziale sarà:

L=(e, u).

Già per ottenere quest’elenco parziale abbiamo dovuto compiere una scelta fra 20 possibili, come è evidente dal grafico che segue.

(5)

PERMUTAZIONI

()

(a)

(ae) (ai) (ao) (au)

(e)

(ea) (ei) (eo) (eu)

(i)

(ia) (ie) (io) (iu)

(o)

(oa) (oe) (oi) (ou)

(u)

(ua) (ue) (ui) (uo)

(6)

PERMUTAZIONI

Continuando potremmo, ad esempio, costruire l’elenco:

L=(e, u, i, a, o)

Avremmo così fatto una scelta su 5·4·3·2·1=120 possibili.

Esistono, in altre parole, 120 elenchi distinti che possono essere formati ordinando un insieme di 5 elementi.

Nel linguaggio del calcolo combinatorio questa deduzione si esprime così:

Si legge «permutando 5 elementi si ottengono 5 fattoriale elenchi distinti».

Il simbolo ! (letto «fattoriale») è un operatore postfisso (che segue cioè il numero a cui è applicato), il cui significato è intuitivo: consente di scrivere in maniera sintetica il prodotto di un numero per tutti i naturali che lo precedono.

Ovviamente, per un insieme generico, costituito da n elementi, si avrà:

(7)

PERMUTAZIONI CON RIPETIZIONI

Consideriamo ora un insieme diverso dal precedente:

I={a, a, a, k, w, H, Z, 1}

Supponiamo che questi siano gli 8 simboli che abbiamo scelto per formare una password che utilizzeremo per l’accesso ad un certo servizio web.

Quante possibili password si possono ricavare utilizzando i simboli di I?

Facile, potremmo rispondere, basta calcolare le possibili permutazioni di 8 elementi:

Errore! Le password distinte sono di meno. Il calcolo effettuato non tiene, infatti, conto delle password identiche che si generano per la ragione che l’insieme I contiene, ripetuto 3 volte, l’elemento a.

Se nella password «kawaHaZ1» scambio seconda e quarta lettera ottengo

«kawaHaZ1», cioè la stessa password!

(8)

PERMUTAZIONI CON RIPETIZIONI

Abbiamo appena visto che gli scambi che coinvolgono elementi identici non sono validi nel senso che non producono elenchi distinti. Ma quanti sono, nel nostro esempio, gli elementi identici? Le 3 a. Quanti sono gli scambi che le coinvolgono? Facile:

Questo significa che il nostro calcolo delle possibili password aveva generato un numero 6 volte più grande di quello esatto perché teneva conto anche degli elementi ripetuti. Il

calcolo corretto è quindi:

Si legge «permutando 8 elementi di cui uno ripetuto 3 volte, si ottengono 8 fattoriale fratto 3 fattoriale elenchi distinti».

Anche in questo caso è facile generalizzare la formula per un insieme qualsiasi di n elementi di cui uno ripetuto k volte:

(9)

DISPOSIZIONI

Restiamo nell’ambito del problema di creare una password a partire dai simboli appartenenti ad un dato insieme.

Supponiamo stavolta che l’insieme da cui scegliere le lettere per la nostra password sia I={a, b, c, d, e, f, g, h, i, j, k …, y, z, 0, 1, 2, 3, .. 9}

Vogliamo costruire una password di lunghezza 8 e ci domandiamo quante scelte abbiamo.

Il problema non è difficile se ricordiamo come abbiamo ragionato con il caso delle permutazioni.

Per la prima lettera della password abbiamo 36 opzioni (tanti sono i simboli di I).

Scelta la prima, per la seconda possiamo scegliere uno dei 35 simboli rimasti, e così via fino a completare la password.

La password è composta da 8 lettere, quindi abbiamo operato 8 scelte – la prima fra 36 possibilità, poi fra 35(36-1) possibilità, quindi fra 33(36-2) ……… infine fra 29(36-7) possibilità.

Al termine dell’operazione abbiamo la nostra bella password di lunghezza 8, del tutto inconsapevoli del fatto che l’abbiamo scelta fra 1220096908800 possibili altre password!!!

Non ci sono errori, il numero è proprio quello scritto, più di mille miliardi.

(10)

DISPOSIZIONI

Nel linguaggio rigoroso del calcolo combinatorio diciamo che abbiamo determinato il «numero di disposizioni distinte di un insieme di 36 elementi di classe 8 (ovvero a formare elenchi di lunghezza 8)»:

E’ facile convincersi che, nel caso generale di un insieme di n elementi con cui ,

vogliamo formare disposizioni di classe k, la formula diventa:

Moltiplicando denominatore e numeratore per (n-k)! La formula assume un aspetto ,

più compatto:

,

Andrea Prevete, 2016n!

(11)

DISPOSIZIONI CON RIPETIZIONI

Riconsideriamo ancora il problema di creare una password utilizzando i simboli appartenenti ad un dato insieme.

Sia l’insieme di partenza lo stesso:

I={a, b, c, d, e, f, g, h, i, j, k …, y, z, 0, 1, 2, 3, .. 9}

Vogliamo ora costruire la nostra password di lunghezza 8 utilizzando i simboli di I ma con la condizione che un simbolo, una volta utilizzato, non è da considerarsi consumato, può cioè essere utilizzato più volte, ripetuto.

Allora il problema è notevolmente più semplice del caso precedente.

Per ognuna delle 8 scelte relative alla password ho sempre 36 possibilità. Se infatti scelgo come prima lettera della password una f, questa non viene eliminata da I e può – per esempio – essere scelta di nuovo come seconda lettera della password e così via.

Quindi il numero di potenziali password è 36· 36· 36· 36· 36· 36· 36· 36=36

⁸

=2821109907456.

Un numero incredibile: quasi tremila miliardi.

Si parla in questo caso di «disposizioni di n elementi di classe k con ripetizioni»:

, =

(12)

COMBINAZIONI

Cambiamo completamente contesto.

Supponiamo che un’agenzia di grafica pubblicitaria abbia deciso di impostare la prossima campagna cartellonistica su di un uso estremamente ridotto di colori, diciamo tre, scelti in un insieme di otto:

I= {giallo, arancio, marrone, rosso, azzurro, blu, viola, grigio}

Volendo fare dei test per sondare la compatibilità delle varie terne di colori – quando tempo bisogna preventivare per questa fase?

Ovviamente la prima cosa da fare è valutare il numero di terne distinte di colori che è possibile estrarre da I.

Noi sappiamo già contare le terne ordinate, sapendo che corrispondono al numero di disposizioni di 8 elementi di classe 3, cioè:

,

(13)

COMBINAZIONI

Ma nel calcolo appena fatto, per esempio, la terna {giallo, azzurro, grigio} viene contata più volte - dato che vengono considerati distinti gli elenchi (giallo,

azzurro, grigio), (azzurro, giallo, grigio), etc.

Un momento .. ma questo è proprio quello che ci serve!

Una terna come {giallo, azzurro, grigio} è un insieme di 3 elementi da cui, con successive permutazioni si possono ricavare P ₃ =3!=6 elenchi differenti.

Quindi 336 è 6 volte più grande del numero di terne di colori che stiamo cercando. Il calcolo corretto è allora:

, = 56

Nella formula precedente compare il nuovo simbolo C al posto di D. Parliamo

infatti non più di disposizioni ma di «combinazioni di 8 elementi di classe 3».

(14)

COMBINAZIONI

Quindi, in generale, se voglio ottenere il numero di sottoinsiemi distinti di k elementi che posso estrarre da un insieme di n elementi – calcolerò:

,

L’espressione ^! _{! !} è così importante che ad essa è riservata una notazione particolare, la si indica spesso – infatti – con l’espressione . Così la formula per le combinazioni diventa:

, =

(15)

COMBINAZIONI

, leggi «n sopra k», prende anche il nome di coefficiente binomiale.

E’ facile, infatti, convincersi che la potenza ennesima di un binomio può essere espressa tramite i suddetti coefficienti:

Nota bene: per convenzione il fattoriale di zero vale 1, cioè 0!=1

(16)

COMBINAZIONI CON RIPETIZIONE

Cambiamo ancora contesto.

Supponiamo che il responsabile del dipartimento R&S di un’azienda debba assumere tre professionisti per formare un nuovo team di lavoro. Ha libertà di scegliere i profili professionali giusti purchè i candidati abbiano una laurea in economia o in matematica o in informatica o in ingegneria o, ancora, in statistica.

Ovviamente ognuna delle possibili alternative creerà un team con un profilo di competenze ed attitudini differenti. Un gruppo di lavoro con 2 matematici ed uno statistico si comporterà differentemente da uno composto da un informatico, un ingegnere ed un esperto in economia così come da uno composto da 3 ingegneri.

Prima di iniziare i colloqui e quindi effettuare la scelta, il nostro responsabile vorrebbe avere un’idea di quanti team con diverso profilo può formare.

C’è sicuramente un insieme di partenza, quello delle lauree consentite:

I= {economia, matematica, informatica, ingegneria, statistica}

Da questo si possono estrarre dei sottoinsiemi di tre elementi. Per esempio:

{economia, ingegneria, statistica}, {informatica, ingegneria, statistica}, etc

(17)

COMBINAZIONI CON RIPETIZIONE

In questi gruppi non importa l’ordine: un informatico, un ingegnere ed uno statistico sono ovviamente la stessa cosa di un ingegnere, un informatico ed uno statistico.

Ma allora quello che stiamo affrontando è un problema di combinazioni di 5 elementi a formare gruppi di 3 elementi.

= 10

Questa volta il numero sembra addirittura troppo piccolo rispetto a quanto ci suggerisce l’intuito.

Ed infatti stiamo trascurando un aspetto importante del problema: le possibili ripetizioni!

A differenza del problema dei colori che abbiamo affrontato nella sezione precedente, questa

volta gli elementi dell’insieme di partenza (le lauree) possono essere ripetuti per comporre le

terne di professionisti: il gruppo {informatica, informatica, informatica} è, per esempio, un

gruppo accettabile.

(18)

COMBINAZIONI CON RIPETIZIONE

Siamo di fronte, quindi, ad un problema di combinazioni con ripetizioni.

Per risolverlo costruiamo uno schema come segue:

Poi inseriamo nelle celle vuote, a piacere, tre X. Per esempio:

Possiamo interpretarlo come la scelta {matematica, matematica, ingegneria}. Sistemiamo invece le X come segue:

L’interpretazione diventa {economia, ingegneria, statistica}.

Cioè, ogni X nella cella a sinistra di una laurea indica che per essa c’è un posto disponibile nel team. Le X nell’ultima cella si riferiscono invece all’ultima laurea, statistica, che non è stata inserita nella tabella.

ECO MAT INF ING

ECO X X MAT INF X ING

X ECO MAT INF X ING X

(19)

COMBINAZIONI CON RIPETIZIONE

Allora fare una scelta significa scrivere un elenco, per esempio nel caso dell’ultima tabella:

(X, ECO, MAT, INF, X, ING, X)

Calcoliamo tutti gli elenchi possibili, ossia le permutazioni di 4 lauree + 3 X = 7 elementi:

= 5040

Adesso il numero sembra effettivamente troppo grande!

In effetti manca ancora qualcosa. Non abbiamo considerato che se negli elenchi scambiamo la posizione delle X non cambia niente. Ma non cambia niente anche se scambiamo la posizione delle lauree:

(X, ECO, MAT, INF, X, ING, X) è lo stesso che (X, ING, MAT, INF, X, ECO, X)

Quindi dobbiamo dividere il risultato ottenuto per le permutazioni possibili delle X e delle lauree-1.

= 35

Questo è finalmente un numero che ci sembra ragionevole, ed infatti è quello corretto!

(20)

COMBINAZIONI CON RIPETIZIONE

Il risultato che abbiamo conseguito può essere generalizzato con la seguente formula :

= =

Essa esprime il «numero di possibili combinazioni di

classe k ottenibili a partire da un insieme di n elementi che possono essere ripetuti», cioè usati più volte.

(21)

ESERCIZI RISOLTI

• Quattro squadre accedono alla parte finale di un torneo. Quante diverse classifiche si possono avere?

Bisogna evidentemente calcolare tutti i possibili modi in cui è possibile mettere in fila 4 squadre – cioè:

= 24

• Voglio allestire una vetrina disponendo in fila 2 giacche blu, una giacca marrone, 1 maglione, 1 camicia, 1 gilet. Se cambio l’allestimento tutti i giorni riesco a coprire un anno commerciale con vetrine sempre diverse?

Bisogna evidentemente calcolare tutti i possibili modi in cui è possibile mettere in fila 6 capi d’abbigliamento di cui 2 identici fra loro, quindi:

Si, riesco giusto a coprire un anno commerciale!

(22)

ESERCIZI RISOLTI

• In una classe di 16 studenti la settimana prossima saranno eletti il rappresentante, il vice- rappresentante ed il vice-vice-rappresentante. Vorremmo preparare in anticipo una locandina con i risultati. Quante locandine dovremmo preparare per essere certi che ci sia quella giusta.

Bisogna evidentemente calcolare tutti i possibili modi in cui è possibile fare un elenco di lunghezza 3 a partire dai 16 elementi di un insieme – cioè:

, !

( )!

• I migliori 10 studenti di un istituto partecipano a tre gare, rispettivamente di storia, inglese, matematica. Quanti diversi elenchi di vincitori si possono avere?

Ogni studente partecipa a tutte le gare e, quindi, può vincerle tutte. E’ ovviamente un problema di disposizioni con ripetizioni.

,

=

(23)

ESERCIZI RISOLTI

• Un gruppo di 10 amici, incontrandosi, si danno la mano l’un l’altro. Quante strette di mano ci saranno complessivamente?

Come molti problemi del genere, sembra, a prima vista, complicato. In realtà, basta riflettere sul fatto che ogni stretta di mano corrisponde ad una coppia. Quindi è un semplice problema di combinazioni di classe 2 a partire da 10 elementi:

, !

( )! !

·

• Volendo rinnovare la flotta aziendale, decido di comprare tre nuove ammiraglie scelte fra i modelli di punta di Mercedes, Alfa, BMW, Audi, Volvo. Quante diverse scelte devo valutare?

Devo scegliere un gruppo di 3 auto, non importa l’ordine – quindi è un problema di combinazioni. Dato che la traccia non lo esclude, ogni marca può essere scelta più volte, quindi sono ammesse ripetizioni:

,

=

(24)