Pada kisi 4 × 4, lintasan dari kiri bawah ke kanan atas yang hanya bergerak ke atas dan ke kanan ada 8!/(4!·4!) = 70, yang diperlihatkan meja kerja pada tautan kedua. Kebanyakan menambahkan aturan tidak naik di atas diagonal, dan bilangan itu menjadi 8!/(4!·5!) = 14. Kedua rumus berbeda sebesar pengali n + 1 pada penyebut, dan itulah seluruh koreksi Catalan.
56 lintasan terlarang itu tidak tersebar. Menurut argumen refleksi, lintasan yang melewati diagonal berkorespondensi satu-satu dengan lintasan menuju titik ujung yang digeser, dan banyaknya 8!/(3!·5!) = 56. Jadi 70 − 56 = 14 dan kedua layar cocok. Deret yang sama 1, 2, 5, 14, 42 menghitung cara memberi tanda kurung pada rantai perkalian, triangulasi poligon konveks, dan ungkapan tanda kurung yang sah. Tautan ketiga ialah nilai berikutnya C₅ = 10!/(5!·6!) = 42, banyaknya triangulasi segitujuh.
Jawaban
14
Cara membacanya
C₄ yang ditulis sebagai 8!/(4!·5!) di meja kerja. Tautan kedua ialah hitungan tanpa batasan 8!/(4!·4!) = 70, dan yang ketiga bilangan Catalan berikutnya 42.
Sumber
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
Kerjakan di kalkulator
Tautan ini membuka kalkulator yang tepat dengan angka soal ini sudah diketik. Baris di atas adalah yang seharusnya ditampilkan layar — periksa sendiri.