வரிசைமாற்றம்

கட்டற்ற கலைக்களஞ்சியமான விக்கிப்பீடியாவில் இருந்து.
தாவிச் செல்லவும்: வழிசெலுத்தல், தேடல்

கணிதத்தில் வரிசைமாற்றம் (Permutation), சேர்மானம் (Combination) என்ற இரண்டு அடிப்படைக் கருத்துக்கள் பல நூற்றாண்டுகளாகப் புழக்கத்தில் இருந்து வருகின்றன. ஒரு கணத்தின் உறுப்புக்களை ஒரு வரிசையில் அடுக்கி வைத்துப் பின் அவ்வரிசையில் உள்ள உறுப்புகளை மாற்றி அடுக்கி அமைத்தால் இம்மாறுதல் ஒரு வரிசைமாற்றம் அல்லது வரிசை மாற்றல் எனப்படும். மாற்றிக்கிடைத்த வரிசை அமைக்கும் வரிசைமாற்றம் என்றே பெயர். வரிசை அல்லது அடுக்கு என்ற கருத்தையே கொண்டு வராமல் கணத்திலிருந்து ஒரு குறிப்பிட்ட எண்ணிக்கையில் உறுப்புக்களைத் தேர்ந்தெடுத்தால் இச்செயல் ஒரு சேர்வு எனப்படும். இச்செயலினால் கிடைக்கும் உட்கணத்திற்கும் சேர்வு என்றே பெயர். வரிசை மாற்றத்தில் எவ்வுறுப்புக்குப் பக்கத்தில் எவ்வுறுப்பு உள்ளது என்பது வரிசையின் அமைப்புக்கு முக்கியம். ஆனால் சேர்வுக்கு இந்த அடுக்கம் முக்கியம் இல்லை எவை எவை பொறுக்கப்படுகின்றன (தேர்வு பெறுகின்றதன) என்பது மட்டும்தான் முக்கியம். A,B,C என்று மூன்று உறுப்புகள் இருந்தால், வரிசை மாற்றத்தில் ABC, ACB, CBA ஆகிய மூன்றும் வெவ்வேறு வரிசைமாற்றங்கள், ஆனால் சேர்வில் அவை ஒன்றே (அதே மூன்று உறுப்புகள்தான் பொறுக்கப்பட்டுள்ளன).

இவ்விரண்டு கருத்துக்களான விதைகளிலிருந்து சிறுசிறு செடிகளாகப் பல வேறுபட்ட இடங்களில் வேரூன்றி முளைத்து 19ம் நூற்றாண்டில் பெரிய ஆலமரமாகப் பரவி அதன் விழுதுகள் புள்ளியியல், இயற்பியல், வேதியியல், இயலறிவியல்கள் இன்னும் பற்பல அறிவியல் பிரிவுகளிலும் இன்றியமையாத கணிதக் கரணமாகப் பயன்படத் தொடங்கின. இருபதாவது நூற்றாண்டில் அவ்விழுதுகளும் எல்லா பயன்பாடுகளும் ஒன்றுசேர்க்கப் பட்டு இன்று கணிதத்தில் சேர்வியல் (Combinatorics) என்ற ஒரு மிகப்பெரிய அடிப்படைப் பிரிவாகத் திகழ்கிறது. இக்கட்டுரையில் வரிசைமாற்றம் என்ற அடிக் கருத்தைப் பார்ப்போம்.

எடுத்துக்காட்டு வழியாக ஒரு முன்னுரை[தொகு]

டி.என்.ஏ (DNA) தொடரில் A, C, T, G என்ற நான்கு குறிகள் உள்ளன. இவைகளிலிருந்து TGA போன்ற மூன்றுகுறித் தொடர்கள் மட்டும் வரக்கூடியன யாவை? அவை எத்தனை? இவ்விரண்டு கேள்விகளுக்கும் விடை சொல்லவும் இதைப்போன்ற பற்பல எண்ணிக்கைப் பற்றிய கேள்விகளையும் அலசி விடைகாணுவதே வரிசைமாற்றக் கோட்பாட்டின் நோக்கம்.

