LA COMBINATORIA Primi elementi per la scuola dell'obbligo

LA COMBINATORIA Primi elementi per la scuola dell'obbligo

Vittorio De Petris - 15/05/2002 1 - Perché introdurre la combinatoria nella scuola media.

Riprendiamo quanto ha scritto Gian Carlo Rota in Analisi combinatoria (Le Scienze Matematiche -UMI-Zanichelli, 1973):

"Quasi tutta la matematica classica, dall'algebra elementare alla teoria delle equazioni differenziali, è applicabile al mondo reale solo nell'ipotesi che questo sia costituito di oggetti e di eventi a carattere continuo. Però, in molte situazioni comuni in fisica e in chimica ed in altre scienze, si può parlare realisticamente solo di collezione di oggetti a carattere discreto, i quali agiscono in combinazione, un passo per volta; la matematica applicata a tali situazioni si chiama analisi combinatoria. Molti problemi di analisi combinatoria, tra i più interessanti, si sono presentati nella forma di ingegnosi indovinelli, a sfida di matematici e non matematici assieme: a prima vista, alcuni di essi possono sembrare addirittura frivolezze, eppure quasi tutti hanno delle applicazioni immediate ed importanti a problemi scientifici concreti.

Il campo vasto e mal definito della matematica applicata si va rapidamente dividendo in due parti distinte, con pochissimo in comune.

La prima comprende la variopinta discendenza di ciò che nel secolo scorso si chiamava meccanica razionale o meccanica analitica, ed include imprese venerande ed illustri come la meccanica del continuo, la teoria della elasticità e l'ottica geometrica, al pari di sviluppi moderni quali la teoria dei plasmi, la teoria degli sviluppi supersonici e così via. Questa parte è in via di rapida trasformazione, anche per l'introduzione di calcolatori automatici veloci.

La seconda parte, invece, concentra il suo interesse sui cosiddetti fenomeni discreti, sia in matematica, che nelle scienze naturali. Il termine combinatoria, introdotto dal filosofo e scienziato tedesco G.W. Leibniz in un suo classico trattato, è ormai di uso generale fin dal secolo XVII. Problemi di tipo combinatorio s'incontrano in quantità sempre crescente in ogni ramo della scienza, anche in quelli dove raramente si ricorre alla matematica. Si fa strada l'idea che le scienze della vita, raggiunto lo stadio in cui diventa indispensabile un apparato matematico, dovranno ricorrere soprattutto alla teoria combinatoria: questo è già evidente in quelle branche della biologia come la genetica e la biologia molecolare, in cui la ricchezza di dati sperimentali permette la graduale elaborazione di teorie solidamente fondate. La fisica stessa, da tempo fonte di tante ricerche matematiche, si trova oggi di fronte a problemi difficili, in meccanica statistica e in teoria delle particelle elementari, che non possono essere risolti finche non si saranno elaborate teorie completamente nuove, di natura combinatoria, per comprendere la struttura discontinua del mondo molecolare e subatomico.

A tutti questi incentivi dobbiamo aggiungere il calcolo automatico veloce, il quale esige l'impiego di teorie combinatorie, come guida indispensabile all'azione concreta. L'interesse per i problemi combinatori è stato poi grandemente stimolato anche dalla possibilità di saggiare, a mezzo di calcolatori automatici, congetture del tutto inaccessibili. Tutti questi sintomi basterebbero già a pronosticare una più intensa attività di ricerca in teoria combinatoria. Un altro indizio, forse più importante, è dato dall'impulso verso indagini di tipo combinatorio, che si sviluppa nel seno stesso della matematica."

Quanto precede giustifica già ampiamente la necessità di inserire la combinatoria nella didattica della matematica. Non va inoltre dimenticato il contributo che essa ha dato allo sviluppo della teoria della probabilità, della quale la

