# கேடலான் எண்கள்

**கேடலான் எண்கள்** (Catalan numbers) என்ற கருத்து 1830ம் ஆண்டு யுஜீன் கேடலான் (1814-1894) என்பவர் எழுதின ஒரு ஆய்வுக் கட்டுரையிலிருந்து தொடங்கியது. பற்பல எண்ணிக்கைப் பிரச்சினைகளில் அது திரும்பத் திரும்ப வருவதைப் பார்க்கலாம். அதனாலேயே சேர்வியலில் இது ஒரு முக்கிய அத்தியாயமாக நிலைபெற்றுவிட்டது. ஒரு தொடர்வரிசையாக வரும் இந்த எண்களின் n –வது எண்ணுக்கு C<sub>n</sub> என்ற குறியீடு பயன்படுத்தப்படுகிறது. இதனுடைய மதிப்பு  

:<math>\frac{1}{n}\binom{2n-2}{n-1}</math>.அதாவது, <math>\frac{(2n-2)!}{n!(n-1)!}</math>  

ஆகையால்  
C<sub>2</sub> =1; C<sub>3</sub> = 2; C<sub>4</sub> =5; C<sub>5</sub> = 14, C<sub>6</sub> = 42 .....  

C<sub>1</sub> ஐ 1 என்று எடுத்துக்கொள்வது வழக்கம். இக்கட்டுரையில் இவ்வெண்கள் பல வேறுபட்ட சூழ்நிலைகளிலும் தோன்றுவதைப் பார்ப்போம்.  

**முக்கிய குறிப்பு**: C<sub>1</sub> = 1; C<sub>2</sub> =1; C<sub>3</sub> = 2; C<sub>4</sub> =5; C<sub>5</sub> = 14, C<sub>6</sub> = 42 ..... என்ற இந்தக்கட்டுரைத் தொடர்பை  

C<sub>0</sub> = 1; C<sub>1</sub> =1; C<sub>2</sub> = 2; C<sub>3</sub> =5; C<sub>4</sub> = 14, C<sub>5</sub> = 42 ..... என்றும் குறியிடும் வழக்கம் பரவலாக இருக்கிறது. அந்த வழக்கப்படி, (இக்கட்டுரையிலல்ல)  

:<math>C_n =\frac{1}{n+1}\binom{2n}{n}</math>.இக்கட்டுரையில் இது C<sub>n+1</sub> ஆகும்.  

## மூலைவிட்ட முக்கோணப்பிரிவினை

(n + 1) பக்கங்களுள்ள ஒரு குவிந்த பலகோணத்தை உள்பக்கத்தில் ஒன்றுக்கொன்று வெட்டாத மூலைவிட்டங்களால் முக்கோணங்களால் பிரிக்கப்பட T<sub>n+1</sub>வழிகளிருந்தால்  

:***T<sub>n+1</sub> = C<sub>n</sub>***  
ஆக, *T<sub>3</sub>* = 1; *T<sub>4</sub>* = 2; *T<sub>5</sub>* = 5; *T<sub>6</sub>* = 14; *T<sub>7</sub>* = 42 …….  

*T<sub>2</sub>* =1 என்று நாம் விதி செய்துகொள்ளலாம்.  

*T<sub>n+1</sub>* இன் மதிப்பை *C<sub>n</sub>* என்று காண்பதற்கு இதற்கென்று கீழேயுள்ள ஒரு மீள்வரு தொடர்பு (Recurrence relation) உண்டாக்கப்படுகிறது:  

: **(*)**<math>T_{n+1} = T_2 T_n + T_3 T_{n-1} + ... + T_n T_2</math>.  

## அடைப்புக்குறியிடும் செயல்

:<math>x_1x_2 ... x_n</math>  

என்ற பெருக்கலை அடைப்புக் குறிகளிட்டு பெருக்கல்களுக்கு ஒரு தகுந்த சேர்ப்பு விதிகளை உண்டுபண்ண <math>a_n</math> வழிகள் இருப்பதாகக் கொள்வோம்.  