எடுத்துக்காட்டாக, முக்குறித் (மூன்றுகுறித்) தொடர்கள் தேவைப்படுவதால், முதலில் மூன்று இடங்களும் காலியாக (வெற்றாக) இருப்பதாகக் கொள்வோம். அந்த மூற்று வெற்று இடங்களை, நம்மிடம் உள்ள நான்கு குறிகளில் ஏதாவது மூன்றால் நிரப்பவேண்டும் என்றும் கொள்வோம். இப்பொழுது முதல் வெற்று இடத்தை எடுத்துக்கொண்டால், அதனை நான் குறிகளில் ஏதாவது ஒன்றால் நிரப்பலாமாதலால், அவ்வெற்று இடத்தை நிரப்ப நான்கு வெவ்வேறு வழிகளுள்ளன. அவ்விதம் ஏதாவது ஒன்றால் நிரப்பிய பிறகு, இரண்டாவது இடத்தை (ஒரே குறி மீண்டும் வரலாகாது என்பதால்) இதர மூன்று குறிகளில் ஏதேனும் ஒன்றால் நிரப்பலாமாதலால், இரண்டாவது இடத்தை நிரப்ப மொத்தம் மூன்று வழிகளுள்ளன. ஆனால் முதல் இடத்தை நிரப்பும் ஒவ்வொரு வழிக்கும் இரண்டாவது இடத்தை நிரப்ப மூன்று வழிகள் உள்ளன. ஆகவே முதல் இரண்டு இடத்தை நிரப்ப 4 \times 3 = 12 வழிகள் உள்ளன. இப்பொழுது அடுத்ததாக மூன்றாவது இடத்தை நிரப்ப, இரண்டே இரண்டு குறிகள் மட்டுமே மிஞ்சியிருப்பதால், இரண்டே வழிகள் தானுள்ளன. ஆக, முதல் மூன்று இடங்களையும் நிரப்ப 12 \times 2 = 24 வழிகளுள்ளன. இந்த 24ம் கீழே பட்டியலிடப்பட்டுள்ளன:

ATC TCG CGA GAT
ACT TGC CAG GTA
ATG TCA CGT GAC
AGT TAC CTG GCA
ACG TGA CAT GTC
AGC TAG CTA GCT

வரிசைமாற்றங்களின் எண்ணிக்கை[தொகு]

முன்னுரையில் உள்ள ஏரண (தர்க்க) வழியிலேயே சென்று நாம் கீழேயுள்ள அடிப்படைத் தேற்றத்தை நிறுவிவிடலாம்:

n பொருள்களிலிருந்து எடுக்கப்பட்ட r-பொருள் வரிசைமாற்றங்களின் எண்ணிக்கை

n(n - 1)(n - 2) ....(n -[r - 1]),\,
= n (n-1) (n-2) ... (n-r+1) \, = \frac{n!}{(n-r)!} \,.

இதற்குக்குறியீடு: P(n, r) \, அல்லது (n)_r \, அல்லது  P_r^n  \,

இதனால் P(n,1) =  (n)_1  = n. \,

P(n,n) = (n)_n = n! \, = " n \,- பொருள்களைக் கொண்டு" பெறவல்ல எல்லா வரிசைமாற்றங்களின் எண்ணிக்கை.

பல்லுறுப்புக் கெழு[தொகு]

Path(0,0) to (3,4).png

ஒரே மாதிரியான \alpha_1 \, பொருள்களும், ஒரேமாதிரியான \alpha_2 \, பொருள்களும், .... , ஒரேமாதிரியான \alpha_n \, பொருள்களும் ஒரு கணம் கொண்டிருந்தால், அக்கணத்தின் எல்லாப் பொருள்களின் வரிசைமாற்றமங்களின் எண்ணிக்கையைக் கீழே உள்ள சமன்பாடு குறிப்பிடுகின்றது.

