விக்கிப்பீடியா

கேடலான் எண்கள்: திருத்தங்களுக்கு இடையிலான வேறுபாடு

Browse history interactively
← முந்தைய வேறுபாடுஅடுத்த வேறுபாடு →
உள்ளடக்கம் நீக்கப்பட்டது உள்ளடக்கம் சேர்க்கப்பட்டது
VisualWikitext
சி தானியங்கிஇணைப்பு: uk:Число Каталана
சி தானியங்கிமாற்றல்: fr:Nombres de Catalan; cosmetic changes
வரிசை 1:
'''கேடலான் எண்கள்''' (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> ஆகும்.
 
== மூலைவிட்ட முக்கோணப்பிரிவினை ==
[[படிமம்: Catalan 1.png|right|thumb|400px]]
 
(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 என்று நாம் விதி செய்துகொள்ளலாம்.
வரிசை 26:
''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>
வரிசை 40:
: '''''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> என்ற கேடலான் எண்தான்.
 
== சன்னல் புள்ளிகள் வழியாக நேர்மைப் பாதைகள் ==
[[படிமம்: Catalan 2.png|right|thumb|600px]]
 
<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>
வரிசை 101:
= <math>\frac{1}{n} \binom{2n-2}{n-1} = C_n </math>
 
== வட்டத்தில் குறுக்குவெட்டில்லாத நாண்கள் ==
[[படிமம்: Catalan 3.png|right|thumb|400px]]
 
''2n'' நபர்கள் வட்டமாக உட்கார்ந்திருக்கும்போது, எல்லோரும் ஒரே நேரத்தில் கைநீட்டி மற்ற யாராவதொருவருடன் கைகுலுக்க, யாருடைய கையும் மற்ற எவருடைய கையையும் குறுக்கே தாண்டாத முறையில் கைகுலுக்க உள்ள வழிகள் <math>C_{n+1}. </math>
 
இதே பிரச்சினையை வேறுவிதமாகவும் உருமாற்றலாம். ஒரு வட்டத்தின் மேல் ''2n'' புள்ளிகள் கொடுக்கப்பட்டிருக்கின்றன. இவைகளை ஒன்றுக்கொன்று வெட்டாத வகையில் ஜோடி ஜோடியாக நாண்களால் இணைக்கவேண்டும். இதற்குள்ள வழிகளும் மேலே கைகுலுக்கல் பிரச்சினைக்குள்ள வழிகளும் ஒன்றுதான்.
வரிசை 112:
:'''''bebbbeebeebbbeee'''''.
 
இந்த சொல்லில், ''''''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) இவை மாத்திரம் கொண்ட
வரிசை 123:
: (<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'ம் எழுதுவோம். நமக்குக்கிடைப்பது:
வரிசை 139:
: '''+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)))
 
== மலைப்படிமங்கள் ==
[[படிமம்: Catalan 4.png|right|thumb|400px]]
 
''(n-1)'' மேல்நோக்கிக் கோடுகளும் ''(n-1)'' கீழ்நோக்கிக் கோடுகளும் கொண்டதும், அடிவாரத்திற்குக் கீழே போகாததுமான மலைப் படிமங்களின் எண்ணிக்கை <math>C_n</math>.
 
மேல்நோக்கிக்கோடுகளுக்கு '+1'ம் கீழ்நோக்கிக்கோடுகளுக்கு '-1' ம் எழுதினால் இவைகளுக்கும் மேலே கூறிய ஈருருப்புத்தொடர்புகளுக்கும் ஒரு இருவழிக்கோப்பு உண்டாகிறது.
 
== துணைநூல்கள் ==
 
*Catalan, Eugene. (1844): {{lang|fr|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&ndash;229219–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
 
[[பகுப்பு: சேர்வியல்]]
 
[[பகுப்பு: இயற்கணிதம்]]
வரிசை 172:
[[fa:دنباله کاتالان]]
[[fi:Catalanin luku]]
[[fr:NombreNombres de Catalan]]
[[he:מספר קטלן]]
[[it:Numero di Catalan]]
"https://ta.wikipedia.org/wiki/கேடலான்_எண்கள்" இலிருந்து மீள்விக்கப்பட்டது