எடுத்துக்காட்டாக, abcd என்ற பெருக்கலுக்கு அடைப்புக்குறிகள் ஐந்து விதமாகப்போடலாம்:  

: ***a.(b(cd))***  

: ***a.((bc)d) ***  

: ***(ab).(cd)***  

: ***((ab)c).d***  

: ***(a(bc)).d***  

கடைசிப் பெருக்கல் செயல்முறை ' .' என்ற புள்ளியால் காட்டப்பட்டிருப்பதில் ஒரு தத்துவம் இருக்கிறது. இந்தப்புள்ளி <math>x_k</math> க்கும் <math>x_{k+1}</math> க்கும் நடுவில் வந்தால், அதற்கு ஒரு பக்கம் <math>x_1x_2 ... x_k</math> யும் மறுபக்கம் <math>x_{k+1}x_{k+2} ... x_n</math> ம் இருக்கும். இடது பக்கத்திலுள்ள பெருக்கலை அடைப்புக்குறிகளால் காட்டுவதற்கு <math>a_k</math> வழிகளும் வலது பக்கத்திலுள்ள பெருக்கலை அடைப்புக்குறிகளால் காட்டுவதற்கு <math>a_{n-k}</math> வழிகளும் உள்ளன. தர்க்கரீதியாக இந்த வாதத்தின் பின்னேசென்றால் நமக்குக்கிடைப்பது கீழ்வரும் ஒரு மீள்வரு தொடர்பு:  

:**(**)** <math>a_n = a_1 a_{n-1} + a_2 a_{n-2} + ... + a_{n-1} a_1</math>  

<math>T_{n+1}</math>க்கு பதில் <math> a_n</math> ஐ ப்பொருத்தினால், **(*)**ம் **(**)**ம் ஒரே மீள்வரு தொடர்பு தான். அதனால்  

:<math>a_n = T_{n+1} = C_n</math>  

## கழி உடைப்புச்செயல்

*n* அலகுகள் அளவுள்ள ஒரு கழியை ஒவ்வொரு படியிலும் ஒரு அலகை விடப் பெரியதாகவுள்ள துண்டுகளை இரண்டாக உடைப்பதன் மூலம் *n* ஒரு அலகுத் துண்டுகளாக உடைக்க, <math>C_n</math> வழிகளுள்ளன.  

இது எப்படியென்றால், <math>x_1x_2 ... x_n</math> என்ற பெருக்கலுக்கு அடைப்புகள் போடும் செயலையும் கழி உடைப்புச்செயலையும் ஒத்துப்பார். கடைசிப்பெருக்கல் ஏதோ இரண்டைப்பெருக்குகிறது. அந்த இரண்டில் ஒவ்வொன்றும் அடைப்புகளுக்குள் இருக்கின்றன.  

: <math>(x_1x_2 ... x_i)(x_{i+1} ... x_n)</math>  

ஒவ்வொரு அடைப்புக்குள்ளும் அதற்கு முன் நிலையில் ஒரு கடைசிப் பெருக்கல் இருந்திருக்க வேண்டும்.இப்பெருக்கலுக்காகக் கருதப்படும் கடைசிப் பெருக்கல்புள்ளி ஒவ்வொன்றும் ஒரு கழி உடைப்புக்குச் சமானம்.  

: <math>((x_1 .... )(.... x_i)) ((x_{i+1} ... )(.... x_n))</math>  

ஆக, கழிஉடைப்புச்செயல் எண்ணும் <math>C_n</math> என்ற கேடலான் எண்தான்.  

## சன்னல் புள்ளிகள் வழியாக நேர்மைப் பாதைகள்

<math>(n-1) \times (n-1)</math> சன்னல் புள்ளிகளுள்ள இரு பரிமாண தளத்தில் இடது கீழ் மூலையிலிருந்து வலது மேல் மூலைக்கு சன்னல் புள்ளிகள் வழியாக ஆயத்திசைகளிலேயே போகும் பாதைகள் மூலை விட்டத்தைத் தாண்டாமல் இருந்தால் அவை ‘**நேர்மைப் பாதைகள்**' எனப் பெயர் பெறும். இவைகளின் எண்ணிக்கையும் <math>C_n</math> தான்.  

