சுழல்களும் நிலைத்த புள்ளிகளும்

P * (1,2,3,4)^T = (4,1,3,2)^T

நான்கு உறுப்புகளின் வரிசைமாற்றம்: 1 நிலைத்த புள்ளி; 1 3-சுழல்

கணிதத்தில் S என்ற முடிவுறு கணத்தின் மீதான வரிசைமாற்றம் π எனில் அவ்வரிசைமாற்றத்தின் சுழல்கள் (cycles) என்பவை, S இன் மீது செயற்படும் வரிசைமாற்றம் π இன் செயற்பாட்டால் உருவாகும் உட்குலங்களின் சுற்றுப்பாதைகளுக்கு (orbit) இருவழியொத்தவையாக அமைவன ஆகும். இந்த சுற்றுப்பாதைகள் S இன் உட்கணங்களாக அமையும்.

{ c₁, ..., c_l } ஒரு சுற்றுப்பாதை எனில்:

π(c_i) = c_{i + 1}, i = 1, ..., l − 1, மற்றும் π(c_l) = c₁.

இந்த சுற்றுப்பாதைக்குரிய π இன் சுழல் ( c₁ c₂ ... c_n ) என எழுதப்படுகிறது. c₁ ஆக சுற்றுப்பாதையின் எந்தவொரு உறுப்பும் எடுத்துக்கொள்ளப்படலாம் என்பதால், இம்முறையில் எழுதுவது தனித்தவொரு முறையாகா இருக்காது.

ஒரு சுற்றுப்பாதையின் அளவு l எனில் அதுவே, அச்சுற்றுப்பாதையின் சுழலின் நீளம் ஆகும். l = 1 எனில் சுற்றுப்பாதையில் ஒரேயொரு உறுப்பு மட்டுமேயிருக்கும்; அந்த உறுப்பு வரிசைமாற்றத்தின் நிலைத்த புள்ளி எனப்படும்.

ஏதாவது ஒரு வரிசைப்படி ஒரு வரிசைமாற்றத்தின் சுழல்களை அடுத்தடுத்து எழுதுவதன் மூலம் அவ்வரிசைமாற்றம் குறிக்கப்படுகிறது.

எடுத்துக்காட்டு:

$\pi ={\begin{pmatrix}1&6&7&2&5&4&8&3\\2&8&7&4&5&3&6&1\end{pmatrix}}={\begin{pmatrix}1&2&4&3&5&6&7&8\\2&4&3&1&5&8&7&6\end{pmatrix}}$

இதில் 1 ----> 2, 2---->4, 4---->3, 3---->1; 6 ----> 8, 5---->5, 7--->7. எனவே இவ்வரிசைமாற்றத்தைப் பின்வரும் விதங்களில் எழுதலாம்.

π = ( 1 2 4 3 ) ( 5 ) ( 6 8 ) (7) = (7) ( 1 2 4 3 ) ( 6 8 ) ( 5 ) = ( 4 3 1 2 ) ( 8 6 ) ( 5 ) (7) = ...

இதில் π(5)=5, π(7)=7 என்பதால் 5, 7 இரண்டும் π இன் நிலைத்த புள்ளிகள். ஒரு வரிசைமாற்றத்தின் நிலைத்தபுள்ளிகளை அதாவது 1 நீளமுள்ள சுழலைக் குறிக்கவேண்டியது அவசியமில்லை என்பதால் வரிசைமாற்றத்தினை எழுதும் சரியானமுறை:

π = (1 2 4 3)(6 8)

விளக்கம்

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

இதன்

சுழல்முறைக்குறியீடு: (1 4 5)(2 9)(3 6)(7)(8) = (1 4 5)(2 9)(3 6)

சுழலமைப்பு: 32211 அல்லது $32^{2}1^{2}$

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

சுழல்களின் எண்ணிக்கையைக் கொண்டு வரிசைமாற்றங்களின் எண்ணிக்கைக் காணல்

சரியாக j சேரா சுழல்களைக்கொண்ட k உறுப்புகளின் வரிசைமாற்றங்களின் என்ணிக்கையை குறியிடப்படாத முதல்வகை ஸ்டெர்லிங் எண் s(k, j) தருகிறது.

• அனைத்து k > 0 மதிப்புகளுக்கும் s(k, k) = 1

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

• அனைத்து k > 0 மதிப்புகளுக்கும் s(k, 1) = (k − 1)!.

