Don't take life too seriously: it's just a temporary situation

Indice

  1. 1. Pagina principale
  2. 2. Applicazioni in matematica combinatoria
  3. 3. Formule
  4. 4. Valori

I numeri di Catalan compaiono in numerosi problemi di matematica combinatoria: in Enumerative Combinatorics (v. la bibliografia) si trovano 66 applicazioni differenti.

 

Il numero di modi differenti nei quali si può dividere in n – 2 triangoli un poligono convesso di n lati con n – 3 diagonali che non si intersecano è Cn – 2.

La figura seguente mostra i 14 modi di dividere un esagono.

 

I 14 modi di suddividere un esagono convesso in triangoli, tramite diagonali che non si intersecano

 

Per il numero di modi di dividere un poligono in altri poligoni con numero di lati fissato si veda numeri di Catalan generalizzati.

 

Il numero di modi per dividere un poligono convesso di k lati in poligoni (inclusi punti isolati e segmenti) tramite segmenti che non si intersechino è Cn. La figura seguente illustra le 14 suddivisioni di un quadrilatero.

 

I 14 modi di suddividere un quadrilatero convesso in poligoni, tramite diagonali che non si intersecano

 

Considerando appartenenti allo stesso sottoinsieme i punti uniti da segmenti, a ognuno dei modi di tracciare segmenti corrisponde una partizione non incrociata, quindi il numero di partizioni non incrociate di un insieme di n elementi è Cn (v. numeri di Narayana).

Per esempio, vi sono 14 partizioni non incrociate di un insieme di 4 elementi { A, B, C, D }:

  • { A, B, C, D };

  • { A }, { B, C, D };

  • { B }, { A, C, D };

  • { C }, { A, B, D };

  • { D }, { A, B, C };

  • { A, B } { C, D };

  • { A, D } { B, C };

  • { A, B } { C }, { D };

  • { A, C } { B }, { D };

  • { A, D } { B }, { C };

  • { B, C } { A }, { D };

  • { B, D } { A }, { C };

  • { C, D } { A }, { B };

  • { A }, { B } { C }, { D }.

 

Il numero di modi per inserire parentesi in una somma di n addendi, in modo da sommarli a 2 a 2, senza alterare l’ordine iniziale degli addendi, è Cn – 2.

Consideriamo per esempio la somma a + b + c + d: le parentesi possono essere inserite in 5 modi:

  • (a + (b + (c + d)));

  • (a + b) + (c + d);

  • (((a + b) + c) + d);

  • (a + (b + c)) + d;

  • a + ((b + c) + d).

 

Il numero di alberi qualsiasi con n nodi (radice esclusa) è Cn; la figura mostra i 5 alberi con 3 nodi.

 

I 5 alberi con 3 nodi, oltre alla radice

 

Il numero di alberi binari con n nodi terminali è Cn – 2.

Il numero di alberi ordinati non isomorfi con n nodi terminali è Cn – 1.

 

Gli alberi binari nei quali ogni nodo è collegato a 0 o 2 nodi del livello successivo si dicono trivalenti, perché ogni nodo interno è collegato a 3 nodi. Il numero di alberi trivalenti con n nodi interni è Cn. La figura seguente mostra i 5 alberi trivalenti con 3 nodi interni.

 

I 5 alberi trivalenti con 3 nodi interni

 

 

Tracciando da sinistra a destra n tratti ascendenti uguali e altrettanti discendenti, senza mai scendere sotto il livello iniziale, si possono disegnare Cn profili di montagne diversi; la figura seguente mostra i 5 profili con 3 tratti ascendenti.

 

I 5 profili tracciabili con 3 tratti ascendenti

 

 

Il numero di modi in cui 2n persone sedute intorno a un tavolo rotondo possono scambiarsi simultaneamente n strette di mani senza incrociarsi, ovvero il numero di modi per tracciare n corde che non si intersechino tra 2n punti su una circonferenza, è Cn; la figura seguente mostra i 5 modi con 6 persone.

 

I 5 modi nei quali 6 persone possono stringersi la mano senza incrociarsi

 

 

Il numero di cammini lungo linee e colonne da un vertice a quello opposto, che non salgano mai al di sopra della diagonale di un reticolo n × n, detti “cammini di Dick”, è Cn.

La figura seguente illustra i 5 cammini in un reticolo 3 × 3.

 

I 5 cammini che non salgono al di sopra della diagonale in una griglia 3 × 3

 

 

Un problema equivalente è contare il numero di ordini diversi in cui possono essere scrutinati 2n voti in un ballottaggio tra due candidati A e B, in modo tale finiscano alla pari, ma in nessun momento dello scrutinio B sia in testa.

Come in molti problemi simili, modificando le condizioni la soluzione è data dai numeri di Motzkin, strettamente legati a quelli di Catalan. In questo caso, per esempio, se sono ammesse le schede bianche, la soluzione è il numero di Motzkin Mn, dove n è il numero di voti.

 

Conway spiega in The Book of Numbers (vedi bibliografia) come far corrispondere ogni soluzione di uno di questi problemi a ciascuna soluzione degli altri.

 

Il numero di modi per disporre i numeri naturali da 1 a 2n in una tabella 2 × n in modo che righe e colonne contengano numeri in ordine crescente è Cn. Di seguito sono mostrati i 5 modi con n = 3.

1

2

3

 

1

2

4

 

1

2

5

 

1

3

4

 

1

3

5

4

5

6

 

3

5

6

 

3

4

6

 

2

5

6

 

2

4

6

 

Il numero di modi di costruire una “scala” n × n con n rettangoli con lati interi è Cn. La figura seguente illustra i 14 modi di costruire una scala 4 × 4 con 4 rettangoli.

 

I 14 modi di costruire una scala 4 × 4 con 4 rettangoli

 

 

Il numero di permutazioni dei numeri naturali da 1 a n tali che non contengano sottosequenze di tre numeri (anche non consecutivi) in ordine ascendente è Cn. Per esempio, le 14 permutazioni del genere dei numeri naturali da 1 a 4 sono: 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312 e 4321.

 

Se non si permettono rime alternate, cioè rime tra versi separati da altri con rima differente, il numero di possibili schemi di rima per una poesia con n versi è Cn. Per esempio, con 4 versi vi sono 14 possibili schemi di rima: aaaa, aaab, aaba, aabb, aabc, abaa, abac, abba, abbb, abbc, abca, abcb, abcc, abcd.

Senza limitazioni sulle rime, il numero di schemi è l’n-esimo numero di Bell.

Bibliografia

  • Conway, John Horton;  Guy, Richard K.;  The Book of Numbers, New York, Springer-Verlag, 1996.
  • Gardner, Martin;  "Giochi matematici" in Le Scienze, Milano, n. 99, novembre 1976, pag. 112 – 119.
  • Stanley, Richard P.;  Enumerative Combinatorics, Cambridge University Press, vol. I, 1997.
  • Yaglom, A.M.;  Yaglom, I.M.;  Challenging Mathematical Problems with Elementary Solutions, New York, Dover, 1987 -

    Traduzione dal russo di Neelementarnye Zadachi v Elementarnom Izlozhenii (Problemi non elementari e soluzioni elementari), Mosca, Ist. Governativo di stampa per la letteratura tecnico-teorica, 1954. Una splendida raccolta di problemi, generalmente non facili, comparsa per la prima volta in occidente nel 1964 (S. Francisco, Holden-Day Inc., 1964).

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.