இந்த நிறுவலை சற்று கவனமாகவே கையாளவேண்டும். இடது கீழ்மூலையை *(0,0)* என்று ஆயத்தளத்தின் தொடக்கப் புள்ளியாகக்கொள்வோம். இப்பொழுது வலது மேல் மூலை *(n-1, n-1)* ஆகும். *(0,0)* விலிருந்து (*n-1, n-1)* க்குப்போகும் எல்லாப்பாதைகளின் எண்ணிக்கையை ஒரு சேர்வுக் கணக்காகக் கணித்திடலாம். அதாவது, மொத்தம் இருக்கும் *(2n-2)* அடிகளில் எத்தனை வழிகளில் *(n-1)* வலது பக்கம் போகும் அடிகளாகத் தேர்ந்தெடுக்கலாம் என்ற எண்ணிக்கைதான் அது. ஆக, இந்த எண்  

:<math>\binom{2n-2}{n-1}</math>.  

இவைகளில் *y = x* என்ற மூலை விட்டத்தைக் கடக்காத பாதைகள் எத்தனை? இதைக் கணிப்பதைவிட மூலைவிட்டத்தைக் கடக்கும் பாதைகளைக் கணக்கிடுதல் சற்று எளிது. இவைகளை தற்போதைக்கு 'நேர்மையல்லாத பாதைகள்' என்று சொல்வோம்.  

கணம் A: *(0,0)* விலிருந்து *(n-1,n-1)*க்குச்செல்லும் எல்லா'நேர்மையல்லாத பாதைகள்' என்று கொள்.  

கணம் B: *(-1,1)* இலிருந்து *(n-1, n-1)* க்குச்செல்லும் எல்லாப் பாதைகள் என்று கொள்.  

Aக்கும் Bக்கும் ஒரு இருவழிக்கோப்பு உண்டாக்கலாம். எப்படி என்று பார்.  

ஒவ்வொரு நேர்மையல்லாத பாதையும் *y = x* ஐ எங்கோ ஓரிடத்தில் கடக்கத்தான் வேண்டும்; கடந்து *y= x + 1* ஐயும் சந்தித்துத்தான் ஆகவேண்டும். இப்படி முதன்முதலில் சந்திக்கும் இடத்தை P என்று பெயரிடுவோம். (*0,0)* விலிருந்து P வரையில் உள்ள இப்பாதையை *y=x+1* என்ற கோட்டில் பிரதிபலித்தால், அது *(-1,1)* இலிருந்து P வரையில் உள்ள பாதையாக மாறும். இதைத்தொடர்ந்து மீதமுள்ள பாதையில் P இலிருந்து *(n-1, n-1)* வரையில் சென்றால், நமக்கு *(-1, 1)*இலிருந்து *(n-1, n-1)* வரையில் ஒரு பாதை கிடைக்கும்.  

இதற்கு எதிர்மறையாக, *(-1,1)* இலிருந்து *(n-1, n-1)* க்குள்ள ஒவ்வொரு பாதைக்கும், அதே பிரதிபலிப்பின் நேர்மாறைப் பயன்படுத்தி *(0,0)* விலிருந்து *(n-1, n-1)* க்குள்ள ஒரு 'நேர்மையல்லாத பாதை'யை அடையலாம்.  

ஆக, Aக்கும் Bக்கும் ஒரு இருவழிக்கோப்பு உண்டாக்கப்பட்டுவிட்டது. இதனால் தெரிவது என்னவென்றால் *(0,0)* விலிருந்து *(n-1,n-1)*க்குப்போகும் நேர்மையல்லாத பாதைகளின் மொத்த எண்ணிக்கை, *(-1,1)* இலிருந்து *(n-1, n-1)* க்குப்போகும் எல்லாப் பாதைகளின் மொத்த எண்ணிக்கையே. இந்த எண்  

