உள்ளடக்கத்துக்குச் செல்

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

கட்டற்ற கலைக்களஞ்சியமான விக்கிப்பீடியாவில் இருந்து.
P * (1,2,3,4)T = (4,1,3,2)T

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

கணிதத்தில் 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] என்பதால் வரிசைமாற்றத்தினை எழுதும் சரியானமுறை:

π = (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(kj) தருகிறது.[2][3]

  • அனைத்து k > 0 மதிப்புகளுக்கும் s(kk) = 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(kj) = 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(kj) = 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(kj) தருகிறது.

  • ஒவ்வொரு j < 0 அல்லது j > k மதிப்புகளுக்கு:
f(kj) = 0.
  • f(0, 0) = 1.
  • ஒவ்வொரு k > 1 ; kj ≥ 0 மதிப்புகளுக்கு:
f(kj) = 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