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.