I numeri di Catalan — 1. Permutazioni e anagrammi

“Ho scoperto un metodo per ricordarmi una delle tante formule per il calcolo dei numeri di Catalan”.

“Ah, tu pensa che io non so nemmeno cosa siano, questi numeri”.

“Eh, ci sono tanti modi per definirli, tutti equivalenti. Ma forse è meglio prima parlare di anagrammi”.

“Eh?”.

“Sì, mescolamenti di lettere, prendi una parola e riordini le lettere in modo da ottenerne un'altra”.

“E cosa c'entra la matematica?”.

“In matematica si contano i modi che si hanno per mescolare le lettere, in modo da ottenere nuove parole”.

“Ah, ma queste parole devono avere significato?”.

“No, vogliamo contare i modi di mescolare le lettere in una parola, senza tener conto del significato delle nuove parole ottenute. In termini matematici, si dice che stiamo contando le permutazioni di n oggetti”.

“E come si fa questo calcolo?”.

“Ti faccio un esempio, supponi che la parola sia UNO”.

“Ok”.

“Per creare tutte le nuove parole, immagina di avere tre caselle vuote da riempire”.

“Va bene”.

“In quanti modi puoi riempire la prima casella?”.

“Direi tre, no? Ci posso mettere la U, oppure la N, oppure ancora la O”.

“Esatto. Ora, in quanti modi puoi riempire la seconda casella?”.

“Ancora tre, come prima”.

“Eh, no”.

“Perché?”.

“Perché una lettera è già stata usata per la prima casella”.

“Ah! Certo! Mi rimangono due lettere, posso riempire la seconda casella solo in due modi”.

“Molto bene. Quindi finora quanti anagrammi parziali hai fatto?”.

“Uhm, per ogni scelta della prima casella ne ho due per la seconda, quindi tre per due? Sei modi?”.

“Certo, non è nemmeno difficile scriverli tutti:”.

UN_
UO_
NU_
NO_
OU_
ON_

“Ah, vero. E vedo che mi rimane una sola possibilità per la terza casella, la lettera che non ho ancora scelto”.

“Esattamente, ecco i sei anagrammi:”.

UNO
UON
NUO
NOU
OUN
ONU

“Bene, ho capito”.

“Sapresti rifare il calcolo con quattro lettere?”.

“Direi di sì: 4 modi per la prima casella, 3 per la seconda, 2 per la terza, e 1 per l'ultima. Totale: 24”.

“Mi interessa di più la formula del risultato”.

“Ah. Allora la formula è questa: 4×3×2×1”.

“Ottimo. Con n elementi come diventa?”.

“Diventa una schifezza del genere: n × (n − 1) × (n − 2) × … × 2 × 1”.

“Dato che è una schifezza, come dici tu, i Veri Matematici hanno inventato un simbolo apposta per questo tipo di moltiplicazione: si chiama fattoriale e si indica con il punto esclamativo:”.

n! = n × (n − 1) × (n − 2) × … × 2 × 1

“Mh, mi pare di ricordare qualcosa dai tempi della scuola”.

“Eh, già. Ora, quanti sono gli anagrammi della parola MAMMA?”.

“Sono cinque lettere, quindi cinque fattoriale, aspetta che faccio il calcolo”.

“No, non è il risultato corretto”.

“Eh? Perché”.

“Ti rispondo con una domanda: quanti sono gli anagrammi della parola MMM?”.

“Non sono sei?”.

“Prova a scriverli”.

“Uhm, eh, no, non sono sei, non si possono mescolare tre lettere uguali”.

“Quindi?”.

“Quindi c'è un solo anagramma. Però con la parola MAMMA non so mica come fare”.

“Immagina per un momento che le lettere siano tutte diverse”.

“Ma non lo sono, come faccio? Cambio parola?”.

“In un certo senso, sì, fai così: considera la parola M₁A₁M₂M₃A₂”.

“Gulp”.

“Ho solo numerato le lettere in modo da renderle distinguibili una dall'altra. Se non ti piacciono gli indici, puoi immaginare che le lettere abbiano colori diversi”.

“Ah, no, va bene anche così”.

“Ora, quanti anagrammi puoi fare con questa nuova parola?”.

“Dato che le lettere sono tutte diverse, sono cinque fattoriale, no?”.

“Esatto, 5!, che fa 120”.

“Però ci sono parole che sono uguali, se cancelliamo gli indici”.

“Per esempio?”.

“Beh, per esempio M₁A₁M₂M₃A₂ e M₂A₁M₁M₃A₂”.

“Bene. Proviamo a fare un po' di calcoli: quante parole diventano uguali se cancelliamo solo gli indici delle lettere M?”.

“Ci sono 3 lettere M, e se cancello, uhm…  non so”.

“Ti giro la domanda: quante parole diverse puoi fare mescolando soltanto le lettere M?”.

“Ce ne sono tre, se mescolo solo loro… ah, certo, 3!, cioè 6, come abbiamo visto prima”.

