على شبكة 4 × 4، المسارات من الزاوية السفلى اليسرى إلى العليا اليمنى التي لا تسير إلا إلى أعلى وإلى اليمين عددها 8!/(4!·4!) = 70 — وهو ما تكتبه مساحة العمل في الرابط الثاني. ويضيف معظم الناس قاعدة «لا تعلُ فوق القطر أبدًا»، فيصبح العدّ 8!/(4!·5!) = 14. والصيغتان تختلفان بعامل واحد n + 1 في المقام، وهذا هو تصحيح كاتالان كله.
والمسارات غير المشروعة الـ 56 ليست مبعثرة: بحجة الانعكاس يقارن تجاوز القطر كل واحد منها واحدًا بواحد مع مسار إلى نقطة نهاية مُزاحة، وعددها 8!/(3!·5!) = 56. إذن 70 − 56 = 14 ويتفق العرضان. والمتتالية نفسها 1، 2، 5، 14، 42 تعدّ طرق وضع الأقواس في سلسلة عوامل، وتثليثات المضلع المحدّب، ومتتاليات الأقواس المشروعة — والرابط الثالث C₅ = 10!/(5!·6!) = 42، أي التالي صعودًا، وهو عدد تثليثات المسبّع.
الإجابة
14
كيف تقرأها
C₄ على الصورة 8!/(4!·5!) في مساحة العمل. الرابط الثاني هو العدّ بلا قيود 8!/(4!·4!) = 70، والثالث عدد كاتالان التالي، 42.
المصدر
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
احل في الحاسبة
تفتح هذه الروابط الحاسبة المناسبة بأرقام هذه المسألة مُدخَلة بالفعل. السطر أعلاه هو ما ينبغي أن تعرضه الشاشة — تحقّق بنفسك.