Una stessa successione conta parentesi, alberi e triangolazioni

Perché un parser non può provarle tutte

Il numero di modi di parentesizzare una catena di moltiplicazioni è un numero di Catalan, e supera il miliardo prima che la catena arrivi a venti termini. La moltiplicazione fra matrici è associativa, quindi ogni parentesizzazione dà lo stesso prodotto — ma non costano tutte uguale, e la differenza fra l'ordine migliore e il peggiore può essere di ordini di grandezza di operazioni. Enumerare le possibilità per trovare la più economica è quindi senza speranza oltre una manciata di matrici, e la soluzione standard è la programmazione dinamica, che trova l'ottimo in tempo cubico senza risolvere due volte lo stesso sottoproblema. Il numero di Catalan è ciò che quell'algoritmo evita.

L'immagine delle parentesi spiega tutta la famiglia

Ognuno di questi problemi è una sequenza di passi che non deve mai diventare negativa. Leggi una parentesi aperta come più uno e una chiusa come meno uno: una stringa valida è esattamente un cammino che finisce a zero senza mai scendere sotto. Un albero binario percorso in ordine dà lo stesso cammino; anche una triangolazione, e anche una coda che non deve mai servire un cliente non ancora arrivato. Caduto il travestimento, un solo argomento di conteggio li copre tutti, e la dimostrazione standard è un trucco di riflessione che conta i cammini cattivi specchiandoli in un insieme facile da contare.

Domande frequenti

Perché la successione comincia con due uni?

Perché c'è esattamente un modo di non fare nulla ed esattamente uno di fare la cosa più piccola possibile. Con zero coppie di parentesi la stringa vuota è l'unica disposizione valida, e con una coppia c'è un solo piazzamento. Le successioni che contano disposizioni cominciano molto spesso così, e l'uno ripetuto segnala che la definizione è stata estesa con criterio al caso vuoto invece di partire arbitrariamente dal primo valore interessante. Conta anche nel calcolo: la ricorrenza ha bisogno di entrambi come base prima di poter generare qualsiasi cosa.

A che velocità crescono davvero questi numeri?

Poco meno di quattro volte per passo, e il rapporto si avvicina lentamente a quattro al crescere di n: dal diciannovesimo al ventesimo termine vale 3,714, e dal ventinovesimo al trentesimo 3,807. Ciò li colloca fra la crescita esponenziale delle potenze di due e quella assai più violenta dei fattoriali — abbastanza da battere presto la forza bruta, non abbastanza da batterla all'istante. In pratica la soglia sta attorno a venti: sotto, una ricerca esaustiva spesso basta; sopra serve qualcosa di più fine, e il punto esatto dipende da quanto costa ogni caso.