\frac{(\alpha_1+\alpha_2+...+\alpha_n)!}{\alpha_1!\alpha_2! ... \alpha_n!} \,.

இதற்குப் பல்லுறுப்புக் கெழு (multinomial coefficient) என்று பெயர். மொத்த உறுப்புகள் (\alpha_1+\alpha_2+...+\alpha_n) \, என்பது தெளிவு. ஆனால் ஏன் (\alpha_1!\alpha_2! ... \alpha_n!) \, என்பதால் வகுக்கிறோம் என்றால், ஒரே மாதிரியான \alpha_1 \, பொருட்கள் உள்ளதால், அவை தமக்குள் \alpha_1! \, வரிசை மாற்றங்களாக அமையலாம், ஆகவே அவற்றால் மொத்த வரிசைமாற்றங்களில் இருந்து வகுக்க வேண்டும். அதே போலவே \alpha_2! \,, \alpha_3! \,... \alpha_n! \,முதலானவையும்.

எ.கா.: இரு திரட்சி அல்லது இருபரிமாணத் தளத்தில் (a,b) என்ற புள்ளியில் a, b இரண்டும் முழு எண்களானால், அது முழுஎண்சன்னல் புள்ளி எனப்பெயர் பெறும். தொடக்கப்புள்ளி (0,0) இல் இருந்து (3,4) என்ற சன்னல் புள்ளிக்கு முழுஎண் சன்னல்புள்ளிகள் வழியாகப்போகும் குறைந்த தொலைவுடைய வழிகள் எத்தனை என்று கேட்பதாக வைத்துக்கொள்வோம். பல்லுறுப்புக் கெழு கருத்தைக்கொண்டு இதற்கு விடை சொல்லலாம். ஒவ்வொரு வழியும் மூன்று முறை x-ஆயத்திற்கு இணையாகவும், நான்கு முறை y-ஆயத்திற்கு இணையாகவும் போகவேண்டியுள்ளது. xyyxyxy என்ற ஒரு வழி படிமத்தில் காட்டப்பட்டுள்ளது. இப்படி எத்தனை வழிகளுள்ளன? மூன்று xம் நான்கு yம் கொண்ட வரிசைமாற்றங்களின் எண்ணிக்கை

\frac{7!}{(3!)(4!)} \, = 35.

கணக்கோட்பாட்டில் முடிவுறுகணத்தின் வரிசைமாற்றம்[தொகு]

கணக்கோட்பாட்டில், ஒரு முடிவுறு கணம் S இன் வரிசைமாற்றம் என்பது S இன் மேல் வரையறுக்கப்பட்ட இருவழிக்கோப்பு.

S = \{1, 2, 3, 4, 5, 6\} \, என்று கொள்வோம்.  \sigma :  S \mapsto S \, ஒரு இருவழிக்கோப்பு என்றும், \sigma(1) = 5,  \sigma(2) = 3,  \sigma(3) = 2, \sigma(4) = 4, \sigma(5) = 6, \sigma(6) = 1 \, என்றும் கொள்வோம். இதையே வேறுவிதமாகவும் எழுதுவது உண்டு:

\sigma \, = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6\\5 & 3 & 2 & 4 & 6 & 1\end{pmatrix} \,.

மேல் வரியில் இயல்பு வரிசையும், கீழ்வரியில் மாற்றப்பட்ட வரிசையும் காட்டுகிறது.

சுழல்முறையில் வரிசைமாற்றங்கள்[தொகு]

இதை இன்னும் சுருக்கி சுழல் முறையில் எழுதலாம்: \sigma = (156)(23)(4)

