Quattro passi in su e quattro di lato senza attraversare la diagonale: 14 dei 70 percorsi

Il coefficiente binomiale centrale conta tutte le rotte; la formula di Catalan conta quelle legali.

Statistica e dati · Livello: Risultato classico · Aggiornato il 2026-11-10

Su una griglia 4 × 4, le rotte dall'angolo in basso a sinistra a quello in alto a destra che fanno solo passi in su e a destra sono 8!/(4!·4!) = 70, e il banco di lavoro lo stampa come secondo link. La maggior parte aggiunge la regola «mai andare sopra la diagonale», e allora il conteggio è 8!/(4!·5!) = 14. Le due formule differiscono di un fattore n + 1 al denominatore, che è tutta la correzione di Catalan.

I 56 percorsi illegali non sono sparsi: con l'argomento della riflessione, attraversare la diagonale li accoppia uno a uno con le rotte verso un estremo spostato, e quelli sono 8!/(3!·5!) = 56. Quindi 70 − 56 = 14 e i due schermi concordano. La stessa sequenza 1, 2, 5, 14, 42 conta i modi di inserire parentesi in una stringa di fattori, le triangolazioni di un poligono convesso e le stringhe di parentesi legali: il terzo link è C₅ = 10!/(5!·6!) = 42, il successivo, che è il numero di triangolazioni di un ettagono.

Risposta

14

Come leggerla

C₄ come 8!/(4!·5!) sul banco di lavoro. Il secondo link è il conteggio senza restrizioni 8!/(4!·4!) = 70, e il terzo è il numero di Catalan successivo, 42.

Fonte

The Catalan numbers Cₙ = (2n)!/(n!(n+1)!) count monotone lattice paths that stay on one side of the diagonal; Euler used the sequence for polygon triangulations in 1751, the Chinese mathematician Ming'an derived the formula in the 1730s, and Eugène Catalan gave the name in 1838

Svolgilo nella calcolatrice

Questi link aprono la calcolatrice giusta con i numeri di questo problema già digitati. La riga sopra è ciò che lo schermo dovrebbe mostrare — verifica tu stesso.

Questo è un sito di strumenti indipendente di terze parti. Non è affiliato, sponsorizzato né autorizzato da Casio, Texas Instruments o dai loro distributori. I nomi dei modelli e dei prodotti sono marchi dei rispettivi proprietari e compaiono qui solo per identificare i dispositivi.

Le sequenze di tasti in questi manuali sono state scritte a partire dai dati di layout propri di questo sito — gli stessi che usa la calcolatrice online — insieme a informazioni sul prodotto disponibili pubblicamente. Le specifiche e le configurazioni regionali sono verificate sul dispositivo fisico e sulla documentazione più recente del produttore.