NUMERI DI CATALAN

di Camillo Grandi

 

CatalanSono i numeri studiati dal matematico francese Eugène Charles Catalan (1814 – 1894). Grande esperto in teoria dei numeri  e in teoria combinatoria studiò a Parigi, all’École Polytechnique, ma non ebbe vita facile per le sue idee politiche, repubblicane e di sinistra. Nel 1833 venne espulso per la sua attività politica, subendo la stessa sorte toccata ad Evariste Galois che, l’anno precedente in circostanze mai chiarite, era stato assassinato.
Solo l’intervento di Joseph Liouville, il matematico che per primo ebbe il coraggio di pubblicare alcuni lavori di Galois, Catala venne riammesso all’École Polytechnique dove ottenne un incarico di assistente, anche se le sue idee politiche gli impedivano ogni possibilità di carriera. Nel 1865 decise di trasferirsi in Belgio, accettando la cattedra di Analisi all’università di Liegi e rimase in questa città fino alla sua morte nel 1894.
Catalan dedicò una particolare attenzione alle frazioni continue, frazioni che sono la somma di un numero e di una frazione, il cui denominatore è la somma di un numero e di una frazione  che a sua volta è la somma di un numero e di una frazione e così via, con un numero di termini che può essere finito o infinito. Se indichiamo i numeri con a, b, c, d, e r, lo schema sarà il seguente:

Catalan

Se r è un numero razionale, il numero dei termini è finito.
Catalan è anche il padre di una interessante successione di numeri, battezzati in suo onore Numeri di Catalan, da lui scoperti analizzando un semplice problema geometrico.

Sono i numeri di cui vogliamo occuparci in questa occasione. Il problema analizzato da Catalan è il seguente:  calcolare il numero delle possibili scomposizioni di un poligono in triangoli, tramite diagonali che però non devono intersecarsi.
Vediamo dapprima graficamente alcuni di questi numeri: un quadrato, ad esempio, può essere scomposto in triangoli, secondo la regola data, in 2 modi diversi, un pentagono in 5 modi diversi e un esagono ha già 14 diverse scomposizioni.

Quadrato, 2 soluzioni:

Catalan

Pentagono, 5 soluzioni:

Catalan

Esagono, 14 soluzioni:

Catalan

Eptagono, 42 soluzioni:

Catalan

Ottagono, ...132 soluzioni

I primi termini di questa successione sono:

1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

Sarebbe naturalmente molto complicato rappresentare graficamente tutte le scomposizioni  di un poligono di dieci, venti o più lati. Per fortuna, Catalan stesso nel 1838 diede una formula per il calcolo di questi numeri; grazie a questa formula, con l’uso di una semplice calcolatrice, si tratta di un calcolo veloce, senza difficoltà:

Catalan

Ad esempio, per n = 6 abbiamo il quinto numero di Catalan:

C5=Catalan

E’ sorprendente il numero di situazioni nelle quali compaiono i numeri di Catalan. Vediamo alcuni esempi.

Calcoliamo i possibili percorsi su una griglia quadrettata, al variare del numero di quadretti, per andare da un estremo all’altro della diagonale principale.

I 2 percorsi su una griglia 2 x 2

Catalan

I 5 percorsi su una griglia 3 × 3

Catalan

I 14 percorsi su una griglia 4 × 4

Catalan

I 42 percorsi su una griglia 5 × 5

Catalan

Li ritroviamo ancora nel numero dei nodi di un diagramma ad albero.

3 nodi

Catalan

4 nodi

Catalan

5 nodi

Catalan

6 nodi

Catalan

Anche il numero delle parentesi da collocare in un insieme di numeri che devono essere moltiplicati fra loro, due per volta, ci riporta ai numeri di Catalan. Ad esempio, dati 5 numeri a, b, c, d, ed  e, le parentesi possono essere collocate in 14 modi diversi. Si tenga presente che abbiamo indicato le parentesi a livelli diversi, sempre con parentesi tonde, come si usa oggi, specialmente con il calcolatore, senza più introdurre altri tipi di parentesi, ad esempio quadre o graffe.

(a (b (c (d e))))   (a (b ((c d) e)))
(a ((b c) (d e)))   (a ((b (c d)) e))
(a (((b c) d) e))   ((a b) (c (d e)))
((a b) ((c d) e))   ((a (b c)) (d e))
((a (b (c d))) e)   ((a ((b c) d)) e)
(((a b) c) (d e))   (((a b) (c d)) e)
(((a (b c)) d) e)   ((((a b) c) d) e)

I 14 modi possibili di collocazione delle parentesi con 5 numeri, a, b, c, d, e.

Ma sono infinite le situazioni in cui compaiono i numeri di Catalan. Ad esempio, il modo in cui 2n persone, sedute attorno a un tavolo, possono  stringersi la mano in n coppie, senza incrociare le braccia.
E’ sorprendente come un semplice problema all’apparenza banale, qual è in questo caso, quello analizzato da Catalan, delle possibili scomposizioni di poligoni in triangoli, porti a innumerevoli applicazioni in campi all’apparenza lontani fra loro. Ma è proprio questa la sorpresa che riserva la matematica: stupire e affascinare chi si avvicina, anche da dilettante,  ai suoi segreti.

MihăilescuPreda Mihăilescu è un matematico rumeno nato a Bucarest nel 1955. Nel 1973 lasciò la Romania e si trasferì a Zurigo dove studiò Matematica e Inform.atica. Attualmente insegna all’Università di Göttingen.
E’ noto per aver dimostrato, nel 2002 la congettura di Catalan.

Catalan, in una lettera all’editore della prestigiosa rivista matematica Crelle, nel 1844, scriveva:
Je vous prie, Monsieur, de vouloir bien énoncer, dans votre recueil, le théorème suivant, que je crois vrai, bien que je n'aie pas encore réussi à le démontrer complètement: d'autres seront peut-être plus heureux:
Deux nombres entiers consécutifs, autres que 8 et 9 ne peuvent être des puissances exactes; autrement dit: l'équation

xp - yq = 1

dans laquelle les inconnues sont entières et positives, n'admèt qu'une seule solution.

Vediamo il problema.
Consideriamo la successione dei quadrati e dei cubi dei numeri interi maggiori di 1. Una successione che inizia con 4, 8, 9, 16, 25, 27, 36. Il cubo di due, 8, e il quadrato di tre, 9, fanno parte di questa successione e sono anche numeri consecutivi. Catalan, nella lettera che abbiamo appena ripreso affermava che questa coppia di numeri, 8 e 9, era l’unica coppia di numeri interi consecutivi della successione, “anche se non sono ancora riuscito a dimostrarlo”.
L’equazione xp - yq = 1 ammette un’unica soluzione: 32 – 23 = 1.
Ma questa per Catalan era soltanto una congettura e la dimostrazione è arrivata soltanto nel 2002, per merito di Preda Mihăilescu.

 

Per saperne di più

La biografia di Catalan:
http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Catalan.html

I numeri di Catalan:
http://www-groups.dcs.st-and.ac.uk/~history/Miscellaneous/CatalanNumbers/catalan.html

Maggiori informazioni sulla congettura di Catalan:
http://mathworld.wolfram.com/CatalansConjecture.html

L’home page di Preda Mihăilescu:
http://www-math.uni-paderborn.de/~preda/