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

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

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

ஆகையால் C₂ =1; C₃ = 2; C₄ =5; C₅ = 14, C₆ = 42 .....

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

முக்கிய குறிப்பு: C₁ = 1; C₂ =1; C₃ = 2; C₄ =5; C₅ = 14, C₆ = 42 ..... என்ற இந்தக்கட்டுரைத் தொடர்பை

C₀ = 1; C₁ =1; C₂ = 2; C₃ =5; C₄ = 14, C₅ = 42 ..... என்றும் குறியிடும் வழக்கம் பரவலாக இருக்கிறது. அந்த வழக்கப்படி, (இக்கட்டுரையிலல்ல)

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

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

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

T_n+1 = C_n

ஆக, T₃ = 1; T₄ = 2; T₅ = 5; T₆ = 14; T₇ = 42 …….

T₂ =1 என்று நாம் விதி செய்துகொள்ளலாம்.

T_n+1 இன் மதிப்பை C_n என்று காண்பதற்கு இதற்கென்று கீழேயுள்ள ஒரு மீள்வரு தொடர்பு (Recurrence relation) உண்டாக்கப்படுகிறது:

(*)$T_{n+1}=T_{2}T_{n}+T_{3}T_{n-1}+...+T_{n}T_{2}$.

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

$x_{1}x_{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_{1}x_{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_{1}x_{2}...x_{n}$ என்ற பெருக்கலுக்கு அடைப்புகள் போடும் செயலையும் கழி உடைப்புச்செயலையும் ஒத்துப்பார். கடைசிப்பெருக்கல் ஏதோ இரண்டைப்பெருக்குகிறது. அந்த இரண்டில் ஒவ்வொன்றும் அடைப்புகளுக்குள் இருக்கின்றன.

$(x_{1}x_{2}...x_{i})(x_{i+1}...x_{n})$

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

$((x_{1}....)(....x_{i}))((x_{i+1}...)(....x_{n}))$

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

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

$(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}$

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

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_{1}x_{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)))

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

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

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

துணைநூல்கள்

• Catalan, Eugene. (1844): Note extraite d’une lettre adress´ee. J. Reine Angew. Math., 27:192.
• Stanley, R.P. (1999): Enumerative Combinatorics, Vol. 2. Cambridge University Press. (pp. 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