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

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

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

ஆகையால்
C2 =1; C3 = 2; C4 =5; C5 = 14, C6 = 42 .....

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

**முக்கிய குறிப்பு**: C1 = 1; C2 =1; C3 = 2; C4 =5; C5 = 14, C6 = 42 ..... என்ற இந்தக்கட்டுரைத் தொடர்பை

C0 = 1; C1 =1; C2 = 2; C3 =5; C4 = 14, C5 = 42 ..... என்றும் குறியிடும் வழக்கம் பரவலாக இருக்கிறது. அந்த வழக்கப்படி, (இக்கட்டுரையிலல்ல)

:C_n =\frac{1}{n+1}\binom{2n}{n}.இக்கட்டுரையில் இது Cn+1 ஆகும்.

## மூலைவிட்ட முக்கோணப்பிரிவினை
right|thumb|400px

(n + 1) பக்கங்களுள்ள ஒரு குவிந்த பலகோணத்தை உள்பக்கத்தில் ஒன்றுக்கொன்று வெட்டாத மூலைவிட்டங்களால் முக்கோணங்களால் பிரிக்கப்பட Tn+1வழிகளிருந்தால்
 
:***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) உண்டாக்கப்படுகிறது:

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

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

:x_1x_2 ... x_n

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

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

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

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

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

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

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

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

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

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

:a_n = T_{n+1} =  C_n

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

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

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

: (x_1x_2 ... x_i)(x_{i+1} ... x_n)

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

: ((x_1 .... )(.... x_i)) ((x_{i+1} ... )(.... x_n))

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

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

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

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

:\binom{2n-2}{n-1}.

இவைகளில் *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)* க்குப்போகும் எல்லாப் பாதைகளின் மொத்த எண்ணிக்கையே. இந்த எண்

:= \binom{2n-2}{n},

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

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

= \binom{2n-2}{n-1}  -  \binom{2n-2}{n} 

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

## வட்டத்தில் குறுக்குவெட்டில்லாத நாண்கள்
right|thumb|400px

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

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

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

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

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

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

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

: (a_1, a_2, … a_{2n-2})

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

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

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

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

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

: **.).).)**

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

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

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

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

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

## மலைப்படிமங்கள்
right|thumb|400px

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

மேல்நோக்கிக்கோடுகளுக்கு '+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

பகுப்பு:சேர்வியல்
பகுப்பு:இயற்கணிதம்
பகுப்பு:முழுஎண் தொடர்வரிசைகள்