k உறுப்புகளின் வரிசைமாற்றத்தில் சுழல்களின் எண்ணிக்கை 1 எனில் அச்சுழல்களின் நீளம் k ஆக இருக்கும். அதாவது அச்சுழல்கள் ஒவ்வொன்றும் k உறுப்புகளைக் கொண்டிருக்கும். 1 முதல் k வரையிலான உறுப்புகளை k! வழிகளில் வரிசைமாற்றலாம். அதேசமயம் k நீளமுள்ள ஒரு சுழலை வெவ்வேறுவிதமாக k வழிகளில் எழுதலாம். எடுத்துக்காட்டாக, 4 நீளமுள்ள சுழல் ( 1 2 4 3 ) = ( 2 4 3 1 ) = ( 4 3 1 2 ) = ( 3 1 2 4 ) என நான்கு விதங்களில் எழுதப்படுவதைக் காணலாம். எனவே

s(k, 1) = k!/k = (k − 1)!.

• அனைத்து k > j > 1 மதிப்புகளுக்கும், s(k, j) = s(k − 1,j − 1) + s(k − 1, j)·(k − 1)

j சுழல்கள் கொண்டதாக k உறுப்புகளை இருவேறு வழிகளில் வரிசைமாற்றலாம்:

உறுப்பு k ஐ ஒரு நிலைத்த புள்ளியாக எடுத்துக்கொண்டால் j − 1 சுழல்கள் கொண்ட k − 1 உறுப்புகளின் s(k − 1, j − 1) வரிசைமாற்றங்களில் ஒன்றைத் தேர்ந்தெடுத்து k உறுப்பை 1 நீளமுடைய சுழலாக அதனுடன் சேர்த்துக்கொள்ளலாம். (s(k − 1,j − 1) )

உறுப்பு k ஐ ஒரு நிலைத்த புள்ளியாக எடுத்துக்கொள்ளாவிட்டால் j சுழல்கள் கொண்ட k − 1 உறுப்புகளின் s(k − 1, j ) வரிசைமாற்றங்களில் ஒன்றைத் தேர்ந்தெடுத்து k உறுப்பை ஒவ்வொரு சுழலிலுமுள்ள k − 1 உறுப்புகளில் ஏதேனும் ஒன்றின்முன் சேர்த்துக்கொள்ளலாம் ( s(k − 1, j)·(k − 1).

எனவே,

s(k, j) = s(k − 1,j − 1) + s(k − 1, j)·(k − 1)

சில மதிப்புகள்

k	j
	1	2	3	4	5	6	7	8	9	sum
1	1									1
2	1	1								2
3	2	3	1							6
4	6	11	6	1						24
5	24	50	35	10	1					120
6	120	274	225	85	15	1				720
7	720	1,764	1,624	735	175	21	1			5,040
8	5,040	13,068	13,132	6,769	1,960	322	28	1		40,320
9	40,320	109,584	118,124	67,284	22,449	4,536	546	36	1	362,880
	1	2	3	4	5	6	7	8	9	sum

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

j நிலைப்புள்ளிகள் கொண்ட k உறுப்புகளை வரிசைமாற்றும் வழிகளின் எண்ணிக்கையை f(k, j) தருகிறது.

• ஒவ்வொரு j < 0 அல்லது j > k மதிப்புகளுக்கு:

f(k, j) = 0.

• f(0, 0) = 1.
• ஒவ்வொரு k > 1 ; k ≥ j ≥ 0 மதிப்புகளுக்கு:

f(k, j) = f(k − 1, j − 1) + f(k − 1, j)·(k − 1  − j) + f(k − 1, j + 1)·(j + 1)

சில மதிப்புகள்

k	j
	0	1	2	3	4	5	6	7	8	9	sum
1	0	1									1
2	1	0	1								2
3	2	3	0	1							6
4	9	8	6	0	1						24
5	44	45	20	10	0	1					120
6	265	264	135	40	15	0	1				720
7	1,854	1,855	924	315	70	21	0	1			5,040
8	14,833	14,832	7,420	2,464	630	112	28	0	1		40,320
9	133,496	133,497	66,744	22,260	5,544	1,134	168	36	0	1	362,880
	0	1	2	3	4	5	6	7	8	9	sum

மேற்கோள்கள்

• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, பன்னாட்டுத் தரப்புத்தக எண் 978-0-13-602040-0
• Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, பன்னாட்டுத் தரப்புத்தக எண் 0-521-45761-0
• Gerstein, Larry J. (1987), Discrete Mathematics and Algebraic Structures, W.H. Freeman and Co., பன்னாட்டுத் தரப்புத்தக எண் 0-7167-1804-9