:= <math>\binom{2n-2}{n}</math>,  

ஏனென்றால், வலது பக்கம் எடுக்கப்படவேண்டிய அடிகளின் எண்ணிக்கை =* n ,* மற்றும், மொத்த அடிகளின் எண்ணிக்கை = *(n-1)-(-1) + (n-1)-1 = 2n - 2.*  

இதிலிருந்து, *(0,0)*விலிருந்து (*n-1,n-1*)க்கு நேர்மையான பாதைகளின் எண்ணிக்கை  

= <math>\binom{2n-2}{n-1} - \binom{2n-2}{n} </math>  

= <math>\frac{1}{n} \binom{2n-2}{n-1} = C_n </math>  

## வட்டத்தில் குறுக்குவெட்டில்லாத நாண்கள்

*2n* நபர்கள் வட்டமாக உட்கார்ந்திருக்கும்போது, எல்லோரும் ஒரே நேரத்தில் கைநீட்டி மற்ற யாராவதொருவருடன் கைகுலுக்க, யாருடைய கையும் மற்ற எவருடைய கையையும் குறுக்கே தாண்டாத முறையில் கைகுலுக்க உள்ள வழிகள் <math>C_{n+1}. </math>  

இதே பிரச்சினையை வேறுவிதமாகவும் உருமாற்றலாம். ஒரு வட்டத்தின் மேல் *2n* புள்ளிகள் கொடுக்கப்பட்டிருக்கின்றன. இவைகளை ஒன்றுக்கொன்று வெட்டாத வகையில் ஜோடி ஜோடியாக நாண்களால் இணைக்கவேண்டும். இதற்குள்ள வழிகளும் மேலே கைகுலுக்கல் பிரச்சினைக்குள்ள வழிகளும் ஒன்றுதான்.  

இவ்விதம் நாண்கள் வரையப்பட்டுவிட்டதாகக் கொள்வோம். வட்டத்தைச் சுற்றிப்போகும்போது, ஒரு நாணின் நுணியைச் சந்தித்தால் அதை **b** என்றும், ஏற்கனவே சந்தித்த நாணை மறுமுறை (அதாவது அதன் மறு நுணியை) சந்தித்தால் அதை **e** என்றும் பெய்ரிடு. இப்படி எல்லா நாண்களின் நுணிகளையும் பெய்ரிட்ட ஒரு படிமத்தைப்பார். வட்டத்தில் ஏதாவது ஒரு இடத்தில் தொடங்கி நுணிகளின் பெயர்களைக் குறித்துக் கொண்டேபோனால் நமக்கு இப்படி ஒரு 'சொல்' கிடைக்கிறது:  

இந்த சொல்லில், ***'b***' என்றால் 'வலது பக்கம் ஒரு அடி எடுத்துவை' என்றும் ***'e***' என்றல் 'மேல்பக்கம் ஒரு அடி எடுத்து வை' என்றும் ஒரு பொருள் கொடுத்தால், நமக்குக் கிடைப்பது ஒரு <math>n \times n</math> சன்னல் புள்ளியிட்ட ஒரு ஆயத்தளத்தில் (*0,0)* இலிருந்து *(n,n)* வரையில் உள்ள ஒரு நேர்மைப்பாதை.  

ஆக, இப்படிப்பட்ட சொற்களின் மொத்த எண்ணிக்கை, *(0,0)*விலிருந்து *(n,n)*க்குப்போகும் நேர்மைப் பாதைகளின் எண்ணிக்கை தான். இது கேடலான் எண் <math>C_{n+1}</math>; அதாவது  
:<math>\frac{1}{n+1}\binom{2n}{n}.</math>  

## ஈருறுப்புத் தொடர்புகளின் பகுதிக் கூட்டுத்தொகைகள்

(+1), (-1) இவை மாத்திரம் கொண்ட  

: (<math>a_1</math>, <math>a_2</math>, … <math>a_{2n-2}</math>)  