combinatoria costituisce ancora una premessa indispensabile, come risulta anche dalla seguente affermazione di J.Piaget (La genesi dell'idea di fortuito nel bambino", Newton e Compton Editori, 1976), secondo il quale "...La comprensione stessa dell'idea di fortuito implica quella di operazioni combinatorie, di cui il fatto fortuito costituisce una frazione di realizzazione..."

2 Qualche considerazione preliminare sulla combinatoria.

Partiamo da una tipica situazione combinatoria. Abbiamo davanti alcuni oggetti e ci prepariamo a disporli in ordine, secondo una certa regola, cercando di ottenere tutte le possibili combinazioni. Ad esempio, abbiamo fissato un alfabeto costituito da un certo numero di lettere e vogliamo scrivere parole, senza tener conto del significato delle parole stesse, purché esse rispettino le regole prestabilite.

La prima domanda che ci si pone in questi casi è: "Quante combinazioni diverse si possono fare?". La risposta è molto importante, poiché la conoscenza di tale numero è fondamentale per sapere se, cercando concretamente di procedere alla costituzione di tali combinazioni, si riesce alla fine a realizzarle tutte. A volte si scopre che il numero di casi è così grande che è in pratica impossibile riuscire a formularne un elenco completo. In genere, ciò che interessa è proprio e soltanto il numero di combinazioni. Qualcuno ha definito la combinatoria come l'arte di contare ... senza contare, mettendo in evidenza la maggiore importanza che in combinatoria ha la conoscenza del numero di combinazioni,

rispetto alla conoscenza delle combinazioni stesse.

In ogni caso, non è possibile fornire risposta alla domanda, se prima non si hanno i seguenti dati:

• numero di oggetti disponibili (lettere dell'alfabeto);

• numero di quelli che costituiscono una singola combinazione (parole di una certa lunghezza)

• regole per procedere alla loro costituzione.

Tra le regole, alcune consentono di utilizzare in una combinazione tutti gli oggetti disponibili, altre ne utilizzano solo una parte. Si può consentire che uno stesso oggetto sia utilizzato non più di una volta o più volte in una stessa combinazione. In quest'ultimo caso, occorre stabiilire se è fissato o no il numero di possibili ripetizioni. Altre regole stabiliscono se conta o no l'ordine in cui sono disposti gli oggetti nelle varie combinazioni.

A seconda delle risposte date alle domande precedenti, varieranno sia il numero che il tipo di combinazioni. A ciascuna di esse saranno dati nomi diversi (permutazioni, disposizioni, combinazioni, con o senza ripetizione, assegnata o meno).

Una volta individuata quale fra le possibili configurazioni combinatorie è quella che c'interessa, il problema del calcolo è di facile soluzione: basterà applicare la formula. Non è sempre facile individuare la configurazione più adatta al problema combinatorio che si ha davanti.

3 Schema dicotomico per trovare la giusta combinazione.

Lo schema che segue, basato su una serie di scelte dicotomiche, può fornire un aiuto per superare tali difficoltà. Esso non è esaustivo, poiché vi sono in combinatoria altre situazioni (ad esempio, combinazioni o disposizioni con

ripetizione assegnata ecc.), per le quali, tuttavia, è possibile procedere moltiplicando in vari modi le formule valide nei casi qui analizzati.

elementi contenuti in una combinazione). Poi si può procedere lungo il grafo, scegliendo il percorso in base alla risposta data ai vari quesiti; al termine si otterrà una risposta fra le 7 possibili elencate a destra.

4 - Permutazioni semplici.

Seguendo lo schema alla pagina precedente, fissiamo alcune regole:

• abbiamo a disposizione n lettere, tutte differenti;

• combiniamo le lettere, ciascuna presa una sola volta per formare parole di n lettere;

• una parola differisce da un'altra per l'ordine in cui le lettere sono disposte.

Ad esempio, dato un alfabeto formato dalla lettere {A,B,C,D}, formare tutte le possibili parole di quattro lettere. In combinatoria, tali combinazioni prendono il nome di permutazioni semplici di n oggetti. Il termine "semplici" sta ad indicare la regola per la quale non si possono ripetere gli stessi elementi all'interno di ogni permutazione. Il nostro discorso sulla combinatoria parte da questo caso, in cui tutte le n lettere disponibili sono utilizzate, una sola volta, per formare parole di n lettere. L'operazione da fare è solo quella di scambiarle di posto, variando l'ordine, per trovare tutti i possibili anagrammi della parola, come fa un allenatore di una squadra di pallavolo quando decide il modo in cui schierare in campo i sei giocatori della propria squadra, o quando, il primo giorno dell'anno, gli alunni vanno ad occupare i banchi in un'aula. In quanti modi possiamo disporre lettere, giocatori o alunni?

Con pochi oggetti è abbastanza facile trovare tutte le permutazioni. Le cose si complicano quando le parole sono formate da molte lettere. Ci si pongono allora un paio di domande:

• Siamo sicuri di aver trovato tutte le possibili permutazioni?

• E' possibile sapere in anticipo il loro numero?

Le due domande sono collegate, poiché solo sapendo il numero totale di permutazioni potremo essere sicuri (a meno di inconsapevoli duplicazioni) di rispondere affermativamente alla prima domanda.

Supponiamo di conoscere il numero esatto di permutazioni di n elementi e di volerle scrivere tutte. Se n non è troppo grande, il compito può essere facilmente realizzato con l'uso di grafi ad albero. Facciamo un esempio: si vogliano far sedere quattro persone sui sedili di una vettura. In quanti modi possiamo collocarle? Il grafo ad albero visualizza tutte le possibili permutazioni di quattro elementi e permette di farne un elenco completo. Si parte con quattro rami per occupare il primo posto nell'auto con uno qualsiasi dei quattro passeggeri A, B, C, D. Ognuno dei quattro rami genera a sua volta tre rami, uno per ciascuno dei tre passeggeri rimasti. Sistemati i primi due passeggeri, andiamo a sistemare il terzo: sarà uno dei due rimasti, riportato su uno dei due rami che seguono. Si arriva così all'ultima ramificazione con un solo ramo: è il quarto passeggero, che andrà ad occupare l'ultimo posto.

Per avere tutte le permutazioni, basterà scrivere di seguito le lettere che s'incontrano, partendo dal vertice sulla sommità dell'albero, fino a ciascuno dei rami terminali. Avremo:

ABCD ABDC ACBD ACDB ADBC ADCB

BACD BADC BCAD BCDA BDAC BDCA

CABD CADB CBAD CBDA CDAB CDBA

DABC DACB DBAC DBCA DCAB DCBA

Quante sono tutte le permutazioni? Il numero si ottiene osservando il modo con cui l'albero genera di volta in volta i

rami. I quattro rami iniziali generano tre rami, ciascuno dei quali ne produce due, che ne producono infine ancora una altro. Basta moltiplicare 4 x 3 x 2 x 1 e si ottiene 24. Abbiamo così scoperto il fondamentale principio di

moltiplicazione, in base al quale si risolvono molti problemi di tipo combinatorio. In matematica, il prodotto di n fattori interi decrescenti da n ad 1 si chiama fattoriale di n e si indica con il simbolo n!(si legge n fattoriale), che è anche il simbolo con cui si indicano le permutazioni semplici di n oggetti:

n! = n· (n-1)· (n-2) · (n-3)....3· 2 ·1

Il punto esclamativo è dovuto al senso di meraviglia che suscita il rapido crescere di n! al crescere di n. Vediamo alcuni valori, calcolati tenendo presente che n! = n.(n-1)! e che, per convenzione si pone 0! = 1 (del resto, c'è un solo modo di scrivere una parola usando zero caratteri: non scrivere nulla!).

n 0 1 2 3 4 5 6 7 8 9 10

n! 1 1 2 6 24 120 720 5.040 40.320 36.2880 3.628.800

Si vede che già con 10!, si ottiene un valore di oltre 3 milioni e mezzo. Basta un numero non troppo grande, per avere fattoriali di valore impressionante. Ad esempio, utilizzando tutte le 21 lettere dell'alfabeto italiano, gli anagrammi di 21 lettere sono:

21! = 51.090.942.171.709.440.000 ≈ (5.11 x 10¹⁹)

E' perfino difficile leggere un numero così grande: sono oltre 51 miliardi di miliardi. Scrivendo una parola al secondo, ci vorrebbero 1.620.083.148.519 anni per scriverle tutte, più dell'età stimata dell'universo. Gli inglesi, che usano un alfabeto di 26 caratteri, impiegherebbero ancora di più per scrivere tutti i 403 milioni di miliardi di miliardi e passa di parole che si possono ottenere anagrammando il loro alfabeto.

5 Disposizioni semplici.

Apportiamo qualche variazione alle tre regole fissate, che avevano dato luogo alle permutazioni semplici.

• fissiamo un alfabeto di n lettere;

• una parola contiene esattamente k lettere, tutte diverse tra loro. (k ≤ n);

• per ottenere una parola diversa da quella precedente, si possono sostituire una o più lettere con altrettante di quelle rimanenti, oppure variare l'ordine con cui sono disposte le lettere (o fare entrambe le cose).

Ad esempio, un bimbo gioca con 5 tesserine, ciascuna delle quali reca impressa una lettera diversa, e forma parole di tre lettere, oppure un gruppo di persone elegge un presidente, un vicepresidente e un segretario, oppure si realizzano bandierine tricolori (con tre colori tutti diversi), utilizzando una tavolozza di cinque colori, ecc. Questo tipo di combinazioni sono definite disposizioni semplici di n elementi di classe k ed indicate con il simbolo (n)k

La situazione è abbastanza simile a quella già vista in precedenza, con la differenza che il numero di nodi in ciascun ramo dell'albero non è più pari al numero n di elementi disponibili, ma è uguale ad un numero k minore o uguale ad n.

Ad esempio, nel caso di un presidente, un vice presidente ed un segretario, scelti fra i 20 soci di una cooperativa, avremo un presidente scelto tra tutti i 20 soci, un vicepresidente scelto tra i 19 soci rimasti ed un segretario scelto fra i rimanenti 18 soci.

In base al principio di moltiplicazione, per calcolare il numero di tutte le disposizioni, si dovrà moltiplicare

20 x 19 x 18 = 6.840

Chiameremo fattoriale decrescente il prodotto di k fattori decrescenti a partire da n, il cui valore è:

(n)k = n (n-1) (n-2) ... (n-k+1)

Ad esempio, con la prime quattro lettere dell'alfabeto, si possono scrivere le seguenti 24 parole di tre lettere, tutte diverse tra loro.

ABC ABD ACB ACD ADB ADC BAC BAD BCA BCD BDA BDC CAB CAD CBA CBD CDA CDB DAB DAC DBA DBC DCA DCB

Il valore k può essere minore o uguale ad n. E' facile capire che, per k=n, le disposizioni semplici non sono altro che permutazioni semplici di n elementi viste al paragrafo precedente, il cui valore si indica però con n! in luogo di (n)n .

6 Combinazioni semplici.

Esaminiamo ora una delle più classiche situazioni dalla quale scaturiscono combinazioni alle quali spetta la definizione di combinazioni semplici, da cui ha preso il nome tutta la combinatoria. Le regole che presiedono alla costituzione delle combinazioni semplici sono:

• Si dispone di n lettere, tutte diverse tra loro

• se ne prendono ogni volta k (k ≤ n) per formare una parola di k lettere

• due parole differiscono se hanno almeno una lettera diversa

• non ha importanza l'ordine con cui sono disposte le lettere.

Un esempio chiarirà meglio la situazione. Si deve costituire una commissione di k membri, scegliendoli all'interno di un gruppo di n persone. E' chiaro che non ha importanza l'ordine con cui sono scelti i membri. Ciò vale in Parlamento o in un Consiglio Comunale, in cui k deputati o consiglieri sono scelti fra tutti gli n cittadini, ma ognuno ha gli stessi poteri di qualunque altro, indipendentemente dai voti presi.

Nel linguaggio comune, il termine combinazione è usato a volte in modo improprio, quando ad esempio si definisce combinazione il gruppo di cifre necessarie per aprire una cassaforte. In questo caso si tratta invece di disposizioni, essendo importante anche l'ordine con cui le cifre sono composte. In particolare, si tratta di disposizioni con ripetizione, dal momento che una stessa cifra può essere usata più volte.

Prima di procedere alla individuazione delle regole che determinano il numero di combinazioni semplici di n elementi, presi k alla volta, è opportuno raccontare una storiella.

Il principio del pastore.

Un turista si rivolge ad un pastore incontrato in montagna: Certo è una bella fatica dover contare tutti i giorni un numero così grande di pecore!

Ribatte il pastore: No, mi bastano pochi secondi!

Il turista, incuriosito, chiede: Come fai?".

Risponde il pastore: E' facile! Prima conto le zampe, e poi ... divido per 4.!

La regola del pastore, che chiameremo principio di divisione, può sembrare alquanto ridicola, ma non lo è poi tanto. A volte, si fa prima a contare le "zampe" che le "pecore".

Un esempio, tratto dalla biografia di Gauss, può servire a chiarire questa apparente contraddizione. Il piccolo Gauss ebbe dal maestro l'ingrato compito di sommare i primi 100 numeri naturali. Dopo un po' l'allievo presentò la risposta :

"La somma è 5050". Il maestro restò esterrefatto e chiese a Gauss come avesse fatto ad ottenere la somma in così breve tempo. Gauss rispose che gli era bastato riflettere sul fatto che, abbinando ai numeri da 1 a 100 i numeri da 100 ad 1, si ottenevano 100 coppie (un termine sulla 1^a riga e l'altro sulla 2^a) la cui somma è sempre 101:

1 2 3 4 ... 97 98 99 100

100 99 98 97 ... 4 3 2 1

Moltiplicando 100 x 101, si ottiene 10.100, che è il doppio della somma richiesta. A questo punto, basta dividere per 2 e il gioco è fatto: la somma richiesta è 5.050!

Si fa prima dunque a contare 200 numeri usando la moltiplicazione e dividendo per 2, che contarne 100 uno la volta.

Torniamo alla nostra questione: quante combinazioni di n elementi di classe k si possono formare? Sappiamo già che le disposizioni semplici, per gli stessi valori di k sono date dal fattoriale decrescente (n)k. Fra queste, però, ce ne sono alcune che sono costituite dagli stessi elementi per i quali varia soltanto l'ordine. Queste vanno contate una volta sola, dal momento che nelle combinazioni non interessa l'ordine. Quante ne sono? A questa domanda sappiamo già rispondere: si tratta delle permutazioni di k elementi, pari a k! Basta allora applicare il principio di divisione. Si avrà:

Il simbolo con cui vengono indicate le combinazioni semplici di n elementi presi k la volta, si chiama anche coefficiente binomiale, per ragioni che vedremo in seguito.

E' bene chiarire l'uso della precedente formula con un esempio concreto: quante diverse commissioni si possono costituire, scegliendo 5 rappresentanti in un gruppo di 30 persone?

Le combinazioni semplici rivestono una particolare importanza nel calcolo combinatorio, trovando applicazione nella risoluzione di svariati problemi. Torneremo ancora sulle combinazioni, esaminando altri problemi. Chiariremo alcuni aspetti ed alcune proprietà del calcolo combinatorio. Ora, però, occorre completare il quadro, esaminando altre situazioni combinatorie, nelle quali gli n elementi dell'insieme possono essere utilizzati più volte per la costituzione di una combinazione.

7 Disposizioni con ripetizione.

Le permutazioni, disposizioni e combinazioni semplici hanno per regola quella di non poter contenere uno stesso elemento più di una volta. La situazione cambia non poco, se si toglie tale limitazione.

Cominciamo con le disposizioni con ripetizione di n elementi di classe k: si tratta di formare parole di k lettere con un alfabeto di n lettere, potendo utilizzare da 0 a k volte ciascuna lettera per formare le varie parole. Il fatto di poter utilizzare più volte uno stesso elemento, consente di avere anche k>n.

Facciamo un esempio: da un alfabeto di tre lettere {A,B,C} si formano parole di 3 lettere.

Nel precedente caso delle disposizioni semplici, il grafo ad albero presentava un numero decrescente di rami ad ogni nodo successivo, poiché, una volta utilizzato un elemento, non lo si poteva più utilizzare nei posti successivi. Qui, invece, la situazione è diversa. Il grafo ad albero ha sempre 3 rami ad ogni nodo. Infatti, una volta deciso quale delle tre lettere mettere al primo posto, avremo ancora a disposizione le stesse tre lettere anche per il secondo e terzo posto. Si hanno perciò 3³ parole di 3 lettere in un alfabeto di 3 lettere.

Come abbiamo già detto, con tre lettere possiamo scrivere anche parole di 4, 5 ... n lettere, che danno luogo, rispettivamente a 3⁴, 3⁵, ..., 3ⁿ disposizioni con ripetizione.

Nelle permutazioni e le disposizioni semplici il principio di moltiplicazione dava luogo a fattoriali decrescenti. Nel caso delle disposizioni con ripetizione di n elementi di classe k, lo stesso principio produce, invece, la potenza: n^k. E' con tale simbolo che si indicano le disposizioni con ripetizione di n elementi di classe k..

Un esempio di disposizioni con ripetizione è la classica schedina del totocalcio, in cui ogni colonna costituisce una parola di 13 lettere, da un alfabeto di 3 lettere {1, X, 2}. Si possono realizzare 3¹³ colonne, pari a 1.594.323 giocate diverse.

8 Permutazioni con ripetizione assegnata.

Abbiamo già visto un esempio di permutazioni nella composizione di tutti i possibili anagrammi di una parola. Le permutazioni semplici comportano una limitazione implicita: le parole devono avere tutte lettere differenti, dal momento che uno stesso elemento non può essere ripetuto più volte. Proviamo, invece, ad anagrammare la parola MAMMA, in cui compaiono tre M e due A. La situazione si complica, poiché, mentre uno scambio tra la 2 ^a e la 3 ^a lettera darebbe luogo alla nuova parola MMAMA, uno scambio tra la 1^a e la 3 ^a o tra la 1 ^a e la 4 ^a darebbe luogo sempre alla stessa parola MAMMA.

Sarà il caso di tornare a chieder consiglio al ... pastore col suo strano modo di contare le pecore. In un primo momento si potrà anagrammare la parola, come se le lettere fossero tutte diverse. Avremo in tal caso 5! casi, in pratica 120 parole.

Molte di queste sono ripetizioni della stessa parola. Ciò accade nel caso in cui siano state scambiate tra loro le tre M della parola MAMMA: sono in tutto 3! casi. Rimangono le altre ripetizioni dovute agli scambi delle due A della parola MAMMA, che sono a loro volta 2! casi. Applicando il principio del pastore o principio di divisione avremo:

La formula che determina il numero di permutazioni di k elementi, il primo ripetuto k1 volte, il secondo k2 volte, l'ennesimo ripetuto kn volte, ponendo n = (k1 + k2 + ... + kn), è dunque:

Il simbolo a sinistra della formula, in analogia con quanto fatto per le combinazioni (il cui simbolo è stato chiamato coefficiente binomiale), è denominato coefficiente multinomiale.

9 Combinazioni con ripetizione.

Abbiamo già visto la differenza essenziale tra disposizioni e combinazioni semplici. Essa consiste nel fatto che queste ultime non considerano l'ordine con cui sono elencati gli elementi in un raggruppamento, quale motivo di distinzione tra l'uno e l'altro.

Anche tra disposizioni e combinazioni con ripetizione permane la stessa differenza, già vista per quelle semplici. Le parole AABBB e BABAB, formate da due A e tre B, in ordine differente sono considerate due diverse disposizioni, mentre le stesse costituiscono una sola combinazione, essendo indifferente l'ordine con cui compaiono gli elementi.

Il principio del pastore consente di passare dalle disposizioni semplici alle combinazioni semplici, eliminando tutte le disposizioni costituite dallo stesso insieme di elementi, scritti in ordine differente.

Nel caso delle disposizioni e combinazioni con ripetizione, la situazione si complica un po'. La ripetizione, non prefissata, degli stessi elementi fa variare il numero delle ripetizioni stesse. Sono infatti disposizioni diverse AABBC e AABBB. La prima dà luogo, permutando i vari elementi, a 30 diverse parole, che corrispondono ad una stessa combinazione. La seconda ne produce, invece, solo 10, con gli stessi elementi in ordine differente. Il principio di divisione ci porterebbe a dividere ogni volta per un valore variabile (il primo gruppo per 30 ed il secondo per 10).

Con pochi elementi, con un po' di pazienza, sarebbe possibile costruire tutte le possibili disposizioni e poi eliminare quelle che producono combinazioni equivalenti. Tale procedura finirebbe tuttavia per diventare troppo laboriosa con un numero di elementi appena un po' numeroso. Occorre perciò cercare altre vie per ottenere il risultato.

Osserviamo, intanto che le combinazioni semplici di n elementi di classe k sono sempre in corrispondenza biunivoca con le permutazioni di due elementi, il primo ripetuto k volte e il secondo ripetuto (n-k) volte; si ha infatti,

rispettivamente:

Basta infatti moltiplicare i due termini della prima frazione per (n-k)! e si ottiene immediatamente la seconda formula.

Dimostriamo ora che la corrispondenza tra combinazioni e permutazioni di due elementi, il primo ripetuto k volte ed il secondo (n-k) volte, vale anche per il caso delle combinazioni con ripetizione.

Usiamo un modello frequente in combinatoria: quello delle biglie e delle scatole. Una combinazione è indicata da un numero n di scatole, contraddistinte ciascuna da una lettera. Si prendono k biglie e si dispongono nelle n scatole; trattandosi di combinazioni con ripetizione, una scatola potrà contenere da 0 a k biglie. La biglia indicherà quale scatola sarà considerata di volta in volta. Vediamo alcuni esempi nello schema qui a lato.

Consideriamo la situazione appena descritta da un altro punto di vista. Togliendo la cornice esterna e le pareti divisorie orizzontali dallo schema precedente, rimane una successione di biglie e di pareti divisorie verticali che dividevano una scatola dall'altra. Nello schema a lato, su ogni riga, sono presenti tre biglie e tre pareti divisorie. Le varie combinazioni si ottengono permutando in vari modi le tre biglie e le tre pareti divisorie (barrette).

Ciò corrisponde a trovare tutti gli anagrammi della parola AAABBB, in cui la A rappresenta le biglie e la B le barrette.

Non è difficile allora vedere la corrispondenza tra le combinazioni con ripetizione di tre lettere, prese da un alfabeto di 4 lettere, e le permutazioni di 6 elementi (biglie + barrette), il primo (biglie) ripetuto 3 volte e il secondo (barrette) ripetuto (4-1) volte. Generalizzando, se si hanno n scatole e k biglie, le combinazioni con ripetizione di n elementi di classe k, corrisponderanno alle permutazioni di due elementi il primo ripetuto k volte ed il secondo (n-1) volte. Avremo la seguente formula:

Tale formula, che fornisce il numero di combinazioni con ripetizione di n elementi di classe k, può essere scritta in altro modo, dividendo i due termini della frazione per (n-1)! :

Si calcola cioè il fattoriale crescente di k fattori a partire da n e si divide per k! . Tale formula, applicata al caso delle 4 scatole e 3 biglie, darà:

10 Dalla Combinatoria al triangolo di Pascal.

Consideriamo ancora il modello delle biglie e delle scatole per proporre un problema di tipo combinatorio. Supponiamo di avere 5 scatole e 5 biglie.

Vogliamo collocare qualcuna delle biglie nelle scatole, in modo che una scatola contenga al più una biglia. Indichiamo con A le scatole che contengono biglie e con B quelle che non ne contengono. Le 5 scatole diventano così una parola di 5 lettere prese dall'alfabeto {A, B}.

Il problema di trovare in quanti modi le biglie possono essere collocate nelle scatole, diventa così quello di trovare quanti anagrammi ci sono. Nell'esempio precedente, la parola è ABAAB. I quanti modi si possono collocare 3 biglie in 5 scatole? Il calcolo è indicato nella formula a lato. Abbiamo già visto al §8 che vi è una corrispondenza biunivoca tra permutazioni di due elementi il primo ripetuto k volte e il secondo (n-k) volte e combinazioni di n elementi di classe k o (n-k).

N.

biglie

Parola da permutare

N. di permutazioni

0 BBBBB 1

1 ABBBB 5

2 AABBB 10

3 AAABB 10

4 AAAAB 5

5 AAAAA 1

Tenendo presente tale corrispondenza, proviamo a calcolare in quanti modi si possono collocare le biglie nelle 5 scatole, variando di volta in volta il numero delle biglie:

E' facile riscontrare che il numero delle permutazioni calcolato nella tabella è esattamente uguale a quello delle combinazioni di n elementi di classe k, con n = 5 e k che varia da 0 a 5.

Il numero delle permutazioni coincide con quello delle disposizioni con ripetizione di 2 elementi di classe n (le lettere A e B prese, con ripetizione, n la volta), che sono 2ⁿ.

Una situazione molto simile a quella appena esaminata si presenta nello schema qui a lato. In esso si parte dal punto A e, seguendo le linee della griglia, s'arriva al punto B. Il percorso minimo è quello costituito da 5 passi verso destra e 3 verso l'alto, in qualunque ordine siano compiuti. Si possono scegliere perciò tanti percorsi diversi, quanti sono tutti gli anagrammi della parola DDDDDAAA, che sono 56.

L'esempio di percorso qui a lato corrisponde alla parola DDADDAAD.

Vogliamo generalizzare un po' il problema, realizzando un reticolo a maglie quadrate (reticolo di Polya).Su tale reticolo si calcolano i numeri dei percorsi minimi per andare dal punto (0,0) fino ad un punto (x, y). Per andare dal punto (0,0) al punto (0,0) c'è un solo modo: restarci! Il numero di percorsi per raggiungere gli altri punti del reticolo sono indicati in corrispondenza degli stessi. Ciascun numero può essere calcolato in base al numero di permutazioni delle parole formate dalle lettere D (destra) e dalle lettere A (alto), che indicano il percorso minimo per andare da (0,0) al punto indicato nello schema. Si può anche calcolare il numero di combinazioni di (x+y) elementi di classe x, o (x+y) elementi di classe y. Nello schema si vede che i valori simmetrici rispetto alla diagonale sono uguali. Pertanto il numero di percorsi per andare ad un punto (x, y) o ad un punto (y, x) è lo stesso.

Si dimostra così l'uguaglianza indicata nelle formule qui a lato. Tale uguaglianza, oltre che giustificare la simmetria tra i percorsi posti nello schema precedente, è utile per eseguire il calcolo delle combinazioni per la via più breve. E' preferibile calcolare le combinazioni di 8 elementi di classe 3, piuttosto che quelle di 8 elementi di classe 5, le quali richiedono fattoriali più grandi. Lo schema precedente è utile per fare un'altra considerazione.

Prendiamo tre caselle contigue, contrassegnandole con le lettere A, B, C, e scriviamo le rispettive coordinate. Quanti percorsi vi sono per raggiungere una delle tre posizioni indicate con A, B e C? Osservando attentamente lo schema, è facile arrivare alla seguente conclusione che, per andare in C, occorre passare necessariamente per A o per B. Di conseguenza, il numero di percorsi per arrivare a C sarà uguale alla somma di quelli per andare ad A e di quelli per andare a B. Si ha cioè:

Questa formula permette di calcolare in modo ricorsivo i numeri nello schema. Basta sommare i valori posti a sinistra e al di sotto del numero da calcolare. Proviamo ora a compiere una rotazione dello schema (eliminando il reticolo e lasciando solo i numeri).

Ci apparirà il ben noto triangolo di Pascal.

Il triangolo presenta talune caratteristiche molto interessanti. I suoi valori, come abbiamo visto, si possono ottenere per via ricorsiva, sommando i due termini posti immediatamente al di sopra del numero da calcolare (proprietà di Stifel). I valori, in ogni caso, si possono calcolare direttamente, per mezzo delle combinazioni di n elementi di classe k. Basta porre n = numero di riga, e k = numero d'ordine di ciascun elemento di una riga a partire da 0.

Il triangolo di Pascal (noto in Italia come triangolo di Tartaglia) è usato, fra l'altro, per calcolare i coefficienti della potenza del binomio (a + b)ⁿ.

Per tale ragione, il simbolo delle combinazioni viene anche denominato coefficiente binomiale

Fra le innumerevoli proprietà del triangolo di Pascal, alcune sono molto utili per comprendere molte delle proprietà del calcolo combinatorio:

• I due termini estremi di ogni riga hanno valore 1, poiché corrispondono rispettivamente ai due coefficienti binomiali:

• I termini simmetrici di una riga sono uguali, per la proprietà già vista nel precedente reticolo di Polya.

• A partire dalla seconda riga, un qualsiasi termine è dato dalla somma dei due termini posti immediatamente al di sopra di esso, in base alla proprietà di Stiefel.

• La somma dei valori di una riga ennesima è sempre uguale a 2ⁿ, per la ragione già vista in precedenza.

10 - L'insieme delle parti di un n-insieme.

Dato un insieme A costituito da un numero finito n di elementi, si può costruire un insieme PA, costituito da tutti i sottoinsiemi di A, detto insieme delle parti di A.

Ad esempio, dato un insieme A = {a, b, c, d, e}, esistono:

1 sottoinsieme vuoto{}

5 sottoinsiemi con 1 elemento: {a},{b},{c},{d},{e}

10 sottoinsiemi con 2 elementi: {a,b},{a,c},{a,d},{a,e},{b,c},{b,d},{b,e},{c,d},{c,e},{d,e}

10 sottoinsiemi con 3 elementi:{c,d,e},{b,d,e},{b,c,e},{b,c,d},{a,d,e},{a,c,e},{a,c,d},{a,b,e},{a,b,d},{a,b,c}

5 sottoinsiemi con 4 elementi:{b,c,d,e},{a,c,d,e},{a,b,d,e},{a,b,c,e},{a,b,c,d}

1 sottoinsieme con 5 elementi:{a,b,c,d,e}

Come si vede, il numero di sottoinsiemi di k elementi ciascuno, presi da un insieme di n elementi è dato dalle combinazioni di n elementi di classe k.

Il totale di tutti i sottoinsiemi è sempre 2ⁿ, per la ragione vista al paragrafo precedente.

Nel nostro caso l'insieme della parti è costituito da 2⁵ = 32 sottoinsiemi; infatti: 1+5+10+10+5+1 = 32.

11 - Il Quincunx di Galton.

Lo schema del reticolo con il numero di percorsi che portano dal punto iniziale (0,0) ad un punto di coordinate (x, y) può dar luogo alla costruzione di un piano inclinato con ostacoli, detto Quincunx di Galton.

Una pallina, lasciata cadere dal punto più alto, è costretta dagli ostacoli incontrati lungo il percorso a deviare in modo casuale a destra o a sinistra.

Si può calcolare il numero di percorsi che conducono a ciascun passaggio attraversato dalla pallina. Esso è dato dal numero di combinazioni di n elementi di classe k (n = riga e k = colonna). E' anche possibile fare il calcolo usando i numeri del triangolo di Pascal.

In particolare, i percorsi che conducono nelle caselle indicate con le lettere A, B, C, D, E, F, G, sono rispettivamente 1, 6, 15, 20, 15, 6, 1, per un totale di 2⁶

= 64. Come si vede, il numero di percorsi che conducono al punto D è maggiore di quello dei percorsi che conducono alle altre caselle. E' lecito dunque attendersi che una pallina, finirà per cadere più spesso in D che in altre caselle. In effetti, il calcolo delle probabilità ci assicura che una pallina ha una probabilità di finire in una casella pari al rapporto tra il numero di casi favorevoli e il numero totale di percorsi. Nel nostro caso, la probabilità di finire in D è 20/64 ed è maggiore rispetto a quella di finire nelle altre.

Si può calcolare la probabilità che la pallina finisca in un'altra casella, rapportando il numero di percorsi che conducono ad essa con il loro numero totale.

Realizzando materialmente un quincunx di Galton e lanciando un gran numero di palline, si potranno determinare le frequenze relative cioè i rapporti tra il numero di esiti favorevoli (costituiti dall'arrivo della biglia in una delle caselle terminali) e il numero di prove fatte. Raffrontando i valori ottenuti con le rispettive probabilità, si potrà verificare che, per un numero sufficientemente elevato di prove, i due valori saranno molto vicini, così come previsto dalla legge empirica del caso, nota come legge dei grandi numeri.

Il modello descritto permette di concludere il nostro itinerario attraverso la combinatoria, che costituisce una naturale premessa al calcolo delle probabilità, così come storicamente è avvenuto. Certamente il calcolo delle probabilità e la statistica, hanno acquisito col tempo una sempre maggiore autonomia dal calcolo combinatorio ed hanno stabilito legami con altre parti della matematica. Il calcolo combinatorio rimane tuttavia, un utile approccio alla probabilità, almeno a livello didattico.

TABELLA RIEPILOGATIVA

Permutazioni semplici di n elementi: n! = n(n-1)(n-2)(n-3)· ... · 3·2·1 Disposizioni semplici di n elementi di classe k (n)n = n(n-1)(n-2) ...(n-k+1) Combinazioni semplici di n elementi di classe k

Disposizioni con ripetizione di n elementi di classe k n^k Permutazione di n elementi, con ripetizione assegnata k1, k2,..., kn

volte.

(n = k1 + k2 + ... + kn)

Combinazioni con ripetizione di n elementi di classe k

PROBLEMI

1. Quanti sono gli anagrammi (anche privi di senso) delle parole CAMPO, RAPIDO, SCHERMO?

2. In quanti modi si possono schierare in campo (senza distinzione di ruoli):

a. 5 giocatori di una squadra di Hockey b. 6 giocatori di una squadra di pallavolo c. 11 giocatori di una quadra di calcio d. 15 giocatori di una squadra di rugby

3. Calcola, approssimativamente, in quanti modi si possono sistemare nei banchi i 25 alunni di una classe.

4. Nella classe precedente si vogliono eleggere un capoclasse ed un vice capoclasse. Quante diverse coppie potrebbero essere costituite?

5. Quante bandierine tricolori si possono disegnare con una tavolozza di 6 colori?

6. In quanti modi un postino frettoloso può disporre a caso 5 lettere mettendole ciascuna in una buca differente, scelta fra le 12 di un casellario?

7. Trovare tutte le possibili parole che un bimbo di un anno può scrivere mettendo in fila 4 letterine prese da una scatola che ne contiene 12, l'una diversa dall'altra.

8. Quante tinte diverse si possono ottenere, mescolando 3 dosi della stessa quantità e di 3 colori diversi, scelte fra 7 vernici diverse?

9. Quante cinquine diverse si possono giocare al lotto?

10. Quante formazioni diverse (a prescindere dal ruolo) potrebbe schierare in campo l'allenatore della Nazionale, se ha convocato 20 giocatori?

11. Quanti sono i sottoinsiemi di 5 elementi in un insieme di 8 elementi?

12. In quanti modi si possono collegare mediante rette i 7 punti di un piano (a tre a tre non allineati)?

13. Quanti, fra lati e diagonali, sono i segmenti che collegano i vertici di un ottagono?

14. In un cavo a 10 fili, un telefono è collegato ad una coppia di fili. Quanti tentativi al massimo si dovranno fare per collegare un secondo telefono dall'altra parte del cavo, se non si conosce il colore dei fili ai quali è collegato il primo?

15. Quante diverse colonne si possono fare al totocalcio?

16. Quanti numeri di 4 cifre (contando anche gli zeri non significativi) di possono scrivere nel sistema di numerazione a base 8?

17. Un byte a 8 bit è una parola di 8 lettere, scritta con l'alfabeto {0,1}. Quanti diversi byte si possono comporre?

18. Quanti sono i diversi esiti nel lancio di 3 dadi?

19. In un reticolo di Polya (vedi § 9), quanti diversi percorsi si possono fare per andare dal punto (0,0) al punto (5,3)?

20. Quanti sono gli anagrammi della parola MATEMATICA?

21. Quanti sono gli anagrammi della parola COMBINATORIA?

22. Quanti sono i diversi esiti nel lancio di 4 monete?

23. In una fabbrica di vernici una macchina mescola 4 dosi di vernice, usando anche più dosi di uno stesso colore.

Con 4 colori base, quante diverse tinte si possono realizzare?

24. Un barman dispone di 6 liquori diversi. Per inventare un nuovo cocktail decide di lanciare 3 dadi, assegnando a ciascun liquore una delle 6 facce. Quanti diversi cocktail potrebbe inventare con tale sistema?

25. In una mensa aziendale ciascun dipendente può prelevare fino a tre frutti (uguali o diversi, non importa), scegliendoli fra cassette contenenti 5 tipi diversi di frutta. Quante diverse razioni di frutta di possono realizzare, se nessuno rinuncia ai tre frutti ai quali ha diritto? E se invece si considera la possibilità di rinunciare in tutto o in parte?

26. Un distributore automatico di palline di chewing-gum dà due palline colorate da masticare con una moneta.

Essendoci 6 colori diversi nel contenitore, quante diverse coppie di palline si potranno avere?

27. Una slot-machine è formata da tre ruote affiancate, ciascuna delle quali ha 10 simboli diversi lungo il bordo.

Attraverso una finestrella si vedono affiancati i tre simboli presentati dalle rispettive ruote. In quanti modi si possono presentare i tre simboli, non contando l'ordine con cui compaiono? E tenendo conto anche dell'ordine?

28. In un'azienda il titolare dopo aver subito piccoli furti, dei quale sospetta qualcuno fra i dipendenti, ha fatto installare un segnale acustico al cancello di uscita. Ogni giorno, mentre i 15 dipendenti attraversano il cancello di uscita, il segnale indica a caso uno fra i dipendenti, da sottoporre a perquisizione. Quante diverse

combinazioni si possono avere in una settimana lavorativa di 6 giorni, nella scelta dei dipendenti da sottoporre a perquisizione?

29. In una pretura, se l'imputato non ha incaricato un proprio avvocato di fiducia, il giudice gli assegna un avvocato d'ufficio, scegliendolo a caso da un'urna contenente i 15 nomi degli avvocati del foro. Tale operazione si verifica in media 3 volte al giorno ed ogni volta il nome estratto viene reimbussolato. Quante diverse terne di avvocati potrebbero essere scelte in un giorno?

30. Per avere tutti i 216 esiti diversi nel lancio di tre dadi (vedi problema n. 18), occorre usare tre dadi di colore differente, in modo da distinguere anche l'ordine con cui escono i tre numeri. Se si usano invece dadi dello stesso colore, non potendo più distinguere l'ordine, quante diverse uscite si potranno avere?

RISPOSTE AI PROBLEMI

1) [120] [720] [5040] 7) [11.880] 13) [28] 19) [56] 25) [35] [56]

2) [120] [720] [39.916.800]

[1.307.674.368.000] 8) [35] 14) [45] 20) [151.200] 26) [21]

3) [≈1,55 . 10²⁵ ] 9)

[43.949.268]

15) [1.594.323]

21)

[59.875.200]

27) [220]

[1.000]

4) [600] 10) [167.960] 16) [4.096] 22) [16] 28) [38.760]

5) [120] 11) [56] 17) [256] 23) [35] 29) [680]

6) [95.040] 12) [21] 18) [216] 24) [56] 30) [56]