اثبات مستقيم(ترجمه شده از منبع مذکور):

ميدونيم تعداد مسير هايي که ميشه از پايين چپ به بالا راست جدول زير رسيد برابربا $\binom{2n}{n}$ هست.حالا تعداد مسير هايي رو ميشماريم که هيچ وقت از خط واصل پايين چپ به بالا راست عبور نميکنن(اسم اين مسيرها رو ميزاريم مسير مقبول).که همون جمله n ام دنباله کاتالاني هست.

از تناظر استفاده ميکنيم به اين صورت که هر مسير مقبول رو به n+1 مسير متناظر ميکنيم.اگه يه مسیر غيرمقبول داشته باشيم انقدر الگوريتم زيرو روش اجرا ميکنيم تا مقبول بشه:

تعريف : بالازدگي يه مسير رو تعداد حرکت هاي عمودي انجام گرفته بالاي خط واصل پايين چپ به بالا راست جدول تو اون مسير تعريف ميکنيم.مثلا بالازدگي مسير زير 5 تاست: از پايين چپ شروع ميکنيم و انقدر راهو ادامه ميديم تا براي اولين بار از خط وسط عبور کنيم.

انقدر مسیرو ادامه ميديم تا دوباره بخوريم به خط وسط.(واضحه که آخرين حرکتي که باهاش دوباره ميخوريم به خط وسط افقيه که اونو x ميناميم(تو شکل رنگش سياهه) )

قسمت هاي قبل و بعد از x رو مطابق شکل زير جابجا ميکنيم:

واضحه که دقيقا يکي از تعداد بالا زدگي ها کم ميشه.مثلا تو شکل بالا از 3 تا تبديل ميشه به 2 تا.دليلش هم اينه که اولين خط عمودي که از خط واصل ميزنه بالا (يعني خط بعد از نقطه سياه رنگ در شکل بالا) تنها خط عموديه که طي انجام عمليات جابجايي مياد زير خط واصل و ساير خطوط عمودي بالاي خط واصل،بالاي اون ميمونن.

چندتا مثال دیگه از اجرای الگوریتم تا مقبول شدن مسیر:

همچنين مشاهده ميشه که اين حرکات برگشت پذيرند.و چون بالازدگي يه مسير عددي بين 0 تا n ه (n+1 حالت داره) پس به ازاي يک مسير مقبول با n بار اجراي اين الگوريتم به n مسير غيرمقبول ميرسيم که با احتساب خودش n+1 مسير ميشه.پس تعداد مسير هاي مقبول $\frac{1}{n+1}$ کل مسير هاست.

موفق باشيد!