PERSONE CHE … CONTANO!

RELAZIONI RICORSIVE

Siete riusciti a risolvere il problema n.26 sulle parentesi? Piuttosto impegnativo, vero?

26. Un problema di parentesi

In quanti modi diversi è possibile associare n fattori in un dato ordine mediante l’uso di parentesi?

Indichiamo con la soluzione del problema. Abbiamo ottenuto, per via diretta, che , e . Ci siamo poi fermati davanti al caso di sei fattori, spaventati all’idea di dover elencare tutti i modi di mettere le parentesi. Proviamo a vedere se il valore di è davvero così difficile da ottenere. Per prima cosa scriviamo i sei fattori: .

La difficoltà di elencare tutti i modi di disporre le quattro coppie di parentesi non sta soltanto nel numero probabilmente elevato di casi, ma nell’individuazione di un procedimento che ci assicuri di non escludere alcun caso. A questo scopo ragioniamo come segue. Il prodotto dei sei fattori può essere ottenuto in cinque modi diversi moltiplicando:

• il primo fattore col prodotto degli ultimi cinque;
• il prodotto dei primi due col prodotto degli ultimi quattro;
• il prodotto dei primi tre col prodotto degli ultimi tre;
• il prodotto dei primi quattro col prodotto degli ultimi due;
• il prodotto dei primi cinque con l’ultimo.

Nel primo caso possiamo scrivere il prodotto nella forma

.

I modi di inserire le parentesi nel secondo fattore bcdef sono tanti quanti i modi di inserire le parentesi in cinque fattori, e cioè . Dunque, senza bisogno di scrivere le tre coppie di parentesi mancanti in tutti i modi possibili, siamo in grado, sfruttando i risultati precedenti, di dire in quanti modi ciò può essere fatto!

Nel secondo caso il prodotto si scrive nella forma

.

Il primo fattore si può scrivere in un solo modo, mentre il secondo in modi diversi! Ci sono quindi 5 modi di disporre le parentesi tra sei fattori in modo che l’ultima moltiplicazione sia fatta tra il prodotto dei primi due e quello degli ultimi quattro!

Il terzo caso conduce all’espressione

dove, in ciascuno dei due fattori, le parentesi si possono disporre in modi diversi. Per la regola del prodotto abbiamo allora modi diversi di disporre le parentesi.

Il quarto caso è rappresentato dall’espressione

ed è del tutto analogo al secondo, per un totale di modi diversi di disporre le parentesi.

Infine, il quinto caso porta all’espressione

,

che, analogamente al primo caso, conduce alla risposta .

In definitiva .

Proviamo a calcolare, con lo stesso metodo, anche . Questa volta, con 7 fattori, i casi sono 6:

, , ,

, , .

Nel caso generico, il prodotto finale si ottiene moltiplicando il prodotto dei primi k fattori col prodotto dei rimanenti :

Nei primi fattori le parentesi possono essere disposte in modi, mentre negli ultimi in modi, per un totale (regola del prodotto!) di modi.

Ne segue che

.

Nell’esempio precedente però noi non abbiamo considerato e ! Del resto, un solo fattore non richiede l’uso delle parentesi! Per esempio, nel caso , il risultato sarebbe , che equivale a porre . Come a dire che in un fattore con solo un numero c’è un solo modo di disporre le parentesi: non metterle affatto! È invece ovvio che debba essere .

Otteniamo allora

.

Verifichiamo che la formula funziona fin da .

Abbiamo che:

.

La formula generale è allora data da

che, usando il simbolo di sommatoria, assume la forma compatta:

.

Abbiamo così espresso il termine generico della successione che rappresenta la soluzione del problema mediante una relazione ricorsiva, ossia una relazione in cui la soluzione è data da un’espressione in cui compare (in questo caso più volte) la soluzione stessa, ma relativamente a casi di dimensione minore. Inoltre abbiamo esplicitato la soluzione nel caso di dimensione più piccola, quello relativo a . Come ha ampiamente spiegato il professor Apotema nei numeri 15, 17 e 19 de “Il Leonardo”, ciò è sufficiente per determinare la soluzione relativa a un qualsiasi valore di n.

Qualcuno si è accorto che il problema delle parentesi è strettamente legato al problema 25 della fila alla cassa?

Si tratta di un legame non del tutto ovvio. A prima vista si può essere portati a credere che le parentesi, che compaiono sempre a coppie, giochino il ruolo delle persone in fila alla cassa e, in particolare, che le parentesi aperte corrispondano alle persone con una banconota da 10€ e quelle chiuse alle persone con una banconota da 20€. Per esempio, nel caso dell’espressione , le parentesi si succedono nell’ordine , che ricorda la fila ddvvdv del problema 25. Ma non è questa la corrispondenza, perché uno stesso schema di parentesi corrisponde a più modi di eseguire il prodotto. Nei prodotti e , che differiscono per la sistemazione delle parentesi, lo schema di queste ultime è lo stesso: . Per scoprire se c’è davvero un legame tra i due problemi proviamo a calcolare il numero di file che non si bloccano per diversi valori del numero n di coppie di persone. Ricordiamo che questo numero è dato da

.

Abbiamo che

,

,

,

,

,

.

Confrontiamo ora, mediante una tabella, i valori di con quelli di .

Dai valori tabulati sembra valere la relazione . Qual è il misterioso legame tra i due problemi? Proviamo ad analizzare il caso con .

Abbiamo che :

ai due modi di inserire le parentesi fra tre fattori

,

corrispondono le due file di due coppie di persone che non si bloccano

ddvv , dvdv.

Il segreto sta nel considerare l’albero binario (perfettamente binario) associato a ciascun prodotto:

Immaginiamo ora, partendo dalla radice, di visitare l’albero in modo simmetrico, e cioè di scendere lungo i rami di sinistra e, arrivati a fine corsa, risalire a ritroso i rami fino al primo nodo da cui scende un ramo destro per poi tenere di nuovo sempre la sinistra, ecc.

Se indichiamo con 1 i rami sinistri e con 0 quelli destri ecco che la visita dell’albero dell’espressione produce la successione di rami 1100, mentre quella dell’albero dell’espressione fornisce la successione 1010.

Sostituendo 1 con d e 0 con v abbiamo così ottenuto le file ddvv e dvdv!

Verifichiamo la corrispondenza nel caso .

Abbiamo questa volta 5 modi di disporre le parentesi:

, , , , ,

a cui corrispondono i seguenti alberi binari e le rispettive file:

La corrispondenza è perfetta! Del resto con 4 fattori si fanno 3 prodotti e l’albero binario dell’espressione ha un ramo sinistro e uno destro per ogni prodotto, per un totale di 3 rami sinistri e 3 rami destri. Inoltre la visita dell’albero in modo simmetrico garantisce di ottenere una successione di rami ogni punto della quale non è mai preceduto da un numero di rami destri che supera quello dei rami sinistri. Viceversa, ad ogni successione di rami di questo tipo corrisponde l’albero di un’espressione.

L’aver determinato questa corrispondenza tra il problema delle parentesi e quello della fila alla cassa ci consente di determinare una formula diretta per il numero di modi di disporre le parentesi con n fattori:

.

Passiamo a un altro problema.

27. Un problema di teoria dell’informazione

Supponiamo che un messaggio venga trasmesso mediante una successione di segnali di quattro diversi tipi. Rispetto a una certa unità di tempo il primo tipo di segnale ha durata 1, il secondo ha durata 2, il terzo 5 e il quarto 10. Quanti messaggi diversi di durata 12 posso trasmettere?

Come sempre accade nei problemi combinatori, possiamo cominciare col tentare di elencare una per una le soluzioni. Anche se si tratta di un tentativo destinato quasi sempre a fallire, a causa del numero elevato di soluzioni che questo tipo di problemi ammette, resta pur sempre un lavoro utile al fine di ben comprendere il problema.

In questo caso cominciamo con lo scrivere queste soluzioni:

10,2; 10,1,1; 5,5,2; 5,5,1,1; 5,2,2,2,1; 5,2,2,1,2;

5,2,2,1,1,1; 5,2,1,2,2; 5,2,1,2,1,1; …

Dovrebbe essere chiaro l’ordine con cui abbiamo proceduto. I messaggi sono stati costruiti in ordine alfabetico, partendo dal segnale di durata maggiore e in modo da avere lunghezza 12. Ma lo scopo di questa rubrica è quello di fornire degli strumenti concettuali per affrontare problemi di conteggio e, in questo numero, di abituare il lettore a usare lo strumento della ricorsione. Indichiamo dunque con il numero di messaggi di lunghezza di durata n. La soluzione del problema è data allora da . Come trovare una relazione ricorsiva per la successione ? Come nel problema delle parentesi, cominciamo col distinguere alcuni casi. Ci basterà poi ricorrere alla regola della somma! Questa volta possiamo individuare 4 casi, a seconda del tipo del segnale iniziale del messaggio. Quanti sono i messaggi che iniziano col segnale di durata 10? Basta pensare che restano a disposizione solo unità di tempo e la risposta è allora ! Con un ragionamento analogo si trova che i messaggi che iniziano con un segnale di durata 5, 2 e 1 sono rispettivamente in numero di , e . Per la regola (d’oro!) della somma possiamo allora scrivere la relazione ricorsiva:

.

Passiamo dunque al calcolo di .

,

dove

,

,

,

.

E quanto vale ? Vale semplicemente 1, in quanto c’è un unico modo di formare un messaggio di durata zero: non inviare alcun segnale! Quale valore dobbiamo poi attribuire alla funzione M quando l’argomento è negativo? Ovviamente zero, perché non esistono messaggi di durata negativa!

Ritorniamo al calcolo di ma, per non ripetere inutilmente più volte gli stessi calcoli, cominciamo da .

La soluzione è dunque 377.

A questo punto vediamo di tirare le somme. Alcuni problemi combinatori possono essere risolti determinando una relazione ricorsiva. In particolare abbiamo visto un paio di esempi in cui la soluzione è esprimibile mediante una funzione, dove il numero n rappresenta la dimensione del problema. Si tratta allora di determinare una relazione ricorsiva per la funzione F. A questo scopo si cerca di suddividere il conteggio in casi in ciascuno dei quali si ripresenta, con una dimensione minore, il problema di partenza. La relazione ricorsiva si ottiene allora semplicemente usando la regola della somma! Questa relazione riconduce il calcolo della funzione relativo all’argomento n al calcolo della funzione stessa per argomenti minori. Ma non si può rimandare il calcolo all’infinito, ed ecco che occorre individuare la base della ricorsione, cioè dei valori dell’argomento per i quali il valore della funzione (la soluzione del problema) viene determinato in modo diretto.

Per la prossima volta (n.28 de “Il Leonardo”) provate a generalizzare la soluzione del problema 27 al caso di messaggi composti da k tipi diversi di segnali di durata , , … , in modo da ottenere un messaggio di durata esattamente . Ovviamente si chiede di determinare una relazione ricorsiva per la funzione che esprime il numero di messaggi diversi di durata T e di esplicitare con chiarezza la base della ricorsione. Buon divertimento! G.G.