“Perfetto. E quante, invece, se mescoli soltanto le due lettere A?”.

“Beh, 2!, cioè 2”.

“Giusto. Quindi, tra tutti i 120 possibili modi che hai di mescolare quelle lettere, otterrai gruppi di parole che diventano uguali quando cancelli gli indici. In particolare, quando cancelli gli indici della M, avrai dei gruppi formati da 6 parole che diventano tutte uguali. Quando cancelli gli indici della A, avrai dei gruppi da 2”.

“Sì, quindi? Devo contare i gruppi?”.

“Proprio così”.

“Ancora non so come fare”.

“Ragiona al contrario: una singola parola, come per esempio MAMMA, crea un gruppo formato da molte parole, quando aggiungi gli indici”.

“Eh, ma quante?”.

“Tieni fisse le lettere, muovi soltanto gli indici”.

“Ah, ho 6 modi per muovere gli indici della M e 2 per quelli della A. Ho capito! Ho 6×2 parole uguali nel gruppo”.

“Proprio così: per convincerti, te le scrivo tutte:”.

M₁A₁M₂M₃A₂
M₁A₂M₂M₃A₁
M₁A₁M₃M₂A₂
M₁A₂M₃M₂A₁
M₂A₁M₁M₃A₂
M₂A₂M₁M₃A₁
M₂A₁M₃M₁A₂
M₂A₂M₃M₁A₁
M₃A₁M₁M₂A₂
M₃A₂M₁M₂A₁
M₃A₁M₂M₁A₂
M₃A₂M₂M₁A₁

“Ok, devo raggruppare le 120 parole in gruppi da 12, quindi ottengo 120/12, cioè 10 anagrammi diversi”.

“Giusto, eccoli qua:”.

MMMAA
MMAMA
MMAAM
MAMMA
MAMAM
MAAMM
AMMMA
AMMAM
AMAMM
AAMMM

“Va bene, ho capito”.

“In generale, la formula è quindi questa: conti tutte le lettere e ne calcoli il fattoriale, poi conti la numerosità dei gruppi di lettere che si ripetono, e dividi il risultato che hai ottenuto prima per il fattoriale di ognuna di queste numerosità”.

“Mh, sì, credo di aver capito”.

“Niente di meglio che fare un esempio: quanti sono gli anagrammi della parola MATEMATICA?”.

“Allora, ci sono 10 lettere, quindi 10!, però ci sono 2 lettere M, quindi devo dividere per 2!, ci sono 3 lettere A, quindi devo dividere per 3!, poi ci sono anche 2 lettere T, quindi divido ancora per 2!. Il calcolo è quindi 10!/(2! × 3! × 2!)”.

“Che fa 151200. Bene, quindi hai capito la regola per gli anagrammi. Ora, un problema. Data una griglia 5 × 5, quanti sono i percorsi minimi che puoi fare partendo dall'angolo in basso a sinistra e arrivando all'angolo in alto a destra?”.

“Eeeh?”.

“Una cosa del genere:”.

“Boh? Non ne ho idea”.

“Hai capito cosa significa percorsi minimi?”.

“Veramente no”.

“Sono i percorsi più corti possibile”.

“Ah. Quindi non posso tornare indietro, posso solo andare a destra o in alto”.

“Molto bene! Quanti passi in alto?”.

“Ah, al massimo 5”.

“No, non al massimo”.

“Oh, certo, esattamente cinque, vero. Devo andare verso l'alto cinque volte se voglio arrivare nella riga più in alto. So anche cosa stai per chiedermi: quanti passi verso destra? Anche quelli sono esattamente 5”.

“Perfetto. Il percorso nella figura là in alto, quindi, può essere riassunto da dieci istruzioni: vai a destra, vai in alto, vai in alto, vai in alto, vai a destra, vai a destra, vai in alto, vai a destra, vai a destra, vai in alto”.

“Sì, molto noioso, ma è giusto.”.

“Ti abbrevio le istruzioni in questo modo: DAAADDADDA”.

“Ahh, ma quindi un percorso è una parola, e contare tutti i percorsi significa contare tutte le parole di quel tipo!”.

“Proprio così. Quindi quanti sono questi percorsi?”.

“Una parola da 10 lettere, con 5 A e 5 D, quindi 10! / (5! × 5!), fa 252”.

“Perfetto. Ultima domanda: com'è la formula per una scacchiera n × n?”.

“Vediamo: ci sono 2n lettere, e due gruppi da n elementi ciascuno, quindi (2n)! / (n! × n!)”.

“Benissimo. Per motivi che ora non ti dirò, perché aprono un altro mondo, quel numero si indica anche in questo modo:”.

“Ah”.

“Per quanto riguarda i calcoli, basta usare il tastino nCr della calcolatrice”.

“Bene, buono a sapersi. Quindi questi sono i numeri di Catalan?”.

“No, ancora no, questo è un argomento propedeutico”.

“Gulp”.