Catalan number

وکیپیڈیا سے

اصطلاح	term
کیٹیلان	Catalan

ریاضیات کے شعبہ تالیفیات میں کیٹلان عدد ایک متوالیہ تعریف کرتے ہیں، اور یہ تالیفیات میں کافی مفید ثابت ہوتے ہیں۔ n^واں کیٹلان عدد $C n$ یوں تعریف ہوتا ہے:

$C_n = \frac{1}{n} \binom{2n-2}{n-1} = \binom{2n-2}{n-1} - \binom{2n-2}{n}$

تعریف:راہ: کارتیسی مستوی میں شُبیکہ نقطہ $\ (x_0, y_0)$ سے شبیکہ نقطہ $\ (x_m, y_m)$ راہ شبیکہ نقاط کے متوالیہ ${(x i, y i)}$ کو کہتے ہیں، جبکہ نقاط $\ (x_i, y_i)$ کی یہ خصوصیت ہو کہ $i=0,1,\cdots, m-1$ کے لیے $x_{i+1}=x_i+1,\, y_{i+1}=y_i$ یا پھر $x_{i+1}=x_i,\, y_{i+1}=y_i+1$

تعریف: راہ کو اچھا کہتے ہیں اگر

$y_i<x_i \, , \, i=0,1, \cdots,m$

نقطہ $\ (x_0, y_0)$ سے نقطہ $\ (x_m, y_m)$ راہوں کی تعداد

$\binom{(x_m-x_0)+(y_m-y_0)}{x_m-x_0} =\binom{(x_m-x_0)+(y_m-y_0)}{y_m-y_0}$

ہے۔ یہ اس وجہ سے ہے کہ نقطہ $\ (x_0, y_0)$ سے نقطہ $\ (x_m, y_m)$ جانے تک $\ (x_m-x_0)+(y_m-y_0)$ قدم ہیں اور ہر قدم پر آپ کو اُفقی یا عمودی طرف کا انتخاب کرنا ہے، یعنی $\ (x_m-x_0)+(y_m-y_0)$ میں سے $\ (x_m-x_0)$ افقی قدموں کا انتخاب، یا $\ (x_m-x_0)+(y_m-y_0)$ میں سے $\ (y_m-y_0)$ عمودی قدموں کا انتخاب۔