Catalan's triangle
مشترکہ ریاضی میں، کاتالان کا مثلث ایک عدد مثلث ہے جس کی اندراجات n X اور k Y پر مشتمل تاروں کی تعداد اس طرح دیتی ہیں کہ تار کے کسی بھی ابتدائی حصے میں X سے زیادہ Y نہیں ہوتا ہے۔ یہ کاتالان نمبروں کی عمومی شکل ہے، اور اس کا نام یوجین چارلس کاتالان کے نام پر رکھا گیا ہے۔ بیلی دکھاتا ہے کہ مندرجہ ذیل خصوصیات کو پورا کرتا ہے: ۔ ۔ فارمولا 3 سے پتہ چلتا ہے کہ مثلث میں اندراج مثلث میں بائیں اور اوپر کی طرف نمبروں کو شامل کرکے بار بار حاصل کیا جاتا ہے۔ ریکرشن فارمولے کے ساتھ کاتالان مثلث کا سب سے قدیم ظہور 1800 میں لوئس فرانکوئس انٹون اربوگاسٹ کے ذریعہ شائع کردہ کیلکولس پر مقالے کے صفحہ 214 میں ہے۔ شاپیرو ایک اور مثلث متعارف کراتا ہے جسے وہ کاتالان مثلث کہتا ہے جو یہاں زیر بحث مثلث سے الگ ہے۔ عمومی فارمولا کے لیے عمومی فارمولا اس طرح دیا گیا ہے کہ کب، اخترن-واں کاتالان نمبر ہے۔ - th صف کا قطار کا مجموعہ-th کاتالان نمبر ہے، جس میں ہاکی اسٹک کی شناخت اور کاتالان نمبروں کے لیے ایک متبادل اظہار استعمال ہوتا ہے۔ اقدار کی جدول کچھ اقدار {| کلاس = "وکیٹیبل" سٹائل = "ٹیکسٹ-الائن: رائٹ ؛" |-! کے ذریعے دی جاتی ہیں۔ ! چوڑائی = "50" | 0! چوڑائی = "50" | 1! چوڑائی = "50" | 2! چوڑائی = "50" | 3! چوڑائی = "50" | 4! چوڑائی = "50" | 5! چوڑائی = "50" | 6! چوڑائی = "50" | 7! چوڑائی = "50"۔ 8 |-! 0 | 1 | | | | | | | | | | | | | | | | | | | | |-! 1 | 1 | | 1 | | | | | | | | | | | | | | | | | | |-! 2 | 1 | | 2 | | 2 | | | | | | | | | | | | | | | | |-! 3 | 1 | | 3 | | 5 | | 5 | | | | | | | | | | | | | |-! 4 | 1 | | 4 | | 9 | | 14 | | 14 | | | | | | | | | | | |-! 5 | 1 | | 5 | | 14 | | 28 | | 42 | | 42 | | | | | | | |-! 6 | 1 | | 6 | | 20 | | 48 | | 90 | | 132 | | 132 | | | |-! 7 | 1 | | 7 | | 27 | | 75 | | 165 | | 297 | | 429 | | 429 | | |-! 8 | 1 | | 8 | | 35 | | 110 | | 275 | | 572 | | 1001 | | 1430 | | 1430 |} دونوں کو ثابت کرنے کے لیے پہلے حصے سے پراپرٹیز فارمولا 3 کا استعمال کیا جا سکتا ہے۔ اگر، تو پھر کسی مرحلے پر s سے زیادہ ہونا ضروری ہے، تو۔ - th ویلیو کی مشترکہ تشریح غیر کم ہونے والی پارٹیشنوں کی تعداد ہے جس میں زیادہ سے زیادہ حصے کے ساتھ بالکل ایسے حصے ہوتے ہیں کہ ہر حصہ اس کے انڈیکس سے کم یا برابر ہو۔ لہذا، مثال کے طور پر، گنتی عمومی کاتالان کے ٹریپیزوئڈز نمبر ٹریپیزوئڈز کا ایک قابل شمار مجموعہ ہیں جو کاتالان کے مثلث کو عام کرتے ہیں۔ کیٹالان کا ٹریپیزائڈ آف آرڈر ایک نمبر ٹریپیزائڈ ہے جس کی اندراجات X-s اور Y-s پر مشتمل تاروں کی تعداد اس طرح دیتی ہیں کہ تار کے ہر ابتدائی حصے میں Y-s کی تعداد X-s کی تعداد سے زیادہ یا اس سے زیادہ نہ ہو۔ تعریف کے مطابق، کاتالان کا ٹریپیزائڈ آف آرڈر کاتالان کا مثلث ہے، یعنی۔ کاتالان کے ٹریپیزائڈ آف آرڈر کی کچھ اقدار {| کلاس = "وکیبل" سٹائل = "ٹیکسٹ-الائن: رائٹ ؛" |-! کے ذریعے دی گئی ہیں۔ ! چوڑائی = "50" | 0! چوڑائی = "50" | 1! چوڑائی = "50" | 2! چوڑائی = "50" | 3! چوڑائی = "50" | 4! چوڑائی = "50" | 5! چوڑائی = "50" | 6! چوڑائی = "50" | 7! چوڑائی = "50"۔ 8 |-! 0 | 1 | | 1 | | | | | | | | | | | | | | | | | | | |-! 1 | 1 | | 2 | | 2 | | | | | | | | | | | | | | | | |-! 2 | 1 | | 3 | | 5 | | 5 | | | | | | | | | | | | | |-! 3 | 1 | | 4 | | 9 | | 14 | | 14 | | | | | | | | | | | |-! 4 | 1 | | 5 | | 14 | | 28 | | 42 | | 42 | | | | | | | |-! 5 | 1 | | 6 | | 20 | | 48 | | 90 | | 132 | | 132 | | | |-! 6 | 1 | | 7 | | 27 | | 75 | | 165 | | 297 | | 429 | | 429 | | |-! 7 | 1 | | 8 | | 35 | | 110 | | 275 | | 572 | | 1001 | | 1430 | | 1430 |} کاتالان کے ٹریپیزائڈ آرڈر کی کچھ اقدار {| کلاس = "وکیٹیبل" سٹائل = "ٹیکسٹ-الائن: رائٹ ؛" |-! ! چوڑائی = "50" | 0! چوڑائی = "50" | 1! چوڑائی = "50" | 2! چوڑائی = "50" | 3! چوڑائی = "50" | 4! چوڑائی = "50" | 5! چوڑائی = "50" | 6! چوڑائی = "50" | 7! چوڑائی = "50"۔ 8! چوڑائی = "50"۔ 9 |-! 0 | 1 | | 1 | | 1 | | | | | | | | | | | | | | | | | | |-! 1 | 1 | | 2 | | 3 | | 3 | | | | | | | | | | | | | | | |-! 2 | 1 | | 3 | | 6 | | 9 | | 9 | | | | | | | | | | | | |-! 3 | 1 | | 4 | | 10 | | 19 | | 28 | | 28 | | | | | | | | | | | |-! 4 | 1 | | 5 | | 15 | | 34 | | 62 | | 90 | | 90 | | | | | | | |-! 5 | 1 | | 6 | | 21 | | 55 | | 117 | | 207 | | 297 | | | | | | |-! 6 | 1 | | 7 | | 28 | | 83 | | 200 | | 407 | | 704 | | 1001 | | 1001 | |-! 7 | 1 | | 8 | | 36 | | 119 | | 319 | | 726 | | 1430 | | 2431 | | 3432 | | 3432 |} پھر، ہر عنصر اوپر والے عنصر اور بائیں والے عنصر کا مجموعہ ہے۔ کے لیے ایک عمومی فارمولا (،،) کے ذریعے دیا گیا ہے۔ ثبوت 1 کے عمومی فارمولے کے ثبوت اس ثبوت میں آندرے کے عکاسی کے طریقہ کار کی توسیع شامل ہے جیسا کہ کاتالان نمبر کے دوسرے ثبوت میں استعمال کیا گیا ہے۔ مندرجہ ذیل سے پتہ چلتا ہے کہ کس طرح نقشہ کے نیچے بائیں سے اوپر دائیں طرف کا ہر راستہ جو رکاوٹ کو عبور کرتا ہے وہ بھی اختتامی نقطہ پر جھلک سکتا ہے۔ ہم ان راستوں کی تعداد کا تعین کرنے کے لیے تین صورتوں پر غور کرتے ہیں جو اس رکاوٹ کو پار نہیں کرتے ہیں: (1) جب رکاوٹ کو پار نہیں کیا جا سکتا، تو تمام راستے درست ہیں، یعنی۔ ۔ (2) جب کوئی ایسا راستہ بنانا ناممکن ہو جو رکاوٹ کو پار نہ کرے، یعنی۔ ۔ (3) کب، پھر 'سرخ' راستوں کی تعداد مائنس 'پیلے رنگ' راستوں کی تعداد ہے جو رکاوٹ کو عبور کرتے ہیں، یعنی۔ ۔ لہذا اس سے آنے والے راستوں کی تعداد رکاوٹ کو پار نہیں کرتی ہے جیسا کہ پچھلے حصے "جنرلائزیشن" کے فارمولے میں اشارہ کیا گیا ہے۔ ثبوت 2 سب سے پہلے، ہم دو حصوں میں تقسیم کرکے تکرار کے تعلق کی توثیق کرتے ہیں، پہلا XY امتزاج کے لیے جو X میں ختم ہوتا ہے اور دوسرا Y میں ختم ہونے والوں کے لیے۔ اس لیے پہلے گروپ میں درست امتزاج ہوتے ہیں اور دوسرے میں ہوتے ہیں۔ ثبوت 2 اس بات کی تصدیق کر کے مکمل کیا جاتا ہے کہ حل تکرار کے تعلق کو مطمئن کرتا ہے اور اور کے لیے ابتدائی شرائط کی پابندی کرتا ہے۔ حوالہ جات اعداد کے مثلث