இன் மொத்தக்கூட்டுத்தொகை சூனியமாகவும், எல்லா பகுதிக்கூட்டுத் தொகைகளும்(அதாவது, <math>{a_1, a_1 + a_2, a_1 + a_2 + a_3, ...} </math>) எதிர்ம மில்லாமலும் உள்ள ஈருறுப்புத் தொடர்புகளின் எண்ணிக்கை <math>C_n</math>.  

இதன் உண்மையை நிறுவவதற்கு இம்மாதிரி ஈருறுப்புத்தொடர்புகளுக்கும், <math>x_1x_2...x_n</math> ஐ அடைப்புக்குறிகளால் அடைக்கப்படும் வழிகளுக்கும் ஒரு இருவழிக்கோப்பு உண்டாக்குவோம். எடுத்துக்காட்டாக, n = 4 என்று கொள்வோம். abcd என்ற பெருக்குத்தொகை ஐந்து வழிகளில் அடைப்புக்குறிகளால் அடைக்கப்படுகிறது. அவைகளில் ஒரு வழி:  

:(*): (((a.b).c).d)  

இங்கு 3 பெருக்கல்களும், மூன்று ஜோடி அடைப்புகளும் உள்ளன. குறிப்பு: பெருக்கலின் தொடக்கத்திற்கும் முடிவுக்கும் கூட ஒரு ஜோடி அடைப்புக்குறி போடப்படுகிறது.  

இப்பொழுது இருவழிக்கோப்பு எப்படி வருகிறதென்று பார்க்கலாம். (*)இல் பெருக்கல் புள்ளிகளையும், வலது பக்க அடைப்புகளையும் மாத்திரம் வைத்துக்கொள்வோம். மற்ற எல்லாக்குறிகளையும் எழுத்துக்களையும் அழித்துவிடுவோம். இப்பொழுது நமக்குக்கிடைப்பது:  

: **.).).)**  

ஒவ்வொரு பெருக்கல்புள்ளிக்கும் ஒரு '+1'ம், ஒவ்வொரு வலது அடைப்புக்கும் ஒரு '-1'ம் எழுதுவோம். நமக்குக்கிடைப்பது:  

: **+1, -1, +1, -1, +1, -1**.  

இத்தொடர்பின் மொத்தக்கூட்டுத்தொகை சூனியம். எல்லா பகுதிக்கூட்டுத்தொகைகளும் எதிர்மமில்லாமலும் உள்ளன. இவ்விதம் ஏற்படும் இருவழிக்கோப்பில் இரு மாதிரிகள்:  

அடைப்புக்குறியிடல்: ((a.(b.c)).d) <math>\leftrightarrow </math> தொடர்பு: +1, +1, -1, -1, +1, -1  

தொடர்பு: +1, +1, +1, -1, -1, -1 <math>\leftrightarrow</math> அடைப்புக்குறியிடல்: (a.(b.(c.d)))  

## மலைப்படிமங்கள்

*(n-1)* மேல்நோக்கிக் கோடுகளும் *(n-1)* கீழ்நோக்கிக் கோடுகளும் கொண்டதும், அடிவாரத்திற்குக் கீழே போகாததுமான மலைப் படிமங்களின் எண்ணிக்கை <math>C_n</math>.  

மேல்நோக்கிக்கோடுகளுக்கு '+1'ம் கீழ்நோக்கிக்கோடுகளுக்கு '-1' ம் எழுதினால் இவைகளுக்கும் மேலே கூறிய ஈருருப்புத்தொடர்புகளுக்கும் ஒரு இருவழிக்கோப்பு உண்டாகிறது.  

## துணைநூல்கள்

- Catalan, Eugene. (1844):
- Stanley, R.P. (1999): *Enumerative Combinatorics*, Vol. 2. Cambridge University Press. (pp.&nbsp;219–229)
- V. Krishnamurthy, C.R. Pranesachar, K.N. Ranganathan, B.J. Venkatachala. Challenge and Thrill of Precollege Mathematics. 2nd edn. 2007 New Age International, New Delhi