அதாவது \sigma என்ற வரிசைமாற்றத்தின் செயல்பாட்டினால் உறுப்பு 1 உறுப்பு 5க்கும், உறுப்பு 5 உறுப்பு 6 க்கும் உறுப்பு 6 உறுப்பு 1 க்கும் போவதைத்தான் (156) என்ற சுழல் காட்டுகிறது. இதேமாதிரி 2, 3க்கும், 3, 2க்கும் எடுத்துச்செல்லப்படுவதை (23) என்ற சுழல் காட்டிக் கொடுக்கிறது. 4, 4க்கே போவதால் அது ஒரு ஓருறுப்புச் சுழலாக இருக்கிறது. ஆக இம்மூன்று சுழல்களின் கூட்டுப்பயன் தான் \sigma என்ற வரிசைமாற்றத்தின் மறுக்குறியீடு.

இவ்விதம் எந்த வரிசைமாற்றத்தையும் சுழல்முறையில் குறிகாட்ட (represent) முடியும்.மேலேயுள்ள \sigma வை (156)(23)(4)என்ற சுழல் முறையில் குறிகாட்டும்போது, (321) என்ற சுழலமைப்பில் சுழல்கள் உள்ளன. இதே சுழலமைப்புக் கொண்ட பல வரிசைமாற்றங்கள் இருக்கக்கூடும்.

எ.கா.: (165)(24)(3); (243)(14)(5) மற்றும் பல.

வேறு சுழலமைப்பிலும் வரிசைமாற்றங்கள் இருக்கக்கூடும்.

எ.கா.: (23)(15)(46): சுழலமைப்பு(222).

(142)(3)(5)(6): சுழலமைப்பு (3111). இன்னும் பல.

6 பொருள்களைக்கொண்டு அமையப்படும் வரிசைமாற்றங்களில் எத்தனை வரிசைமாற்றங்கள் ஒரு குறிப்பிட்ட சுழலமைப்பு கொண்டதாக இருக்கமுடியும்? உதாரணமாக, மூன்று சுழல்கள் கொண்ட எத்தனை வரிசைமாற்றங்கள் உண்டு? விடை:225. முதல் வகை ஸ்டர்லிங் எண்கள் இவ்வெண்ணிக்கைகளைத் தருகின்றன.

சுழல்களைப்பற்றிய வரையறைகள்[தொகு]

S = {a_1, a_2, ..., a_n} என்று கொள்வோம். இதனுடைய வரிசைமாற்றம் ஒவ்வொன்றும் \sigma: S \mapsto S என்ற இருவழிக்கோப்பு. இதை சுழல்முறையில் குறிகாட்ட, ஏதாவது ஒரு உறுப்பிலிருந்து தொடங்கு. a_1 இலிருந்து தொடங்குவோம். அது \sigma(a_1) க்குப்போகிறது.இது \sigma(\sigma(a_1)) = \sigma^2(a_1) க்குப்போகிறது.ஆக,

a_1 \rightarrow \sigma(a_1) \rightarrow \sigma^2(a_1) \rightarrow ....\rightarrow \sigma^{k_1}(a_1)= a_1.

இங்கு இந்தச்சுழலின் நீளம் k_1.

\sigma(a_1), \sigma^2(a_1), ..., \sigma^{k_1}(a_1) இவைகள் n உறுப்புகளையும் கொண்டுவிட்டால், இத்திரிபில் மொத்தமே ஒரு சுழல்தான். இல்லாவிட்டால், இவைகளில் இல்லாத ஒரு உறுப்பிலிருந்து தொடங்கி மேற்படி செயல்பாட்டைத் திரும்பச்செய். எல்லாஉறுப்புகளும் சுழல்களுக்குள் வரும் வரையில் இதையே தொடர்ந்து செய்தால், கடைசியில் கீழுள்ளபடி ஒரு சுழற்பிரிவு கிடைக்கும்:

நீளம் 1 உள்ள j_1 சுழல்கள்,
நீளம் 2 உள்ள j_2 சுழல்கள்,
... ...
நீளம் k உள்ள j_k சுழல்கள்.

ஆக, \sigma வின் சுழலமைப்பை இப்படிச்சொல்வது வழக்கம்: 1^{j_1}2^{j_2}...k^{j_k}.

