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

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

{ c1, ..., cl } ஒரு சுற்றுப்பாதை எனில்:

π(ci) = ci + 1, i = 1, ..., l − 1, மற்றும் π(cl) = c1.

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

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

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

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

இதில் 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} என்று கொள்வோம். இதனுடைய வரிசைமாற்றம் ஒவ்வொன்றும்  என்ற இருவழிக்கோப்பு. இதை சுழல்முறையில் குறிகாட்ட, ஏதாவது ஒரு உறுப்பிலிருந்து தொடங்கலாம். a_1 இலிருந்து தொடங்கினால் அது  க்குப்போகிறது. இது  =  க்குப்போகிறது. ஆக,

.

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

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

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

எனவே இந்த வரிசைமாற்றத்தின் சுழலமைப்புக் குறியீடு:
 = 
 ஆக இருக்கும்.

இந்த சுழலமைப்பிலுள்ள வரிசைமாற்றங்களின் எண்ணிக்கை (தேற்றத்தின்படி): 

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

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

இந்த சுழலமைப்பிலுள்ள எல்லா வரிசைமாற்றங்களின் எண்ணிக்கை =  = 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

குறிப்புகள்

மேற்கோள்கள்




பகுப்பு:வரிசைமாற்றங்கள்