கட்டாயம் 1j_1 + 2j_2 + ... +kj_k  =  n.

இந்த சுழலமைப்பையுள்ள வரிசைமாற்றங்களின் எண்ணிக்கை (தேற்றத்தின்படி) \frac{n!}{1^{j_1}2^{j_2}...k^{j_k}{j_1}!{j_2}!...{j_k}!}

எ.கா.: \sigma = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\4 & 9 & 6 & 5 & 1 & 3 & 7 & 8 & 2\end{pmatrix}.

இதன் சுழல்முறைக்குறிகாட்டி: (145)(29)(36)(7)(8)

சுழலமைப்பு: 32211 அல்லது 32^21^2

இந்த சுழலமைப்பிலுள்ள எல்லா வரிசைமாற்றங்களின் எண்ணிக்கை = \frac{9!}{1^2.2^2.3.1!.2!.2!} = 7,560.

வரிசைமாற்றங்களின் சேர்வை[தொகு]

n உறுப்புகள் உள்ள ஒரு கணத்தின் எல்லா வரிசைமாற்றங்களையும் ஒன்றுக்கொன்று சேர்க்கக்ககூடிய சேர்வை விதி ஒன்றிருக்கிறது.அதாவது, {1,2,3,4,5} என்ற 5-கணத்தை எடுத்துக் கொள்ளுவோம்.

\sigma = \begin{pmatrix}1 & 2 & 3 & 4 & 5\\
5 & 4 & 3 & 1 & 2
\end{pmatrix}
\tau = \begin{pmatrix}1 & 2 & 3 & 4 & 5\\
2 & 4 & 5 & 1 & 3
\end{pmatrix}

என்றால்,

\sigma \circ \tau  = \begin{pmatrix}1 & 2 & 3 & 4 & 5\\
4 & 1 & 2 & 5 & 3
\end{pmatrix}

அதாவது, முதலில் \tau; பிறகு \sigma. வேறுவிதமாகச் சொன்னால், சேர்வை வலமிருந்து இடம் போகிறது. \sigma \circ \tau வை \sigma\tau என்றே எழுதவும் செய்யலாம்.

சமச்சீர் குலம்[தொகு]

n பொருள்களின் வரிசைமாற்றங்கள் எல்லாம் அடங்கிய கணம் S_n என்று குறிக்கப்படும். இதனில் n! வரிசைமாற்றங்கள் உள்ளன. இது மேலே வரையறுக்கப்பட்ட சேர்வைக்கு குலம் ஆகிறது. இது n பொருள்களின் சமச்சீர் குலம் (Symmetric Group on n objects) எனப்படும். இது n! உறுப்புகள் கொண்ட ஒரு முடிவுறு குலம். ஒரு பொருள்களையும் இடம் மாற்றாத முற்றொருமை வரிசைமாற்றம் தான் இந்த குலத்தின் முற்றொருமை உறுப்பு ; அதாவது,

e = \begin{pmatrix}1 & 2 & 3 &\dots & n\\
1 & 2 & 3 &\dots & n 
\end{pmatrix}.

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

எ.கா. ::\sigma = \begin{pmatrix}1 & 2 & 3 & 4 & 5\\
5 & 4 & 3 & 1 & 2
\end{pmatrix} என்றால் அதன் நேர்மாறு

= \sigma^{-1} = \begin{pmatrix}1 & 2 & 3 & 4 & 5\\
4 & 5 & 3 & 2 & 1
\end{pmatrix}

இவற்றையும் பார்க்கவும்[தொகு]

துணைநூல்கள்[தொகு]

D.T. Finkbeiner, et al. A Primer of Discrete Mathematics. W.H. Freeman & Co. 1987. SanFrancisco.

V. Krishnamurthy. Combinatorics: Theory and Applications. 1986. Ellis Horwood

"http://ta.wikipedia.org/w/index.php?title=வரிசைமாற்றம்&oldid=1554498" இருந்து மீள்விக்கப்பட்டது